従来の Trie は実装が簡単ですが、占有するスペースが非常に大きく、特に文字セットが 26 文字の英語に限定されていない場合、拡張されたスペースがまったく受け入れられません。
Double array Trie はスペース最適化された Trie ツリーです。この記事ではその原理については説明しません。このプログラムもこの論文を参照して書かれています。
論文で言及されていないいくつかの詳細および論文と矛盾する実装については、次のとおりです。
1. 文字列を挿入する場合、文字列が別の文字列の部分文字列である場合、ターミネータをエッジとして使用して新しいノードを生成し、新しいノードの Base を 0 に設定します。
したがって、文字列の末尾には 2 つの状況が存在します。1 つは Base 値が負で、残りの文字 (おそらく 1 つのターミネータのみ) が Tail 配列に格納されている場合です。もう 1 つは Base が 0 である場合です。
したがって、お問い合わせの際には、これら 2 つの状況を考慮する必要があります。
2. 最初の種類の競合 (論文のケース 3) の場合は、Tail の文字列の一部を取り出し、それをエッジとしてインデックスに入れる必要がある場合があります。この論文では、末尾文字列を移動するのではなく、Base 値を直接変更する方法を使用しています。
以下は Java で実装されたコードで、同じ文字列の挿入や部分文字列の挿入などを処理できます。
次のようにコードをコピーします。
/*
* 名前: ダブル アレイ トライ
* 著者: 丁亜光
*メール:[email protected]
* ブログ: blog.csdn.net/dingyaguang117
※日付：2012/5/21
* 注: 単語の終わりは次の 2 つのケースのいずれかになります。
* 1. Base[cur_p] == pos ( pos<0 および Tail[-pos] == 'END_CHAR' )
* 2. Check[Base[cur_p] + Code('END_CHAR')] == cur_p
*/
java.util.ArrayListをインポートします。
java.util.HashMapをインポートします。
java.util.Mapをインポートします。
java.util.Arraysをインポートします。
パブリック クラス DoubleArrayTrie {
最後の文字 END_CHAR = '/0';
最終 int DEFAULT_LEN = 1024;
int Base[] = 新しい int [DEFAULT_LEN];
int Check[] = 新しい int [DEFAULT_LEN];
char Tail[] = 新しい文字 [DEFAULT_LEN];
int 位置 = 1;
Map<Character,Integer> CharMap = new HashMap<Character,Integer>();
ArrayList<Character> CharList = new ArrayList<Character>();
public DoubleArrayTrie()
{
ベース[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);
}
CharMap.get(c) を返します。
}
private int CopyToTailArray(String s,int p)
{
int _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++;
}
_Pos を返します。
}
private int x_check(Integer []set)
{
for(int i=1; ; ++i)
{
ブール値フラグ = 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 || チェック[cur_p]!= 0)
{
フラグ = false;
壊す;
}
}
if (フラグ) は 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) ブレーク;
if(Check[Base[p]+i] == p)
{
ret.add(i);
}
}
retを返します。
}
private boolean TailContainString(int start,String s2)
{
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) は false を返します。
}
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]) は false を返します。
}
true を返します。
}
public void Insert(String s) が例外をスローする
{
s += END_CHAR;
int pre_p = 1;
int cur_p;
for(int i=0; i<s.length(); ++i)
{
//ステータスの場所を取得する
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//長さが既存の長さを超える場合、配列を拡張します
if (cur_p >= Base.length) Extend_Array();
//アイドル状態
if(Base[cur_p] == 0 && Check[cur_p] == 0)
{
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
壊す;
}それ以外
//現在のステータス
if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
{
pre_p = cur_p;
続く;
}それ以外
//競合 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)//繰り返しの文字列を挿入
{
壊す;
}
//共通文字の場合、最後の判定でターミネータが除外されているため、両方ともターミネータではないはずです。
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;
続く;
}
それ以外
{
//2 つの文字が同じでない場合、そのうちの 1 つがターミネータである可能性があります。
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;
//末尾はEND_FLAGです
if(末尾[頭] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
それ以外
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
if(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
それ以外
Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
壊す;
}
}それ以外
//競合 2: 現在のノードはすでに占有されており、プリベースを調整する必要があります。
if(Check[cur_p] != pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> リスト = null;
もし(真)
{
toBeAdjust = pre_p;
リスト = リスト 1;
}
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)
{
//バグ
int tmp1 = Origin_base + list.get(j);
int tmp2 = avail_base + list.get(j);
ベース[tmp2] = ベース[tmp1];
チェック[tmp2] = チェック[tmp1];
//続報あり
if(Base[tmp1] > 0)
{
ArrayList<Integer> サブシーケンス = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Check[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
ベース[tmp1] = 0;
チェック[tmp1] = 0;
}
// 新しい cur_p を更新します
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
Base[cur_p] = 0;
それ以外
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
壊す;
}
}
}
public boolean Exists(文字列単語)
{
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) false を返します。
if(Base[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
true を返します。
false を返します。
}
pre_p = cur_p;
}
if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
true を返します。
false を返します。
}
//内部関数は、一致する単語の最後の Base インデックスを返します。
クラスFindStruct
{
int p;
文字列プレフィックス="";
}
private FindStruct Find(文字列単語)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
for(int i=0;i<word.length();++i)
{
// バグ
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p)
{
fs.p = -1;
fs を返します。
}
if(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
fs を返します。
}
fs.p = -1;
fs を返します。
}
pre_p = cur_p;
}
fs.p = cur_p;
fs を返します。
}
public ArrayList<String> GetAllChildWord(int インデックス)
{
ArrayList<String> 結果 = new ArrayList<String>();
if(ベース[インデックス] == 0)
{
result.add("");
結果を返します。
}
if(ベース[インデックス] < 0)
{
文字列 r="";
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= テール[i];
}
result.add(r);
結果を返します。
}
for(int i=1;i<=CharMap.size();++i)
{
if(Check[Base[index]+i] == インデックス)
{
for(String s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
結果を返します。
}
public ArrayList<String> FindAllWords(String word)
{
ArrayList<String> 結果 = new ArrayList<String>();
文字列プレフィックス = "";
FindStruct fs = Find(単語);
int p = fs.p;
if (p == -1) 結果を返します。
if(Base[p]<0)
{
文字列 r="";
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= テール[i];
}
result.add(fs.prefix+r);
結果を返します。
}
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));
}
rを返します。
}
結果を返します。
}
}
テストコード:
次のようにコードをコピーします。
java.io.BufferedReaderをインポートします。
java.io.FileInputStreamをインポートします。
インポート java.io.IOException;
java.io.InputStreamをインポートします。
インポートjava.io.InputStreamReader;
java.util.ArrayListをインポートします。
java.util.Scannerをインポートします。
javax.xml.crypto.Dataをインポートします。
パブリッククラス Main {
public static void main(String[] args) throws Exception {
ArrayList<String> 単語 = new ArrayList<String>();
BufferedReader リーダー = new BufferedReader(new InputStreamReader(new FileInputStream("E:/ウサギの実験学習センター [クラス内]/ACM コンペティション/ACM 第 4 回学校コンペティション/E コマンド プロンプト/words3.dic")));
文字列 ;
int num = 0;
while((s=reader.readLine()) != null)
{
Words.add(s);
数値++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
for(文字列単語:単語)
{
dat.Insert(単語);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
スキャナー sc = 新しいスキャナー(System.in);
while(sc.hasNext())
{
文字列ワード = sc.next();
System.out.println(dat.Exists(word));
System.out.println(dat.FindAllWords(word));
}
}
}
以下はテスト結果です。6W の英単語の DAT を構築するのに約 20 秒かかります。
配列を拡大すると、長さは毎回 2 倍に増加します (最初は 1024)
Base 配列と Check 配列の長さは 131072 です。
尻尾の長さは262144です
TTT1