Le Trie traditionnel est simple à mettre en œuvre, mais l'espace qu'il occupe est vraiment inacceptable. Surtout lorsque le jeu de caractères n'est pas limité aux 26 caractères anglais, l'espace éclaté est tout simplement inacceptable.
Double array Trie est un arbre Trie optimisé pour l'espace. Le principe ne sera pas abordé dans cet article. Veuillez vous référer à Une implémentation efficace des structures Trie. Ce programme est également écrit en référence à cet article.
Concernant plusieurs détails non mentionnés dans le document et des implémentations incompatibles avec le document :
1. Pour insérer des chaînes, si une chaîne est une sous-chaîne d'une autre chaîne, j'utiliserai également le terminateur comme arête pour générer un nouveau nœud. Je définirai la base du nouveau nœud sur 0.
Par conséquent, il existe deux situations à la fin d'une chaîne : l'une est que la valeur de base est négative et les caractères restants (peut-être un seul terminateur) sont stockés dans le tableau Tail ; l'autre est que la valeur de base est 0 ;
Par conséquent, vous devez considérer ces deux situations lorsque vous effectuez une demande de renseignements.
2. Pour le premier type de conflit (cas 3 dans l'article), il peut être nécessaire de retirer une partie de la chaîne dans Tail et de la mettre dans l'index comme arête. L'article utilise la méthode de déplacement de la chaîne de queue vers la gauche. Ma méthode modifie directement la valeur de base au lieu de déplacer la chaîne de queue.
Voici le code implémenté en Java, qui peut gérer l'insertion de la même chaîne, l'insertion de sous-chaînes, etc.
Copiez le code comme suit :
/*
* Nom : Trie à double matrice
* Auteur : Yaguang Ding
* Mail : [email protected]
* Blog : blog.csdn.net/dingyaguang117
* Date : 2012/05/21
* Remarque : la fin d'un mot peut être dans l'une ou l'autre de ces deux casses :
* 1. Base[cur_p] == pos ( pos<0 et Tail[-pos] == 'END_CHAR' )
* 2. Vérifiez[Base[cur_p] + Code('END_CHAR')] == cur_p
*/
importer java.util.ArrayList ;
importer java.util.HashMap ;
importer java.util.Map ;
importer java.util.Arrays ;
classe publique DoubleArrayTrie {
caractère final END_CHAR = '/0';
final int DEFAULT_LEN = 1024 ;
int Base[] = nouveau int [DEFAULT_LEN];
int Check[] = new int [DEFAULT_LEN];
char Tail[] = nouveau 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);
pour(int i=0;i<26;++i)
{
CharMap.put((char)('a'+i),CharMap.size()+1);
CharList.add((char)('a'+i));
}
}
vide privé Extend_Array()
{
Base = Arrays.copyOf(Base, Base.length*2);
Check = Arrays.copyOf(Check, Check.length*2);
}
vide privé Extend_Tail()
{
Queue = Arrays.copyOf(Tail, Tail.length*2);
}
privé int GetCharCode (char c)
{
si (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
retourner CharMap.get(c);
}
privé int CopyToTailArray (String s,int p)
{
int _Pos = Pos;
while(s.length()-p+1 > Tail.length-Pos)
{
Extend_Tail();
}
pour(int i=p; i<s.length();++i)
{
Tail[_Pos] = s.charAt(i);
_Pos++;
}
retourner _Pos ;
}
private int x_check (Entier []set)
{
pour(int i=1; ; ++i)
{
indicateur booléen = vrai ;
pour(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 || Vérifier[cur_p]!= 0)
{
drapeau = faux ;
casser;
}
}
si (drapeau) renvoie i ;
}
}
privé ArrayList<Integer> GetChildList(int p)
{
ArrayList<Integer> ret = new ArrayList<Integer>();
pour(int i=1; i<=CharMap.size();++i)
{
if(Base[p]+i >= Check.length) break;
si (Vérifier [Base [p] + i] == p)
{
ret.add(i);
}
}
retour à la retraite;
}
booléen privé TailContainString (int start, String s2)
{
pour(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
renvoie vrai ;
}
booléen privé TailMatchString (int start, String s2)
{
s2 += FIN_CHAR ;
pour(int i=0;i<s2.length();++i)
{
if(s2.charAt(i) != Tail[i+start]) return false;
}
renvoie vrai ;
}
public void Insert (String s) lève une exception
{
s += FIN_CHAR ;
int pre_p = 1;
int cur_p;
pour(int i=0; i<s.length(); ++i)
{
//Obtenir l'emplacement du statut
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//Si la longueur dépasse la longueur existante, développez le tableau
if (cur_p >= Base.length) Extend_Array();
//état inactif
if(Base[cur_p] == 0 && Vérifier[cur_p] == 0)
{
Base[cur_p] = -Pos;
Vérifiez[cur_p] = pre_p;
Pos = CopierVersTailArray(s,i+1);
casser;
}autre
//statut existant
if(Base[cur_p] > 0 && Check[cur_p] == pre_p)
{
pre_p = cur_p;
continuer;
}autre
//Conflit 1 : lorsque Base[cur_p] est inférieur à 0, il rencontre une chaîne compressée et stockée dans 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)//Insérer une chaîne répétée
{
casser;
}
//Dans le cas de lettres communes, parce que le jugement dernier a exclu le terminateur, donc les deux ne doivent pas être des terminateurs.
if (Tail[head] == s.charAt(i+1))
{
intava_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});
Base[cur_p] = disponibilité_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;
continuer;
}
autre
{
//Si les deux lettres ne sont pas identiques, l'une d'elles peut être le terminateur.
int disponibilité_base ;
ava_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
Base[cur_p] = disponibilité_base ;
Check[avail_base+GetCharCode(Tail[head])] = cur_p;
Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//La queue est END_FLAG
si(Queue[tête] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
autre
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
si(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
autre
Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopierVersTailArray(s,i+2);
casser;
}
}autre
//Conflit 2 : le nœud actuel est déjà occupé et la pré-base doit être ajustée.
if(Vérifiez[cur_p] != pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> list = null;
si (vrai)
{
toBeAdjust = pre_p;
liste = liste1;
}
int origin_base = Base[toBeAdjust];
list.add(GetCharCode(s.charAt(i)));
intava_base = x_check((Integer[])list.toArray(new Integer[list.size()]));
list.remove(list.size()-1);
Base[toBeAdjust] = disponibilité_base ;
pour(int j=0; j<list.size(); ++j)
{
//BOGUE
int tmp1 = origin_base + list.get(j);
int tmp2 = disponibilité_base + list.get(j);
Base[tmp2] = Base[tmp1];
Vérifier[tmp2] = Vérifier[tmp1];
//Il y a un suivi
si(Base[tmp1] > 0)
{
ArrayList<Integer> sous-séquence = GetChildList(tmp1);
pour(int k=0; k<subsequence.size(); ++k)
{
Vérifiez[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Base[tmp1] = 0 ;
Vérifiez[tmp1] = 0 ;
}
//Mise à jour du nouveau cur_p
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
si(s.charAt(i) == END_CHAR)
Base[cur_p] = 0 ;
autre
Base[cur_p] = -Pos;
Vérifiez[cur_p] = pre_p;
Pos = CopierVersTailArray(s,i+1);
casser;
}
}
}
public booléen existe (mot de chaîne)
{
int pre_p = 1;
int cur_p = 0;
pour(int i=0;i<word.length();++i)
{
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p) return false;
si (Base [cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
renvoie vrai ;
renvoie faux ;
}
pre_p = cur_p;
}
if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
renvoie vrai ;
renvoie faux ;
}
//Fonction interne, renvoie le dernier index de base du mot correspondant,
classeFindStruct
{
int p;
Préfixe de chaîne="";
}
privé FindStruct Find (mot de chaîne)
{
int pre_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
pour(int i=0;i<word.length();++i)
{
// BOGUE
fs.prefix += word.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Vérifiez[cur_p] != pre_p)
{
fs.p = -1 ;
retourner fs ;
}
si (Base [cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
retourner fs ;
}
fs.p = -1 ;
retourner fs ;
}
pre_p = cur_p;
}
fs.p = cur_p;
retourner fs ;
}
public ArrayList<String> GetAllChildWord(int index)
{
ArrayList<String> result = new ArrayList<String>();
si (Base [index] == 0)
{
result.add("");
renvoyer le résultat ;
}
si (Base[index] < 0)
{
Chaîne r="";
pour(int i=-Base[index];Tail[i]!=END_CHAR;++i)
{
r+= Queue[i];
}
result.add(r);
renvoyer le résultat ;
}
pour(int i=1;i<=CharMap.size();++i)
{
if(Check[Base[index]+i] == index)
{
pour (String s:GetAllChildWord(Base[index]+i))
{
result.add(CharList.get(i)+s);
}
//result.addAll(GetAllChildWord(Base[index]+i));
}
}
renvoyer le résultat ;
}
public ArrayList<String> FindAllWords (mot de chaîne)
{
ArrayList<String> result = new ArrayList<String>();
Préfixe de chaîne = "" ;
FindStruct fs = Trouver(mot);
int p = fs.p;
if (p == -1) renvoie le résultat ;
si(Base[p]<0)
{
Chaîne r="";
pour(int i=-Base[p];Tail[i]!=END_CHAR;++i)
{
r+= Queue[i];
}
result.add(fs.prefix+r);
renvoyer le résultat ;
}
si (Base[p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
pour(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
retourner r ;
}
renvoyer le résultat ;
}
}
Code d'essai :
Copiez le code comme suit :
importer java.io.BufferedReader ;
importer java.io.FileInputStream ;
importer java.io.IOException ;
importer java.io.InputStream ;
importer java.io.InputStreamReader ;
importer java.util.ArrayList ;
importer java.util.Scanner ;
importer javax.xml.crypto.Data ;
classe publique Principale {
public static void main (String[] args) lève une exception {
ArrayList<String> mots = new ArrayList<String>();
BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Rabbit's Experimental Learning Center [En classe]/ACM Competition/ACM 4th School Competition/E Command Prompt/words3.dic")));
Chaîne s ;
numéro int = 0 ;
while((s=reader.readLine()) != null)
{
mots.ajouter(s);
num++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
pour(Mot de chaîne : mots)
{
dat.Insert(mot);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Scanner sc = nouveau scanner (System.in);
pendant que(sc.hasNext())
{
Mot de chaîne = sc.next();
System.out.println(dat.Exists(mot));
System.out.println(dat.FindAllWords(word));
}
}
}
Voici les résultats du test. Il faut environ 20 secondes pour construire un DAT de 6W mots anglais.
Lorsque j'agrandis le tableau, la longueur augmente jusqu'à 2 fois à chaque fois, initialement 1024
La longueur des tableaux Base et Check est de 131072
La longueur de la queue est de 262144
TTT1