¿Cuál es el mejor algoritmo de compresión de texto?

Si por “mejor” se refiere a la relación de compresión, de acuerdo con el Benchmark de compresión de texto grande es CMIX. El único problema es que necesita una computadora con 32 GB de memoria para ejecutarlo. Y luego llevará 4 días comprimir o descomprimir 1 GB de texto.

Como la mayoría de los programas mejor clasificados, CMIX utiliza el preprocesamiento de diccionario y la mezcla de contexto de estilo PAQ. El preprocesador reemplaza las palabras con símbolos de 1 a 3 bits de un diccionario y realiza otro procesamiento, como reemplazar letras mayúsculas por un símbolo especial y el símbolo de minúscula correspondiente. También puede analizar prefijos y sufijos comunes.

Un modelo de contexto toma un contexto (por ejemplo, los últimos n bits) y adivina una probabilidad p de que el siguiente bit sea un 0 o 1. El resultado se alimenta a un codificador aritmético, que codifica el bit muy cerca del límite de Shannon de log2 1 / p bits. Por lo tanto, la relación de compresión depende completamente de qué tan bien se estima p . Un algoritmo de mezcla de contexto hace predicciones muy precisas al combinar las predicciones de muchos modelos independientes. CMIX utiliza varios cientos de modelos, por lo que requiere tanto tiempo y memoria. La razón por la que hay tantos modelos es porque hay muchos contextos posibles diferentes, muchas formas de convertir un contexto en una predicción, muchas formas de actualizar el modelo y muchas formas de combinar adaptativamente las predicciones de otros modelos y seleccionar los mejores usando Una jerarquía de mezcladores. Los mezcladores de contexto prácticos pueden usar de 2 a 20 modelos, sacrificando algo de compresión por simplicidad y usabilidad.

Los mejores compresores se acercan realmente a comprender el texto. Modelan la estructura léxica, semántica y gramatical del lenguaje. Por ejemplo, el diccionario se organiza agrupando palabras relacionadas, como madre con padre y lunes con martes . Esto da como resultado códigos de diccionario que difieren solo en los bits bajos. Luego, algunos de los modelos contextuales dejarán caer los bits bajos, permitiendo que el compresor prediga que vi a mi padre el lunes después de haber visto que vi a mi madre el martes .

Los detalles técnicos pueden ser bastante complicados. Si está interesado en aprender más, consulte Compresión de datos explicada.

Depende de lo que quieras decir con “mejor”. Siempre hay una compensación entre velocidad y compresión. Puede encontrar puntos de referencia de compresión en toda la web, por ejemplo:
http://mattmahoney.net/dc/text.html

El libro Introducción a la compresión de datos
( http://www.cs.cmu.edu/afs/cs/pro …) también tiene una lista de algoritmos de compresión de texto y describe los detalles de PPM y Burrows-Wheeler.

Personalmente he usado PPM en 7zip y funciona bien en cuanto a relaciones de velocidad y compresión.

Suponiendo que está hablando de compresión sin pérdidas (los textos pueden comprimirse con pérdida con el lenguaje SMS, por ejemplo), es bien sabido que no puede comprimir sin pérdida “cualquier” archivo binario. En otras palabras, algunos archivos aumentarán su tamaño. Esto se debe a los archivos de encabezado del codificador y a las matemáticas básicas de biyecciones imposibles entre [0, …, N] y [0, …, N-1], o al principio del agujero de paloma Dirichlet (Schubfachprinzip). Ver http://en.wikipedia.org/wiki/Pig

Como se dijo antes, “mejor” generalmente se refiere a una relación de compresión promedio @ Sam-Jp. El conjunto de caracteres de los textos (p. Ej., Ascii de 7 u 8 bits importa) y su tipo también es importante. La “mejor compresión” en archivos de texto escrito en lenguaje humano puro se comporta de manera diferente en los archivos postscript, rtf, doc o incluso pdf que contienen texto, ya que algunos formatos ya encapsulan la compresión. En consecuencia, la “mejor” relación de compresión depende del contenido de la base de datos, la homogeneidad y la tipología de los archivos de texto, como se ve en la compresión de texto en inglés en el enlace @ Igor-Carron: http://www.maximumcompression.co

Speed ​​@ Jonathan-Hseu también es bastante importante. Dependiendo de su aplicación (desde el archivo hasta las interacciones de la base de datos @ Daniel-Lemire), uno se enfoca en la compresión o la descompresión (generalmente se comprime una vez, descomprime muchas), o ambas.

Pero también se pueden evaluar otras características, especialmente con la llegada de grandes conjuntos de datos y diversos sistemas de adquisición:
-rendimiento de acceso aleatorio o capacidad de búsqueda en archivos comprimidos
-resistencia al error (resistencia a bits corruptos)
-capacidad en línea, es decir, poder comprimir eficientemente el flujo de datos tal como viene
-compresión de textos estructurados no solo en un orden ráster sino en árboles, gráficos
-baja complejidad o eficiencia energética del codificador, decodificador o ambos
-posible paralelización
-posibilidad de codificación distribuida (trabajo de compresión compartido en diferentes nodos de una red)

Finalmente, incluso para el texto, uno puede pensar fuera de la caja sin pérdidas. Y volveremos a los SMS citados anteriormente, donde el significado es importante, pero tal vez no sea la ortografía correcta, ver, por ejemplo, Kaufman & Klein, Compresión semi-sin pérdida
http://www.computer.org/portal/w

Como de costumbre, hacer la pregunta de “mejor” resuelve al refinar la pregunta del propósito real, al definir métricas adicionales de calidad y la ponderación adecuada de esas métricas para definir “su” mejor @ Alex-Kamil. Los temas en las siguientes fuentes son inspiradores:

* Transacciones IEEE sobre teoría de la información
http://ieeexplore.ieee.org/xpl/R
* Transacciones IRE en Teoría de la Información
http://ieeexplore.ieee.org/xpl/R
* Conferencia de compresión de datos
pages.cs.brandeis.edu/~dcc/

Finalmente, al no ser un especialista sino un aficionado en la compresión sin pérdidas, recientemente me sorprendió el rendimiento (en relación de compresión) de Deplump ( http://www.deplump.com/index.html ) en algunos largos archivos de texto en inglés y algunos archivos binarios (en comparación con mis favoritos rar, Bzip2 y 7zip citados en otras respuestas). Puede probarlo para archivos cortos en línea. Para obtener información adicional, consulte F. Wood et al. The Sequence Memoizer, 2011 (ver http://www.sequencememoizer.com/ ) o la página web de Franck Wood http://www.stat.columbia.edu/~fw