Join FlipAndroid.COM Telegram Group: https://t.me/joinchat/F_aqThGkhwcLzmI49vKAiw


Manera de almacenar un diccionario grande con poca huella de memoria + búsquedas rápidas (en Android)

Estoy desarrollando una aplicación de juego de palabras para Android que necesita un diccionario de palabras grande (~ 250.000 palabras) disponible. Necesito:

  • Razonablemente rápido busca por ejemplo tiempo constante preferible, necesidad de hacer quizás 200 búsquedas un segundo en la ocasión para resolver un rompecabezas de la palabra y quizás 20 búsquedas dentro de 0.2 segundo más a menudo para comprobar palabras que el usuario apenas deletreó.

EDIT: Las búsquedas normalmente están preguntando "¿Está en el diccionario?". Quisiera apoyar hasta dos comodines en la palabra también, pero esto es bastante fácil apenas generando todas las cartas posibles que los comodines podrían haber sido y comprobando las palabras generadas (es decir 26 * 26 búsquedas para una palabra con dos comodines) .

  • Android Mapview: Fusionar marcadores superpuestos en un nuevo marcador
  • Forma correcta de dar formato a la fecha con cadenas como hoy, ayer, mañana, etc
  • La mejor práctica para calcular la velocidad media de las coordenadas GPS
  • La similitud perceptual entre dos secuencias de audio
  • Cómo calcular el pie exacto paso de contar con acelerómetro en android?
  • Android Compass orientación en poco fiable (filtro de paso bajo)
    • Ya que es una aplicación para dispositivos móviles, usar la menor cantidad de memoria posible y requerir sólo una pequeña descarga inicial para los datos del diccionario es la máxima prioridad.

    Mis primeros intentos ingenuos utilizaron la clase HashMap de Java, que causó una excepción de memoria. He mirado en el uso de las bases de datos SQL lite disponibles en Android, pero esto parece como exceso.

    ¿Cuál es una buena manera de hacer lo que necesito?

  • Android: borra la pila trasera
  • Añadir IMEI y MAC a wlan0 a Genymotion / AndroVM
  • Cómo agregar acciones a la parte superior de una división ActionBar
  • Indeterminado ProgressBar no se muestra durante la operación AsyncTask
  • Cómo acceder al botón dentro de "incluir" el diseño
  • ¿Cuál es el beneficio de ViewHolder?
  • 7 Solutions collect form web for “Manera de almacenar un diccionario grande con poca huella de memoria + búsquedas rápidas (en Android)”

    Usted puede alcanzar sus metas con enfoques más humildes también … si es un juego de palabras entonces sospecho que está manejando 27 letras alfabeto. Así que suponga un alfabeto de no más de 32 letras, es decir, 5 bits por letra. Usted puede meter entonces 12 letras (12 x 5 = 60 bits) en un solo Java largo usando la codificación trivial de 5 bits / letra.

    Esto significa que en realidad si usted no tiene palabras más largas que 12 letras / palabra sólo puede representar su diccionario como un conjunto de largos de Java. Si usted tiene 250.000 palabras una presentación trivial de este conjunto como un único orden ordenado de largos debe tener 250.000 palabras x 8 bytes / palabra = 2.000.000 ~ 2MB de memoria. La búsqueda es entonces por búsqueda binaria, que debe ser muy rápida dada la pequeña dimensión del conjunto de datos (menos de 20 comparaciones como 2 ^ 20 te lleva a más de un millón).

    Si tienes palabras más largas que 12 letras, entonces guardaría las palabras de> 12 letras en otra matriz donde 1 palabra sería representada por 2 largos Java concatenados de una manera obvia.

    NOTA: la razón por la que esto funciona y es probablemente más eficiente en el espacio que un trie y al menos muy simple de implementar es que el diccionario es constante … los árboles de búsqueda son buenos si usted necesita modificar el conjunto de datos, pero si los datos Conjunto es constante, a menudo se puede ejecutar un camino con la búsqueda binaria simple.

    Estoy asumiendo que usted quiere comprobar si la palabra dada pertenece al diccionario.

    Eche un vistazo al filtro de floración .

    El filtro de bloom puede hacer "no X pertenece a un conjunto predefinido" tipo de consultas con requisitos de almacenamiento muy pequeños. Si la respuesta a la pregunta es sí, tiene probabilidad pequeña (y ajustable) de estar equivocada, si la respuesta a la pregunta es no, entonces la respuesta garantizada es correcta.

    Según el artículo de Wikipedia podría necesitar menos de 4 MB de espacio para el diccionario de 250 000 palabras con 1% de probabilidad de error.

    El filtro de bloom 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 alguna pequeña probabilidad.

    Una manera muy eficiente de almacenar un directorio es un Dirigido Acyclic Word Graph (DAWG).

    Aquí hay algunos enlaces:

    • Dirigido Acyclic Word Graph o DAWG descripción con sourcecode
    • Construcción del CDAWG para un Trie
    • Implementación de la gráfica acíclica dirigida

    Estarás buscando algún tipo de trie . Tal vez una búsqueda ternaria sería buena, creo. Proporcionan una búsqueda muy rápida y un bajo consumo de memoria. Este artículo da más información sobre las 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, los TSTs

    Combinan la eficacia del tiempo de intentos digitales con la eficiencia del espacio de los árboles binarios de la búsqueda.

    Como se muestra en esta tabla, los tiempos de búsqueda son muy comparables con el uso de una tabla hash.

    También puede utilizar el Android NDK y hacer la estructura en C o C ++.

    Los dispositivos que trabajé básicamente trabajaron a partir de un archivo binario comprimido, 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, a continuación, cargar sólo la parte de los datos realmente necesarios.

    Era idea fresca según lo sugerido por "Antti Huima" que intentaba almacenar palabras del diccionario usando de largo

    FlipAndroid es un fan de Google para Android, Todo sobre Android Phones, Android Wear, Android Dev y Aplicaciones para Android Aplicaciones.