El algoritmo de cadena Lempel-Ziv-Markov ( LZMA ) es un algoritmo que se utiliza para realizar una compresión de datos sin pérdidas . 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 se mantiene una velocidad de descompresión similar a otros algoritmos de compresión de uso común. [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 escalable arbitrariamente y una compresión eficiente de datos que es parcialmente incompresible. Sin embargo, se afirma que es inseguro y menos eficiente que LZMA. [6]
Descripción general
LZMA utiliza un algoritmo de compresión de diccionario (una variante de LZ77 con un gran tamaño de diccionario y soporte especial para distancias de coincidencia utilizadas repetidamente), cuya salida luego se codifica con un codificador de rango , utilizando un modelo complejo para hacer una predicción de probabilidad de cada bit. El compresor de diccionario busca coincidencias utilizando estructuras de datos de diccionario sofisticadas y produce un flujo de símbolos literales y referencias de frases, que el codificador de rango codifica un bit a la vez: son posibles muchas codificaciones y se utiliza un algoritmo de programación dinámica para seleccionar un óptimo bajo ciertas aproximaciones. [7]
Antes de LZMA, la mayoría de los modelos de codificador 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 ofrece mucho mejor compresión 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 diccionario pueden ser y suelen ser mucho más grandes, 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, y cada paquete describe un solo byte o una secuencia LZ77 con su longitud y distancia codificadas implícita o explícitamente. 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 los bits relacionados del mismo campo) en paquetes anteriores del mismo tipo. Tanto el lzip [8] como la documentación del SDK de LZMA describen este formato de flujo. [7]
Hay 7 tipos de paquetes: [8]
Código empaquetado (secuencia de bits) | Nombre del paquete | Descripción del paquete |
---|---|---|
0 + byteCode | ILUMINADO | Un solo byte codificado mediante un codificador de rango binario adaptativo. |
1 + 0 + len + dist | PARTIDO | Una secuencia típica de LZ77 que describe la longitud y la distancia de la secuencia. |
1 + 1 + 0 + 0 | SHORTREP | Una secuencia LZ77 de un byte. La distancia es igual a la última distancia LZ77 utilizada. |
1 + 1 + 0 + 1 + len | LONGREP [0] | Una secuencia LZ77. La distancia es igual a la última distancia LZ77 utilizada. |
1 + 1 + 1 + 0 + len | LONGREP [1] | Una secuencia LZ77. La distancia es igual a la penúltima distancia LZ77 utilizada. |
1 + 1 + 1 + 1 + 0 + len | LONGREP [2] | Una secuencia LZ77. La distancia es igual a la tercera distancia LZ77 utilizada por última vez. |
1 + 1 + 1 + 1 + 1 + len | LONGREP [3] | Una secuencia LZ77. La distancia es igual a la cuarta última distancia LZ77 utilizada. |
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 las distancias más recientes y la vuelven a insertar en el frente, para evitar entradas repetidas inútiles, mientras que MATCH solo agrega la distancia al frente incluso si ya está presente en la lista y SHORTREP y LONGREP [0] no modifique la lista.
La longitud se codifica de la siguiente manera:
Código de longitud (secuencia de bits) | Descripción |
---|---|
0+ 3 bits | La longitud codificada con 3 bits da un rango de longitudes de 2 a 9. |
1 + 0 + 3 bits | La longitud codificada con 3 bits da un rango de longitudes de 10 a 17. |
1 + 1 + 8 bits | La longitud codificada con 8 bits da un rango de longitudes de 18 a 273. |
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 puntos al byte agregado más recientemente en el diccionario.
La codificación de distancia comienza con un "intervalo de distancia" de 6 bits, que determina cuántos bits adicionales se necesitan. Las distancias se decodifican como una concatenación binaria de dos bits, del más al menos significativo, según el intervalo de distancia, algunos bits codificados con una probabilidad fija de 0,5 y algunos bits codificados en contexto, de acuerdo con la siguiente tabla (intervalos de distancia 0-3 codifican directamente distancias 0-3).
Ranura de distancia de 6 bits | 2 bits más altos | 0.5 bits de probabilidad fijos | Bits codificados por contexto |
---|---|---|---|
0 | 00 | 0 | 0 |
1 | 01 | 0 | 0 |
2 | 10 | 0 | 0 |
3 | 11 | 0 | 0 |
4 | 10 | 0 | 1 |
5 | 11 | 0 | 1 |
6 | 10 | 0 | 2 |
7 | 11 | 0 | 2 |
8 | 10 | 0 | 3 |
9 | 11 | 0 | 3 |
10 | 10 | 0 | 4 |
11 | 11 | 0 | 4 |
12 | 10 | 0 | 5 |
13 | 11 | 0 | 5 |
14–62 (par) | 10 | ((ranura / 2) - 5) | 4 |
15–63 (impar) | 11 | (((ranura - 1) / 2) - 5) | 4 |
Detalles del algoritmo de descompresión
No parece existir una especificación completa en lenguaje natural del formato comprimido, aparte de la que se intenta en el siguiente texto.
La descripción a continuación se basa en el decodificador compacto XZ Embedded de Lasse Collin incluido en la fuente del kernel de Linux [9] del cual los detalles de los algoritmos LZMA y LZMA2 se pueden deducir con relativa facilidad: por lo tanto, aunque citar el código fuente como referencia no es ideal, cualquier programador debería poder verificar las siguientes afirmaciones con unas pocas horas de trabajo.
Codificación de rango de bits
Los datos LZMA se decodifican en el nivel más bajo un bit a la vez por el decodificador de rango, en la dirección del decodificador LZMA.
La decodificación de rango basada en el contexto es invocada por el algoritmo LZMA pasándole una referencia al "contexto", que consiste en la variable prob sin signo de 11 bits (generalmente implementada usando un tipo de datos de 16 bits) que representa la probabilidad predicha de que el bit sea 0, que es leído y actualizado por el decodificador de rango (y debe inicializarse a 2 ^ 10, lo que representa una probabilidad de 0.5).
En cambio, la decodificación de rango de probabilidad fija asume una probabilidad de 0,5, pero funciona de manera 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 en el flujo interpretado como big-endian; el primer byte de la secuencia se ignora por completo.
La normalización procede de esta manera:
- Desplaza tanto el rango como el código a la izquierda en 8 bits
- Leer un byte del flujo comprimido
- Establezca los 8 bits de código menos significativos en el valor de 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:
- Si el rango es menor que 2 ^ 24, realice la normalización
- Establecer enlazado al piso ( rango / 2 ^ 11) * prob
- Si el código es menor que limitado :
- Establecer rango para enlazar
- Establezca problema en problema + piso ((2 ^ 11 - problema ) / 2 ^ 5)
- Devolver bit 0
- De lo contrario (si el código es mayor o igual que el límite ):
- Establecer rango en rango - limitado
- Establecer código a código - enlazado
- Establecer problema en problema - piso ( problema / 2 ^ 5)
- Devolver bit 1
La decodificación de rango de probabilidad fija de un bit procede de esta manera:
- Si el rango es menor que 2 ^ 24, realice la normalización
- Establecer rango al piso ( rango / 2)
- Si el código es menor que el rango :
- Devolver bit 0
- De lo contrario (si el código es mayor o igual que el rango ):
- Establecer código en código - rango
- Devolver bit 1
La implementación del kernel de Linux de la decodificación de probabilidad fija en rc_direct, por razones de rendimiento, no incluye una rama condicional, sino que resta el rango del código incondicionalmente y usa el bit de signo resultante para decidir el bit a devolver y para generar un máscara que se combina con el código y se agrega al rango .
Tenga en cuenta que:
- La división por 2 ^ 11 cuando se calcula la operación de límite y 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)
- La decodificación de probabilidad fija no es estrictamente equivalente a la decodificación de rango basada en contexto con cualquier valor de problema , debido al hecho de que la decodificación de rango basada en contexto descarta los 11 bits inferiores del rango antes de multiplicar por problema como se acaba de describir, mientras que la decodificación de probabilidad fija solo descarta el último bit
Rango de codificación de números enteros
El decodificador de rango también proporciona las facilidades de decodificación de árbol de bits, árbol de bits inverso y de probabilidad fija, que se utilizan para decodificar números enteros y generalizar la decodificación de un solo bit descrita anteriormente. Para decodificar enteros sin signo menores que el límite , se proporciona una matriz de ( límite - 1) variables de probabilidad de 11 bits, que se organizan conceptualmente como los nodos internos de un árbol binario completo con hojas límite .
La decodificación de árbol de bits no inverso funciona manteniendo un puntero al árbol de variables, que comienza en la raíz. Siempre que el puntero no apunte a una hoja, un bit se decodifica usando la variable indicada por el puntero, y el puntero se mueve a los hijos de la izquierda o de la derecha dependiendo de 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 inversa 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 permite conceptualmente tener tamaños de rango que no son potencias de dos, aunque LZMA no hace uso de esto).
En su lugar, la decodificación de árbol de bits inversa 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 el mismo número de bits. Es equivalente a realizar una decodificación de árbol de bits no inversa con una potencia de dos límites e invertir los últimos bits log2 ( límite ) del resultado.
En la función rc_bittree en el kernel de Linux, los enteros se devuelven realmente en el rango [ límite , 2 * límite ) (con el límite agregado al valor conceptual), y la variable en el índice 0 en la matriz no se usa, mientras que la que está en el índice 1 es la raíz, y los índices secundarios izquierdo y derecho se calculan como 2 i y 2 i + 1. En su lugar, la función rc_bittree_reverse agrega enteros en el rango [0, límite ) a una variable proporcionada por la persona que llama, donde el límite está implícitamente representado por su logaritmo, y tiene su propia implementación independiente por razones de eficiencia.
La decodificación de números enteros de probabilidad fija simplemente realiza la decodificación de bits de probabilidad fija repetidamente, leyendo los bits desde el más significativo al menos significativo.
Configuración LZMA
El decodificador LZMA está configurado por un byte de "propiedades" lclppb y un tamaño de diccionario. El valor del byte lclppb es lc + lp * 9 + pb * 9 * 5, donde:
- lc es el número de bits altos del byte anterior para usar como contexto para la codificación literal (el valor predeterminado usado por LZMA SDK es 3)
- lp es el número de bits bajos de la posición del diccionario para incluir en literal_pos_state (el valor predeterminado utilizado por LZMA SDK es 0)
- pb es el número de bits bajos de la posición del diccionario que se incluirán en pos_state (el valor predeterminado utilizado por LZMA SDK es 2)
En los flujos que no son LZMA2, lc no debe ser mayor que 8, y lp y pb no deben ser mayores que 4. En los flujos LZMA2, ( lc + lp ) y pb no deben ser mayores que 4.
En el formato de archivo 7-zip LZMA, 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 LZMA, mientras que el tamaño del diccionario se especifica en el encabezado LZMA2 como se describe más adelante.
Contextos de codificación LZMA
El formato de paquete LZMA ya se ha descrito, y esta sección especifica cómo LZMA modela estadísticamente los flujos codificados con 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 introducirlos, se definen algunos valores que se utilizan como índices en estos arreglos multidimensionales.
El valor de estado se basa conceptualmente en cuál de los patrones de la siguiente tabla coincide con los últimos 2-4 tipos de paquetes vistos, y se implementa como un estado de máquina de estado actualizado de acuerdo con la tabla de transición enumerada en la tabla cada vez que se envía un paquete.
El estado inicial es 0 y, por lo tanto, se supone que los paquetes anteriores al comienzo son paquetes LIT.
Expresar | paquetes anteriores | siguiente estado cuando el siguiente paquete es | ||||||
---|---|---|---|---|---|---|---|---|
4to anterior | 3er anterior | 2do anterior | anterior | ILUMINADO | PARTIDO | LONGREP [*] | SHORTREP | |
0 | ILUMINADO | ILUMINADO | ILUMINADO | 0 | 7 | 8 | 9 | |
1 | PARTIDO | ILUMINADO | ILUMINADO | 0 | 7 | 8 | 9 | |
2 | LONGREP [*] | ILUMINADO | ILUMINADO | 0 | 7 | 8 | 9 | |
*PARTIDO | SHORTREP | |||||||
3 | ILUMINADO | SHORTREP | ILUMINADO | ILUMINADO | 0 | 7 | 8 | 9 |
4 | PARTIDO | ILUMINADO | 1 | 7 | 8 | 9 | ||
5 | LONGREP [*] | ILUMINADO | 2 | 7 | 8 | 9 | ||
*PARTIDO | SHORTREP | |||||||
6 | ILUMINADO | SHORTREP | ILUMINADO | 3 | 7 | 8 | 9 | |
7 | ILUMINADO | PARTIDO | 4 | 10 | 11 | 11 | ||
8 | ILUMINADO | LONGREP [*] | 5 | 10 | 11 | 11 | ||
9 | ILUMINADO | SHORTREP | 6 | 10 | 11 | 11 | ||
10 | *PARTIDO | PARTIDO | 4 | 10 | 11 | 11 | ||
11 | *PARTIDO | *REPS | 5 | 10 | 11 | 11 |
Los valores pos_state y literal_pos_state constan respectivamente de pb y lp (hasta 4, del encabezado LZMA o del paquete de propiedades LZMA2) bits menos significativos de la posición del diccionario (el número de bytes codificados desde el último módulo de reinicio del diccionario del tamaño del diccionario). Tenga en cuenta que el tamaño del diccionario es normalmente el múltiplo de una gran potencia de 2, por lo que estos valores se describen de manera equivalente como los bits menos significativos del número de bytes sin comprimir vistos desde el último reinicio del diccionario.
El valor prev_byte_lc_msbs se establece en los bits más significativos de lc (hasta 4, del encabezado LZMA o del paquete de propiedades LZMA2) del byte anterior sin comprimir.
El valor is_REP indica si un paquete que incluye una longitud es LONGREP en lugar de 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 encontrado en el diccionario en la última distancia utilizada); solo se usa 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 era un * MATCH y es la posición de bit más significativa o la más significativa los bits en el literal a codificar / decodificar son iguales a los bits en las posiciones correspondientes en match_byte , mientras que en caso 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 literal / literal de variables 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 según el valor literal_bit_mode en la posición del bit del siguiente bit. para decodificar después del contexto de árbol de bits denotado por el nodo.
La afirmación, que se encuentra en algunas fuentes, de que los literales después de un * MATCH se codifican como el XOR del valor del byte con match_byte es incorrecta; en su lugar, se codifican simplemente como su valor de byte, pero utilizando el pseudo árbol de bits que se acaba de describir y el contexto adicional enumerado en la tabla siguiente.
Los grupos de variables de probabilidad utilizados en LZMA son los siguientes:
Nombre XZ | Nombre del SDK de LZMA | Parametrizado por | Usado cuando | Modo de codificación | Si el bit 0 entonces | Si el bit 1 entonces |
---|---|---|---|---|---|---|
is_match | IsMatch | estado , pos_state | inicio del paquete | un poco | ILUMINADO | *PARTIDO |
is_rep | IsRep | Expresar | después de la secuencia de bits 1 | un poco | PARTIDO | *REPS |
is_rep0 | IsRepG0 | Expresar | después de la secuencia de bits 11 | un poco | SHORTREP / LONGREP [0] | LONGREP [1-3] |
is_rep0_long | IsRep0Long | estado , pos_state | después de la secuencia de bits 110 | un poco | SHORTREP | LONGREP [0] |
is_rep1 | IsRepG1 | Expresar | después de la secuencia de bits 111 | un poco | LONGREP [1] | LONGREP [2/3] |
is_rep2 | IsRepG2 | Expresar | después de la secuencia de bits 1111 | un poco | LONGREP [2] | LONGREP [3] |
literal | Literal | prev_byte_lc_msbs , literal_pos_state , literal_bit_mode [posición de bit], contexto de árbol de bits | después de la secuencia de bits 0 | 256 valores pseudo-árbol de bits | valor de byte literal | |
dist_slot | PosSlot | min ( match_length , 5), contexto de árbol de bits | distancia: inicio | 64 valores de árbol de bits | ranura de distancia | |
dist_special | SpecPos | distance_slot , contexto de árbol de bits inverso | distancia: 4-13 ranuras de distancia | (( intervalo_distancia >> 1) - 1) -bit árbol de bits inverso | pocos bits de distancia | |
dist_align | Alinear | contexto de árbol de bits inverso | distancia: más de 14 ranuras de distancia, después de bits de probabilidad fija | Árbol de bits inverso de 4 bits | pocos bits de distancia | |
len_dec.choice | LenChoice | is_REP | duración del partido: inicio | un poco | 2-9 longitud | 10+ de longitud |
len_dec.choice2 | LenChoice2 | is_REP | longitud de coincidencia: después de la secuencia de bits 1 | un poco | 10-17 de longitud | 18+ de longitud |
len_dec.low | LenLow | is_REP , pos_state , contexto de árbol de bits | longitud de coincidencia: después de la secuencia de bits 0 | Árbol de bits de 8 valores | bits de poca longitud | |
len_dec.mid | LenMid | is_REP , pos_state , contexto de árbol de bits | longitud de coincidencia: después de la secuencia de bits 10 | Árbol de bits de 8 valores | pedazos medios de longitud | |
len_dec.high | LenHigh | is_REP , contexto de árbol de bits | longitud de coincidencia: después de la secuencia de bits 11 | Árbol de bits de 256 valores | pedazos altos de longitud |
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 de LZMA diferentes. Esto mejora la compresión de archivos parcial o completamente incompresibles y permite la compresión multiproceso y la descompresión multiproceso dividiendo el archivo en ejecuciones que se pueden comprimir o descomprimir de forma independiente en paralelo. Las críticas a los cambios de LZMA2 sobre LZMA incluyen campos de encabezado que no están cubiertos por 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:
- 40 indica un tamaño de diccionario de 4 GB - 1
- Incluso los valores inferiores a 40 indican un tamaño de diccionario de 2 v / 2 + 12 bytes
- Los valores impares inferiores a 40 indican un tamaño de diccionario de 3 × 2 ( v - 1) / 2 + 11 bytes
- Los valores superiores a 40 no son válidos
Los datos LZMA2 consisten en paquetes que comienzan con un byte de control, con los siguientes valores:
- 0 denota el final del archivo
- 1 denota un restablecimiento del diccionario seguido de un fragmento sin comprimir
- 2 denota un fragmento sin comprimir sin un reinicio del diccionario
- 3-0x7f son valores inválidos
- 0x80-0xff denota un fragmento LZMA, donde los 5 bits más bajos se utilizan como bit 16-20 del tamaño sin comprimir menos uno, y el bit 5-6 indica lo que se debe restablecer
Los bits 5-6 para trozos LZMA pueden ser:
- 0: nada restablecer
- 1: restablecimiento del estado
- 2: restablecimiento de estado, restablecimiento de propiedades mediante el byte de propiedades
- 3: restablecimiento de estado, restablecimiento de propiedades mediante el byte de propiedades, restablecimiento del diccionario
Los restablecimientos del estado de LZMA provocan un restablecimiento de todos los estados de LZMA excepto el diccionario, y específicamente:
- El codificador de rango
- El valor del estado
- Las últimas distancias para partidos repetidos
- Todas las probabilidades LZMA
Los trozos sin comprimir constan de:
- Un valor big-endian de 16 bits que codifica el tamaño de los datos menos uno
- Los datos que se copiarán literalmente en el diccionario y la salida
Los trozos de LZMA constan de:
- Un valor big-endian de 16 bits que codifica los 16 bits bajos del tamaño sin comprimir menos uno
- Un valor big-endian de 16 bits que codifica el tamaño comprimido menos uno
- Un byte de propiedades / lclppb si se establece el bit 6 en el byte de control
- Los datos comprimidos LZMA, comenzando con los 5 bytes (de los cuales se ignora el primero) utilizados para inicializar el codificador de rango (que se incluyen en el tamaño comprimido)
formatos xz y 7z
La . 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 LZMA SDK. [11]
Detalles del algoritmo de compresión
Similar a la situación del formato de descompresión, no parece existir una especificación completa en lenguaje natural de las técnicas de codificación en 7-zip o xz , aparte de la que se intenta en el siguiente texto.
La siguiente descripción se basa en el codificador XZ para Java de Lasse Collin, [12] que parece ser la más legible entre varias reescrituras del 7-zip original utilizando los mismos algoritmos: de nuevo, aunque citar el código fuente como referencia no lo es ideal, cualquier programador debería poder verificar las afirmaciones a continuación con unas pocas horas de trabajo.
Codificador de rango
El codificador de rango no puede realizar ninguna elección interesante y se puede construir fácilmente basándose en la descripción del decodificador.
La inicialización y la terminación no están completamente determinadas; el codificador xz emite 0 como el primer byte que es ignorado por el descompresor y codifica el límite inferior del rango (lo que importa para los bytes finales).
El codificador xz usa una variable de 33 bits sin signo llamada baja (generalmente implementada como un entero de 64 bits, inicializada a 0), una variable de 32 bits sin signo llamada rango (inicializada a 2 32 - 1), una variable de 8 bits sin signo llamado cache (inicializado a 0), y una variable sin firmar llamada cache_size que necesita ser lo suficientemente grande para almacenar el tamaño sin comprimir (inicializado a 1, típicamente implementado como un entero de 64 bits).
Las variables cache / cache_size se usan para manejar apropiadamente los acarreos, y representan un número definido por una secuencia big-endian que comienza con el valor de la caché , y seguida por cache_size 0xff bytes, que se ha desplazado fuera del registro bajo , pero no aún se ha escrito, porque podría incrementarse en uno debido a un acarreo.
Tenga en cuenta que la salida del primer byte siempre será 0 debido al hecho de que la caché y el nivel bajo se inicializan a 0, y la implementación del codificador; el decodificador xz ignora este byte.
La normalización procede de esta manera:
- Si bajo es menor que (2 ^ 32 - 2 ^ 24):
- Salida del byte almacenado en caché a la secuencia comprimida
- Salida cache_size - 1 bytes con valor 0xff
- Establecer caché en bits 24-31 de bajo
- Establecer cache_size en 0
- Si bajo es mayor o igual que 2 ^ 32:
- Envíe el byte almacenado en la caché más uno a la secuencia comprimida
- Salida cache_size - 1 bytes con valor 0
- Establecer caché en bits 24-31 de bajo
- Establecer cache_size en 0
- Incrementar cache_size
- Establecer bajo a los 24 bits más bajos de baja desplazada a la izquierda en 8 bits
- Establecer rango en rango desplazado a la izquierda en 8 bits
La codificación de rango basada en el contexto de un bit utilizando la variable de probabilidad prob procede de esta manera:
- Si el rango es menor que 2 ^ 24, realice la normalización
- Establecer enlazado al piso ( rango / 2 ^ 11) * prob
- Si codifica un bit 0:
- Establecer rango para enlazar
- Establezca problema en problema + piso ((2 ^ 11 - problema ) / 2 ^ 5)
- De lo contrario (si codifica un 1 bit):
- Establecer rango en rango - limitado
- Establecer bajo a bajo + límite
- Establecer problema en problema - piso ( problema / 2 ^ 5)
La codificación de rango de probabilidad fija de un bit procede de esta manera:
- Si el rango es menor que 2 ^ 24, realice la normalización
- Establecer rango al piso ( rango / 2)
- Si codifica un 1 bit:
- Establecer rango bajo a bajo +
La terminación procede de esta manera:
- Realice la normalización 5 veces
La codificación de árbol de bits se realiza como la descodificación, excepto que los valores de los bits se toman del entero de entrada que se va a codificar en lugar del resultado de las funciones de descodificación de bits.
Para los algoritmos que intentan calcular la codificación con el tamaño de codificación posterior al rango más corto, el codificador también debe proporcionar una estimación de eso.
Estructuras de datos de búsqueda de diccionario
El codificador debe poder ubicar coincidencias rápidamente en el diccionario. Dado que LZMA utiliza diccionarios muy grandes (potencialmente del orden de gigabytes) para mejorar la compresión, el simple hecho de escanear todo el diccionario daría como resultado un codificador demasiado lento para ser prácticamente utilizable, por lo que se necesitan estructuras de datos sofisticadas para admitir búsquedas rápidas de coincidencias.
Cadenas hash
El enfoque más simple, llamado "cadenas hash", se parametriza mediante una constante N que puede ser 2, 3 o 4, que normalmente se elige de modo que 2 ^ (8 × N ) sea mayor o igual que el tamaño del diccionario.
Consiste en crear, para cada k menor o igual a N , una tabla hash indexada por tuplas de k bytes, donde cada uno de los cubos contiene la última posición donde los primeros k bytes se han codificado con el valor hash asociado a ese cubo de la tabla hash. .
El encadenamiento se logra mediante una matriz adicional que almacena, para cada posición del diccionario, la última posición anterior vista cuyo primer N bytes hash al mismo valor de los primeros N bytes de la posición en cuestión.
Para encontrar coincidencias de longitud N o superior, se inicia una búsqueda utilizando la tabla hash de tamaño N y se continúa utilizando la matriz de cadena hash; la búsqueda se detiene después de atravesar un número predefinido de nodos de cadena hash, o cuando las cadenas hash "se envuelven", lo que indica que se ha alcanzado la parte de la entrada que se ha sobrescrito en el diccionario.
En cambio, las coincidencias de tamaño menor que N se encuentran simplemente mirando la tabla hash correspondiente, que contiene la última coincidencia, si la hay, o una cadena que tiene el mismo valor; en el último caso, el codificador no podrá encontrar la coincidencia. Este problema se mitiga por el hecho de que para coincidencias cortas distantes, el uso de múltiples literales puede requerir menos bits, y es relativamente poco probable que haya conflictos de hash en cadenas cercanas; El uso de tablas hash más grandes o incluso tablas de búsqueda directa puede reducir el problema a costa de una mayor tasa de errores de caché y, por lo tanto, un rendimiento más bajo.
Tenga en cuenta que todas las coincidencias deben validarse para verificar que los bytes reales coincidan actualmente en esa posición específica del diccionario, ya que el mecanismo de hash solo garantiza que en algún momento pasado hubo caracteres hash en el índice del cubo de la tabla hash (algunas implementaciones pueden ni siquiera garantizar eso, porque no inicializan las estructuras de datos).
LZMA utiliza cadenas de Markov , como implica "M" en su nombre.
Árboles binarios
El enfoque del árbol binario sigue el enfoque de la cadena hash, excepto que utiliza lógicamente un árbol binario en lugar de una lista enlazada para el encadenamiento.
El árbol binario se mantiene de modo que siempre sea un árbol de búsqueda relativo al orden lexicográfico del sufijo y un montón máximo para la posición del diccionario [13] (en otras palabras, la raíz es siempre la cadena más reciente y una cadena secundaria no puede haber sido agregado más recientemente que su padre): asumiendo que todas las cadenas están ordenadas lexicográficamente, estas condiciones determinan claramente de manera única el árbol binario (esto se puede demostrar trivialmente por inducción sobre el tamaño del árbol).
Dado que la cadena a buscar y la cadena a insertar son las mismas, es posible realizar tanto la búsqueda como la inserción en el diccionario (lo que requiere rotar el árbol) en un solo recorrido de árbol.
Patricia intenta
Algunos codificadores LZMA antiguos también admitían una estructura de datos basada en los intentos de Patricia , pero desde entonces ese soporte se ha eliminado ya que se consideró inferior a las otras opciones. [13]
Codificador LZMA
Los codificadores LZMA pueden decidir libremente qué coincidencia generar, o si ignorar la presencia de coincidencias y literales de salida de todos modos.
La capacidad de recordar las 4 distancias utilizadas más recientemente significa que, en principio, usar una coincidencia con una distancia que se necesitará nuevamente más adelante puede ser globalmente óptima incluso si no es localmente óptima y, como resultado de esto, una compresión LZMA óptima. probablemente requiera conocimiento de toda la entrada y podría requerir algoritmos demasiado lentos para ser utilizables en la práctica.
Debido a esto, las implementaciones prácticas tienden a emplear heurísticas no globales.
Los codificadores xz usan un valor llamado nice_len (el valor predeterminado es 64): cuando se encuentra cualquier coincidencia de longitud al menos nice_len , el codificador detiene la búsqueda y la genera, con la longitud máxima coincidente.
Codificador rapido
El codificador rápido XZ [14] (derivado del codificador rápido de 7 zip) es el codificador LZMA más corto del árbol fuente xz.
Funciona así:
- Realizar búsqueda e inserción combinadas en la estructura de datos del diccionario
- Si alguna distancia repetida coincide con la longitud al menos nice_len :
- Genere la distancia utilizada con más frecuencia con un paquete REP
- Si se encontró una coincidencia de al menos nice_len :
- Salida con un paquete MATCH
- Establezca la coincidencia principal en la coincidencia más larga
- Mire la coincidencia más cercana de cada longitud en orden de longitud decreciente, y hasta que no se pueda hacer un reemplazo:
- Reemplace la coincidencia principal con una coincidencia que sea un carácter más corta, pero cuya distancia sea inferior a 1/128 de la distancia de coincidencia principal actual
- Establezca la longitud de la coincidencia principal en 1 si la coincidencia principal actual tiene una longitud de 2 y una distancia de al menos 128
- Si se encontró una coincidencia repetida, y es más corta en 1 carácter como máximo que la coincidencia principal:
- Salida de la coincidencia repetida con un paquete REP
- Si se encontró una coincidencia repetida, y es más corta en 2 caracteres como máximo que la coincidencia principal, y la distancia de coincidencia principal es de al menos 512:
- Salida de la coincidencia repetida con un paquete REP
- Si se encontró una coincidencia repetida, y es más corta en 3 caracteres como máximo que la coincidencia principal, y la distancia de coincidencia principal es de al menos 32768:
- Salida de la coincidencia repetida con un paquete REP
- Si el tamaño de la coincidencia principal es inferior a 2 (o no hay ninguna coincidencia):
- Salida de un paquete LIT
- Realizar una búsqueda de diccionario para el siguiente byte
- Si el siguiente byte es más corto en 1 carácter como máximo que la coincidencia principal, con una distancia inferior a 1/128 veces la distancia de coincidencia principal, y si la longitud de la coincidencia principal es al menos 3:
- Salida de un paquete LIT
- Si el siguiente byte tiene una coincidencia al menos tan larga como la coincidencia principal y con menos distancia que la coincidencia principal:
- Salida de un paquete LIT
- Si el siguiente byte tiene una coincidencia de al menos un carácter más largo que la coincidencia principal, y tal que 1/128 de su distancia es menor o igual que la distancia de coincidencia principal:
- Salida de un paquete LIT
- Si el siguiente byte tiene una coincidencia de más de un carácter más larga que la coincidencia principal:
- Salida de un paquete LIT
- Si alguna coincidencia repetida es más corta en un carácter como máximo que la coincidencia principal:
- Genere la distancia utilizada con más frecuencia con un paquete REP
- Salida de la coincidencia principal con un paquete MATCH
Codificador normal
El codificador normal XZ [15] (derivado del codificador normal 7-zip) es el otro codificador LZMA en el árbol fuente xz, que adopta un enfoque más sofisticado que intenta minimizar el tamaño de codificación posterior al rango de los paquetes generados.
Específicamente, codifica porciones de la entrada utilizando el resultado de un algoritmo de programación dinámica, donde los subproblemas encuentran la codificación aproximadamente óptima (la que tiene un tamaño mínimo de codificación posterior al rango) de la subcadena de longitud L comenzando en el byte que se está comprimiendo. .
Se determina que el tamaño de la parte de la entrada procesada en el algoritmo de programación dinámica es el máximo entre la coincidencia de diccionario más larga y la coincidencia repetida más larga encontrada en la posición de inicio (que está limitada por la longitud máxima de coincidencia LZMA, 273); Además, si se encuentra una coincidencia más larga que nice_len en cualquier punto del rango recién definido, el algoritmo de programación dinámica se detiene, se genera la solución para el subproblema hasta ese punto, se genera la coincidencia nice_len -sized y una nueva programación dinámica La instancia del problema se inicia en el byte después de la salida de la coincidencia.
Las soluciones candidatas a subproblemas se actualizan gradualmente con codificaciones candidatas, construidas tomando la solución para una subcadena más corta de longitud L ', extendida con todas las posibles "colas", o conjuntos de 1-3 paquetes con ciertas restricciones que codifican la entrada en la posición L' . Una vez que se encuentra la solución final de un subproblema, se calculan el estado LZMA y las distancias menos usadas para él, y luego se usan para calcular apropiadamente los tamaños de codificación posterior al rango de sus extensiones.
Al final de la optimización de la programación dinámica, se emite toda la codificación óptima de la subcadena más larga considerada, y la codificación continúa en el primer byte sin comprimir que no esté ya codificado, después de actualizar el estado LZMA y las distancias menos utilizadas.
Cada subproblema se extiende mediante una secuencia de paquetes que llamamos "cola", que debe coincidir con uno de los siguientes patrones:
1er paquete | Segundo paquete | 3er paquete |
---|---|---|
alguna | ||
ILUMINADO | LONGREP [0] | |
*PARTIDO | ILUMINADO | LONGREP [0] |
La razón para extender no solo con paquetes individuales es que los subproblemas solo tienen la longitud de la subcadena como parámetro por razones de rendimiento y complejidad algorítmica, mientras que un enfoque de programación dinámica óptima también requeriría tener las últimas distancias utilizadas y el estado LZMA como parámetro; por lo tanto, extender con múltiples paquetes permite aproximar mejor la solución óptima y específicamente hacer un mejor uso de los paquetes LONGREP [0].
Los siguientes datos se almacenan para cada subproblema (por supuesto, los valores almacenados son para la solución candidata con precio mínimo ), donde por "cola" nos referimos a los paquetes que extienden la solución del subproblema más pequeño, que se describen directamente a continuación. estructura:
XZ para el nombre del miembro de Java | descripción |
---|---|
precio | cantidad a minimizar: número de bits de codificación posterior al rango necesarios para codificar la cadena |
optPrev | tamaño sin comprimir de la subcadena codificada por todos los paquetes excepto el último |
atrásAnterior | -1 si el último paquete es LIT, 0-3 si es una repetición usando el último número de distancia utilizado 0-3, 4 + distancia si es un MATCH (esto siempre es 0 si prev1IsLiteral es verdadero, ya que el último paquete puede solo sea LONGREP [0] en ese caso) |
prev1IsLiteral | Verdadero si la "cola" contiene más de un paquete (en cuyo caso el anterior al último es un LIT) |
hasPrev2 | Verdadero si la "cola" contiene 3 paquetes (solo válido si prev1IsLiteral es verdadero) |
optPrev2 | tamaño sin comprimir de la subcadena codificada por todos los paquetes excepto la "cola" (solo válido si prev1IsLiteral y hasPrev2 son verdaderos) |
backPrev2 | -1 si el primer paquete en la "cola" es LIT, 0-3 si es una repetición usando el último número de distancia usado 0-3, 4 + distancia si es un MATCH (solo válido si prev1IsLiteral y hasPrev2 son verdaderas) |
repeticiones [4] | los valores de las 4 últimas distancias utilizadas después de los paquetes en la solución (calculados solo después de que se haya determinado la mejor solución del subproblema) |
Expresar | el valor del estado LZMA después de los paquetes en la solución (calculado solo después de que se haya determinado la mejor solución del subproblema) |
Tenga en cuenta que en la implementación de XZ para Java, los miembros optPrev y backPrev se reutilizan para almacenar una lista de paquetes de enlace único hacia adelante como parte de la salida de la solución final.
Codificador LZMA2
El codificador XZ LZMA2 procesa la entrada en fragmentos (de hasta 2 MB de tamaño sin comprimir o 64 KB de tamaño comprimido, el que sea menor), entregando cada fragmento al codificador LZMA y luego decidiendo si generar un fragmento LZMA2 LZMA que incluya los datos codificados , o para generar un fragmento sin comprimir LZMA2, dependiendo de cuál sea más corto (LZMA, como cualquier otro compresor, necesariamente expandirá en lugar de comprimir algunos tipos de datos).
El estado de LZMA se restablece solo en el primer bloque, si la persona que llama solicita un cambio de propiedades y cada vez que se emite un fragmento comprimido. Las propiedades de LZMA se cambian solo en el primer bloque o si la persona que llama solicita un cambio de propiedades. El diccionario solo se restablece en el primer bloque.
Capas de codificación superiores
Antes de la codificación LZMA2, dependiendo de las opciones proporcionadas, xz puede aplicar el filtro BCJ, que filtra el código ejecutable para reemplazar las compensaciones relativas con absolutas que son más repetitivas, o el filtro delta, que reemplaza cada byte con la diferencia entre este y el byte N bytes antes.
La codificación paralela se realiza dividiendo el archivo en fragmentos que se distribuyen en subprocesos y, en última instancia, cada uno se codifica (utilizando, por ejemplo, la codificación de bloque xz) por separado, lo que da como resultado un restablecimiento del diccionario entre fragmentos en el archivo de salida.
Implementación de referencia 7-Zip
La implementación de LZMA extraída de 7-Zip está disponible como LZMA SDK. Originalmente tenía doble licencia tanto bajo la GNU LGPL como con la Common Public License , [16] con una excepción especial adicional para los binarios enlazados, pero Igor Pavlov lo 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, [17] es ahora el método de compresión predeterminado para el formato .7z, comenzando con la versión 9.30 el 26 de octubre de 2012. [18]
La biblioteca de compresión LZMA de código abierto de referencia se escribió originalmente en C ++, pero se ha adaptado a ANSI C , C # y Java . [11] También hay enlaces de Python de terceros para la biblioteca C ++, así como puertos de LZMA a Pascal , Go y Ada . [19] [20] [21] [22]
La implementación de 7-Zip utiliza varias variantes de cadenas hash , árboles binarios y Patricia lo intenta como base para su algoritmo de búsqueda de diccionario.
Además de LZMA, 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 algunos 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 de código pequeño y la sobrecarga de memoria relativamente baja, particularmente con longitudes de diccionario más pequeñas, y el código fuente libre hacen que el algoritmo de descompresión LZMA sea adecuado para aplicaciones integradas .
Otras implementaciones
Además de la implementación de referencia de 7-Zip, lo siguiente es compatible con el formato LZMA.
- xz : una implementación de transmisión que contiene una herramienta de línea de comandos similar a gzip , que admite tanto LZMA como LZMA2 en su formato de archivo xz. Se abrió camino en varios software del mundo similar a Unix con su alto rendimiento (en comparación con bzip2 ) y pequeño tamaño (en comparación con gzip ). [2] El kernel de Linux , los sistemas dpkg y RPM contienen código xz, y muchos distribuidores de software como kernel.org , Debian [23] y Fedora ahora usan xz para comprimir sus versiones.
- lzip : otra implementación de LZMA principalmente para sistemas similares a Unix para competir directamente con xz. [24] Principalmente presenta un formato de archivo más simple y, por lo tanto, una recuperación de errores más fácil.
- ZIPX : una extensión del formato de compresiones ZIP que fue creado por WinZip a partir de la versión 12.1. También puede utilizar otros métodos de compresión como BZip y PPMd . [25]
LZHAM
LZHAM (LZ, Huffman, Arithmetic, Markov), es una implementación similar a LZMA que intercambia el rendimiento de compresión por ratios muy altos y un rendimiento de descompresión más alto. Su autor lo puso en el dominio público el 15 de septiembre de 2020. [26]
Referencias
- ^ Igor Pavlov ha afirmado varias veces en SourceForge que el algoritmo es su propia creación. (19 de febrero de 2004). "¿Especificaciones LZMA?" . Archivado desde el original el 9 de noviembre de 2012 . Consultado el 16 de junio de 2013 .
- ^ a b Lasse Collin (31 de mayo de 2005). "Un punto de referencia rápido: Gzip frente a Bzip2 frente a LZMA" . Consultado el 21 de octubre de 2015 .- El puerto LZMA Unix finalmente fue reemplazado por xz, que presenta una compresión mejor y más rápida; desde aquí sabemos que incluso LZMA Unix Port era mucho mejor que gzip y bzip2.
- ^ Klausmann, Tobias (8 de mayo de 2008). "Gzip, Bzip2 y Lzma comparados" . Blog de un animal Alfa . Archivado desde el original el 6 de enero de 2013 . Consultado el 16 de junio de 2013 .
- ^ Igor Pavlov (2013). "Formato 7z" . Consultado el 16 de junio de 2013 .
- ^ Mahoney, Matt. "Explicación de la compresión de datos" . Consultado el 13 de noviembre de 2013 .
- ^ a b Antonio Diaz Diaz. "Formato Xz inadecuado para archivo a largo plazo" . Consultado el 20 de julio de 2018 .
- ^ a b c d "Especificación LZMA.7z en LZMA SDK" . 7-zip.org .
- ^ a b "Formato de flujo Lzip" . Lzip Manual . Consultado el 14 de noviembre de 2019 .
- ^ Collin, Lasse; Pavlov, Igor. "lib / xz / xz_dec_lzma2.c" . Consultado el 16 de junio de 2013 .
- ^ "El formato de archivo .xz" . 2009-08-27 . Consultado el 16 de junio de 2013 .
- ^ a b c Igor Pavlov (2013). "LZMA SDK (Kit de desarrollo de software)" . Consultado el 16 de junio de 2013 .
- ^ "XZ en Java" . Archivado desde el original el 21 de septiembre de 2016 . Consultado el 16 de junio de 2013 .
- ^ a b Salomón, David (19 de diciembre de 2006). Compresión de datos: la referencia completa (4 ed.). Springer Publishing . pag. 245. ISBN 978-1846286025.
- ^ Collin, Lasse; Pavlov, Igor. "LZMAEncoderFast.java" . Archivado desde el original el 16 de julio de 2012 . Consultado el 16 de junio de 2013 .
- ^ Collin, Lasse; Pavlov, Igor. "LZMAEncoderNormal.java" . Archivado desde el original el 8 de julio de 2012 . Consultado el 16 de junio de 2013 .
- ^ "Explorar / LZMA SDK / 4.23" . Sourceforge . Consultado el 12 de febrero de 2014 .
- ^ "Ayuda de Inno Setup" . 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 alrededor del 0,005%, en comparación con el 1,35% del LZMA original) y, opcionalmente, puede comprimir varias partes de archivos grandes en paralelo, lo que aumenta considerablemente la velocidad de compresión con una posible reducción de la relación de compresión.
- ^ "HISTORIA del 7-Zip" . 2012-10-26 . Consultado el 16 de junio de 2013 .
- ^ 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 .
- ^ Birtles, Alan (13 de junio de 2006). "Ayuda de programación: Pascal LZMA SDK" . Consultado el 16 de junio de 2013 .
- ^ 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 .
- ^ "Zip-Ada" .
- ^ Guillem Jover. "Aceptado dpkg 1.17.0 (fuente amd64 todo)" . Control de calidad del paquete Debian . Consultado el 21 de octubre de 2015 .
- ^ Díaz, Díaz. "Puntos de referencia de Lzip" . LZIP (nongnu).
- ^ "¿Qué es un archivo Zipx?" . WinZip.com . Consultado el 14 de marzo de 2016 .
- ^ "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érdidas 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
- Página de inicio oficial
- Especificación de formato Lzip
- Especificación de formato XZ
- LZMA SDK (kit de desarrollo de software)
- Utilidades LZMA = Utilidades XZ
- Binarios de Windows para XZ Utils
- Compresión de datos, compresores y archivadores