LZ77 y LZ78

LZ77 y LZ78 son dos algoritmos para la compresión de datos sin pérdida ofrecidos por Abraham Lempel y Jacob Ziv en 1977 y 1978 (de ahí su nombre). Estos dos algoritmos sientan las bases para la mayoría de los algoritmos de compresión de diccionario , hasta tal punto que comúnmente hablamos de algoritmo LZ para designar un algoritmo de compresión de diccionario. Estos algoritmos se basan esencialmente en una medida de complejidad para secuencias de longitud finita, la complejidad de Lempel-Ziv .

LZ77

Principio

LZ77 es un algoritmo de compresión de diccionario que utiliza una ventana deslizante; los patrones que ya se encuentran en la ventana se reemplazan por una referencia cuando aparecen por primera vez (normalmente, por un par (distancia, longitud) ).

Por extensión, LZ77 también se usa para denotar la familia de algoritmos de compresión de diccionario usando una ventana deslizante, como LZSS y LZMA .

Descripción del algoritmo LZ77

Compresión

Dada una secuencia S a comprimir, primero se escribe en forma de varios componentes yuxtapuestos S i . Para hacer esto, elegimos un entero L S que será la longitud máxima de un S i y un entero n> L S que será el tamaño del búfer. Inicializamos los n-Ls caracteres del búfer con ceros y completamos el búfer con los primeros caracteres L S de S.

El número entero n-Ls es el tamaño de la ventana deslizante (inicializada con ceros como se indicó anteriormente). Para encontrar el S i , en cada iteración, se lleva a cabo una producción exhaustiva de la subsecuencia más larga posible de S tomando el contenido de la ventana deslizante como prefijo, con aquí la restricción de que la longitud de la secuencia producida no puede exceder Ls.

Después de inicializar la ventana a cero y aplicar este proceso de producción, obtenemos la secuencia S 1 de longitud L 1 <Ls luego arrastramos la ventana quitando los primeros caracteres L 1 de la ventana deslizante del búfer e ingresando en el búfer el siguiendo los caracteres L 1 de S. Este proceso se repite (producción luego deslizamiento de la ventana) para encontrar el otro S i hasta llegar al final de la secuencia S.

Esta descomposición divide S en forma de componentes como en el proceso de cálculo de la complejidad de Lempel-Ziv .

En cada paso i, después de haber encontrado S i mediante un proceso de producción, se le asigna una palabra de código que será su representación en el archivo comprimido. Esta palabra de código no es más que el triplete correspondiente (posición, longitud, carácter).

Por tanto, cada S i está codificado por un triplete C i, 1 C i, 2 C i, 3 y se representará así en el archivo comprimido. Por tanto, el modo de representación es el siguiente:

C i, 1 es la representación base α (siendo α el tamaño del alfabeto de los caracteres de S) de p i -1, con p i el índice en la ventana deslizante donde la copia que corresponde a S i (p i es el puntero para la producción de S i ).
C i, 2 es la representación base α de L i - 1 (la duración de la producción en esta etapa)
C i, 3 es el último carácter de S i

Este algoritmo está estrechamente relacionado con el cálculo de complejidad de Lempel-Ziv . Después de haber precedido a S por nL S ceros, de hecho solo descomponemos S en componentes S i (que reemplazamos por su palabra de código) tomando, en cada paso, el contenido de la ventana deslizante como prefijo y luego teniendo una longitud máxima L S fijo para todos los componentes.

Dado que p i es un índice que pertenece al prefijo (aquí, la ventana deslizante), está entre 1 y nL S y se puede representar en base α mediante caracteres α (nL S ) . Del mismo modo, L i está delimitado por L S , necesitamos caracteres α (L S ) para representar L i -1. C i, siendo 3 un solo carácter, cada S i estará representado en el archivo comprimido por L C = α (nL S ) + α (L S ) + 1 caracteres. $\ lceil \ log$ $\ rceil$ $\ lceil \ log$ $\ rceil$ $\ lceil \ log$ $\ rceil$ $\ lceil \ log$ $\ rceil$

Descompresión

La descompresión es muy similar a la compresión.

Inicialización:

usamos una ventana de tamaño nL S que se inicializa con ceros,
recuperamos p i - 1 (y por lo tanto p i ) en los primeros caracteres α (nL S ) de C i (C i, 1 ), $\ lceil \ log$ $\ rceil$
los siguientes caracteres α (L S ) (C i, 2 ) dan el valor de L i - 1. $\ lceil \ log$ $\ rceil$

Después de la inicialización, en cada paso i repetimos L i -1 veces el siguiente proceso:

copiamos el carácter que está en el índice p i al final de la ventana,
luego arrastramos la ventana hacia la derecha para resaltar su primer carácter e ingresamos el carácter que se acaba de copiar en la ventana.

Dado que los primeros caracteres L i - 1 de S i son solo una copia de la parte de la ventana que comienza en el índice p i , recuperamos mediante el proceso anterior los primeros caracteres L i -1 de S i . En este punto, solo nos falta el último carácter de S i, que no es más que el último carácter (C i, 3 ) de C i .

