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 es parcialmente incompresible. [6]
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]
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).
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.
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).
La decodificación de rango de probabilidad fija, en cambio, 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:
La decodificación de rango basada en el contexto de un bit utilizando la variable de probabilidad prob procede de esta manera:
La decodificación de un bit con rango de probabilidad fijo se realiza de esta manera:
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:
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, deteniéndose 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.
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.
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:
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:
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 SDK LZMA. [11]
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 .
Además de la implementación de referencia 7-Zip, los siguientes admiten el formato LZMA.
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]
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 enormemente la velocidad de compresión pero con una posible reducción en la relación de compresión.
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.
