stringtranslate.com

Algoritmo de la cadena Lempel-Ziv-Markov

El algoritmo de cadena Lempel–Ziv–Markov ( LZMA ) es un algoritmo utilizado para realizar una compresión de datos sin pérdida . Ha estado en desarrollo desde 1996 o 1998 por Igor Pavlov [1] y se utilizó por primera vez en el formato 7z del archivador 7-Zip . Este algoritmo utiliza un esquema de compresión de diccionario algo similar al algoritmo LZ77 publicado por Abraham Lempel y Jacob Ziv en 1977 y presenta una alta relación de compresión (generalmente más alta que bzip2 ) [2] [3] y un tamaño de diccionario de compresión variable (hasta 4  GB ), [4] mientras que aún mantiene una velocidad de descompresión similar a otros algoritmos de compresión comúnmente utilizados. [5]

LZMA2 es un formato contenedor simple que puede incluir tanto datos sin comprimir como datos LZMA, posiblemente con múltiples parámetros de codificación LZMA diferentes. LZMA2 admite compresión y descompresión multiproceso escalables de forma arbitraria y una compresión eficiente de datos que son parcialmente incompresibles. [6]

Descripción general

LZMA utiliza un algoritmo de compresión de diccionarios (una variante de LZ77 con diccionarios de gran tamaño y soporte especial para distancias de coincidencia utilizadas repetidamente), cuya salida se codifica luego con un codificador de rango , utilizando un modelo complejo para hacer una predicción de probabilidad de cada bit. El compresor de diccionarios encuentra coincidencias utilizando estructuras de datos de diccionario sofisticadas y produce un flujo de símbolos literales y referencias de frases, que se codifica un bit a la vez por el codificador de rango: son posibles muchas codificaciones y se utiliza un algoritmo de programación dinámica para seleccionar una óptima bajo ciertas aproximaciones. [7]

Antes de LZMA, la mayoría de los modelos de codificadores se basaban puramente en bytes (es decir, codificaban cada bit utilizando solo una cascada de contextos para representar las dependencias de los bits anteriores del mismo byte). La principal innovación de LZMA es que, en lugar de un modelo genérico basado en bytes, el modelo de LZMA utiliza contextos específicos de los campos de bits en cada representación de un literal o frase: esto es casi tan simple como un modelo genérico basado en bytes, pero proporciona una compresión mucho mejor porque evita mezclar bits no relacionados en el mismo contexto. Además, en comparación con la compresión de diccionario clásica (como la que se usa en los formatos zip y gzip ), los tamaños de los diccionarios pueden ser y suelen ser mucho mayores, aprovechando la gran cantidad de memoria disponible en los sistemas modernos. [7]

Descripción general del formato comprimido

En la compresión LZMA, el flujo comprimido es un flujo de bits, codificado mediante un codificador de rango binario adaptativo. El flujo se divide en paquetes, cada uno de los cuales describe un solo byte o una secuencia LZ77 con su longitud y distancia codificadas de forma implícita o explícita. Cada parte de cada paquete se modela con contextos independientes, por lo que las predicciones de probabilidad para cada bit se correlacionan con los valores de ese bit (y bits relacionados del mismo campo) en paquetes anteriores del mismo tipo. Tanto la documentación de lzip [8] como la de LZMA SDK describen este formato de flujo. [7]

Hay 7 tipos de paquetes: [8]

LONGREP[*] se refiere a paquetes LONGREP[0–3], *REP se refiere tanto a LONGREP como a SHORTREP, y *MATCH se refiere tanto a MATCH como a *REP.

Los paquetes LONGREP[n] eliminan la distancia utilizada de la lista de distancias más recientes y la vuelven a insertar al principio, para evitar entradas repetidas inútiles, mientras que MATCH solo agrega la distancia al principio incluso si ya está presente en la lista y SHORTREP y LONGREP[0] no alteran la lista.

La longitud se codifica de la siguiente manera:

Al igual que en LZ77, la longitud no está limitada por la distancia, porque la copia del diccionario se define como si la copia se realizara byte a byte, manteniendo la distancia constante.

Las distancias son lógicamente de 32 bits y la distancia 0 apunta al byte agregado más recientemente en el diccionario.

La codificación de distancia comienza con una "ranura de distancia" de 6 bits, que determina cuántos bits adicionales se necesitan. Las distancias se decodifican como una concatenación binaria de, desde el más significativo hasta el menos significativo, dos bits según la ranura de distancia, algunos bits codificados con una probabilidad fija de 0,5 y algunos bits codificados por contexto, de acuerdo con la siguiente tabla (las ranuras de distancia 0-3 codifican directamente las distancias 0-3).

