Búsqueda rápida en archivos de texto comprimido

Question

Necesito poder buscar texto en una gran cantidad de archivos (.txt) que están comprimidos. La compresión puede cambiarse a otra cosa o incluso convertirse en propiedad. Quiero evitar desempaquetar todos los archivos y comprimir (codificar) la cadena de búsqueda y buscar en archivos comprimidos. Esto debería ser posible usando la compresión de Huffman con el mismo libro de códigos para todos los archivos. No quiero reinventar la rueda, entonces ... ¿alguien conoce una biblioteca que hace algo como esto o el algoritmo de Huffman que se implementa y prueba, o tal vez una idea mejor?

gracias de antemano

Answer 1

La mayoría de los archivos de texto se comprimen con uno de los algoritmos LZ-family, que combinan un Dictionary Coder junto con un Entropy Coder como Huffman.

Como el diccionario Coder se basa en un "diccionario" continuamente actualizado, su resultado de codificación depende del historial (todos los códigos en el diccionario se derivan de los datos de entrada hasta el símbolo actual), por lo que no es Es posible saltar a una ubicación determinada y comenzar a decodificar, sin descodificar primero todos los datos anteriores.

En mi opinión, puede usar un decodificador de flujo zlib que devuelve los datos descomprimidos sin esperar a que se descomprima todo el archivo. Esto no ahorrará tiempo de ejecución pero ahorrará memoria.

Una segunda sugerencia es hacer la codificación de Huffman en palabras en inglés, y olvidarte de la parte del codificador del diccionario. Cada palabra en inglés se asigna a un código único sin prefijo.

Finalmente, @SHODAN dio la sugerencia más sensata, que es indexar los archivos, comprimir el índice y agruparlos con los archivos de texto comprimido. Para hacer una búsqueda, descomprima solo el archivo de índice y busque las palabras. Esto es, de hecho, una mejora con respecto a la codificación de palabras de Huffman: una vez que encontraste la frecuencia de las palabras (para asignar el código de prefijo de manera óptima), ya has creado el índice, para que puedas mantener el índice de búsqueda.

Answer 2

que pueden estar completamente equivocado aquí, pero no creo que habría una manera confiable para buscar una cadena dada sin decodificar los archivos. Mi comprensión de los algoritmos de compresiones es que el flujo de bits correspondiente a una cadena dada dependería en gran medida de lo que viene antes de la cadena en el archivo descomprimido. Es posible que pueda encontrar una codificación dada para una cadena en particular en un archivo determinado, pero estoy bastante seguro de que no será consistente entre los archivos.

Answer 3

Es poco probable que pueda buscar cadenas sin comprimir en un archivo comprimido. Creo que una de sus mejores opciones es indexar los archivos de alguna manera. ¿Usando Lucene tal vez?

Answer 4

Buscar texto en archivos comprimidos puede ser más rápido que buscar lo mismo en archivos de texto sin comprimir.

Una técnica de compresión que he visto que sacrifica algo de espacio con el fin de hacer búsquedas rápidas:

• mantener un diccionario con 2^16 entradas de cada palabra en el texto. Reserve las primeras 256 entradas para bytes literales, en caso de que encuentre una palabra que no esté en el diccionario, incluso si muchos textos grandes tienen menos de 32,000 palabras únicas, por lo que nunca necesitan usar esos bytes literales.
• Comprima el texto original sustituyendo el índice del diccionario de 16 bits para cada palabra.
• (opcional) En el caso normal de que dos palabras estén separadas por un solo carácter de espacio, descarte ese carácter de espacio; de lo contrario, ponga todos los bytes en la cadena entre palabras en el diccionario como una "palabra" especial (por ejemplo, "." y "," y "\ n") etiquetados con el atributo "sin espacios predeterminados", y luego "comprima" "esas cadenas reemplazándolas con el índice del diccionario correspondiente.
• Busque palabras o frases comprimiendo la frase de la misma manera y buscando la cadena comprimida de bytes en el texto comprimido exactamente de la misma manera que buscaría la cadena original en el texto original.

En particular, la búsqueda de una sola palabra por lo general se reduce a comparar el índice de 16 bits en el texto comprimido, que es más rápida que la búsqueda de esa palabra en el texto original, porque

• cada comparación requiere comparar menos bytes - 2, en lugar de cuantos bytes hay en esa palabra, y
• estamos haciendo menos comparaciones, porque el archivo comprimido es más corto.

Algunos tipos de expresiones regulares se pueden traducir a otras expresiones regulares que encuentren directamente elementos en el archivo comprimido (y quizás también encuentre algunos falsos positivos). Dicha búsqueda también hace menos comparaciones que usar la expresión regular original en el archivo de texto original, porque el archivo comprimido es más corto, pero normalmente cada comparación de expresión regular requiere más trabajo, por lo que puede o no ser más rápido que la expresión original en el texto original.

(En principio, podría reemplazar los códigos de 16 bits de longitud fija con códigos de prefijo Huffman de longitud variable, como se menciona rwong - el archivo comprimido resultante sería más pequeño, pero el software para manejar esos archivos sería un un poco más lento y más complicado).

Para las técnicas más sofisticadas, lo podría hacer en

• MG4J: Managing Gigabytes for Java
• "Managing Gigabytes: Compressing and Indexing Documents and Images" por Ian H. Witten, Alistair Moffat, y Timothy C. Bell

Answer 5

Esto es posible, y puede hacerse de manera bastante eficiente. Hay muchas investigaciones interesantes sobre este tema, más formalmente conocidas como una estructura de datos sucinta. Algunos temas que recomendaría investigar: Wavelet tree, FM-index/RRR, arreglos de sufijos sucintos. También puede buscar eficientemente cadenas codificadas de Huffman, como lo han demostrado varias publicaciones.