Algoritmo de la cadena Lempel-Ziv-Markov

El algoritmo de cadena Lempel-Ziv-Markov (LZMA) es un algoritmo utilizado para realizar compresión de datos sin pérdidas. Ha estado en desarrollo desde 1996 o 1998 por Igor Pavlov 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 mayor que bzip2) y un tamaño de diccionario de compresión variable (hasta 4 GB), sin dejar de ser manteniendo una velocidad de descompresión similar a otros algoritmos de compresión comúnmente utilizados.

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 arbitrariamente escalable y compresión eficiente de datos que es parcialmente incompresible.

Descripción general

LZMA utiliza un algoritmo de compresión de diccionario (una variante de LZ77 con tamaños de diccionario enormes 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 encuentra coincidencias utilizando sofisticadas estructuras de datos de diccionario y produce un flujo de símbolos literales y referencias de frases, que el codificador de rango codifica bit a bit: son posibles muchas codificaciones y se utiliza un algoritmo de programación dinámica para seleccionar una óptimo bajo ciertas aproximaciones.

Antes de LZMA, la mayoría de los modelos de codificador se basaban exclusivamente en bytes (es decir, codificaban cada bit utilizando solo una cascada de contextos para representar las dependencias de 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 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 utiliza 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.

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 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 la documentación de lzip como la de LZMA SDK describen este formato de transmisión.

Hay 7 tipos de paquetes:

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 reinsertan al frente, para evitar entradas repetidas inútiles, mientras que MATCH simplemente agrega la distancia al frente incluso si ya está presente en la lista y SHORTREP y LONGREP[0] no modifican 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 puntos hasta el 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, de mayor a menor significado, dos bits dependiendo del 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 (los intervalos de distancia 0-3 codifican directamente distancias 0-3).

Detalles del algoritmo de descompresión

Parece que no existe ninguna especificación completa en lenguaje natural del formato comprimido, aparte de la que se intenta en el siguiente texto.

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 del cual se pueden deducir con relativa facilidad los detalles de los algoritmos LZMA y LZMA2: por lo tanto, aunque citar el código fuente como referencia no es lo ideal, cualquier El programador debería poder comprobar 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 basado en el contexto es invocada por el algoritmo LZMA que le transmite una referencia al "contexto", que consiste en la variable de 11 bits sin firmar Prob (típicamente implementado utilizando un tipo de datos de 16 bits) que representa la probabilidad predicha del bit siendo 0, que es leído y actualizado por el decodificador de rango (y debe ser inicializado a 210{displaystyle 2^{10}, representando 0,5 probabilidad).

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 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 rango en 2³² − 1 y código al valor de 32 bits que comienza en el segundo byte del flujo interpretado como big-endian; el primer byte de la secuencia se ignora por completo.

La normalización procede de esta manera:

1. Cambio ambos rango y código izquierda por 8 bits
2. Lea un byte del flujo comprimido
3. Establecer los 8 bits menos significativos de código al valor byte leído

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

1. Si rango es menos que 224{displaystyle 2^{24}, realizar la normalización
2. Set límites a ⌊ ⌊ range/211⌋ ⌋ × × prob{displaystyle lfloor range/2^{11}rfloor times prob}
3. Si código es menos que límites:
   1. Set rango a límites
   2. Set Prob a Prob + ⌊ ⌊ 211− − prob⌋ ⌋ /25{displaystyle lfloor 2^{11}-probrfloor /2^{5}
   3. Paso de retorno 0
4. De lo contrario (si código es mayor o igual al límites):
   1. Set rango a rango − límites
   2. Set código a código − límites
   3. Set Prob a prob− − ⌊ ⌊ prob/25⌋ ⌋ {displaystyle prob-lfloor prob/2 {5}rfloor }
   4. Paso de retorno 1

La decodificación de un bit con rango de probabilidad fija se realiza de esta manera:

1. Si rango es menos que 224{displaystyle 2^{24}, realizar la normalización
2. Set rango a ⌊ ⌊ range/2⌋ ⌋ {displaystyle lfloor range/2rfloor }
3. Si código es menos que rango:
   1. Paso de retorno 0
4. De lo contrario (si código es mayor o igual que rango):
   1. Set código a código − rango
   2. Paso de retorno 1

La implementación del kernel de Linux de decodificación de probabilidad fija en rc_direct(), por razones de rendimiento, no incluye una rama condicional, sino que resta rango de código incondicionalmente. El bit de signo resultante se utiliza para decidir el bit que se devolverá y para generar una máscara que se combina con el código y se agrega al rango.

Tenga en cuenta que:

1. La división por 211{displaystyle 2^{11} cuando computación límites y el funcionamiento del suelo se hace 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 rangos basados en contextos con ninguna Prob valor, debido al hecho de que la decodificación de rango basado en el contexto descarta los 11 bits inferiores de rango antes de multiplicarse por Prob como acaba de describir, mientras que la probabilidad fija decodificación sólo 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 árbol de bits, árbol de bits inverso y enteros 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 límite, se proporciona una matriz de (límite − 1) variables de probabilidad de 11 bits. que están organizados conceptualmente como los nodos internos de un árbol binario completo con hojas límite.

La decodificación de árbol de bits no inversa funciona manteniendo un puntero al árbol de variables, que comienza en la raíz. Siempre que el puntero no apunte a una hoja, se decodifica un bit usando la variable indicada por el puntero y el puntero se mueve hacia los hijos izquierdo o derecho 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.

Por lo tanto, la decodificación de árbol de bits no inverso ocurre 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 son potencias de dos, aunque LZMA no no hacer uso de esto).

En cambio, la decodificación inversa de árbol de bits 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 una potencia de dos límite e invertir el último log₂(límite ) bits del resultado.

En la función rc_bittree en el kernel de Linux, los números enteros en realidad se devuelven en el [límite, 2 × limit) (con limit agregado al valor conceptual), y la variable en el índice 0 de la matriz no se utiliza, mientras que la del índice 1 no se utiliza. la raíz y los índices secundarios izquierdo y derecho se calculan como 2i y 2i + 1. La función rc_bittree_reverse en su lugar, agrega números enteros en el rango [0, limit) a una variable proporcionada por la persona que llama, donde limit está representado 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 la decodificación de bits de probabilidad fija repetidamente, leyendo los bits del más al menos significativo.

Configuración LZMA

El decodificador LZMA está configurado mediante un parámetro lclppb "properties" byte 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 partes altas del byte anterior para utilizar como un contexto para la codificación literal (el valor predeterminado utilizado por el SDK LZMA 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 el SDK LZMA es 0)
• pb es el número de bits bajos de la posición del diccionario para incluir en pos_state (el valor predeterminado utilizado por el SDK LZMA es 2)

En transmisiones que no sean LZMA2, lc no debe ser mayor que 8, y lp y pb no deben ser mayores que 4. En transmisiones 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 las "propiedades" byte seguido del tamaño del diccionario little-endian de 32 bits en bytes. En LZMA2, el byte de propiedades se puede cambiar opcionalmente al inicio 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

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.

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

El valor estado se basa conceptualmente en cuál de los patrones de la siguiente tabla coincide con los últimos 2 a 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.

Los valores pos_state y literal_pos_state constan respectivamente de pb y lp (hasta 4, desde el encabezado LZMA o 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 potencia grande 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 del lc (hasta 4, del encabezado LZMA o del 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 encontrado 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 de 0 a 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 del bit más significativo 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 en caso contrario es 0; la elección entre 1 o 2 valores 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 dependiendo del valor literal_bit_mode en la posición del siguiente bit a decodificar después del contexto del árbol de bits indicado por el nodo.

La afirmación, encontrada en algunas fuentes, de que los literales después de *MATCH están codificados como el XOR del valor del 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 se enumera en la siguiente tabla.

Los grupos de variables de probabilidad utilizados en LZMA son aquellos:

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 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 sobre LZMA incluyen que los campos de encabezado no están cubiertos por los CRC, y la descompresión paralela no es posible en la práctica.

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 2^{v/2 + 12} tamaño del diccionario
• Valores extraños menos de 40 indican un 3×2^{()v −1)/2 + 11} tamaño del diccionario
• Los valores superiores a 40 son inválidos

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

• 0 denota el final del archivo
• 1 denota un restablecimiento de diccionario seguido de un trozo sin comprimir
• 2 denota un pedazo no comprimido sin un reset del diccionario
• 3-0x7f son valores inválidos
• 0x80–0xff denota un pedazo de LZMA, donde los 5 bits más bajos se utilizan como bit 16–20 del tamaño no comprimido menos uno, y el bit 5–6 indica lo que debe ser reseteado

Los bits 5 y 6 para fragmentos LZMA pueden ser:

• 0: nada reajuste
• 1: reajuste del estado
• 2: reajuste del estado, propiedades reiniciar usando propiedades byte
• 3: reajuste del estado, propiedades reiniciadas utilizando propiedades byte, reset del diccionario

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

• El coder de rango
• El estado valor
• Las últimas distancias para repetidos partidos
• Todas las probabilidades LZMA

Los fragmentos sin comprimir constan de:

• Un valor de 16 bits de gran fin de codificación del tamaño de los datos menos uno
• Los datos para ser copiados literales en el diccionario y la salida

Los fragmentos LZMA constan de:

• Un valor de 16 bits de gran fin de codificación de los bajos 16 bits del tamaño no comprimido menos uno
• Un valor de 16 bits de gran fin de codificación del tamaño comprimido menos uno
• Un byte de propiedades/lclppb si el bit 6 en el byte de control se establece
• Los datos comprimidos LZMA, comenzando por los 5 bytes (de los cuales se ignora el primero) se utilizaron para inicializar el coder de rango (que se incluyen en el tamaño comprimido)

Formatos Xz y 7z

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

Detalles del algoritmo de compresión

Al igual que en la situación del formato de descompresión, no parece existir ninguna 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, que parece ser el más legible entre varias reescrituras del 7-zip original utilizando los mismos algoritmos: nuevamente, aunque citar el código fuente como referencia no es lo ideal, cualquier programador debería poder comprobar las siguientes afirmaciones 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 genera 0 como el primer byte que el descompresor ignora y codifica el límite inferior del rango (que es importante para los bytes finales).

El codificador xz utiliza una variable de 33 bits sin signo llamada baja (normalmente implementada como un entero de 64 bits, inicializada en 0), una variable de 32 bits sin signo llamada rango (inicializada en 2³² − 1), una variable de 8 bits sin signo llamada cache (inicializada en 0) y una variable sin signo llamada cache_size que debe ser lo suficientemente grande como para almacenar el tamaño sin comprimir (inicializado en 1, generalmente implementado como un entero de 64 bits).

Las variables cache/cache_size se utilizan para manejar correctamente los acarreos y representan un número definido por una secuencia big-endian que comienza con cache valor, y seguido de cache_size 0xff bytes, que se ha desplazado fuera del registro bajo, pero aún no 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 cache y low se inicializan en 0 y la implementación del codificador; el decodificador xz ignora este byte.

La normalización procede de esta manera:

1. Si bajo es menos que (232− − 224{displaystyle 2^{32}-2}{24}):
   1. Salida del byte almacenado en cache al flujo comprimido
   2. Producto cache_size − 1 bytes con valor 0xff
   3. Set cache a bits 24-31 de bajo
   4. Set cache_size a 0
2. Si bajo es mayor o igual que 232{displaystyle 2^{32}:
   1. Salida del byte almacenado en cache más uno a la corriente comprimida
   2. Producto cache_size − 1 bytes con valor 0
   3. Set cache a bits 24-31 de bajo
   4. Set cache_size a 0
3. Incremento cache_size
4. Set bajo a los 24 bits más bajos de bajo desplazado a la izquierda por 8 bits
5. Set rango a rango desplazado a la izquierda por 8 bits

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

1. Si rango es menos que 224{displaystyle 2^{24}, realizar la normalización
2. Set límites a ⌊ ⌊ range/211⌋ ⌋ × × prob{displaystyle lfloor range/2^{11}rfloor times prob}
3. Si encogiendo un 0 bit:
   1. Set rango a límites
   2. Set Prob a prob+⌊ ⌊ 211− − prob⌋ ⌋ /25{displaystyle prob+lfloor 2^{11}-probrfloor /2^{5}
4. De lo contrario (si se codificación un poco):
   1. Set rango a rango − límites
   2. Set baja a baja + límites
   3. Set Prob a prob− − ⌊ ⌊ prob/25⌋ ⌋ {displaystyle prob-lfloor prob/2 {5}rfloor }

La codificación de un bit con rango de probabilidad fija se realiza de esta manera:

1. Si rango es menos que 224{displaystyle 2^{24}, realizar la normalización
2. Set rango a ⌊ ⌊ range/2⌋ ⌋ {displaystyle lfloor range/2rfloor }
3. Si encogiendo un poco:
   1. Set bajo a bajo + rango

La rescisión se produce de esta manera:

1. Realizar normalización 5 veces

La codificación de árbol de bits se realiza como la decodificación, excepto que los valores de bits se toman del número entero de entrada que se va a codificar en lugar del resultado de las funciones de decodificació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 en diccionario

El codificador debe poder localizar rápidamente coincidencias en el diccionario. Dado que LZMA utiliza diccionarios muy grandes (potencialmente del orden de gigabytes) para mejorar la compresión, simplemente 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", está parametrizado por una constante N que puede ser 2, 3 o 4, que generalmente se elige de modo que 2^8×N es 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 depósitos contiene la última posición donde los primeros k bytes se cifran en el valor hash asociado con ese depósito 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 cuyos primeros N bytes tienen el mismo valor del primer 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 que se ha atravesado un número predefinido de nodos de la cadena hash, o cuando las cadenas hash "se ajustan", lo que indica que se ha alcanzado la parte de la entrada que se ha sobrescrito en el diccionario.

Las coincidencias de tamaño inferior a N se encuentran simplemente mirando la tabla hash correspondiente, que contiene la última coincidencia, si la hay, o una cadena que obtiene 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 menor rendimiento.

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 depósito de la tabla hash (algunas implementaciones puede que ni siquiera lo garanticen, porque no inicializan las estructuras de datos).

LZMA utiliza cadenas de Markov, como lo implica "M" en su nombre.

Árboles binarios

El enfoque del árbol binario sigue el enfoque de la cadena hash, excepto que lógicamente utiliza un árbol binario en lugar de una lista vinculada para el encadenamiento.

El árbol binario se mantiene de modo que siempre sea un árbol de búsqueda relativo al orden lexicográfico de los sufijos y un montón máximo para la posición del diccionario (en otras palabras, la raíz es siempre la cadena más reciente y una cadena secundaria). no puede haberse agregado más recientemente que su padre): suponiendo que todas las cadenas estén ordenadas lexicográficamente, estas condiciones claramente determinan de manera única el árbol binario (esto es trivialmente demostrable 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 del árbol.

Patricia lo intenta

Algunos codificadores LZMA antiguos también admitían una estructura de datos basada en los intentos de Patricia, pero desde entonces dicha compatibilidad se ha abandonado porque se consideraba inferior a las otras opciones.

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 óptimo incluso si no es localmente óptimo y, como resultado de esto, La 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 utilizan 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 genera él, con la longitud máxima correspondiente.

Codificador rápido

El codificador rápido XZ (derivado del codificador rápido 7-zip) es el codificador LZMA más corto en el árbol fuente xz.

Funciona así:

1. Realizar búsqueda e inserción combinadas en la estructura de datos del diccionario
2. Si alguna distancia repetida coincide con la longitud al menos Bonita.:
   • Salida de la distancia más utilizada con frecuencia con un paquete REP
3. Si se encontró una coincidencia de longitud al menos Bonita.:
   • Póngalo con un paquete MATCH
4. Establecer el partido principal para el partido más largo
5. Mira el partido más cercano de cada longitud en orden de reducción de longitud, y hasta que no se pueda hacer ningún reemplazo:
   • Reemplazar el partido principal con un partido que es un personaje más corto, pero cuya distancia es inferior a 1/128 la distancia de partido principal actual
6. Establecer la longitud principal del partido a 1 si el partido principal actual es de longitud 2 y distancia al menos 128
7. Si se encontró un partido repetido, y es más corto por la mayoría de 1 carácter que el partido principal:
   • Salida del partido repetido con un paquete REP
8. Si se encontró un partido repetido, y es más corto por 2 caracteres que el partido principal, y la distancia principal del partido es por lo menos 512:
   • Salida del partido repetido con un paquete REP
9. Si se encontró un partido repetido, y es más corto por 3 caracteres que el partido principal, y la distancia principal del partido es por lo menos 32768:
   • Salida del partido repetido con un paquete REP
10. Si el tamaño del partido principal es inferior a 2 (o no hay ningún partido):
    • Salida de un paquete LIT
11. Realizar una búsqueda de diccionario para el siguiente byte
12. Si el byte siguiente es más corto por la mayoría de 1 carácter que el partido principal, con la distancia menos de 1/128 veces la distancia del partido principal, y si la longitud del partido principal es por lo menos 3:
    • Salida de un paquete LIT
13. Si el próximo byte tiene una coincidencia al menos mientras el partido principal, y con menos distancia que el partido principal:
    • Salida de un paquete LIT
14. Si el próximo byte tiene un partido por lo menos un personaje más largo que el partido principal, y tal que 1/128 de su distancia es menos o igual que la distancia principal del partido:
    • Salida de un paquete LIT
15. Si el próximo byte tiene un partido más de un personaje más largo que el partido principal:
    • Salida de un paquete LIT
16. Si cualquier partido repetido es más corto por la mayoría de 1 carácter que el partido principal:
    • Salida de la distancia más utilizada con frecuencia con un paquete REP
17. Salida del partido principal con un paquete MATCH

Codificador normal

El codificador normal XZ (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 partes de la entrada utilizando el resultado de un algoritmo de programación dinámica, donde los subproblemas son encontrar 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 que comienza en el byte que se está comprimiendo.

El tamaño de la porción de la entrada procesada en el algoritmo de programación dinámica se determina como el máximo entre la coincidencia más larga del diccionario y la coincidencia repetida más larga encontrada en la posición inicial (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, el nice_len y se inicia una nueva instancia de problema de programación dinámica en el byte posterior a la salida de la coincidencia.

Las soluciones candidatas a subproblemas se actualizan incrementalmente con codificaciones candidatas, se construyen tomando la solución para una subcadena más corta de longitud L', extendida con todas las "colas" posibles o conjuntos de 1 a 3 paquetes con ciertas restricciones que codifican la entrada en el extremo L' posición. Una vez que se encuentra la solución final de un subproblema, se calcula el estado LZMA y las distancias menos utilizadas, y luego se usan para calcular adecuadamente los tamaños de sus extensiones posteriores a la codificación de rango.

Al final de la optimización de la programación dinámica, se genera 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 aún no está 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:

La razón para no extender 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 LZMA estado como parámetro; por lo tanto, ampliar con múltiples paquetes permite aproximarse mejor a 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 un precio mínimo), donde por "cola" nos referimos a los paquetes que amplían la solución del subproblema más pequeño, que se describen directamente en la siguiente estructura:

Tenga en cuenta que en la implementación de XZ para Java, los miembros optPrev y backPrev se reutilizan para almacenar una lista directa de paquetes con un solo enlace 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, lo que sea menor), entrega cada fragmento al codificador LZMA y luego decide si generar un fragmento LZMA2 LZMA que incluya los datos codificados, o para generar un fragmento LZMA2 sin comprimir, 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 LZMA se restablece solo en el primer bloque, si la persona que llama solicita un cambio de propiedades y cada vez que se genera 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 sólo se reinicia 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 los desplazamientos relativos por otros absolutos que son más repetitivos, o el filtro delta, que reemplaza cada byte con la diferencia entre ellos. 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, 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 de 7-Zip

La implementación LZMA extraída de 7-Zip está disponible como LZMA SDK. Originalmente tenía doble licencia bajo GNU LGPL y Licencia pública común, con una excepción especial adicional para binarios vinculados, 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.

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

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. También hay enlaces de Python de terceros para la biblioteca C++, así como puertos de LZMA a Pascal, Go y Ada.

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 en 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 simple codificación delta (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 gratuito 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 admite el formato LZMA.

• xz: una implementación de streaming que contiene una herramienta de línea de comando similar a gzip, soportando tanto LZMA como LZMA2 en su formato de archivo xz. Hizo su 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). Los sistemas Linux kernel, dpkg y RPM contienen código xz, y muchos distribuidores de software como kernel.org, Debian 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. Cuenta principalmente con un formato de archivo más simple y por lo tanto más fácil recuperación de errores.
• ZIPX: una extensión al formato de compresión ZIP que fue creado por WinZip comenzando con la versión 12.1. También puede utilizar otros métodos de compresión como BZip y PPMd.

LZHAM

LZHAM (LZ, Huffman, Arithmetic, Markov), es una implementación similar a LZMA que intercambia el rendimiento de compresión por proporciones muy altas y un mayor rendimiento de descompresión. Su autor lo puso en el dominio público el 15 de septiembre de 2020.