¿Cuál es el estado actual de los algoritmos de compresión de solo texto?

Question

En honor del Hutter Prize, ¿cuáles son los algoritmos principales (y una descripción rápida de cada uno) para la compresión de texto?

Nota: El objetivo de esta pregunta es obtener una descripción de los algoritmos de compresión, no de los programas de compresión.

Answer 1

Los compresores de límite de empuje combinan algoritmos para obtener resultados insanos. algoritmos comunes incluyen:

• El Burrows-Wheeler Transform y here - personajes de reproducción aleatoria (u otros bloques de bits) con un algoritmo predecible para aumentar bloques repetidos que hace que la fuente más fácil de comprimir. La descompresión ocurre normalmente y el resultado no se baraja con la transformación inversa. Nota: BWT solo en realidad no comprime nada. Simplemente hace que la fuente sea más fácil de comprimir.
• Prediction by Partial Matching (PPM) - una evolución de arithmetic coding donde se crea el modelo de predicción (contexto) mediante el crujido de las estadísticas sobre la fuente frente al uso de probabilidades estáticas. A pesar de que sus raíces están en la codificación aritmética, el resultado se puede representar con la codificación de Huffman o un diccionario, así como la codificación aritmética.
• Mezcla de contexto: la codificación aritmética utiliza un contexto estático para la predicción, PPM elige dinámicamente un contexto único, la combinación de contexto usa muchos contextos y pondera sus resultados. PAQ usa la mezcla de contexto. Here's una visión general de alto nivel.
• Dynamic Markov Compression - relacionado con PPM, pero utiliza contextos a nivel de bit frente a byte o más.
• Además, los concursantes del premio Hutter pueden reemplazar el texto común con entradas de bytes pequeños de diccionarios externos y diferenciar el texto en mayúscula y minúscula con un símbolo especial en lugar de usar dos entradas distintas. Es por eso que son tan buenos para comprimir texto (especialmente texto ASCII) y no tan valiosos para la compresión general.

Maximum Compression es un texto muy interesante y un sitio de referencia de compresión general. Matt Mahoney publica otro benchmark. Mahoney's puede ser de particular interés porque enumera el algoritmo principal utilizado por entrada.

Answer 2

Siempre hay lzip.

Bromas aparte:

• donde la compatibilidad es una preocupación, PKZIP (DEFLATE algoritmo) todavía gana.
• bzip2 es el mejor compromiso entre disfrutar de una base de instalación relativamente amplia y una relación de compresión bastante buena, pero requiere un archivador por separado.
• 7-Zip (algoritmo LZMA) se comprime muy bien y está disponible para la LGPL. Sin embargo, pocos sistemas operativos se entregan con soporte incorporado.
• rzip es una variante de bzip2 que, en mi opinión, merece más atención. Podría ser particularmente interesante para archivos de registro grandes que necesitan archivar a largo plazo. También requiere un archivador por separado.

Answer 3

Si desea utilizar PAQ como programa, puede instalar el paquete zpaq en sistemas basados ​​en Debian.El uso se (véase también man zpaq)

zpaq c archivename.zpaq file1 file2 file3 

compresión era de aproximadamente 1/10th de tamaño de un archivo zip. (1.9M vs 15M)