Me preguntaron en una entrevista cómo diseñaría el Oxford English Dictionary.Diseñando el Oxford English Dictionary
Le dije que utilizaría una estructura de datos TREE, pero me contestó que me llevaría mucha memoria. Entonces, ¿qué otra estructura de datos debería usarse?
estructura Uno de datos oí fue utilizado en el pasado en los teléfonos móviles para almacenar diccionarios T9 es el siguiente (bueno, esto se refiere únicamente a la cuestión clave, pero no el almacenamiento de la definición):
entradas se ordenan, y cada entrada debe comenzar con una compensación en la entrada anterior desde donde debe continuarse, y también la continuación. Por ejemplo:
apple
4icable
7tion
Decodificaría a manzana, aplicable, la aplicación. Sin embargo esto podría no ser tan diferente de intentos con cadenas fusionadas, ver
appl -> e
-> ica -> ble
-> tion
Wikipedia destapó el Directed acyclic word graph, que se diferencia de los árboles que no sólo ramas, pero las ramas se fusionan, donde las palabras tienen el mismo sufijo. Esto de hecho podría ser un almacenamiento superior.
a
/\
pplic utom
\/
ation
Por cierto, wikipedia me acaba de decir que "si almacenar todo lo que se necesita es diccionario, un autómata determinista acíclico mínimo usaría menos espacio que un trie". Agregado a la respuesta. – ron
No usaría mucha memoria. Tu respuesta estuvo bien. Tal vez en 1995. Considérate afortunado.
Como han mencionado otros, si no hay suficiente techo de un trie bien diseñado, probablemente no hay espacio para cualquier otro tipo de índice, tampoco. Dado que se trata de una pregunta de entrevista, parece que intentaba orientarlo hacia las estructuras de datos clásicas fuera del núcleo, como B-trees.
Alternativamente, una buena respuesta podría haber sido solicitar más información, como "qué tipo de operaciones querrá hacer en esta estructura de datos, y qué tipo de desempeño necesita". Si solo quiere un corrector ortográfico, entonces un filtro Bloom podría ser la "estructura de datos" más eficiente ...
simplemente una tontería, pero Oxford English Dictionary no usa el mapa en lugar de otra palabra (s) el significado de la palabra en algunas oraciones/frases? En ese caso, la codificación de las palabras es el menor de sus problemas y debe pensar en representar las cosas de significado (palabras con gramática, etc.) o incluso considerar el empaquetamiento basado en el diccionario como LHARC. Por suerte para ti el inglés no es muy complejo de esta manera ... – Spektre