Detalles del algoritmo de descompresión

No parece existir ninguna especificación completa en lenguaje natural del formato comprimido, aparte de la que se intenta en el texto siguiente.

La siguiente descripción se basa en el decodificador compacto XZ Embedded de Lasse Collin incluido en el código fuente del kernel de Linux [9], del cual se pueden deducir con relativa facilidad los detalles de los algoritmos LZMA y LZMA2: por lo tanto, si bien citar el código fuente como referencia no es lo ideal, cualquier programador debería poder verificar las afirmaciones a continuación con unas pocas horas de trabajo.

Codificación de rango de bits

Los datos LZMA se decodifican en el nivel más bajo, bit a bit, mediante el decodificador de rango, siguiendo las instrucciones del decodificador LZMA.

La decodificación de rango basada en contexto es invocada por el algoritmo LZMA pasándole una referencia al "contexto", que consiste en la variable sin signo de 11 bits prob (normalmente implementada utilizando un tipo de datos de 16 bits) que representa la probabilidad prevista de que el bit sea 0, que es leída y actualizada por el decodificador de rango (y debe inicializarse a ⁠ ⁠ , lo que representa una probabilidad de 0,5).

En cambio, la decodificación de rango de probabilidad fija supone una probabilidad de 0,5, pero funciona de forma ligeramente diferente a la decodificación de rango basada en el contexto.

El estado del decodificador de rango consta de dos variables de 32 bits sin signo: rango (que representa el tamaño del rango) y código (que representa el punto codificado dentro del rango).

La inicialización del decodificador de rango consiste en establecer el rango en 2 32 − 1 y el código en el valor de 32 bits comenzando en el segundo byte del flujo interpretado como big-endian; el primer byte del flujo se ignora por completo.

La normalización se realiza de la siguiente manera:

  1. Desplazar el rango y el código hacia la izquierda en 8 bits
  2. Leer un byte del flujo comprimido
  3. Establezca los 8 bits de código menos significativos en el valor del byte leído

La decodificación de rango basada en el contexto de un bit utilizando la variable de probabilidad prob procede de esta manera:

  1. Si el rango es menor que ⁠ ⁠ , realice la normalización
  2. Establecer límite a ⁠ ⁠
  3. Si el código es menor que el límite :
    1. Establecer rango como límite
    2. Establezca prob en prob + ⁠ ⁠
    3. Devuelve el bit 0
  4. De lo contrario (si el código es mayor o igual al límite ):
    1. Establecer rango a rangolímite
    2. Establecer código a códigoenlazado
    3. Establezca prob en ⁠ ⁠
    4. Devolver bit 1

La decodificación de un bit con un rango de probabilidad fijo se realiza de la siguiente manera:

  1. Si el rango es menor que ⁠ ⁠ , realice la normalización
  2. Establezca el rango en ⁠ ⁠
  3. Si el código es menor que el rango :
    1. Devuelve el bit 0
  4. De lo contrario (si el código es mayor o igual que el rango ):
    1. Establecer código en códigorango
    2. Devolver bit 1

Por razones de rendimiento, la implementación del kernel de Linux de la decodificación de probabilidad fija en rc_direct(), no incluye una rama condicional, sino que resta range del código de manera incondicional. El bit de signo resultante se utiliza tanto para decidir el bit que se devolverá como para generar una máscara que se combina con el código y se agrega a range .

Tenga en cuenta que:

  1. La división por ⁠ ⁠ cuando se calcula la operación límite y de piso se realiza antes de la multiplicación, no después (aparentemente para evitar requerir soporte de hardware rápido para la multiplicación de 32 bits con un resultado de 64 bits)
  2. La decodificación de probabilidad fija no es estrictamente equivalente a la decodificación de rango basada en contexto con cualquier valor de probabilidad , debido al hecho de que la decodificación de rango basada en contexto descarta los 11 bits inferiores del rango antes de multiplicar por probabilidad como se acaba de describir, mientras que la decodificación de probabilidad fija solo descarta el último bit.

Codificación de rango de números enteros

El decodificador de rango también proporciona las funciones de decodificación de enteros de probabilidad fija, árbol de bits inverso y árbol de bits, que se utilizan para decodificar enteros y generalizar la decodificación de un solo bit descrita anteriormente. Para decodificar enteros sin signo menores que limit , se proporciona una matriz de ( limit − 1) variables de probabilidad de 11 bits, que están organizadas conceptualmente como los nodos internos de un árbol binario completo con hojas limit .

