Das traditionelle Trie ist einfach zu implementieren, aber der Platzbedarf ist wirklich inakzeptabel. Insbesondere wenn der Zeichensatz nicht auf die 26 englischen Zeichen beschränkt ist, ist der explodierte Platz einfach inakzeptabel.
Double Array Trie ist ein platzoptimierter Trie-Baum. Das Prinzip wird in diesem Artikel nicht besprochen.
Bezüglich einiger Details, die im Dokument nicht erwähnt werden, und Implementierungen, die nicht mit dem Dokument übereinstimmen:
1. Wenn es sich beim Einfügen von Zeichenfolgen um eine Teilzeichenfolge einer anderen Zeichenfolge handelt, verwende ich das Abschlusszeichen auch als Kante, um einen neuen Knoten zu generieren. Ich setze die Basis des neuen Knotens auf 0.
Daher gibt es am Ende einer Zeichenfolge zwei Situationen: Zum einen ist der Basiswert negativ und die verbleibenden Zeichen (möglicherweise nur ein Abschlusszeichen) werden im Tail-Array gespeichert. Zum anderen ist der Basiswert 0.
Daher sollten Sie diese beiden Situationen bei Ihren Anfragen berücksichtigen.
2. Für den ersten Konflikttyp (Fall 3 im Artikel) kann es erforderlich sein, einen Teil der Zeichenfolge in Tail herauszunehmen und ihn als Kante in den Index einzufügen. Das Papier verwendet die Methode, die Endzeichenfolge nach links zu verschieben. Meine Methode ändert den Basiswert direkt, anstatt die Endzeichenfolge zu verschieben.
Das Folgende ist der in Java implementierte Code, der das Einfügen derselben Zeichenfolge, das Einfügen von Teilzeichenfolgen usw. verarbeiten kann.
Kopieren Sie den Codecode wie folgt:
/*
* Name: Double Array Trie
* Autor: Yaguang Ding
* E-Mail: [email protected]
* Blog: blog.csdn.net/dingyaguang117
* Datum: 21.05.2012
* Hinweis: Ein Wort endet in einer dieser beiden Groß-/Kleinschreibungen:
* 1. Base[cur_p] == pos ( pos<0 und Tail[-pos] == 'END_CHAR' )
* 2. Check[Base[cur_p] + Code('END_CHAR')] == cur_p
*/
import java.util.ArrayList;
import java.util.HashMap;
java.util.Map importieren;
java.util.Arrays importieren;
öffentliche Klasse DoubleArrayTrie {
letztes Zeichen 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>();
öffentliches DoubleArrayTrie()
{
Basis[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)
{
boolesches 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;
brechen;
}
}
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;
}
privater boolescher Wert TailContainString(int start,String s2)
{
for(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
return true;
}
privater boolescher 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) löst eine Ausnahme aus
{
s += END_CHAR;
int pre_p = 1;
int cur_p;
for(int i=0; i<s.length(); ++i)
{
//Statusort abrufen
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//Wenn die Länge die vorhandene Länge überschreitet, erweitern Sie das Array
if (cur_p >= Base.length) Extend_Array();
//Ruhezustand
if(Base[cur_p] == 0 && Check[cur_p] == 0)
{
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
brechen;
}anders
//Vorhandener Status
if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
{
pre_p = cur_p;
weitermachen;
}anders
//Konflikt 1: Wenn Base[cur_p] kleiner als 0 ist, wird eine Zeichenfolge gefunden, die komprimiert und in Tail gespeichert wird.
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)//Wiederholte Zeichenfolge einfügen
{
brechen;
}
//Bei gewöhnlichen Buchstaben dürfen beide keine Endzeichen sein, da das letzte Urteil das Endzeichen ausgeschlossen hat.
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;
weitermachen;
}
anders
{
//Wenn die beiden Buchstaben nicht identisch sind, kann einer von ihnen das Endzeichen sein.
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;
//Ende ist END_FLAG
if(Tail[head] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
anders
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
if(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
anders
Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
brechen;
}
}anders
//Konflikt 2: Der aktuelle Knoten ist bereits belegt und die Vorbasis muss angepasst werden.
if(Check[cur_p] != pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> list = null;
wenn(wahr)
{
toBeAdjust = pre_p;
Liste = Liste1;
}
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)
{
//INSEKT
int tmp1 = origin_base + list.get(j);
int tmp2 = avail_base + list.get(j);
Basis[tmp2] = Basis[tmp1];
Check[tmp2] = Check[tmp1];
//Es gibt ein Follow-up
if(Base[tmp1] > 0)
{
ArrayList<Integer> subsequence = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Check[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Basis[tmp1] = 0;
Check[tmp1] = 0;
}
//Neues cur_p aktualisieren
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
Basis[cur_p] = 0;
anders
Base[cur_p] = -Pos;
Check[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
brechen;
}
}
}
public boolean Exists(String-Wort)
{
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;
}
//Interne Funktion, gibt den letzten Basisindex des passenden Wortes zurück,
classFindStruct
{
int p;
String-Präfix="";
}
private FindStruct Find(String-Wort)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
for(int i=0;i<word.length();++i)
{
// INSEKT
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p)
{
fs.p = -1;
fs zurückgeben;
}
if(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
fs zurückgeben;
}
fs.p = -1;
fs zurückgeben;
}
pre_p = cur_p;
}
fs.p = cur_p;
fs zurückgeben;
}
public ArrayList<String> GetAllChildWord(int index)
{
ArrayList<String> result = new ArrayList<String>();
if(Basis[index] == 0)
{
result.add("");
Ergebnis zurückgeben;
}
if(Basis[Index] < 0)
{
String r="";
for(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= Tail[i];
}
result.add(r);
Ergebnis zurückgeben;
}
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));
}
}
Ergebnis zurückgeben;
}
public ArrayList<String> FindAllWords(String Wort)
{
ArrayList<String> result = new ArrayList<String>();
String-Präfix = „“;
FindStruct fs = Find(word);
int p = fs.p;
if (p == -1) Ergebnis zurückgeben;
if(Base[p]<0)
{
String r="";
for(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= Tail[i];
}
result.add(fs.prefix+r);
Ergebnis zurückgeben;
}
if(Basis[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;
}
Ergebnis zurückgeben;
}
}
Testcode:
Kopieren Sie den Codecode wie folgt:
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;
javax.xml.crypto.Data importieren;
öffentliche Klasse Main {
public static void main(String[] args) löst eine Ausnahme aus {
ArrayList<String> Words = new ArrayList<String>();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Rabbit's Experimental Learning Center [In-class]/ACM Competition/ACM 4th School Competition/E Command Prompt/words3.dic")));
String s;
int num = 0;
while((s=reader.readLine()) != null)
{
Wörter.add(s);
num++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
for(String Wort: Wörter)
{
dat.Insert(word);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Scanner sc = neuer Scanner(System.in);
while(sc.hasNext())
{
String word = sc.next();
System.out.println(dat.Exists(word));
System.out.println(dat.FindAllWords(word));
}
}
}
Im Folgenden sind die Testergebnisse aufgeführt. Die Erstellung eines DAT mit 6W englischen Wörtern dauert etwa 20 Sekunden.
Wenn ich das Array vergrößere, erhöht sich die Länge jedes Mal auf das Zweifache, zunächst 1024
Die Länge der Basis- und Prüfarrays beträgt 131072
Die Länge des Schwanzes beträgt 262144
TTT1