Comprimir cadenas pequeñas, ¿con qué crear diccionario externo?

Question

Quiero comprimir cadenas muy pequeñas (aproximadamente 75-100 longitud C# cadena). En el momento en que se crea el diccionario, ya conozco todas las cadenas cortas (casi un billón). No habrá cadenas cortas adicionales en el futuro. Necesito extra exactamente una cadena sin descomprimir otras cadenas.

Ahora estoy buscando para una biblioteca o la mejor manera de hacer lo siguiente:

1. crear un diccionario utilizando todas las cadenas que tengo
2. usar el diccionario para comprimir cada cadena
3. una manera de comprimir una cadena usando el diccionario de 1.

Encontré un good related question, pero esto no es específico de C#. Tal vez hay algo para C# No lo sé, o una biblioteca de lujo o alguien ya lo ha hecho. Esa es la razón por la que hago esta pregunta.

EDIT:

con el diccionario Estoy hablando de cosas como esta: http://en.wikipedia.org/wiki/Dictionary_coder Pero todo ayuda a conseguir las cadenas más cortas. Las cadenas son mensajes de texto cortos en varios idiomas y URL (30%/70%). No es necesario que las cadenas comprimidas sean legibles por humanos. Se almacenará en archivos binarios.

Answer 1

Si hay un billón de cadenas y no más, entonces cada una se puede representar en 40 bits (5 bytes). Todo lo que necesita es una forma de utilizar los 5 bytes como un índice para el billón de cadenas.

¿Cómo se conocen todos los trillones de cuerdas? Si el compresor y el descompresor tienen acceso a todos los trillones de cadenas, o si hay forma de ordenar y recrear las cadenas, entonces todo lo que necesita es el índice.

Si no puede encontrar una manera de indexar las cadenas, puede tomar un subconjunto de las cadenas y usarlas como diccionario para un compresor.Simplemente tome la muestra más representativa (necesita averiguar qué podría hacer que algunas de las cadenas sean más comunes que las otras cadenas o más representativas de las otras cadenas) y concatenarlas en un diccionario de 32K. Alrededor de 400 de tus billones de cuerdas. Luego zlib deflateSetDictionary en el extremo de la compresión e inflateSetDictionary en el extremo de la descompresión, ambos usando exactamente el mismo diccionario de 32K. Eso proporcionará una buena compresión en las cuerdas cortas.

Answer 2

no he usado, pero Smaz suena prometedor para este ...

Smaz es una biblioteca de compresión simple adecuada para la compresión muy cadenas cortas. Las bibliotecas de compresión de uso general construirán el estado necesario para comprimir datos dinámicamente, para poder comprimir todo tipo de datos. Esta es una muy buena idea, pero no para un problema específico de : la compresión de cadenas pequeñas no funcionará.

Smaz lugar no es bueno para la compresión de datos de propósito general, pero puede comprimir texto en un 40-50% en el caso promedio (funciona mejor con Inglés), y es capaz de realizar un poco de compresión para HTML y urls también. ¡El punto importante es que Smaz puede comprimir incluso cadenas de dos o tres bytes!

Por ejemplo, la cadena "the" está comprimida en un solo byte.

Dado que está escrito en C, echa un vistazo a Bart De Smet's example for interoping with C through C#.