El Trie tradicional es fácil de implementar, pero el espacio que ocupa es realmente inaceptable. Especialmente cuando el conjunto de caracteres no se limita a los 26 caracteres en inglés, el espacio ampliado es simplemente inaceptable.
Trie de matriz doble es un árbol Trie optimizado para el espacio. El principio no se discutirá en este artículo. Consulte Una implementación eficiente de estructuras Trie. Este programa también está escrito con referencia a este documento.
Con respecto a varios detalles no mencionados en el documento y las implementaciones inconsistentes con el documento:
1. Para insertar cadenas, si una cadena es una subcadena de otra cadena, también usaré el terminador como borde para generar un nuevo nodo. Estableceré la Base del nuevo nodo en 0.
Por lo tanto, hay dos situaciones al final de una cadena: una es que el valor Base es negativo y los caracteres restantes (tal vez solo un terminador) se almacenan en la matriz Tail; la otra es que la Base es 0;
Por lo tanto, debes considerar estas dos situaciones al realizar consultas.
2. Para el primer tipo de conflicto (Caso 3 en el artículo), puede que sea necesario sacar parte de la cuerda en Tail y ponerla en el índice como borde. El artículo utiliza el método de desplazar la cadena de cola hacia la izquierda. Mi método modifica directamente el valor Base en lugar de mover la cadena de cola.
El siguiente es el código implementado en Java, que puede manejar la inserción de la misma cadena, la inserción de subcadenas, etc.
Copie el código de código de la siguiente manera:
/*
* Nombre: Trie de doble matriz
* Autor: Yaguang Ding
* Correo: [email protected]
* Blog: blog.csdn.net/dingyaguang117
* Fecha: 21/5/2012
*Nota: los finales de una palabra pueden estar en cualquiera de estos dos casos:
* 1. Base[cur_p] == pos ( pos<0 y Tail[-pos] == 'END_CHAR' )
* 2. Verificar[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;
clase pública DoubleArrayTrie {
carácter final END_CHAR = '/0';
finalint DEFAULT_LEN = 1024;
int Base[] = nuevo int [DEFAULT_LEN];
int Comprobar[] = nuevo int [DEFAULT_LEN];
char Tail[] = nuevo carácter [DEFAULT_LEN];
intPos = 1;
Mapa<Carácter,Entero> CharMap = nuevo HashMap<Carácter,Entero>();
ArrayList<Carácter> CharList = new ArrayList<Carácter>();
pública 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));
}
}
vacío privado Extend_Array()
{
Base = Arrays.copyOf(Base, Base.longitud*2);
Verificar = Arrays.copyOf(Verificar, Verificar.longitud*2);
}
vacío privado Extend_Tail()
{
Cola = Arrays.copyOf(Cola, Cola.longitud*2);
}
privado int GetCharCode(char c)
{
si (!CharMap.containsKey(c))
{
CharMap.put(c,CharMap.size()+1);
CharList.add(c);
}
devolver CharMap.get(c);
}
privado int CopyToTailArray (cadena s, int p)
{
int _Pos = Pos;
mientras (s.longitud()-p+1 > Cola.longitud-Pos)
{
Extender_Cola();
}
para(int i=p; i<s.length();++i)
{
Cola[_Pos] = s.charAt(i);
_Pos++;
}
devolver _Pos;
}
privado int x_check(Entero []conjunto)
{
para(int i=1; ; ++i)
{
bandera booleana = verdadero;
para(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 || Comprobar[cur_p]!= 0)
{
bandera = falso;
romper;
}
}
si (bandera) devuelve i;
}
}
privado ArrayList<Integer> GetChildList(int p)
{
ArrayList<Integer> ret = new ArrayList<Integer>();
para(int i=1; i<=CharMap.size();++i)
{
if(Base[p]+i >= Check.length) descanso;
si(Comprobar[Base[p]+i] == p)
{
ret.add(i);
}
}
volver atrás;
}
TailContainString booleano privado (int start,String s2)
{
para(int i=0;i<s2.length();++i)
{
if(s2.charAt(i)! = Tail[i+start]) devuelve falso;
}
devolver verdadero;
}
TailMatchString booleano privado (int start,String s2)
{
s2 +=END_CHAR;
para(int i=0;i<s2.length();++i)
{
if(s2.charAt(i)! = Tail[i+start]) devuelve falso;
}
devolver verdadero;
}
Public void Insert (String s) lanza una excepción
{
s+=END_CHAR;
intpre_p = 1;
intcur_p;
para(int i=0; i<s.length(); ++i)
{
//Obtener ubicación de estado
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
//Si la longitud excede la longitud existente, expande la matriz
if (cur_p >= Base.length) Extend_Array();
//estado inactivo
si(Base[cur_p] == 0 && Comprobar[cur_p] == 0)
{
Base[cur_p] = -Pos;
Verificar[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
romper;
}demás
//estado existente
if(Base[cur_p] > 0 && Comprobar[cur_p] == pre_p)
{
pre_p = cur_p;
continuar;
}demás
// Conflicto 1: cuando Base[cur_p] es menor que 0, encuentra una cadena que está comprimida y almacenada en Tail.
si(Base[cur_p] < 0 && Comprobar[cur_p] == pre_p)
{
int cabeza = -Base[cur_p];
if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)//Insertar cadena repetida
{
romper;
}
//En el caso de letras comunes, debido a que la última sentencia ha excluido al terminador, ambas no deben ser terminadores.
if (Cola[cabeza] == s.charAt(i+1))
{
int disponible_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});
Base[cur_p] = disponibilidad_base;
Verificar[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
Base[avail_base+GetCharCode(s.charAt(i+1))] = -(cabeza+1);
pre_p = cur_p;
continuar;
}
demás
{
//Si las dos letras no son iguales, una de ellas puede ser el terminador.
int disponibilidad_base;
disponible_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});
Base[cur_p] = disponibilidad_base;
Check[avail_base+GetCharCode(Tail[head])] = cur_p;
Verificar[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;
//La cola es END_FLAG
if(Cola[cabeza] == END_CHAR)
Base[avail_base+GetCharCode(Cola[cabeza])] = 0;
demás
Base[avail_base+GetCharCode(Cola[cabeza])] = -(cabeza+1);
si(s.charAt(i+1) == END_CHAR)
Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;
demás
Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;
Pos = CopyToTailArray(s,i+2);
romper;
}
}demás
// Conflicto 2: El nodo actual ya está ocupado y es necesario ajustar la base previa.
si(Compruebe[cur_p] != pre_p)
{
ArrayList<Integer> lista1 = GetChildList(pre_p);
int toBeAdjust;
ArrayList<Integer> lista = nulo;
si (verdadero)
{
toBeAdjust = pre_p;
lista = lista1;
}
int origen_base = Base[toBeAdjust];
list.add(GetCharCode(s.charAt(i)));
int disponible_base = x_check((Integer[])list.toArray(new Integer[list.size()]));
lista.remove(lista.tamaño()-1);
Base[toBeAdjust] = disponibilidad_base;
para(int j=0; j<lista.tamaño(); ++j)
{
//BICHO
int tmp1 = origen_base + lista.get(j);
int tmp2 = disponibilidad_base + lista.get(j);
Base[tmp2] = Base[tmp1];
Verificar[tmp2] = Verificar[tmp1];
//Hay un seguimiento
si(Base[tmp1] > 0)
{
ArrayList<Integer> subsecuencia = GetChildList(tmp1);
for(int k=0; k<subsequence.size(); ++k)
{
Verificar[Base[tmp1]+subsequence.get(k)] = tmp2;
}
}
Base[tmp1] = 0;
Verificar[tmp1] = 0;
}
//Actualizar nuevo cur_p
cur_p = Base[pre_p]+GetCharCode(s.charAt(i));
si(s.charAt(i) == END_CHAR)
Base[cur_p] = 0;
demás
Base[cur_p] = -Pos;
Verificar[cur_p] = pre_p;
Pos = CopyToTailArray(s,i+1);
romper;
}
}
}
booleano público existe (palabra de cadena)
{
intpre_p = 1;
intcur_p = 0;
para(int i=0;i<palabra.longitud();++i)
{
cur_p = Base[pre_p]+GetCharCode(palabra.charAt(i));
if(Check[cur_p]!= pre_p) devuelve falso;
si(Base[cur_p] < 0)
{
if(TailMatchString(-Base[cur_p],word.substring(i+1)))
devolver verdadero;
devolver falso;
}
pre_p = cur_p;
}
if(Comprobar[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)
devolver verdadero;
devolver falso;
}
//Función interna, devuelve el último índice base de la palabra coincidente,
claseBuscarEstructura
{
intp;
Prefijo de cadena="";
}
FindStruct privado Buscar (palabra de cadena)
{
intpre_p = 1;
intcur_p = 0;
FindStruct fs = nuevo FindStruct();
para(int i=0;i<palabra.longitud();++i)
{
// BICHO
fs.prefix += palabra.charAt(i);
cur_p = Base[pre_p]+GetCharCode(palabra.charAt(i));
si(Compruebe[cur_p] != pre_p)
{
fs.p = -1;
devolver fs;
}
si(Base[cur_p] < 0)
{
if(TailContainString(-Base[cur_p],word.substring(i+1)))
{
fs.p = cur_p;
devolver fs;
}
fs.p = -1;
devolver fs;
}
pre_p = cur_p;
}
fs.p = cur_p;
devolver fs;
}
pública ArrayList<String> GetAllChildWord(índice int)
{
ArrayList<String> resultado = nuevo ArrayList<String>();
si(Base[índice] == 0)
{
resultado.add("");
resultado de devolución;
}
si(Base[índice] < 0)
{
Cadena r="";
for(int i=-Base[index];Cola[i]!=END_CHAR;++i)
{
r+= Cola[i];
}
resultado.add(r);
resultado de devolución;
}
para(int i=1;i<=CharMap.size();++i)
{
if(Comprobar[Base[índice]+i] == índice)
{
for(String s:GetAllChildWord(Base[índice]+i))
{
resultado.add(CharList.get(i)+s);
}
//resultado.addAll(GetAllChildWord(Base[index]+i));
}
}
resultado de devolución;
}
pública ArrayList<String> FindAllWords(palabra de cadena)
{
ArrayList<String> resultado = nuevo ArrayList<String>();
Prefijo de cadena = "";
FindStruct fs = Buscar(palabra);
int p = fs.p;
si (p == -1) devuelve resultado;
si(Base[p]<0)
{
Cadena r="";
for(int i=-Base[p];Cola[i]!=END_CHAR;++i)
{
r+= Cola[i];
}
resultado.add(fs.prefix+r);
resultado de devolución;
}
si(Base[p] > 0)
{
ArrayList<String> r = GetAllChildWord(p);
para(int i=0;i<r.size();++i)
{
r.set(i, fs.prefix+r.get(i));
}
devolver r;
}
resultado de devolución;
}
}
Código de prueba:
Copie el código de código de la siguiente manera:
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;
clase pública principal {
public static void main (String [] args) lanza una excepción {
ArrayList<String> palabras = nueva ArrayList<String>();
Lector BufferedReader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/Centro de aprendizaje experimental de Rabbit [en clase]/Concurso ACM/Concurso de la cuarta escuela de ACM/Símbolo del sistema E/words3.dic")));
Cadena s;
número int = 0;
mientras((s=reader.readLine()) != nulo)
{
palabras.añadir(es);
número++;
}
DoubleArrayTrie dat = nuevo DoubleArrayTrie();
para (palabra de cadena: palabras)
{
dat.Insert(palabra);
}
System.out.println(dat.Base.length);
System.out.println(dat.Tail.length);
Escáner sc = nuevo escáner (System.in);
mientras(sc.hasNext())
{
Palabra de cadena = sc.next();
System.out.println(dat.Exists(palabra));
System.out.println(dat.FindAllWords(palabra));
}
}
}
Los siguientes son los resultados de la prueba. Se necesitan unos 20 segundos para construir un DAT de 6W palabras en inglés.
Cuando hago crecer la matriz, la longitud aumenta a 2 veces cada vez, inicialmente 1024
La longitud de las matrices Base y Check es 131072
La longitud de la cola es 262144.
TTT1