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

作者：dingyaguang117 2012-05-30 09:55:55

傳統(tǒng)的Trie實現(xiàn)簡單，但是占用的空間實在是難以接受，特別是當字符集不僅限于英文26個字符的時候，爆炸起來的空間根本無法接受。雙數(shù)組Trie就是優(yōu)化了空間的Trie樹，原理本文就不講了，請參考An Efficient Implementation of Trie Structures，本程序的編寫也是參考這篇論文的。

傳統(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)    //插入重復(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：當前結(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

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

責任編輯：林師授來源： dingyaguang117博客

Java Trie