La decodificación de árbol de bits no inverso funciona manteniendo un puntero al árbol de variables, que comienza en la raíz. Mientras el puntero no apunte a una hoja, se decodifica un bit utilizando la variable indicada por el puntero y el puntero se mueve a los elementos secundarios izquierdo o derecho según si el bit es 0 o 1; cuando el puntero apunta a una hoja, se devuelve el número asociado con la hoja.

La decodificación de árbol de bits no inverso ocurre así desde el bit más significativo al menos significativo, y se detiene cuando solo es posible un valor en el rango válido (esto conceptualmente permite tener tamaños de rango que no sean potencias de dos, aunque LZMA no hace uso de esto).

En cambio, la decodificación de árbol de bits inverso decodifica desde el bit menos significativo hasta los bits más significativos y, por lo tanto, solo admite rangos que son potencias de dos y siempre decodifica la misma cantidad de bits. Es equivalente a realizar una decodificación de árbol de bits no inversa con un límite de potencia de dos e invertir los últimos 2 bits de registro ( límite ) del resultado.

En la función rc_bittree del kernel de Linux, los números enteros se devuelven en realidad en el rango [ limit , 2 × limit ) (con limit añadido al valor conceptual), y la variable en el índice 0 de la matriz no se utiliza, mientras que la del índice 1 es la raíz, y los índices de los hijos izquierdo y derecho se calculan como 2 i y 2 i + 1. La función rc_bittree_reverse , en cambio, añade números enteros en el rango [0, limit ) a una variable proporcionada por el llamador, donde limit se representa implícitamente por su logaritmo, y tiene su propia implementación independiente por razones de eficiencia.

La decodificación de enteros de probabilidad fija simplemente realiza una decodificación de bits de probabilidad fija repetidamente, leyendo los bits desde el más significativo hasta el menos significativo.

Configuración de LZMA

El decodificador LZMA se configura mediante un byte de "propiedades" lclppb y un tamaño de diccionario. El valor del byte lclppb es lc + lp × 9 + pb × 9 × 5 , donde:

En corrientes que no sean LZMA2, lc no debe ser mayor que 8, y lp y pb no deben ser mayores que 4. En corrientes LZMA2, ( lc + lp ) y pb no deben ser mayores que 4.

En el formato de archivo LZMA de 7-zip, la configuración se realiza mediante un encabezado que contiene el byte de "propiedades" seguido del tamaño del diccionario little-endian de 32 bits en bytes. En LZMA2, el byte de propiedades se puede cambiar opcionalmente al comienzo de los paquetes LZMA2, mientras que el tamaño del diccionario se especifica en el encabezado LZMA2 como se describe más adelante.

Contextos de codificación LZMA

Ya se ha descrito el formato de paquete LZMA y esta sección especifica cómo LZMA modela estadísticamente los flujos codificados LZ o, en otras palabras, qué variables de probabilidad se pasan al decodificador de rango para decodificar cada bit.

Estas variables de probabilidad se implementan como matrices multidimensionales; antes de introducirlas, se definen algunos valores que se utilizan como índices en estas matrices multidimensionales.

El valor del estado se basa conceptualmente en cuáles de los patrones de la siguiente tabla coinciden con los últimos 2 a 4 tipos de paquetes vistos, y se implementa como un estado de máquina de estados que se actualiza de acuerdo con la tabla de transición que aparece en la tabla cada vez que se emite un paquete.

El estado inicial es 0 y, por lo tanto, se supone que los paquetes anteriores al comienzo son paquetes LIT.

Los valores pos_state y literal_pos_state consisten respectivamente en los bits menos significativos pb y lp (hasta 4, del encabezado LZMA o del paquete de propiedades LZMA2) de la posición del diccionario (la cantidad de bytes codificados desde el último reinicio del diccionario módulo el tamaño del diccionario). Tenga en cuenta que el tamaño del diccionario normalmente es el múltiplo de una gran potencia de 2, por lo que estos valores se describen de manera equivalente como los bits menos significativos de la cantidad de bytes sin comprimir vistos desde el último reinicio del diccionario.

El valor prev_byte_lc_msbs se establece en los lc bits más significativos (hasta 4, desde el encabezado LZMA o el paquete de propiedades LZMA2) del byte sin comprimir anterior.

El valor is_REP indica si un paquete que incluye una longitud es un LONGREP en lugar de un MATCH.

