欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java中實現(xiàn)雙數(shù)組Trie樹實例

 更新時間:2015年01月15日 11:32:31   投稿:junjie  
這篇文章主要介紹了Java中實現(xiàn)雙數(shù)組Trie樹實例,雙數(shù)組Trie就是一種優(yōu)化了空間的Trie樹,本文給出了實現(xiàn)代碼、測試代碼和測試結(jié)果,需要的朋友可以參考下

傳統(tǒng)的Trie實現(xiàn)簡單,但是占用的空間實在是難以接受,特別是當字符集不僅限于英文26個字符的時候,爆炸起來的空間根本無法接受。

雙數(shù)組Trie就是優(yōu)化了空間的Trie樹,原理本文就不講了,請參考An Efficient Implementation of Trie Structures,本程序的編寫也是參考這篇論文的。

關(guān)于幾點論文沒有提及的細節(jié)和與論文不一一致的實現(xiàn):

1.對于插入字符串,如果有一個字符串是另一個字符串的子串的話,我是將結(jié)束符也作為一條邊,產(chǎn)生一個新的結(jié)點,這個結(jié)點新節(jié)點的Base我置為0

所以一個字符串結(jié)束也有2中情況:一個是Base值為負,存儲剩余字符(可能只有一個結(jié)束符)到Tail數(shù)組;另一個是Base為0。

所以在查詢的時候要考慮一下這兩種情況

2.對于第一種沖突(論文中的Case 3),可能要將Tail中的字符串取出一部分,作為邊放到索引中。論文是使用將尾串左移的方式,我的方式直接修改Base值,而不是移動尾串。


下面是java實現(xiàn)的代碼,可以處理相同字符串插入,子串的插入等情況

復制代碼 代碼如下:

/*
 * Name:   Double Array Trie
 * Author: Yaguang Ding
 * Mail: dingyaguang117@gmail.com
 * Blog: blog.csdn.net/dingyaguang117
 * Date:   2012/5/21
 * Note: a word ends may be either of these two case:
 * 1. Base[cur_p] == pos  ( pos<0 and Tail[-pos] == 'END_CHAR' )
 * 2. Check[Base[cur_p] + Code('END_CHAR')] ==  cur_p
 */


import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Arrays;


public class DoubleArrayTrie {
 final char END_CHAR = '\0';
 final int DEFAULT_LEN = 1024;
 int Base[]  = new int [DEFAULT_LEN];
 int Check[] = new int [DEFAULT_LEN];
 char Tail[] = new char [DEFAULT_LEN];
 int Pos = 1;
 Map<Character ,Integer> CharMap = new HashMap<Character,Integer>();
 ArrayList<Character> CharList = new ArrayList<Character>();
 
 public DoubleArrayTrie()
 {
  Base[1] = 1;
  
  CharMap.put(END_CHAR,1);
  CharList.add(END_CHAR);
  CharList.add(END_CHAR);
  for(int i=0;i<26;++i)
  {
   CharMap.put((char)('a'+i),CharMap.size()+1);
   CharList.add((char)('a'+i));
  }
  
 }
 private void Extend_Array()
 {
  Base = Arrays.copyOf(Base, Base.length*2);
  Check = Arrays.copyOf(Check, Check.length*2);
 }
 
 private void Extend_Tail()
 {
  Tail = Arrays.copyOf(Tail, Tail.length*2);
 }
 
 private int GetCharCode(char c)
 {
  if (!CharMap.containsKey(c))
  {
   CharMap.put(c,CharMap.size()+1);
   CharList.add(c);
  }
  return CharMap.get(c);
 }
 private int CopyToTailArray(String s,int p)
 {
  int _Pos = Pos;
  while(s.length()-p+1 > Tail.length-Pos)
  {
   Extend_Tail();
  }
  for(int i=p; i<s.length();++i)
  {
   Tail[_Pos] = s.charAt(i);
   _Pos++;
  }
  return _Pos;
 }
 
 private int x_check(Integer []set)
 {
  for(int i=1; ; ++i)
  {
   boolean flag = true;
   for(int j=0;j<set.length;++j)
   {
    int cur_p = i+set[j];
    if(cur_p>= Base.length) Extend_Array();
    if(Base[cur_p]!= 0 || Check[cur_p]!= 0)
    {
     flag = false;
     break;
    }
   }
   if (flag) return i;
  }
 }
 
