PAQ es una serie de archivadores de compresión de datos sin pérdidas que han pasado por el desarrollo colaborativo hasta los primeros puestos en varios puntos de referencia que miden la relación de compresión (aunque a expensas de la velocidad y el uso de memoria). Las versiones especializadas de PAQ han ganado el Premio Hutter y el Desafío de Calgary . [1] PAQ es un software gratuito distribuido bajo la Licencia Pública General GNU . [2]
Algoritmo
PAQ utiliza un algoritmo de mezcla de contexto . La mezcla de contexto está relacionada con la predicción por coincidencia parcial (PPM) en que el compresor se divide en un predictor y un codificador aritmético , pero difiere en que la predicción del siguiente símbolo se calcula utilizando una combinación ponderada de estimaciones de probabilidad de una gran cantidad de modelos. condicionado a diferentes contextos. A diferencia de PPM, no es necesario que un contexto sea contiguo. La mayoría de las versiones de PAQ recopilan estadísticas del siguiente símbolo para los siguientes contextos:
- n -gramas ; el contexto son los últimos n bytes antes del símbolo predicho (como en PPM);
- n -gramas de palabra completa, ignorando mayúsculas y minúsculas y caracteres no alfabéticos (útil en archivos de texto);
- contextos "dispersos", por ejemplo, el segundo y cuarto bytes que preceden al símbolo predicho (útil en algunos formatos binarios);
- contextos "analógicos", que consisten en los bits de orden superior de palabras anteriores de 8 o 16 bits (útiles para archivos multimedia);
- contextos bidimensionales (útiles para imágenes, tablas y hojas de cálculo); la longitud de la fila se determina encontrando la longitud de paso de los patrones de bytes repetidos;
- modelos especializados, como ejecutables x86 , imágenes BMP , TIFF o JPEG ; estos modelos están activos solo cuando se detecta el tipo de archivo en particular.
Todas las versiones de PAQ predicen y comprimen un bit a la vez, pero difieren en los detalles de los modelos y en cómo se combinan y posprocesan las predicciones. Una vez que se determina la probabilidad del siguiente bit, se codifica mediante codificación aritmética . Hay tres métodos para combinar predicciones, según la versión:
- En PAQ1 a PAQ3, cada predicción se representa como un par de recuentos de bits . Estos recuentos se combinan mediante una suma ponderada, con mayor peso dado a contextos más largos.
- En PAQ4 a PAQ6, las predicciones se combinan como antes, pero los pesos asignados a cada modelo se ajustan para favorecer los modelos más precisos.
- En PAQ7 y posteriores, cada modelo genera una probabilidad en lugar de un par de conteos. Las probabilidades se combinan utilizando una red neuronal artificial .
PAQ1SSE y versiones posteriores posprocesan la predicción utilizando la estimación de símbolos secundarios (SSE). La predicción combinada y un pequeño contexto se utilizan para buscar una nueva predicción en una tabla. Una vez codificado el bit, la entrada de la tabla se ajusta para reducir el error de predicción. Las etapas de SSE pueden canalizarse con diferentes contextos o calcularse en paralelo con los resultados promediados.
Codificación aritmética
Una cadena s se comprime a la cadena de bytes más corta que representa un número x de big-endian base-256 en el rango [0, 1] tal que P ( r < s ) ≤ x
r ≤ s ), donde P ( r < s ) es la probabilidad de que una cadena aleatoria r con la misma longitud que s sea lexicográficamente menor que s . Siempre es posible encontrar una x tal que la longitud de x sea como máximo un byte más larga que el límite de Shannon , −log 2 P ( r = s ) bits. La longitud de s se almacena en el encabezado del archivo.
El codificador aritmético en PAQ se implementa manteniendo para cada predicción un límite superior e inferior en x , inicialmente [0, 1]. Después de cada predicción, el rango actual se divide en dos partes en proporción a P (0) y P (1), la probabilidad de que el siguiente bit de s sea un 0 o 1 respectivamente, dados los bits anteriores de s . A continuación, el siguiente bit se codifica seleccionando el subrango correspondiente para que sea el nuevo rango.
El número x se descomprime de nuevo en la cadena s haciendo una serie idéntica de predicciones de bits (ya que se conocen los bits anteriores de s ). El rango se divide como con la compresión. La porción que contiene x se convierte en el nuevo rango y el bit correspondiente se agrega a s .
En PAQ, los límites inferior y superior del rango se representan en 3 partes. Los dígitos de base 256 más significativos son idénticos, por lo que se pueden escribir como bytes iniciales de x . Los siguientes 4 bytes se guardan en la memoria, de modo que el byte inicial sea diferente. Se supone que los bits finales son todos ceros para el límite inferior y todos unos para el límite superior. La compresión se termina escribiendo un byte más desde el límite inferior.
Ponderación del modelo adaptativo
En las versiones de PAQ hasta PAQ6, cada modelo asigna un conjunto de contextos distintos a un par de recuentos, , un recuento de bits cero, y , un recuento de 1 bits. Para favorecer la historia reciente, la mitad de la cuenta sobre 2 se descarta cuando se observa el bit opuesto. Por ejemplo, si el estado actual asociado con un contexto es y se observa un 1, entonces los recuentos se actualizan a (7, 4).
Un bit se codifica aritméticamente con un espacio proporcional a su probabilidad, ya sea P (1) o P (0) = 1 - P (1). Las probabilidades se calculan mediante la suma ponderada de los recuentos de 0 y 1:
- S 0 = Σ yo w yo norte 0 yo ,
- S 1 = Σ yo w yo norte 1 yo ,
- S = S 0 + S 1 ,
- P (0) = S 0 / S ,
- P (1) = S 1 / S ,
donde w i es el peso del i -ésimo modelo. A través de PAQ3, los pesos se fijaron y se establecieron de manera ad-hoc. (Los contextos de orden n tenían una ponderación de n 2 ). A partir de PAQ4, las ponderaciones se ajustaron de forma adaptativa en la dirección que reduciría los errores futuros en el mismo conjunto de contexto. Si el bit a codificar es y , entonces el ajuste de peso es:
- norte yo = norte 0 yo + norte 1 yo ,
- error = y - P (1),
- w i ← w i + [( S n 1 i - S 1 n i ) / ( S 0 S 1 )] error.
Mezcla de redes neuronales
A partir de PAQ7, cada modelo genera una predicción (en lugar de un par de recuentos). Estas predicciones se promedian en el dominio logístico:
- x i = estirar (P i (1)),
- P (1) = calabaza (Σ yo w yo x yo ),
donde P (1) es la probabilidad de que el siguiente bit sea un 1, P i (1) es la probabilidad estimada por el i -ésimo modelo, y
- estirar ( x ) = ln ( x / (1 - x )),
- squash ( x ) = 1 / (1 + e - x ) (inverso de estiramiento).
Después de cada predicción, el modelo se actualiza ajustando los pesos para minimizar el costo de codificación:
- w yo ← w yo + η x yo ( y - P (1)),
donde η es la tasa de aprendizaje (normalmente 0,002 a 0,01), y es el bit predicho y ( y - P (1)) es el error de predicción. El algoritmo de actualización de peso se diferencia de la propagación hacia atrás en que se eliminan los términos P (1) P (0). Esto se debe a que el objetivo de la red neuronal es minimizar el costo de codificación, no el error cuadrático medio .
La mayoría de las versiones de PAQ utilizan un contexto pequeño para seleccionar entre conjuntos de pesos para la red neuronal. Algunas versiones utilizan múltiples redes cuyas salidas se combinan con una red más antes de las etapas SSE. Además, para cada entrada de predicción de que puede haber varias entradas que son no lineales funciones de P i (1), además de tramo (P (1)).
Modelado de contexto
Cada modelo divide los bits conocidos de s en un conjunto de contextos y asigna cada contexto a un historial de bits representado por un estado de 8 bits. En las versiones hasta PAQ6, el estado representa un par de contadores ( n 0 , n 1 ). En PAQ7 y versiones posteriores, bajo ciertas condiciones, el estado también representa el valor del último bit o la secuencia completa. Los estados se asignan a probabilidades utilizando una tabla de 256 entradas para cada modelo. Después de una predicción del modelo, la entrada de la tabla se ajusta ligeramente (normalmente en un 0,4%) para reducir el error de predicción.
En todas las versiones de PAQ8, los estados representables son los siguientes:
- La secuencia de bits exacta de hasta 4 bits.
- Un par de conteos y un indicador del bit más reciente para secuencias de 5 a 15 bits.
- Un par de recuentos para secuencias de 16 a 41 bits.
Para mantener el número de estados en 256, se colocan los siguientes límites en los recuentos representables: (41, 0), (40, 1), (12, 2), (5, 3), (4, 4), ( 3, 5), (2, 12), (1, 40), (0, 41). Si un recuento excede este límite, entonces el siguiente estado es uno elegido para tener una proporción similar de n 0 a n 1 . Por lo tanto, si el estado actual es ( n 0 = 4, n 1 = 4, último bit = 0) y se observa un 1, entonces el nuevo estado no es ( n 0 = 4, n 1 = 5, último bit = 1 ). Más bien, es ( n 0 = 3, n 1 = 4, último bit = 1).
La mayoría de los modelos de contexto se implementan como tablas hash . Algunos contextos pequeños se implementan como tablas de búsqueda directa .
Preprocesamiento de texto
Algunas versiones de PAQ, en particular PAsQDa, PAQAR (ambos derivados de PAQ6) y PAQ8HP1 a PAQ8HP8 (derivados de PAQ8 y destinatarios del premio Hutter ) preprocesan archivos de texto buscando palabras en un diccionario externo y reemplazándolas con códigos de 1 a 3 bytes. . Además, las letras mayúsculas se codifican con un carácter especial seguido de la letra minúscula. En la serie PAQ8HP, el diccionario está organizado agrupando palabras relacionadas sintáctica y semánticamente. Esto permite que los modelos utilicen solo los bits más significativos de los códigos del diccionario como contexto.
Comparación
La siguiente tabla es una muestra del Índice de referencia Compresión de texto grande por Matt Mahoney, que consiste en un archivo que consta de 10 9 bytes (1 GB o 0.931 GiB ) de Inglés Wikipedia texto.
Programa | Tamaño comprimido (bytes) | % del tamaño original | Tiempo de compresión ( ns / byte) | Memoria (MiB) |
---|---|---|---|---|
PAQ8HP8 | 133,423,109 | 13.34 | 64 639 | 1849 |
PPMd | 183,976,014 | 18,4 | 880 | 256 |
bzip2 | 254,007,875 | 25,4 | 379 | 8 |
InfoZIP | 322,649,703 | 32,26 | 104 | 0,1 |
Consulte las pruebas comparativas de compresión sin pérdida para obtener una lista de las pruebas comparativas de compresión de archivos.
Historia
A continuación se enumeran las principales mejoras del algoritmo PAQ. Además, ha habido una gran cantidad de mejoras incrementales, que se omiten.
- PAQ1 fue lanzado el 6 de enero de 2002 por Matt Mahoney. Utilizaba pesos fijos y no incluía un modelo análogo o disperso.
- PAQ1SSE / PAQ2 fue lanzado el 11 de mayo de 2003 por Serge Osnach. Mejoró significativamente la compresión al agregar una etapa de estimación de símbolo secundario (SSE) entre el predictor y el codificador. SSE ingresa un contexto breve y la predicción actual y genera una nueva predicción de una tabla. Luego, la entrada de la tabla se ajusta para reflejar el valor real del bit.
- PAQ3N , publicado el 9 de octubre de 2003, agregó un modelo escaso.
- PAQ4 , publicado el 15 de noviembre de 2003 por Matt Mahoney utilizó ponderación adaptativa. PAQ5 (18 de diciembre de 2003) y PAQ6 (30 de diciembre de 2003) fueron mejoras menores, incluido un nuevo modelo analógico. En este punto, PAQ era competitivo con los mejores compresores PPM y atrajo la atención de la comunidad de compresión de datos, lo que resultó en una gran cantidad de mejoras incrementales hasta abril de 2004. Berto Destasio afinó los modelos y ajustó el programa de descuento de recuento de bits. Johan de Bock realizó mejoras en la interfaz de usuario. David A. Scott realizó mejoras en el codificador aritmético. Fabio Buffoni hizo mejoras de velocidad.
- Durante el período del 20 de mayo de 2004 al 27 de julio de 2004, Alexander Ratushnyak lanzó siete versiones de PAQAR , que realizaron mejoras de compresión significativas al agregar muchos modelos nuevos, múltiples mezcladores con pesos seleccionados por contexto, agregando una etapa SSE a cada salida de mezclador y agregar un preprocesador para mejorar la compresión de los archivos ejecutables de Intel. PAQAR se mantuvo como el compresor mejor clasificado hasta finales de 2004, pero fue significativamente más lento que las versiones anteriores de PAQ.
- Durante el período del 18 de enero de 2005 al 7 de febrero de 2005, Przemyslaw Skibinski lanzó cuatro versiones de PASqDa , basadas en PAQ6 y PAQAR con la adición de un preprocesador de diccionario de inglés. Logró la clasificación más alta en el corpus de Calgary, pero no en la mayoría de los demás puntos de referencia.
- Una versión modificada de PAQ6 ganó el Calgary Challenge el 10 de enero de 2004 por Matt Mahoney. Esto fue mejorado por diez versiones posteriores de PAQAR por Alexander Ratushnyak. El más reciente fue presentado el 5 de junio de 2006, que consta de datos comprimidos y código fuente del programa por un total de 589,862 bytes.
- PAQ7 fue lanzado en diciembre de 2005 por Matt Mahoney. PAQ7 es una reescritura completa de PAQ6 y variantes (PAQAR, PAsQDa). La relación de compresión fue similar a PAQAR pero 3 veces más rápida. Sin embargo, carecía de x86 y de un diccionario, por lo que no comprimía los ejecutables de Windows ni los archivos de texto en inglés ni PAsQDa. Incluye modelos para archivos BMP, TIFF y JPEG en color, por lo que comprime mejor estos archivos. La principal diferencia con PAQ6 es que utiliza una red neuronal para combinar modelos en lugar de un mezclador de descenso de gradiente. Otra característica es la capacidad de PAQ7 para comprimir imágenes de mapa de bits y jpeg incrustadas en archivos Excel, Word y pdf.
- PAQ8A se lanzó el 27 de enero de 2006, PAQ8C el 13 de febrero de 2006. Se trataba de una versión preliminar experimental del PAQ8 anticipado. Se corrigieron varios problemas en PAQ7 (compresión deficiente en algunos casos). PAQ8A también incluyó un modelo para comprimir ejecutables (x86).
- PAQ8F fue lanzado el 28 de febrero de 2006. PAQ8F tenía 3 mejoras sobre PAQ8A: un modelo de contexto más eficiente en memoria, un nuevo modelo de contexto indirecto para mejorar la compresión y una nueva interfaz de usuario para soportar arrastrar y soltar en Windows. No utiliza un diccionario de inglés como las variantes PAQ8B / C / D / E.
- PAQ8G fue lanzado el 3 de marzo de 2006 por Przemyslaw Skibinski. PAQ8G es PAQ8F con diccionarios agregados y algunas otras mejoras como un TextFilter rediseñado (que no disminuye el rendimiento de compresión en archivos no textuales)
- PAQ8H fue lanzado el 22 de marzo de 2006 por Alexander Ratushnyak y actualizado el 24 de marzo de 2006. PAQ8H se basa en PAQ8G con algunas mejoras en el modelo.
- PAQ8I fue lanzado el 18 de agosto de 2006 por Pavel L. Holoborodko, con correcciones de errores el 24 de agosto, 4 de septiembre y 13 de septiembre. Agregó un modelo de imagen en escala de grises para archivos PGM .
- PAQ8J fue lanzado el 13 de noviembre de 2006 por Bill Pettis. Se basó en PAQ8F con algunas mejoras en el modelo de texto tomadas de PAQ8HP5. Por lo tanto, no incluyó los diccionarios de texto de PAQ8G ni el modelo PGM de PAQ8I .
- Serge Osnach lanzó una serie de mejoras de modelado: PAQ8JA el 16 de noviembre de 2006, PAQ8JB el 21 de noviembre y PAQ8JC el 28 de noviembre.
- PAQ8JD fue lanzado el 30 de diciembre de 2006 por Bill Pettis. Desde entonces, esta versión se ha adaptado a Windows de 32 bits para varios procesadores y a Linux de 32 y 64 bits .
- PAQ8K fue lanzado el 13 de febrero de 2007 por Bill Pettis. Incluye modelos adicionales para archivos binarios.
- PAQ8L fue lanzado el 8 de marzo de 2007 por Matt Mahoney. Se basa en PAQ8JD y agrega un modelo DMC .
- PAQ8O fue lanzado el 24 de agosto de 2007 por Andreas Morphis. Contiene modelos BMP y JPEG mejorados sobre PAQ8L. Opcionalmente se puede compilar con soporte SSE2 y para Linux de 64 bits. El algoritmo tiene notables beneficios de rendimiento en sistemas operativos de 64 bits.
- PAQ8P fue lanzado el 25 de agosto de 2008 por Andreas Morphis. Contiene un modelo BMP mejorado y agrega un modelo WAV .
- PAQ8PX fue lanzado el 25 de abril de 2009 por Jan Ondrus. Contiene varias mejoras como mejor compresión WAV y compresión EXE .
- PAQ8KX fue lanzado el 15 de julio de 2009 por Jan Ondrus. Es una combinación de PAQ8K con PAQ8PX.
- PAQ8PF fue lanzado el 9 de septiembre de 2009 por LovePimple sin código fuente (que requiere la licencia GPL ). Comprime un 7% peor, pero es 7 veces más rápido en comparación con PAQ8PX v66 (medido con 1 MB de texto en inglés)
- PAQ9A fue lanzado el 31 de diciembre de 2007 por Matt Mahoney. Una nueva versión experimental. No incluye modelos para tipos de archivos específicos, tiene un preprocesador LZP y admite archivos de más de 2 GB.
- ZPAQ fue lanzado el 12 de marzo de 2009 por Matt Mahoney. Utiliza un nuevo formato de archivo diseñado para que el programa ZPAQ actual pueda descomprimir archivos creados por futuras versiones de ZPAQ [3] (las diversas variantes de PAQ enumeradas anteriormente no son compatibles conversiones posteriores deesta manera). Lo logra especificando el algoritmo de descompresión en un programa de código de bytes que se almacena en cada archivo de almacenamiento creado. [4]
Premios Hutter
Las series PAQ8HP1 a PAQ8HP8 fueron lanzadas por Alexander Ratushnyak desde el 21 de agosto de 2006 hasta el 18 de enero de 2007 como presentaciones del Premio Hutter . El Premio Hutter es un concurso de compresión de texto que utiliza un conjunto de datos XML y en inglés de 100 MB derivados de la fuente de Wikipedia. La serie PAQ8HP se bifurcó de PAQ8H. Los programas incluyen diccionarios de preprocesamiento de texto y modelos ajustados específicamente al punto de referencia. Se eliminaron todos los modelos que no son de texto. Los diccionarios se organizaron para agrupar palabras relacionadas sintáctica y semánticamente y para agrupar palabras por sufijo común. La primera estrategia mejora la compresión porque las palabras relacionadas (que probablemente aparecerán en un contexto similar) pueden modelarse en los bits de orden superior de sus códigos de diccionario. La última estrategia hace que el diccionario sea más fácil de comprimir. El tamaño del programa de descompresión y del diccionario comprimido se incluye en la clasificación del concurso.
El 27 de octubre de 2006, se anunció [5] que PAQ8HP5 ganó un premio Hutter por compresión sin pérdidas del conocimiento humano de € 3.416.
El 30 de junio de 2007, el PAQ8HP12 de Ratushnyak recibió un segundo premio Hutter de 1732 €, [6] mejorando su récord anterior en un 3,46%.
Derivaciones de PAQ
Al ser un software libre , PAQ puede ser modificado y redistribuido por cualquiera que tenga una copia. Esto ha permitido a otros autores bifurcar el motor de compresión PAQ y agregar nuevas características como una interfaz gráfica de usuario o una mejor velocidad (a expensas de la relación de compresión). Los derivados de PAQ notables incluyen:
- WinUDA 0.291 , basado en PAQ6 pero más rápido [7]
- UDA 0.301 , basado en el algoritmo PAQ8I [7]
- KGB , basado en PAQ6 [8] (la versión beta se basa en PAQ7).
- Emilcont basado en PAQ6 [9]
- Interfaz de interfaz gráfica de usuario de Peazip (para Windows y Linux) para LPAQ , [10] ZPAQ y varios algoritmos PAQ8 * [11]
- PWCM (mezcla de contexto ponderado PAQ) es una implementación de código cerrado desarrollada independientemente del algoritmo PAQ utilizado en WinRK. [12]
- PAQCompress es una interfaz gráfica de usuario para varias versiones más nuevas de PAQ, incluidas las últimas versiones de PAQ8PX, PAQ8PXD y PAQ8PXV. Se actualiza cada vez que se lanza una nueva versión. El software agrega inteligentemente una extensión al nombre de archivo que puede usar para descomprimir el archivo usando la versión de PAQ correcta. El software es de código abierto. [13]
- PerfectCompress [14] es un software de compresión que incluye UCA (ULTRA Compressed Archive). Un formato de compresión que incluía PAQ8PX v42 a v65 y que ahora puede usar PAQ8PF, PAQ8KX o PAQ8PXPRE como el compresor UCA predeterminado. Además, PerfectCompress puede comprimir archivos a PAQ8PX v42 a v67 y ZPAQ, y a partir de la versión 6.0, puede comprimir archivos a LPAQ y PAQ8PF beta 1 a beta 3. PerfectCompress v6.10 introdujo compresión de soporte para el PAQ8PXPRE recientemente lanzado. PerfectCompress 6.12 introduce soporte para la serie PAQ8KX. [15]
- FrontPAQ , pequeña interfaz gráfica de usuario para PAQ. La última versión es FrontPAQ v8 compatible con PAQ8PX, PAQ8PF y FP8. El software ya no se actualiza y se anima a los usuarios a utilizar PAQCompress, que implementa las últimas versiones de PAQ. [dieciséis]
Ver también
- Lista de formatos de archivo
- Comparación de archivadores de archivos
Referencias
- ^ "El desafío de compresión / SHA-1" . Mailcom.com . Consultado el 19 de mayo de 2010 .
- ^ "Página de inicio de los compresores PAQ" . Consultado el 10 de julio de 2007 .
Puede descargar, usar, copiar, modificar y distribuir estos programas bajo los términos de la licencia pública general de GNU.
- ^ "Página de manual de Ubuntu zpaq (1)" .
- ^ "Especificación de nivel 1 de ZPAQ" (PDF) . Consultado el 3 de septiembre de 2010 .
- ^ James Bowery. Alexander Ratushnyak gana el primer premio Hutter . Publicado el 27 de octubre de 2006. Consultado el 30 de octubre de 2006. [ enlace muerto ]
- ^ http://prize.hutter1.net/award2.gif
- ↑ a b Página de inicio de dwing Archivado el 24 de febrero de 2007 en Wayback Machine.
- ^ "Página de inicio de KGB Archiver" . Kgbarchiver.net . Consultado el 19 de mayo de 2010 .
- ^ "EmilCont Ultracompression" . Freewebs.com. Archivado desde el original el 10 de septiembre de 2010 . Consultado el 19 de mayo de 2010 .
- ^ Matt Mahoney (2007). "LPAQ" . Consultado el 29 de diciembre de 2013 .
- ^ "PeaZip" . PeaZip . Consultado el 6 de octubre de 2013 .
- ^ "Prueba comparativa de compresión de datos de un solo archivo, ordenada por relación de compresión" . Maximumcompression.com. 2007-04-14 . Consultado el 19 de mayo de 2010 .
- ^ "PAQCompress" . Moisés Cardona . 2019-01-10 . Consultado el 5 de marzo de 2019 .
- ^ "Sitio web oficial de PerfectCompress" . Moises-studios.110mb.com. 2010-04-03 . Consultado el 19 de mayo de 2010 .
- ^ "Página oficial de Facebook de PerfectCompress" . Facebook.com . Consultado el 19 de mayo de 2010 .
- ^ "FrontPAQ - Interfaz gráfica de usuario para PAQ8PF y PAQ8PX" . encode.su . Consultado el 26 de julio de 2019 .
Otras lecturas
- David Salomon, Giovanni Motta, (con contribuciones de David Bryant), Handbook of Data Compression , 5ta edición, Springer, 2009, ISBN 1-84882-902-7 , 5.15 PAQ, págs. 314–319
- Byron Knoll, Nando de Freitas, A Machine Learning Perspective on Predictive Coding with PAQ , Universidad de Columbia Británica, Vancouver, Canadá, 17 de agosto de 2011
enlaces externos
- Página web oficial
- Binarios de Linux compilados : descarga de ejecutables de línea de comandos de Linux.