trie o árbol de búsqueda binaria equilibrada para almacenar el diccionario?

Question

Tengo un requisito simple (quizás hipotético):

Quiero almacenar diccionario de palabras inglés (n palabras) y dado una palabra (longitud de caracteres m), el diccionario puede decir si la palabra existe en el diccionario o no. ¿Cuál sería una estructura de datos apropiada para esto?

¿un árbol de búsqueda binaria equilibrada? como se hace en las estructuras de datos STL asociativo C++, como conjunto, mapa

o

un trie en cadenas

Algunos análisis de complejidad: en un bst equilibrada, el tiempo sería (log n) * m (comparando 2 cadenas toma O (m) tiempo carácter por carácter)

en trie, si en cada nodo, podríamos ramificar en O (1) tiempo, podemos encontrar usando O (m), pero la suposición de que en cada nodo, podemos ramificar en O (1) el tiempo no es válido. en cada nodo, las ramas máximas posibles serían 26. si queremos O (1) en un nodo, mantendremos una matriz corta indexable en los caracteres de cada nodo. Esto hará explotar el espacio. Después de algunos niveles en el trie, la bifurcación se reducirá, por lo que es mejor mantener una lista vinculada de los siguientes caracteres e indicadores del nodo.

¿Qué aspecto más práctico? cualquier otra compensación?

Gracias,

Answer 1

Yo diría que use un Trie, o mejor aún use su primo más eficiente en el espacio, el Directed Acyclic Word Graph (DAWG).

Tiene las mismas características de tiempo de ejecución (insertar, buscar, eliminar) como un Trie, pero se superpone a los sufijos comunes, así como a los prefijos comunes que pueden suponer un gran ahorro de espacio.

Answer 2

La búsqueda binaria va a ser más fácil de implementar y que sólo va a incluir la comparación de decenas de cadenas a lo sumo. Dado que conoce los datos por adelantado, puede construir un árbol binario equilibrado para que el rendimiento sea predecible y fácil de entender.

Teniendo esto en cuenta, utilizaría un árbol binario estándar (probablemente usando set de C++ ya que normalmente se implementa como un árbol).

Answer 3

Una solución simple es almacenar el dict como palabras ordenadas y \ separadas en el disco, cargarlo en la memoria y realizar una búsqueda binaria. La única parte no estándar aquí es que debe escanear hacia atrás el comienzo de una palabra cuando realiza la búsqueda binaria.

Aquí hay un código! (Se asume globales wordlist apuntando a la dict cargado, y wordlist_end que apunta a justo después del final de la dict cargado.

// Return >0 if word > word at position p. 
// Return <0 if word < word at position p. 
// Return 0 if word == word at position p. 
static int cmp_word_at_index(size_t p, const char *word) { 
    while (p > 0 && wordlist[p - 1] != '\n') { 
    p--; 
    } 
    while (1) { 
    if (wordlist[p] == '\n') { 
     if (*word == '\0') return 0; 
     else return 1; 
    } 
    if (*word == '\0') { 
     return -1; 
    } 
    int char0 = toupper(*word); 
    int char1 = toupper(wordlist[p]); 
    if (char0 != char1) { 
     return (int)char0 - (int)char1; 
    } 
    ++p; 
    ++word; 
    } 
} 

// Test if a word is in the dictionary. 
int is_word(const char* word_to_find) { 
    size_t index_min = 0; 
    size_t index_max = wordlist_end - wordlist; 
    while (index_min < index_max - 1) { 
    size_t index = (index_min + index_max)/2; 
    int c = cmp_word_at_index(index, word_to_find); 
    if (c == 0) return 1; // Found word. 
    if (c < 0) { 
     index_max = index; 
    } else { 
     index_min = index; 
    } 
    } 
    return 0; 
} 

Una gran ventaja de este enfoque es que el dict se almacena en una forma legible por humanos en el disco, y que no necesita ningún código elegante para cargarlo (asignar un bloque de memoria y leer() de una sola vez).

Si desea utilizar un trie, puede usar un paquete y representación comprimida de sufijos. Aquí hay un enlace a uno de los estudiantes de Donald Knuth, Franklin Liang, que escribió sobre este truco en su tesis.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7018&rep=rep1&type=pdf

Se utiliza un medio de almacenamiento de la representación directa textual dict, le da la velocidad de un trie, y se puede (como la representación textual dict) almacenar todo el asunto en el disco y cargarlo en una ir.

El truco que utiliza es empaquetar todos los nodos en una sola matriz, intercalarlos siempre que sea posible. Además de un nuevo puntero (y un bit marcador de fin de palabra) en cada ubicación de matriz como en un trie común, almacenas la letra para la que está destinado este nodo, esto te permite saber si el nodo es válido para tu estado. o si es de un nodo superpuesto. Lea el documento vinculado para obtener una explicación más completa y clara, así como un algoritmo para empaquetar el trie en este conjunto.

No es trivial implementar el algoritmo de compresión de sufijos y codiciosos descrito, pero es bastante fácil.

Answer 4

Si esto es C++, también debería considerar std::tr1::unordered_set. (Si tiene C++ 0x, puede usar std::unordered_set.)

Esto solo usa una tabla hash internamente, que apostaría a que en la práctica superará cualquier estructura tipo árbol. También es trivial de implementar porque no tienes nada que implementar.

Answer 5

El estándar de la industria es almacenar el diccionario en una tabla hash y tener un tiempo amortizado O (1) de búsqueda. El espacio no es más crítico en la industria, especialmente debido al avance en la informática distributiva.

hashtable es la forma en que Google implementa su característica de autocompletar. Específicamente, tenga cada prefijo de una palabra como clave y coloque la palabra como el valor en la tabla hash.