Tengo una enorme lista de secuencias de varios bytes (vamos a llamarlas palabras) que necesito almacenar en un archivo y que necesito poder buscar rápidamente. Enorme significa: alrededor de 2 millones de esos, cada 10-20 bytes de longitud.Compresión y búsqueda de la enorme lista de palabras
Además, cada palabra tendrá una etiqueta valor asociado con ella, de modo que pueda utilizar eso para hacer referencia a más de datos (externa) de cada elemento (por lo tanto, el diccionario de un corrector ortográfico no funciona aquí como que sólo proporciona una hit-test).
Si esto fuera solo memoria, y si hubiera suficiente memoria, podría simplemente almacenar todas las palabras en un mapa hash (también conocido como diccionario, también conocido como pares clave-valor) o en una lista ordenada para una búsqueda binaria.
Sin embargo, me gustaría comprimir los datos altamente, y también preferiría no tener que leer los datos en la memoria, sino buscar dentro del archivo.
Como las palabras se basan principalmente en el idioma inglés, hay una cierta probabilidad de que ciertos "sillables" en las palabras aparezcan con mayor frecuencia que otros, lo que probablemente sea útil para un algoritmo eficiente.
¿Alguien me puede indicar una técnica o algoritmo eficiente para esto?
¿O incluso ejemplos de código?
actualización
Calculo que DAWG ni nada rutas similares en el camino sufijos comunes de esta manera no va a funcionar para mí, porque entonces no voy a ser capaz de etiquetar cada ruta completa palabra con un individuo valor. Si tuviera que detectar los sufijos comunes, tendría que ponerlos en su propio diccionario (tabla de búsqueda) para que un nodo trie pueda hacer referencia a ellos, pero el nodo mantendría su propio nodo final para almacenar el valor de la etiqueta de esa ruta.
De hecho, eso es probablemente el camino a seguir:
En lugar de construir los nodos del árbol de sólo caracteres individuales, que podrían tratar de encontrar secuencias de caracteres de uso frecuente, y hacer un nodo de esos también. De esta forma, los nodos individuales pueden cubrir múltiples caracteres, lo que puede conducir a una mejor compresión.
Ahora, si eso es viable, ¿cómo podría encontrar secuencias a menudo usadas en todas mis frases? Con aproximadamente 2 millones de frases que constan de 1 a 3 palabras, será difícil ejecutar todas las permutaciones de todas las subcadenas posibles ...
20 bytes * 2 millones = 40Mb. Eso es minúsculo en comparación con la cantidad típica de memoria en una computadora. Si los almacena en una matriz ordenada, usará la búsqueda binaria para buscar, y apenas necesitará memoria adicional. – jkff
Sí, 40mb no es mucho. Y si le preocupa la velocidad, mantenga los datos en la memoria lo más simple posible. – ruslik
Como se indica a continuación, los 40 MB deben venir con la aplicación, y me gusta mantener el tamaño de descarga de la aplicación mucho más pequeño. Además, esa no es la única partición. Hay una porción más grande de otro conjunto de "palabras", que no necesita ser buscable pero aún compresible porque equivaldrá a alrededor de 1GB en cadenas sin formato. Una vez que encontré un algo adecuado para lo anterior, espero usarlo también en este otro conjunto más grande. –