)
>
trie中了。插入后的结果如Figure 3所示：
Trie的删除操作
Trie的删除操作也是非常简单。把前面的插入熟悉后，自己看论文《An Efficient Implementation of TrieStructures》就能懂了，这里也就不继续解说了。
论文剩下的部分就是性能的评估，感兴趣的可以自行了解。最后有实现的伪代码，还是有一定的参考价值的。
其实，字符串处理的相关数据结构，无非是利用了字符串的前缀和后缀信息。比如SuffixArray(后缀数组)利用的是后缀信息，Trie树，利用的是前缀信息。
理解DATrie树，我们应该认识到，DATrie是一种数据结构，理解数据结构，只需要理解数据结构对数据的”增删改查”四种操作就可以了。对于DATrie，其核心在于理解插入操作；而插入操作的难点在于理解BASE数组和CHECK数组，BASE数组和CHECK数组的难点在于插入时出现冲突的解决方案。所以，DATrie树的难点只有一个：冲突解决方案。
在学习的过程，反复在纸上画出trie的结构，自己推理double-array值对于理解trie是非常有帮助的。
最后提供一个测试样例：“ba” “bac” ”be”“bae”，因为没有这个样例，我在编码的时候被困了好几天。
在我的笔记本电脑上<i5+4G内存+32位win7+2.4GZ>，用DATrie 插入38万数量的词典，用时240084毫秒,查询用时299毫秒。
最后还是贴出代码吧！
package com.vancl.dic;import java.io.DataInputStream;import java.io.DataOutputStream;import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.RandomAccessFile;import java.util.ArrayList;import java.util.Arrays;public class DATrie {final int DEF_LEN=1024;final char END_TAG=’#’;//#在CWC中的value=1int[] base = new int[DEF_LEN];int[] check = new int[DEF_LEN];char[] tail =new char[DEF_LEN];int tailPos;public DATrie(){base[1]=1;tailPos=1;Hash.put(END_TAG,1);}/** 查找一个词是否在Trie树结构中* */public boolean retrieval(String word){//执行查询操作int pre=1,cur=0;for(int i=0;i<word.length();i++){cur=base[pre]+GetCode(word.charAt(i));if(check[cur]!=pre)return false;//到tail数组中去查询if(base[cur]<0 ){int head=-base[cur];return MatchInTail(word, i+1, head);}pre=cur;}//这一句是关键，，对于一个串是另一个字符串 子串的情况if(check[base[cur]+GetCode(END_TAG)]==cur)return true;return false;}public void insert(String word){word+=END_TAG;for(int i=0,pre=1,cur;i<word.length();i++){cur=base[pre]+GetCode(word.charAt(i));//容量不够的时，扩容if(cur>=base.length)extend();//空白位置，可以添加，这里需要注意的是如果check[cur]=0,则base[cur]=0成立if( check[cur] == 0){check[cur]=pre;base[cur]=-tailPos;toTail(word,i+1); //把剩下的字符串存储到tail数组中return;//当前词已经插入到DATire中}//公共前缀，直接走if(check[cur]==pre && base[cur]>0 ){pre=cur;continue;}//遇到压缩到tail中的字符串，有可能是公共前缀if(check[cur] == pre && base[cur]<0 ){//是公共前缀，把前缀解放出来int new_base_value,head;head=-base[cur];//插入相同的字符串if(tail[head]==END_TAG && word.charAt(i+1)== END_TAG)return ;if(tail[head]==word.charAt(i+1)){int ncode=GetCode(word.charAt(i+1));new_base_value=x_check(new Integer[]{ncode});//解放当前结点base[cur]=new_base_value;//连接到新的结点base[new_base_value+ncode]=-(head+1);check[new_base_value+ncode]=cur;//把边推向前一步,继续pre=cur;continue;}/** 两个字符不相等,这里需要注意”一个串是另一个串的子串的情况”* */int tailH=GetCode(tail[head]),nextW=GetCode(word.charAt(i+1));new_base_value=x_check(new Integer[]{tailH,nextW});base[cur]=new_base_value;//确定父子关系check[new_base_value+tailH] = cur;check[new_base_value+nextW] = cur;//处理原来tail的首字符base[new_base_value+tailH] = (tail[head] == END_TAG) ? 0 : -(head+1);//处理新加进来的单词后缀base[new_base_value+nextW] = (word.charAt(i+1) == END_TAG) ? 0 : -tailPos;toTail(word,i+2); return;}/** 冲突:当前结点已经被占用，需要调整pre的base* 这里也就是整个DATrie最复杂的地方了* */if(check[cur] != pre){int adjustBase=pre;Integer[] list=GetAllChild(pre);//父结点的所有孩子Integer[] tmp=GetAllChild(check[cur]);//产冲突结点的所有孩子int new_base_value;if(tmp!=null && tmp.length<=list.length+1){list=tmp;tmp=null;adjustBase=check[cur];new_base_value=x_check(list);}else{//由于当前字符也是结点的孩子，所以需要把当前字符加上list=Arrays.copyOf(list, list.length+1);list[list.length-1]=GetCode(word.charAt(i));new_base_value=x_check(list);//但是当前字符 现在并不是他的孩子，所以暂时先需要去掉list=Arrays.copyOf(list, list.length-1);}int old_base_value=base[adjustBase];base[adjustBase]=new_base_value;int old_pos,new_pos;//处理所有节点的冲突for(int j=0;j<list.length;j++){old_pos=old_base_value+list[j];new_pos=new_base_value+list[j];/** if(old_pos==pre)pre=new_pos;* 这句代码差不多花了我3天的时间，才想出来* 其间，反复看论文，理解DATrie树的操作过程。* 动手在纸上画分析DATrie可能的结构。最后找到* 样例：”ba”,”bac”,”be”,”bae” 解决问题* */if(old_pos==pre)pre=new_pos;//把原来老结点的信息迁移到新节点上base[new_pos]=base[old_pos];check[new_pos]=check[old_pos];//有后续,所有孩子都用新的父亲替代原来的父亲if(base[old_pos]>0){tmp=GetAllChild(old_pos);for (int k = 0; k < tmp.length; k++) {check[base[old_pos]+tmp[k]] = new_pos;}}//释放废弃的节点空间base[old_pos]=0;check[old_pos]=0;}//冲突处理完毕，把新的单词插入到DATrie中cur=base[pre]+GetCode(word.charAt(i));if(check[cur]!=0){System.err.println(“collision exists~!”);}base[cur]=(word.charAt(i)==END_TAG)?0:-tailPos;check[cur]=pre;toTail(word,i+1);return;//这里不能忘记了}}}//到Tail数组中进行比较private boolean MatchInTail(String word,int start,int head){word+=END_TAG;while(start<word.length()){if(word.charAt(start++)!=tail[head++])return false;}return true;}/** 寻找最小的q,q要满足的条件是：q>0 ,并且对于list中所有的元素都有check[q+c]=0* */private int x_check(Integer[] c){int cur,q=1,i=0;do{cur = q + c[i++];if(cur >= check.length) extend();if(check[cur] != 0 ){i=0;++q;}}while(i<c.length);return q;}//寻找一个节点的所有子元素private Integer[] GetAllChild(int pos){if(base[pos]<0)return null;ArrayList<Integer> c=new ArrayList<Integer>();for(int i=1;i<=Hash.size();i++){if(base[pos] + i >= check.length)break;if(check[base[pos]+i] == pos)c.add(i);}return c.toArray(new Integer[c.size()]);}public Integer GetCode(char ch){return Hash.GetCode(ch);}//将字符串的后缀存储到tail数组中private void toTail(String w,int pos){//如果容量不足，就扩容if(tail.length-tailPos < w.length()-pos)tail=Arrays.copyOf(tail, tail.length<<1);while(pos<w.length()){tail[tailPos++]=w.charAt(pos++);}}private void extend(){base=Arrays.copyOf(base, base.length<<1);check=Arrays.copyOf(check, check.length<<1);}}宁愿停歇在你门前的那棵树上，看着你，守护你。