El valor match_byte es el byte que se habría decodificado si se hubiera utilizado un paquete SHORTREP (en otras palabras, el byte que se encuentra en el diccionario en la última distancia utilizada); sólo se utiliza justo después de un paquete *MATCH.

literal_bit_mode es una matriz de 8 valores en el rango 0–2, uno para cada posición de bit en un byte, que son 1 o 2 si el paquete anterior fue un *MATCH y es la posición de bit más significativa o todos los bits más significativos en el literal a codificar/decodificar son iguales a los bits en las posiciones correspondientes en match_byte , mientras que de lo contrario es 0; la elección entre los valores 1 o 2 depende del valor del bit en la misma posición en match_byte .

El conjunto de variables literal/Literal puede verse como un "pseudo-árbol de bits" similar a un árbol de bits pero con 3 variables en lugar de 1 en cada nodo, elegidas dependiendo del valor literal_bit_mode en la posición de bit del próximo bit a decodificar después del contexto del árbol de bits denotado por el nodo.

La afirmación, encontrada en algunas fuentes, de que los literales después de un *MATCH se codifican como el XOR del valor de byte con match_byte es incorrecta; en cambio, se codifican simplemente como su valor de byte, pero utilizando el pseudo-árbol de bits que se acaba de describir y el contexto adicional que aparece en la tabla siguiente.

Los grupos de variables de probabilidad utilizados en LZMA son los siguientes:

Formato LZMA2

El contenedor LZMA2 admite múltiples ejecuciones de datos LZMA comprimidos y datos sin comprimir. Cada ejecución comprimida de LZMA puede tener una configuración y un diccionario LZMA diferentes. Esto mejora la compresión de archivos parcial o totalmente incompresibles y permite la compresión y descompresión multiproceso al dividir el archivo en ejecuciones que se pueden comprimir o descomprimir de forma independiente en paralelo. Las críticas a los cambios de LZMA2 con respecto a LZMA incluyen que los campos de encabezado no están cubiertos por los CRC y que la descompresión paralela no es posible en la práctica. [6]

El encabezado LZMA2 consta de un byte que indica el tamaño del diccionario:

Los datos LZMA2 constan de paquetes que comienzan con un byte de control, con los siguientes valores:

Los bits 5-6 para los fragmentos LZMA pueden ser:

Los restablecimientos de estado de LZMA provocan el restablecimiento de todos los estados de LZMA excepto el diccionario y, específicamente:

Los fragmentos sin comprimir constan de:

Los fragmentos de LZMA constan de:

Formatos xz y 7z

El formato . xz , que puede contener datos LZMA2, está documentado en tukaani.org , [10] mientras que el formato de archivo . 7z, que puede contener datos LZMA o LZMA2, está documentado en el archivo 7zformat.txt contenido en el LZMA SDK. [11]

Implementación de referencia de 7-Zip

La implementación de LZMA extraída de 7-Zip está disponible como LZMA SDK. Originalmente, tenía licencia dual, tanto GNU LGPL como Common Public License , [12] con una excepción especial adicional para binarios vinculados, pero Igor Pavlov la colocó en el dominio público el 2 de diciembre de 2008, con el lanzamiento de la versión 4.62. [11]

La compresión LZMA2, que es una versión mejorada de LZMA, [13] es ahora el método de compresión predeterminado para el formato .7z, a partir de la versión 9.30 del 26 de octubre de 2012. [14]

La biblioteca de compresión de código abierto de referencia LZMA se escribió originalmente en C++, pero se ha adaptado a ANSI C , C# y Java . [11] También existen enlaces de Python de terceros para la biblioteca C++, así como adaptaciones de LZMA a Pascal , Go y Ada . [15] [16] [17] [18]

La implementación de 7-Zip utiliza varias variantes de cadenas hash , árboles binarios y árboles Patricia como base para su algoritmo de búsqueda de diccionario.

Además de LZMA, el SDK y 7-Zip también implementan múltiples filtros de preprocesamiento destinados a mejorar la compresión, que van desde la codificación delta simple (para imágenes) y BCJ para código ejecutable. También proporciona otros algoritmos de compresión utilizados en 7z.

El código de solo descompresión para LZMA generalmente se compila en alrededor de 5 KB, y la cantidad de RAM requerida durante la descompresión está determinada principalmente por el tamaño de la ventana deslizante utilizada durante la compresión. El tamaño pequeño del código y la sobrecarga de memoria relativamente baja, particularmente con longitudes de diccionario más pequeñas, y el código fuente gratuito hacen que el algoritmo de descompresión LZMA sea adecuado para aplicaciones integradas .

