Java实现双数组Trie树(DoubleArrayTrie,DAT) - JAVA

传统的Trie实现简单，但是占用的空间实在是难以接受，特别是当字符集不仅限于英文26个字符的时候，爆炸起来的空间根本无法接受。

双数组Trie就是优化了空间的Trie树，原理本文就不讲了，请参考An Efficient Implementation of Trie Structureshttp://www.google.com.hk/url sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CGUQFjAA&url=http%3A%2F%2Fsc.snu.ac.kr%2F~xuan%2Fspe777ja.pdf&ei=WO_CT9bFPKWviQfd3byzCg&usg=AFQjCNH7_meaLSKZ6ssfMV47TFsHQGHAxQ，本程序的编写也是参考这篇论文的。

关于几点论文没有提及的细节和与论文不一一致的实现：

1.对于插入字符串，如果有一个字符串是另一个字符串的子串的话，我是将结束符也作为一条边，产生一个新的结点，这个结点新节点的Base我置为0

所以一个字符串结束也有2中情况：一个是Base值为负，存储剩余字符(可能只有一个结束符)到Tail数组；另一个是Base为0。

所以在查询的时候要考虑一下这两种情况

2.对于第一种冲突（论文中的Case 3），可能要将Tail中的字符串取出一部分，作为边放到索引中。论文是使用将尾串左移的方式，我的方式直接修改Base值，而不是移动尾串。

下面是java实现的代码，可以处理相同字符串插入，子串的插入等情况

[java] /*
* Name: Double Array Trie
* Author: Yaguang Ding
* 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

Java实现双数组Trie树(DoubleArrayTrie,DAT) (一)