婷婷五月天乱日韩欧美色色色,尤物蜜芽第一页人特黄,一级A黄色片一级a免费看片

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案

Java實現(xiàn)雙數(shù)組Trie樹(DoubleArrayTrie,DAT)

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

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了高安免費建站歡迎大家使用！

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

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

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

所以一個字符串結(jié)束也有2中情況：一個是Base值為負(fù)，存儲剩余字符(可能只有一個結(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 CharMap = new HashMap(); 
  
  
  
      ArrayList CharList = new ArrayList(); 
  
  
  
       
  
  
  
      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
  
  
  
  
        { 
  
  
  
              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
  
  
  
  
            { 
  
  
  
                  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 GetChildList(int p) 
  
  
  
      { 
  
  
  
          ArrayList ret = new ArrayList(); 
  
  
  
          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
  
  
  
  
        { 
  
  
  
              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
  
  
  
  
        { 
  
  
  
              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
  
  
  
  
        { 
  
  
  
              //獲取狀態(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)    //插入重復(fù)字符串 
  
  
  
                  { 
  
  
  
                      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：當(dāng)前結(jié)點已經(jīng)被占用，需要調(diào)整pre的base 
  
  
  
              if(Check[cur_p] != pre_p) 
  
  
  
              { 
  
  
  
                  ArrayList list1 = GetChildList(pre_p); 
  
  
  
                  int toBeAdjust; 
  
  
  
                  ArrayList 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
  
  
  
  
                { 
  
  
  
                      //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 subsequence = GetChildList(tmp1); 
  
  
  
                          for(int k=0; 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
  
  
  
  
        { 
  
  
  
              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
  
  
  
  
        { 
  
  
  
              // 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 GetAllChildWord(int index) 
  
  
  
      { 
  
  
  
          ArrayList result = new ArrayList(); 
  
  
  
          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 FindAllWords(String word) 
  
  
  
      { 
  
  
  
          ArrayList result = new ArrayList(); 
  
  
  
          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 r =  GetAllChildWord(p); 
  
  
  
              for(int i=0;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 words = new ArrayList(); 
  
  
  
          BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/兔子的試驗學(xué)習(xí)中心[課內(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

原文地址：Java實現(xiàn)雙數(shù)組Trie樹(DoubleArrayTrie,DAT)

文章標(biāo)題：Java實現(xiàn)雙數(shù)組Trie樹(DoubleArrayTrie,DAT)
分享網(wǎng)址：http://m.5511xx.com/article/copcdgh.html

日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

新聞中心

其他資訊