Esto conduce a la última fase del paso i que consiste en:

copie el último carácter de C i (que es el último carácter de S i ) al final de la ventana antes de realizar un último desplazamiento a la derecha, de un carácter, de la ventana.

Obtenemos así S i mediante la recuperación de la L i últimos caracteres de la ventana. Después de haber aplicado este proceso a todas las palabras de código C i , se obtiene la secuencia S mediante la concatenación de S i .

Ejemplo

Compresión / descompresión de una secuencia mediante el algoritmo LZ77

Aplicamos el algoritmo de compresión a la secuencia ternaria

S = 001010210210212021021200

cuyo alfabeto A = {0,1,2} tiene α = 3 caracteres.

Tomamos n = 18 y L S = 9.

Comenzamos calculando L C que es igual a 5 (nL S = 9 y ). $\ lceil \ log _ {3} 9 \ rceil = 2$

Compresión:

Paso 0. Inicialización del búfer:

Tenemos, en el búfer de tamaño n = 18, como se explicó anteriormente, nL S = 9 ceros seguidos de L S = 9 primeros caracteres de S (cf. Imagen 1).

Etapa 1.

En este ejemplo, cualquier índice de la ventana deslizante podría tomarse como p 1 (la coincidencia más larga es 00 cualquiera que sea el puntero inicial), elegimos p 1 = 9 (cf. Image2_lz77)

Por tanto, obtenemos S 1 = 001; L 1 = 3, lo que da:

C 1,1 = 22 (representación en base 3 de p 1 -1 con 3 (18 - 9) = 2 caracteres) $\ lceil \ log$ $\ rceil$
C 1,2 = 02 (representación en base 3 de L 1 - 1 con 3 (9) = 2 caracteres) $\ lceil \ log$ $\ rceil$
C 1,3 = 1 (el último carácter de S 1 )

Luego arrastramos la ventana para mostrar L 1 = primeros 3 caracteres e ingresamos los siguientes 3 caracteres de S en el búfer (cf. Image3_lz77).

2do paso.

Luego procedemos al cálculo de C 2 (código correspondiente a S 2 ): Tomamos p 2 = 8 (que hace posible tener la correspondencia más larga) con L 2 = 4 y S2 = 0102. Al proceder de la misma manera que para S 1 , obtenemos C 2 = 21102 (cf. Image4_lz77).

Continuamos de esta manera hasta el final de la secuencia para encontrar C 3 = 20212 y C 4 = 02220.

Después de la compresión, obtenemos para S la secuencia comprimida:

22021 21102 20212 02220

Descompresión:

Descomprimimos S de la siguiente manera:

descomprimimos para que el C i obtenga el S i
concatenamos estos S i para obtener S.

Para C 1 = 22021, tenemos:

p 1 = 9 (C 1,1 = 22, los primeros 2 caracteres de C 1 , representa 8 en base 3, por lo tanto p 1 = 8 + 1 = 9),
L 1 = 3 (C 1,2 = 02, los siguientes 2 caracteres de C 1 , representan 2 en base 3, por lo tanto L 1 = 2 + 1 = 3),
el último carácter C 1,3 = 1 de C 1 es el último carácter de la palabra S 1 .

El proceso de descompresión presentado anteriormente se aplica a C 1 (cf. decompression_lz77). Por tanto, encontramos S 1 = 001.

Procedemos de la misma manera, en orden, para los C i que quedan.

Limites y usos

LZ77 tiene algunos defectos, en particular, si no se encuentra una cadena en el diccionario, el símbolo a comprimir se codifica por "posición = 0", "longitud = 0", "nuevo símbolo", es decir, ocupa 3 bytes. en lugar de solo uno en el archivo original. Este defecto se elimina en la variante LZSS .

El algoritmo LZ77 se utiliza en particular en el algoritmo de desinflado (antes de la codificación Huffman ) y para comprimir archivos en el sistema de archivos NTFS de Windows .

LZ78

LZ78 es un algoritmo de compresión de diccionario (publicado en (en) " Compresión de secuencias individuales mediante codificación de tasa variable " , Transacciones IEEE sobre teoría de la información ,Septiembre de 1978) utilizando un diccionario global (y ya no una ventana), construido de la misma manera por el compresor y el descompresor, respectivamente, para compresión y descompresión. Esto evita el problema principal de su predecesor (LZ77) que no puede encontrar una cadena de caracteres si está fuera de la ventana.

Por extensión, LZ78 también se usa para denotar la familia de algoritmos de compresión de diccionario usando un diccionario implícito, como Lempel-Ziv-Welch .

LZ78 ha tenido menos éxito que LZ77, por razones de eficiencia y porque ha sido protegido por una patente de software en los Estados Unidos.

Ver también

comprimir : un programa que utiliza el algoritmo Lempel-Ziv-Welch .

Referencias

NTFS