almacenamiento de cadena comprimida

Question

Digamos que tengo muchos objetos que contienen cadenas de longitud no trivial (alrededor de ~ 3-4kb). Las cadenas son todas diferentes entre sí, pero al mismo tiempo contienen muchas partes/subsecuencias comunes. En promedio, quizás el 80-90% de una cuerda individual está contenida con las otras también. ¿Existe una manera fácil de explotar automáticamente esta gran redundancia para comprimir los datos?
Idealmente, la solución sería C++ y transparente para el usuario (es decir, puedo usarla como si estuviera accediendo a un estándar de lectura solo const std :: string pero en lugar de leer desde el almacenamiento comprimido).

Answer 1

Algorítmicamente, Lempel–Ziv–Welch con un diccionario para todos los objetos/cadenas podría ser un buen comienzo.

Answer 2

Si las partes comunes de las cadenas son comunes porque están compuestas de otras cadenas, entonces puede obtener algo de tracción usando la clase stlportrope, que se ve por todo el mundo como std :: string, pero utiliza subcadena representación en árbol con copiar al escribir que los dos muy eficiente del espacio (subcadenas comunes son compartidos) y muy bueno en las inserciones y eliminaciones (log (n)) hace

al usar la cuerda:

• usted está haciendo un motor de plantilla. las instancias de documentos se crean a partir de una plantilla sustituyendo datos variables en la plantilla y luego se almacenan en caché para usos futuros. Las partes que son comunes a las plantillas y las instancias se almacenan solo una vez y se comparten entre instancias, insertos y eliminaciones son baratas.

Cuando no utilizar la cuerda:

• que está cargando muchos documentos desde fuera del dominio de la aplicación (desde el disco, o en una red) y su utilización sin modificaciones. la cuerda no comparte cuerdas si no se copian de una cuerda a otra. Si puede permitirse hacer el trabajo para encontrar las subcadenas comunes, la cuerda todavía se puede usar para mejorar sus representaciones finales.

Answer 3

Puede usar huffman coding la implementación no es difícil, también hay algoritmos de zip en idiomas (como C# y java) y puede usarlos.

También Si está seguro de que el 80-90% se repite en todos, cree un diccionario de todas las palabras, luego, para cada cadena, la posición de la palabra del diccionario, significa que tiene una matriz de bits de gran tamaño (10000 ie) y marque posición relacionada bits[i] a 1 si existe un words[i] en la cadena actual. piense que cada longitud de palabra es de 5 caracteres, entonces la abreviatura toma alrededor de 1/5 de tamaño.

Answer 4

Como mencionó @Saeed, una codificación Huffman simple funcionará bien aquí.

No es necesario en el diccionario, si las palabras comunes se conocen a priori (ha mencionado que es un HTML). Simplemente precompute una tabla huffman utilizando datos estadísticos de muchos archivos HTML (tenga en cuenta que puede codificar una etiqueta entera con un solo símbolo, y puede tener tantos símbolos como desee).