Otras implementaciones

Además de la implementación de referencia 7-Zip, los siguientes admiten el formato LZMA.

LZHAM

LZHAM (LZ, Huffman, Arithmetic, Markov) es una implementación similar a LZMA que intercambia el rendimiento de compresión por índices muy altos y un mayor rendimiento de descompresión. Su autor la colocó en el dominio público el 15 de septiembre de 2020. [22]

Referencias

  1. ^ Igor Pavlov ha afirmado varias veces en SourceForge que el algoritmo es su propia creación. (19 de febrero de 2004). "¿Cuál es la especificación de LZMA?". Archivado desde el original el 9 de noviembre de 2012. Consultado el 16 de junio de 2013 .
  2. ^ de Lasse Collin (31 de mayo de 2005). "Una evaluación comparativa rápida: Gzip vs. Bzip2 vs. LZMA" . Consultado el 21 de octubre de 2015 .- El puerto Unix LZMA finalmente fue reemplazado por xz, que presenta una compresión mejor y más rápida; desde aquí sabemos que incluso el puerto Unix LZMA era mucho mejor que gzip y bzip2.
  3. ^ Klausmann, Tobias (8 de mayo de 2008). «Comparación de Gzip, Bzip2 y Lzma». Blog de un animal Alfa . Archivado desde el original el 6 de enero de 2013. Consultado el 16 de junio de 2013 .
  4. ^ Igor Pavlov (2013). «Formato 7z» . Consultado el 16 de junio de 2013 .
  5. ^ Mahoney, Matt. "Explicación de la compresión de datos" . Consultado el 13 de noviembre de 2013 .
  6. ^ ab Antonio Diaz Diaz. "El formato Xz es inadecuado para el archivo a largo plazo" . Consultado el 20 de julio de 2018 .
  7. ^ abcd "Especificación LZMA.7z en LZMA SDK". 7-zip.org .
  8. ^ ab "Formato de flujo Lzip". Manual de Lzip . Consultado el 14 de noviembre de 2019 .
  9. ^ Collin, Lasse; Pavlov, Igor. "lib/xz/xz_dec_lzma2.c" . Consultado el 16 de junio de 2013 .
  10. ^ "El formato de archivo .xz". 2009-08-27 . Consultado el 2013-06-16 .
  11. ^ abc Igor Pavlov (2013). «LZMA SDK (Software Development Kit)» . Consultado el 16 de junio de 2013 .
  12. ^ "Explorar /LZMA SDK/4.23". SourceForge . Consultado el 12 de febrero de 2014 .
  13. ^ "Inno Setup Help". jrsoftware.org . Consultado el 16 de junio de 2013. LZMA2 es una versión modificada de LZMA que ofrece una mejor relación de compresión para datos no comprimibles (los datos aleatorios se expanden aproximadamente un 0,005 %, en comparación con el 1,35 % con LZMA original) y, opcionalmente, puede comprimir varias partes de archivos grandes en paralelo, lo que aumenta considerablemente la velocidad de compresión pero con una posible reducción de la relación de compresión.
  14. ^ "HISTORIA del 7-Zip". 26 de octubre de 2012. Consultado el 16 de junio de 2013 .
  15. ^ Bauch, Joachim (7 de abril de 2010). «PyLZMA: enlaces de Python independientes de la plataforma para la biblioteca de compresión LZMA» . Consultado el 16 de junio de 2013 .
  16. ^ Birtles, Alan (13 de junio de 2006). "Ayuda para programación: Pascal LZMA SDK" . Consultado el 16 de junio de 2013 .
  17. ^ Vieru, Andrei (28 de junio de 2012). «Paquete compress/lzma para Go 1». Archivado desde el original el 21 de septiembre de 2016. Consultado el 16 de junio de 2013 .
  18. ^ "Zip-Ada".
  19. ^ Guillem Jover. "Aceptado dpkg 1.17.0 (fuente amd64 all)". Control de calidad de paquetes Debian . Consultado el 21 de octubre de 2015 .
  20. ^ Díaz, Díaz. "Puntos de referencia de LZIP". LZIP (nongnu).
  21. ^ "¿Qué es un archivo Zipx?". WinZip.com . Consultado el 14 de marzo de 2016 .
  22. ^ "LZHAM – Códec de compresión de datos sin pérdida". Richard Geldreich. LZHAM es un códec de compresión de datos sin pérdida escrito en C/C++ con una relación de compresión similar a LZMA pero con una velocidad de descompresión entre 1,5 y 8 veces más rápida.

Enlaces externos