Estructura de datos de espacio eficiente para almacenar una lista de palabras?

Question

¿Hay algo mejor que un Trie para esta situación?

• Almacenamiento de una lista de palabras en inglés 100k ~
• necesita usar un mínimo de memoria
• búsquedas deben ser razonables, pero no tiene que ser la velocidad del rayo

estoy trabajando con Java, así que mi primer intento fue simplemente usar un Set <String>. Sin embargo, estoy apuntando a un dispositivo móvil y ya tengo poca memoria. Dado que muchas palabras en inglés comparten prefijos comunes, un trie parece una apuesta decente para salvar algo de memoria. ¿Alguien conoce otras buenas opciones?

EDITAR - Más información - La estructura de datos se utiliza para dos operaciones

• de respuesta: ¿Es alguna palabra XYZ en la lista?
• Generando el barrio de palabras en torno a XYZ con una letra diferente

Gracias por las buenas sugerencias

Answer 1

¿Qué estás haciendo? Si se trata de un corrector ortográfico, podría usar un filtro de florecimiento; consulte esto code kata.

Answer 2

usted todavía tiene que mantener la estructura de árbol en sí con Trie. Huffman encoding el alfabeto o las letras N (para formas comunes como "tion", "un", "ing") pueden aprovechar la frecuencia de ocurrencia en su diccionario y comprimir la entrada en bits.

Answer 3

Una estructura vi para minimizar el espacio en un diccionario ortográfico era para codificar cada palabra como:

• el número de caracteres (un byte) en común con el último; y
• la nueva terminación.

Así que la lista de palabras

HERE   would encode as THIS 
sanctimonious      0,sanctimonious 
sanction       6,on 
sanguine       3,guine 
trivial       0,trivial 

Usted está ahorrando 7 bytes recta hasta allí (19%), sospecho que el ahorro sería similar a un diccionario de 20.000 palabras simplemente debido a las distancias mínimas entre (prefijos comunes de) palabras adyacentes.

Para acelerar la búsqueda, había una tabla de 26 entradas en la memoria que contenía los desplazamientos iniciales de las palabras que comenzaban con a, b, c, ..., z. Las palabras en estos desplazamientos siempre tenían 0 como primer byte, ya que no tenían letras en común con la palabra anterior.

Esto parece ser una especie de trie, pero sin los punteros, que seguramente costarían mucho espacio si todos los personajes del árbol tuvieran un puntero de 4 bytes asociado.

Ten en cuenta que esto era de mis días de CP/M donde la memoria era mucho más escasa de lo que es ahora.

Answer 4

A Patricia trie puede ser más apropiado:

http://en.wikipedia.org/wiki/Patricia_tree

Mi memoria (difusa) me dice que no fueron utilizados en algunos de los primeros motores de búsqueda de texto completo ...

Paul.

Answer 5

idea completamente salvaje ... (es decir, muy probablemente muy mal)

¿Qué hay de almacenamiento de las palabras como un árbol de todas las posibles combinaciones de letras?

Luego, cada "palabra" solo cuesta un solo carácter y dos apuntadores (uno para el carácter y otro para un terminador). De esta forma, cuantas más letras tengan en común, menor será el costo de cada palabra.

 . . 
    // 
    r-p-s-. 
    /\\ 
    a \s-. 
/ t-. 
c  \ 
     s-. 

coche carpa carpas coches carrito carros

Así por 9 caracteres y 14 punteros obtenemos 6 "palabras" por un total de 25 cartas.

Las búsquedas serían rápidas (búsquedas de punteros en lugar de comparaciones de carbonilla) y podría hacer algunas optimizaciones de tallos para ahorrar aún más espacio ...?

EDITAR: Parece que reinventé la rueda. ;-)

Answer 6

relativa a los puestos de Pablo:

Cualquier razón por la cual no se puede considerar un Trie en su caso? Si es sólo una cuestión implementaiton, aquí es una aplicación estricta de Patricia inserción y búsqueda trie en C (de NIST):

Patricia Insert in C

Patricia Search in C