O Trie tradicional é simples de implementar, mas o espaço que ocupa é realmente inaceitável. Especialmente quando o conjunto de caracteres não está limitado aos 26 caracteres ingleses, o espaço explodido é simplesmente inaceitável.
Double array Trie é uma árvore Trie com otimização de espaço. O princípio não será discutido neste artigo.
Em relação a vários detalhes não mencionados no artigo e implementações inconsistentes com o artigo:
1. Para inserir strings, se uma string for uma substring de outra string, também usarei o terminador como borda para gerar um novo nó. Definirei a Base do novo nó como 0.
Portanto, existem duas situações no final de uma string: uma é que o valor Base é negativo e os caracteres restantes (talvez apenas um terminador) são armazenados no array Tail a outra é que a Base é 0.
Portanto, você deve considerar essas duas situações ao fazer perguntas.
2. Para o primeiro tipo de conflito (Caso 3 do artigo), pode ser necessário retirar parte da string em Tail e colocá-la no índice como uma aresta. O artigo usa o método de deslocar a sequência final para a esquerda. Meu método modifica diretamente o valor Base em vez de mover a sequência final.
A seguir está o código implementado em java, que pode lidar com a inserção da mesma string, a inserção de substrings, etc.
Copie o código do código da seguinte forma:
/*
* Nome: Trie de Matriz Dupla
* Autor: Yaguang Ding
* Correio: [email protected]
* Blog: blog.csdn.net/dingyaguang117
* Data: 21/05/2012
* Nota: o final de uma palavra pode ser um destes dois casos:
* 1. Base[cur_p] == pos ( pos<0 e Tail[-pos] == 'END_CHAR' )
* 2. Verifique[Base[cur_p] + Código('END_CHAR')] == cur_p
*/
importar java.util.ArrayList;
importar java.util.HashMap;
importar java.util.Map;
importar java.util.Arrays;
classe pública DoubleArrayTrie {
caractere final END_CHAR = '/0';
final int DEFAULT_LEN = 1024;
int Base[] = novo int [DEFAULT_LEN];
verificação int[] = novo int [DEFAULT_LEN];
char Tail[] = novo caractere [DEFAULT_LEN];
intPos = 1;
Map<Caracter,Integer> CharMap = new HashMap<Caracter,Integer>();
ArrayList<Caracter> CharList = new ArrayList<Caracter>();
public DoubleArrayTrie()
{
Base[1] = 1;
CharMap.put(END_CHAR,1);
CharList.add(END_CHAR);
CharList.add(END_CHAR);
para(int i=0;i<26;++i)
{
CharMap.put((char)('a'+i),CharMap.size()+1);
CharList.add((char)('a'+i));
}
}
vazio privado Extend_Array()
{
Base = Arrays.copyOf(Base, Base.length*2);
Verificar = Arrays.copyOf(Verificar, Verificar.comprimento*2);
}
vazio privado Extend_Tail()
{
Cauda = Arrays.copyOf(Cauda, Cauda.comprimento*2);
}
privado int GetCharCode(char c)
{
if (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
retornar CharMap.get(c);
}
privado int CopyToTailArray(String s,int p)
{
int _Pos = Pos;
while(s.length()-p+1 > Tail.length-Pos)
{
Estender_Tail();
}
for(int i=p; i<s.comprimento();++i)
{
Cauda[_Pos] = s.charAt(i);
_Pos++;
}
retornar _Pos;
}
private int x_check(número inteiro []conjunto)
{
para(int i=1; ; ++i)
{
sinalizador booleano = verdadeiro;
for(int j=0;j<set.length;++j)
{
int cur_p = i+conjunto[j];
if(cur_p>= Base.length) Extend_Array();
if(Base[cur_p]!= 0 || Verificar[cur_p]!= 0)
{
bandeira = falso;
quebrar;
}
}
if (sinalizador) retornar 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(Verificar[Base[p]+i] == p)
{
ret.add(i);
}
}
retorno ret;
}
privado booleano TailContainString(int início,String s2)
{
for(int i=0;i<s2.comprimento();++i)
{
if(s2.charAt(i) != Tail[i+start]) retorna falso;
}
retornar verdadeiro;
}
private boolean TailMatchString(int início,String s2)
{
s2 += END_CHAR;
for(int i=0;i<s2.comprimento();++i)
{
if(s2.charAt(i) != Tail[i+start]) retorna falso;
}
retornar verdadeiro;
}
public void Insert(String s) lança exceção
{
s += END_CHAR;
int pré_p = 1;
int cur_p;
for(int i=0; i<s.comprimento(); ++i)
{
//Obter localização do status
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//Se o comprimento exceder o comprimento existente, expanda o array
if (cur_p >= Base.length) Extend_Array();
//estado inativo
if(Base[cur_p] == 0 && Verificação[cur_p] == 0)
{
Base[cur_p] = -Pos;
Verifique[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
quebrar;
}outro
//status existente
if(Base[cur_p] > 0 && Verificação[cur_p] == pre_p)
{
pré_p = cur_p;
continuar;
}outro
//Conflito 1: Quando Base[cur_p] é menor que 0, ele encontra uma string que é compactada e armazenada em Tail.
if(Base[cur_p] < 0 && Verificação[cur_p] == pre_p)
{
int head = -Base[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)//Inserir string repetida
{
quebrar;
}
//No caso de cartas comuns, porque o último julgamento excluiu o terminador, então ambos devem ser não terminadores.
if (Cauda[cabeça] == s.charAt(i+1))
{
int disponibilidade_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});
Base[cur_p] = disponibilidade_base;
Verifique[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
Base[avail_base+GetCharCode(s.charAt(i+1))] = -(head+1);
pré_p = cur_p;
continuar;
}
outro
{
//Se as duas letras não forem iguais, uma delas pode ser o terminador.
int disponibilidade_base;
disponibilidade_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
Base[cur_p] = disponibilidade_base;
Verifique[avail_base+GetCharCode(Tail[head])] = cur_p;
Verifique[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//A cauda é END_FLAG
if(Cauda[cabeça] == END_CHAR)
Base[avail_base+GetCharCode(Tail[head])] = 0;
outro
Base[avail_base+GetCharCode(Tail[head])] = -(head+1);
if(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
outro
Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
quebrar;
}
}outro
//Conflito 2: O nó atual já está ocupado e a pré-base precisa ser ajustada.
if(Verificar[cur_p]!= pre_p)
{
ArrayList<Integer> list1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> lista = null;
se (verdadeiro)
{
toBeAdjust = pre_p;
lista = lista1;
}
int origem_base = Base[toBeAdjust];
list.add(GetCharCode(s.charAt(i)));
int disponibilidade_base = x_check((Integer[])list.toArray(new Integer[list.size()]));
lista.remove(lista.tamanho()-1);
Base[toBeAdjust] = disponibilidade_base;
for(int j=0; j<lista.tamanho(); ++j)
{
//ERRO
int tmp1 = origem_base + list.get(j);
int tmp2 = disponibilidade_base + list.get(j);
Base[tmp2] = Base[tmp1];
Verificação[tmp2] = Verificação[tmp1];
//Há um acompanhamento
se(Base[tmp1] > 0)
{
ArrayList<Integer> subsequência = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Verifique[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Base[tmp1] = 0;
Verifique[tmp1] = 0;
}
//Atualiza o novo cur_p
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
if(s.charAt(i) == END_CHAR)
Base[cur_p] = 0;
outro
Base[cur_p] = -Pos;
Verifique[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
quebrar;
}
}
}
booleano público existe (palavra de string)
{
int pré_p = 1;
int cur_p = 0;
for(int i=0;i<palavra.comprimento();++i)
{
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Check[cur_p] != pre_p) retorna falso;
if(Base[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
retornar verdadeiro;
retornar falso;
}
pré_p = cur_p;
}
if(Verificar[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
retornar verdadeiro;
retornar falso;
}
//Função interna, retorna o último índice base da palavra correspondente,
classFindStruct
{
intp;
String prefix="";
}
privado FindStruct Find (palavra de string)
{
int pré_p = 1;
int cur_p = 0;
FindStruct fs = new FindStruct();
for(int i=0;i<palavra.comprimento();++i)
{
// ERRO
fs.prefix += palavra.charAt(i);
cur_p = Base[pre_p]+GetCharCode(word.charAt(i));
if(Verificar[cur_p]!=pre_p)
{
fs.p = -1;
retornar fs;
}
if(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
retornar fs;
}
fs.p = -1;
retornar fs;
}
pré_p = cur_p;
}
fs.p = cur_p;
retornar fs;
}
public ArrayList<String> GetAllChildWord(int índice)
{
ArrayList<String> resultado = new ArrayList<String>();
if(Base[índice] == 0)
{
resultado.add("");
resultado de retorno;
}
if(Base[índice] < 0)
{
String r="";
for(int i=-Base[index];Cauda[i]!=END_CHAR;++i)
{
r+= Cauda[i];
}
resultado.add(r);
resultado de retorno;
}
for(int i=1;i<=CharMap.size();++i)
{
if(Verificar[Base[índice]+i] == índice)
{
for(String s:GetAllChildWord(Base[índice]+i))
{
resultado.add(CharList.get(i)+s);
}
//resultado.addAll(GetAllChildWord(Base[índice]+i));
}
}
resultado de retorno;
}
public ArrayList<String> FindAllWords(String palavra)
{
ArrayList<String> resultado = new ArrayList<String>();
Prefixo de string = "";
FindStruct fs = Encontrar(palavra);
int p = fs.p;
if (p == -1) retornar resultado;
se(Base[p]<0)
{
String r="";
for(int i=-Base[p];Cauda[i]!=END_CHAR;++i)
{
r+= Cauda[i];
}
resultado.add(fs.prefix+r);
resultado de retorno;
}
se(Base[p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
for(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
retornar r;
}
resultado de retorno;
}
}
Código de teste:
Copie o código do código da seguinte forma:
importar java.io.BufferedReader;
importar java.io.FileInputStream;
importar java.io.IOException;
importar java.io.InputStream;
importar java.io.InputStreamReader;
importar java.util.ArrayList;
importar java.util.Scanner;
importar javax.xml.crypto.Data;
classe pública Principal {
public static void main(String[] args) lança exceção {
ArrayList<String> palavras = new ArrayList<String>();
Leitor BufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Centro de Aprendizagem Experimental do Coelho [em sala de aula]/Competição ACM/Competição ACM 4ª Escola/Prompt de Comando E/words3.dic")));
Sequências;
int num = 0;
while((s=leitor.readLine()) != null)
{
palavras.add(s);
num++;
}
DoubleArrayTrie dat = new DoubleArrayTrie();
para (palavra da string: palavras)
{
dat.Inserir(palavra);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Scanner sc = novo Scanner(System.in);
enquanto(sc.hasNext())
{
String palavra = sc.next();
System.out.println(dat.Exists(palavra));
System.out.println(dat.FindAllWords(palavra));
}
}
}
A seguir estão os resultados do teste. Demora cerca de 20 segundos para construir um DAT de 6W palavras em inglês.
Quando eu aumento a matriz, o comprimento aumenta para 2 vezes a cada vez, inicialmente 1024
O comprimento das matrizes Base e Check é 131072
O comprimento da cauda é 262144
TTT1