 private ArrayList<Integer> GetChildList(int p)
 {
  ArrayList<Integer> ret = new ArrayList<Integer>();
  for(int i=1; i<=CharMap.size();++i)
  {
   if(Base[p]+i >= Check.length) break;
   if(Check[Base[p]+i] == p)
   {
    ret.add(i);
   }
  }
  return ret;
 }
 
 private boolean TailContainString(int start,String s2)
 {
  for(int i=0;i<s2.length();++i)
  {
   if(s2.charAt(i) != Tail[i+start]) return false;
  }
  
  return true;
 }
 private boolean TailMatchString(int start,String s2)
 {
  s2 += END_CHAR;
  for(int i=0;i<s2.length();++i)
  {
   if(s2.charAt(i) != Tail[i+start]) return false;
  }
  return true;
 }
 
 
 public void Insert(String s) throws Exception
 {
  s += END_CHAR;
  
  int pre_p = 1;
  int cur_p;
  for(int i=0; i<s.length(); ++i)
  {
   //獲取狀態(tài)位置
   cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
   //如果長度超過現(xiàn)有,拓展數(shù)組
   if (cur_p >= Base.length) Extend_Array();
   
   //空閑狀態(tài)
   if(Base[cur_p] == 0 && Check[cur_p] == 0)
   {
    Base[cur_p] = -Pos;
    Check[cur_p] = pre_p;
    Pos = CopyToTailArray(s,i+1);
    break;
   }else
   //已存在狀態(tài)
   if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
   {
    pre_p = cur_p;
    continue;
   }else
   //沖突 1:遇到 Base[cur_p]小于0的,即遇到一個被壓縮存到Tail中的字符串
   if(Base[cur_p] < 0 && Check[cur_p] == pre_p)
   {
    int head = -Base[cur_p];
    
    if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR) //插入重復字符串
    {
     break;
    }
    
    //公共字母的情況,因為上一個判斷已經(jīng)排除了結(jié)束符,所以一定是2個都不是結(jié)束符
    if (Tail[head] == s.charAt(i+1))
    {
     int avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});
     Base[cur_p] = avail_base;
     
     Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
     Base[avail_base+GetCharCode(s.charAt(i+1))] = -(head+1);
     pre_p = cur_p;
     continue;
    }
    else
    {
     //2個字母不相同的情況,可能有一個為結(jié)束符
     int avail_base ;
     avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
     
     Base[cur_p] = avail_base;
     
     Check[avail_base+GetCharCode(Tail[head])] = cur_p;
     Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
     
     //Tail 為END_FLAG 的情況
     if(Tail[head] == END_CHAR)
      Base[avail_base+GetCharCode(Tail[head])] = 0;
     else
      Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
     if(s.charAt(i+1) == END_CHAR)
      Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
     else
      Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
     
     Pos = CopyToTailArray(s,i+2);
     break;
    }
   }else
   //沖突2:當前結(jié)點已經(jīng)被占用,需要調(diào)整pre的base
   if(Check[cur_p] != pre_p)
   {
    ArrayList<Integer> list1 = GetChildList(pre_p);
    int toBeAdjust;
    ArrayList<Integer> list = null;
    if(true)
    {
     toBeAdjust = pre_p;
     list = list1;
    }
    
    int origin_base = Base[toBeAdjust];
    list.add(GetCharCode(s.charAt(i)));
    int avail_base = x_check((Integer[])list.toArray(new Integer[list.size()]));
    list.remove(list.size()-1);
    
    Base[toBeAdjust] = avail_base;
    for(int j=0; j<list.size(); ++j)
    {
     //BUG
     int tmp1 = origin_base + list.get(j);
     int tmp2 = avail_base + list.get(j);
     
     Base[tmp2] = Base[tmp1];
     Check[tmp2] = Check[tmp1];
     
     //有后續(xù)
     if(Base[tmp1] > 0)
     {
      ArrayList<Integer> subsequence = GetChildList(tmp1);
      for(int k=0; k<subsequence.size(); ++k)
      {
       Check[Base[tmp1]+subsequence.get(k)] = tmp2;
      }
     }
     
     Base[tmp1] = 0;
     Check[tmp1] = 0;
    }
    
    //更新新的cur_p
    cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
    
    if(s.charAt(i) == END_CHAR)
     Base[cur_p] = 0;
    else
     Base[cur_p] = -Pos;
    Check[cur_p] = pre_p;
    Pos = CopyToTailArray(s,i+1);
    break;
   }
  }
 }
 
 public boolean Exists(String word)
 {
  int pre_p = 1;
  int cur_p = 0;
  
  for(int i=0;i<word.length();++i)
  {
   cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
   if(Check[cur_p] != pre_p) return false;
   if(Base[cur_p] < 0)
   {
    if(TailMatchString(-Base[cur_p],word.substring(i+1)))
     return true;
    return false;
   }
   pre_p = cur_p;
  }
  if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
   return true;
  return false;
 }
 
 //內(nèi)部函數(shù),返回匹配單詞的最靠后的Base index,
 class FindStruct
 {
  int p;
  String prefix="";
 }
 private FindStruct Find(String word)
 {
  int pre_p = 1;
  int cur_p = 0;
  FindStruct fs = new FindStruct();
  for(int i=0;i<word.length();++i)
  {
   // BUG
   fs.prefix += word.charAt(i);
   cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
   if(Check[cur_p] != pre_p)
   {
    fs.p = -1;
    return fs;
   }
   if(Base[cur_p] < 0)
   {
    if(TailContainString(-Base[cur_p],word.substring(i+1)))
    {
     fs.p = cur_p;
     return fs;
    }
    fs.p = -1;
    return fs;
   }
   pre_p = cur_p;
  }
  fs.p =  cur_p;
  return fs;
 }
 
 public ArrayList<String> GetAllChildWord(int index)
 {
  ArrayList<String> result = new ArrayList<String>();
  if(Base[index] == 0)
  {
   result.add("");
   return result;
  }
  if(Base[index] < 0)
  {
   String r="";
   for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
   {
    r+= Tail[i];
   }
   result.add(r);
   return result;
  }
  for(int i=1;i<=CharMap.size();++i)
  {
   if(Check[Base[index]+i] == index)
   {
    for(String s:GetAllChildWord(Base[index]+i))
    {
     result.add(CharList.get(i)+s);
    }
    //result.addAll(GetAllChildWord(Base[index]+i));
   }
  }
  return result;
 }
 
 public ArrayList<String> FindAllWords(String word)
 {
  ArrayList<String> result = new ArrayList<String>();
  String prefix = "";
  FindStruct fs = Find(word);
  int p = fs.p;
  if (p == -1) return result;
  if(Base[p]<0)
  {
   String r="";
   for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
   {
    r+= Tail[i];
   }
   result.add(fs.prefix+r);
   return result;
  }
  
  if(Base[p] > 0)
  {
   ArrayList<String> r =  GetAllChildWord(p);
   for(int i=0;i<r.size();++i)
   {
    r.set(i, fs.prefix+r.get(i));
   }
   return r;
  }
  
  return result;
 }
 
}

測試代碼:

復制代碼 代碼如下:

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

import javax.xml.crypto.Data;


public class Main {

 public static void main(String[] args) throws Exception {
  ArrayList<String> words = new ArrayList<String>();
  BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/兔子的試驗學習中心[課內(nèi)]/ACM大賽/ACM第四屆校賽/E命令提示/words3.dic")));
  String s;
  int num = 0;
  while((s=reader.readLine()) != null)
  {
   words.add(s);
   num ++;
  }
  DoubleArrayTrie dat = new DoubleArrayTrie();
  
  for(String word: words)
  {
   dat.Insert(word);
  }
  
  System.out.println(dat.Base.length);
  System.out.println(dat.Tail.length);
  
  Scanner sc = new Scanner(System.in);
  while(sc.hasNext())
  {
   String word = sc.next();
   System.out.println(dat.Exists(word));
   System.out.println(dat.FindAllWords(word));
  }
  
 }

}

下面是測試結(jié)果,構(gòu)造6W英文單詞的DAT,大概需要20秒

我增長數(shù)組的時候是每次長度增加到2倍,初始1024

Base和Check數(shù)組的長度為131072

Tail的長度為262144

TTT1

相關(guān)文章

最新評論