java - sobre - Forma de almacenar un diccionario grande con poca huella de memoria+búsquedas rápidas(en Android)
neuropsicologia de la memoria pdf (7)
Estoy desarrollando una aplicación de juego de palabras para Android que necesita un diccionario grande (~ 250,000 palabras) disponible. Necesito:
- búsquedas razonablemente rápidas, por ejemplo, tiempo constante preferible, necesita hacer quizás 200 búsquedas por segundo en ocasiones para resolver un rompecabezas de palabras y quizás 20 búsquedas en 0.2 segundos más a menudo para verificar las palabras que el usuario acaba de escribir.
EDITAR: las búsquedas suelen preguntar "¿Está en el diccionario?". Me gustaría apoyar hasta dos comodines en la palabra también, pero esto es bastante fácil simplemente generando todas las letras posibles que podrían haber sido los comodines y comprobando las palabras generadas (es decir, 26 * 26 búsquedas para una palabra con dos comodines) .
- como es una aplicación móvil, usar la menor cantidad de memoria posible y requerir solo una pequeña descarga inicial para los datos del diccionario es la máxima prioridad.
Mis primeros intentos ingenuos usaron la clase HashMap de Java, que causó una excepción de falta de memoria. He analizado el uso de las bases de datos SQL lite disponibles en Android, pero esto parece excesivo.
¿Cuál es una buena manera de hacer lo que necesito?
Los dispositivos que trabajé básicamente funcionaban desde un archivo comprimido binario, con una topología que se parecía a la estructura de un árbol binario. En las hojas, tendrías el texto comprimido de Huffmann. Encontrar un nodo implicaría tener que saltar a varias ubicaciones del archivo, y luego solo cargar la parte de los datos realmente necesarios.
Querrás algún tipo de trie . Quizás un trie ternario de búsqueda sería bueno, creo. Dan una búsqueda muy rápida y un uso de memoria bajo. Este documento brinda más información sobre TST. También habla sobre la clasificación, por lo que no todo se aplicará. Este artículo podría ser un poco más aplicable. Como dice el artículo, TSTs
combine la eficiencia del tiempo de los intentos digitales con la eficiencia del espacio de los árboles de búsqueda binarios.
Como muestra this tabla, los tiempos de búsqueda son muy similares a usar una tabla hash.
Supongo que quiere verificar si la palabra dada pertenece al diccionario.
Eche un vistazo al filtro de floración .
El filtro de bloom puede hacer consultas tipo "¿pertenece X a un conjunto predefinido?" Con requisitos de almacenamiento muy pequeños. Si la respuesta a la consulta es sí, tiene una probabilidad pequeña (y ajustable) de ser incorrecta, si la respuesta a la pregunta es no, entonces la respuesta garantiza que es correcta.
Según el artículo de Wikipedia, podría necesitar menos de 4 MB de espacio para su diccionario de 250 000 palabras con un 1% de probabilidad de error.
El filtro de floración responderá correctamente "está en el diccionario" si la palabra realmente está contenida en el diccionario. Si el diccionario no tiene la palabra, el filtro de floración puede dar falsamente la respuesta "está en el diccionario" con una pequeña probabilidad.
También puede usar el Android NDK y hacer la estructura en C o C ++.
Una forma muy eficiente de almacenar un directorio es un Gráfico de palabras acíclica dirigido (DAWG).
Aquí hay algunos enlaces:
Una idea muy genial, como lo sugiere "Antti Huima", tratando de almacenar palabras del diccionario usando long . y luego buscar utilizando búsqueda binaria.
Usted puede lograr sus objetivos con enfoques más humildes también ... si se trata de un juego de palabras, entonces sospecho que está manejando 27 letras del alfabeto. Así que supongamos un alfabeto de no más de 32 letras, es decir, 5 bits por letra. Puede meter 12 letras (12 x 5 = 60 bits) en una única longitud de Java utilizando 5 bits / letra de codificación trivial.
Esto significa que, en realidad, si no tiene palabras más largas que 12 letras / palabras, puede representar su diccionario como un conjunto de longitudes Java. Si tiene 250,000 palabras, una presentación trivial de este conjunto como una matriz única ordenada de largos debe tomar 250,000 palabras x 8 bytes / palabra = 2,000,000 ~ 2MB de memoria. La búsqueda se realiza mediante búsqueda binaria, que debe ser muy rápida dado el pequeño tamaño del conjunto de datos (menos de 20 comparaciones, ya que 2 ^ 20 lo lleva a más de un millón).
SI tiene palabras más largas que 12 letras, entonces almacenaría las palabras> 12 letras en otra matriz donde 1 palabra estaría representada por 2 longitudes Java concatenadas de una manera obvia.
NOTA: la razón por la cual esto funciona y es probablemente más eficiente en términos de espacio que un trie y al menos muy fácil de implementar es que el diccionario es constante ... los árboles de búsqueda son buenos si necesita modificar el conjunto de datos, pero si los datos son el conjunto es constante, a menudo puede ejecutar un camino con simple búsqueda binaria.