Un algoritmo de compresión eficiente para cadenas de texto cortas [cerrado]

Estoy buscando un algoritmo para comprimir cadenas de texto pequeñas: 50-1000 bytes (es decir, URL). ¿Qué algoritmo funciona mejor para esto?

Echa un vistazo a Smaz :

Smaz es una biblioteca de compresión simple adecuada para comprimir cadenas muy cortas.

Huffman tiene un costo estático, la tabla Huffman, por lo que no estoy de acuerdo, es una buena opción.

Hay versiones adaptativas que eliminan esto, pero la tasa de compresión puede sufrir. En realidad, la pregunta que debe hacerse es "qué algoritmo para comprimir cadenas de texto con estas características". Por ejemplo, si se esperan largas repeticiones, una simple codificación Run-Lengh podría ser suficiente. Si puede garantizar que solo las palabras en inglés, los espacios, la puntuación y los dígitos ocasionales estarán presentes, entonces Huffman con una tabla de Huffman predefinida podría dar buenos resultados.

En general, los algoritmos de la familia Lempel-Ziv tienen muy buena compresión y rendimiento, y abundan las bibliotecas para ellos. Yo iría con eso.

Con la información de que lo que se está comprimiendo son URL, entonces sugeriría que, antes de comprimir (con cualquier algoritmo que esté fácilmente disponible), CODIFICARlos. Las URL siguen patrones bien definidos, y algunas partes son altamente predecibles. Al hacer uso de este conocimiento, puede codificar las URL en algo más pequeño para comenzar, y las ideas detrás de la codificación Huffman pueden ayudarlo aquí.

Por ejemplo, al traducir la URL en una secuencia de bits, puede reemplazar "http" con el bit 1 y cualquier otra cosa con el bit "0" seguido del protocolo real (o usar una tabla para obtener otros protocolos comunes, como https, ftp, archivo). El ": //" se puede descartar por completo, siempre que pueda marcar el final del protocolo. Etc. Lea sobre el formato de URL y piense en cómo se pueden codificar para ocupar menos espacio.

No tengo código a mano, pero siempre me gustó el enfoque de construir una tabla de búsqueda 2D de tamaño 256 * 256 caracteres ( RFC 1978 , PPP Predictor Compression Protocol ). Para comprimir una cadena, realice un bucle sobre cada carácter y use la tabla de búsqueda para obtener el siguiente carácter 'predicho' utilizando los caracteres actuales y anteriores como índices en la tabla. Si hay una coincidencia, escribe un solo 1 bit; de lo contrario, escriba un 0, el carácter y actualice la tabla de búsqueda con el carácter actual. Este enfoque básicamente mantiene una tabla de búsqueda dinámica (y cruda) del siguiente carácter más probable en el flujo de datos.

Puede comenzar con una tabla de búsqueda puesta a cero, pero obviamente funciona mejor en cadenas muy cortas si se inicializa con el carácter más probable para cada par de caracteres, por ejemplo, para el idioma inglés. Mientras la tabla de búsqueda inicial sea la misma para compresión y descompresión, no es necesario que la emita a los datos comprimidos.

Este algoritmo no proporciona una relación de compresión brillante, pero es increíblemente económico con recursos de memoria y CPU y también puede funcionar en un flujo continuo de datos: el descompresor mantiene su propia copia de la tabla de búsqueda a medida que se descomprime, por lo tanto, la tabla de búsqueda se ajusta al tipo de datos que se comprimen.

Cualquier algoritmo / biblioteca que admita un diccionario preestablecido, por ejemplo, zlib .

De esta forma, puede cebar el compresor con el mismo tipo de texto que probablemente aparezca en la entrada. Si los archivos son similares de alguna manera (por ejemplo, todas las URL, todos los programas C, todas las publicaciones de StackOverflow, todos los dibujos de arte ASCII), aparecerán ciertas subcadenas en la mayoría o en todos los archivos de entrada.

Cada algoritmo de compresión ahorrará espacio si la misma subcadena se repite varias veces en un archivo de entrada (por ejemplo, "el" en texto en inglés o "int" en el código C).

Pero en el caso de las URL, ciertas cadenas (por ejemplo, " http: // www .", ".Com", ".html", ".aspx" generalmente aparecerán una vez en cada archivo de entrada. Por lo tanto, debe compartirlas entre archivos de alguna manera, en lugar de tener una aparición comprimida por archivo, colocarlos en un diccionario preestablecido logrará esto.

La codificación de Huffman generalmente funciona bien para esto.

Si está hablando de comprimir el texto, no solo acortarlo, entonces Deflate / gzip (envoltorio alrededor de gzip), zip funciona bien para archivos y texto más pequeños. Otros algoritmos son altamente eficientes para archivos más grandes como bzip2, etc.

Wikipedia tiene una lista de tiempos de compresión. (busque la comparación de la eficiencia)

Name       | Text         | Binaries      | Raw images
-----------+--------------+---------------+-------------
7-zip      | 19% in 18.8s | 27% in  59.6s | 50% in 36.4s
bzip2      | 20% in  4.7s | 37% in  32.8s | 51% in 20.0s
rar (2.01) | 23% in 30.0s | 36% in 275.4s | 58% in 52.7s
advzip     | 24% in 21.1s | 37% in  70.6s | 57& in 41.6s
gzip       | 25% in  4.2s | 39% in  23.1s | 60% in  5.4s
zip        | 25% in  4.3s | 39% in  23.3s | 60% in  5.7s

Es posible que desee echar un vistazo al Esquema de compresión estándar para Unicode .

SQL Server 2008 R2 lo usa internamente y puede lograr hasta un 50% de compresión.