De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda

LZ77 y LZ78 son los dos algoritmos de compresión de datos sin pérdidas publicados en artículos de Abraham Lempel y Jacob Ziv en 1977 [1] y 1978. [2] También se conocen como LZ1 y LZ2 respectivamente. [3] Estos dos algoritmos forman la base de muchas variaciones, incluidas LZW , LZSS , LZMA y otras. Además de su influencia académica, estos algoritmos formaron la base de varios esquemas de compresión ubicuos, incluidos GIF y el algoritmo DEFLATE utilizado enPNG y ZIP .

Ambos son, teóricamente, codificadores de diccionario . LZ77 mantiene una ventana deslizante durante la compresión. Más tarde se demostró que esto era equivalente al diccionario explícito construido por LZ78; sin embargo, solo son equivalentes cuando se pretende descomprimir todos los datos.

Dado que LZ77 codifica y decodifica desde una ventana deslizante sobre los caracteres vistos anteriormente, la descompresión siempre debe comenzar al comienzo de la entrada. Conceptualmente, la descompresión del LZ78 podría permitir el acceso aleatorio a la entrada si se conociera todo el diccionario de antemano. Sin embargo, en la práctica, el diccionario se crea durante la codificación y decodificación creando una nueva frase cada vez que se emite un token. [4]

Los algoritmos fueron nombrados un Hito IEEE en 2004. [5] En 2021 Jacob Ziv recibió la Medalla de Honor IEEE por su participación en su desarrollo. [6]

Eficiencia teórica [ editar ]

En el segundo de los dos artículos que introdujeron estos algoritmos, se analizan como codificadores definidos por máquinas de estados finitos. Se desarrolla una medida análoga a la entropía de información para secuencias individuales (a diferencia de conjuntos probabilísticos). Esta medida da un límite en la tasa de compresión de datos que se puede lograr. Luego se muestra que existen codificadores finitos sin pérdida para cada secuencia que logran este límite a medida que la longitud de la secuencia crece hasta el infinito. En este sentido, un algoritmo basado en este esquema produce codificaciones óptimas asintóticamente. Este resultado se puede probar de forma más directa, como por ejemplo en las notas de Peter Shor . [7]

LZ77 [ editar ]

Los algoritmos LZ77 logran la compresión reemplazando las apariciones repetidas de datos con referencias a una sola copia de esos datos existente anteriormente en el flujo de datos sin comprimir. Una coincidencia está codificada por un par de números denominados par longitud-distancia , que es equivalente a la declaración "cada uno de los siguientes caracteres de longitud es igual a los caracteres exactamente a distancia detrás de él en el flujo sin comprimir". (La distancia a veces se denomina desplazamiento ).

Para detectar coincidencias, el codificador debe realizar un seguimiento de cierta cantidad de los datos más recientes, como los últimos 2 kB , 4 kB o 32 kB. La estructura en la que se guardan estos datos se denomina ventana deslizante , por lo que LZ77 a veces se denomina compresión de ventana deslizante . El codificador necesita mantener estos datos para buscar coincidencias, y el decodificador necesita mantener estos datos para interpretar las coincidencias a las que se refiere el codificador. Cuanto más grande sea la ventana deslizante, más atrás podrá buscar el codificador para crear referencias.

No solo es aceptable, sino que con frecuencia es útil permitir que los pares de longitud y distancia especifiquen una longitud que realmente exceda la distancia. Como comando de copia, esto es desconcertante: "Regrese cuatro caracteres y copie diez caracteres de esa posición a la posición actual". ¿Cómo se pueden copiar diez caracteres cuando solo cuatro de ellos están realmente en el búfer? Al abordar un byte a la vez, no hay problema para atender esta solicitud, porque a medida que se copia un byte, se puede alimentar nuevamente como entrada al comando de copia. Cuando la posición de origen de la copia llega a la posición de destino inicial, se alimentan los datos que se pegaron desde el principio.de la posición de copia de origen. La operación es, por tanto, equivalente a la declaración "copia los datos que te dieron y pégalos repetidamente hasta que quepan". Dado que este tipo de par repite una sola copia de datos varias veces, se puede utilizar para incorporar una forma flexible y sencilla de codificación de longitud de ejecución .

Otra forma de ver las cosas es la siguiente: mientras se codifica, para que el puntero de búsqueda continúe encontrando pares coincidentes más allá del final de la ventana de búsqueda, todos los caracteres de la primera coincidencia en el desplazamiento D y adelante hasta el final de la ventana de búsqueda deben haber coincidido de entrada, y estos son los caracteres (vistos anteriormente) que comprenden una única unidad de ejecución de la longitud L R , que debe ser igual a D . Luego, a medida que el puntero de búsqueda avanza más allá de la ventana de búsqueda y avanza, hasta que el patrón de ejecución se repita en la entrada, los punteros de búsqueda y de entrada estarán sincronizados y coincidirán con los caracteres hasta que se interrumpa el patrón de ejecución. Entonces, los caracteres L se han emparejado en total, L > D , y el código es [D , L , c ].

Tras la decodificación de [ D , L , c ], de nuevo, D = L R . Cuando se leen los primeros caracteres L R en la salida, esto corresponde a una única unidad de ejecución adjunta al búfer de salida. En este punto, se podría pensar que el puntero de lectura solo necesita devolver int ( L / L R ) + (1 si L mod L R ≠ 0) veces al inicio de esa única unidad de ejecución almacenada en búfer, leer los caracteres L R ( o tal vez menos en la última declaración), y repita hasta un total de Lse leen los caracteres. Pero al reflejar el proceso de codificación, dado que el patrón es repetitivo, el puntero de lectura solo necesita seguir en sincronía con el puntero de escritura una distancia fija igual a la longitud de ejecución L R hasta que se hayan copiado L caracteres a la salida en total.

Teniendo en cuenta lo anterior, especialmente si se espera que predomine la compresión de las ejecuciones de datos, la búsqueda de la ventana debe comenzar al final de la ventana y continuar hacia atrás, ya que los patrones de ejecución, si existen, se encontrarán primero y permitirán que la búsqueda termine. absolutamente si se alcanza la longitud máxima actual de la secuencia coincidente, o juiciosamente, si se alcanza una longitud suficiente, y finalmente por la simple posibilidad de que los datos sean más recientes y puedan correlacionarse mejor con la siguiente entrada.

Pseudocódigo [ editar ]

El pseudocódigo es una reproducción de la ventana deslizante del algoritmo de compresión LZ77.

mientras la entrada no esté vacía, haz prefijo: = prefijo de entrada más largo que comienza en la ventana  si el prefijo existe entonces d: = distancia al inicio del prefijo l: = longitud del prefijo c: = char siguiendo el prefijo en la entrada demás d: = 0 l: = 0 c: = primer carácter de entrada terminara si  salida (d, l, c)  descartar l + 1 caracteres del frente de la ventana s: = pop l + 1 caracteres desde el frente de la entrada anexar s en la parte posterior de la ventanarepetir

Implementaciones [ editar ]

Aunque todos los algoritmos LZ77 funcionan por definición con el mismo principio básico, pueden variar ampliamente en la forma en que codifican sus datos comprimidos para variar los rangos numéricos de un par de longitud-distancia, alterar el número de bits consumidos para un par de longitud-distancia, y distinguir sus pares de longitud-distancia de los literales (datos sin procesar codificados como ellos mismos, en lugar de como parte de un par de longitud-distancia). Algunos ejemplos:

  • El algoritmo ilustrado en el artículo original de 1977 de Lempel y Ziv genera todos sus datos en tres valores a la vez: la longitud y la distancia de la coincidencia más larga encontrada en el búfer y el literal que siguió a esa coincidencia. Si dos caracteres sucesivos en el flujo de entrada pudieran codificarse solo como literales, la longitud del par longitud-distancia sería 0.
  • LZSS mejora LZ77 mediante el uso de un indicador de 1 bit para indicar si el siguiente fragmento de datos es un par literal o de longitud-distancia, y el uso de literales si un par de longitud-distancia sería más largo.
  • En el formato PalmDoc , un par de longitud-distancia siempre se codifica mediante una secuencia de dos bytes. De los 16 bits que componen estos dos bytes, 11 bits se utilizan para codificar la distancia, 3 para codificar la longitud y los dos restantes se utilizan para asegurarse de que el decodificador pueda identificar el primer byte como el comienzo de esos dos. secuencia de bytes.
  • En la implementación utilizada para muchos juegos por Electronic Arts , [8] el tamaño en bytes de un par de longitud-distancia se puede especificar dentro del primer byte del propio par de longitud-distancia; dependiendo de si el primer byte comienza con 0, 10, 110 o 111 (cuando se lee en orientación de bit big-endian ), la longitud de todo el par longitud-distancia puede ser de 1 a 4 bytes.
  • A partir de 2008 , el método de compresión basado en LZ77 más popular es DEFLATE ; combina LZSS con codificación Huffman . [9] Los literales, las longitudes y un símbolo para indicar el final del bloque de datos actual se colocan todos juntos en un alfabeto. Las distancias se pueden colocar de forma segura en un alfabeto separado; debido a que una distancia solo ocurre justo después de una longitud, no se puede confundir con otro tipo de símbolo o viceversa.

LZ78 [ editar ]

Los algoritmos LZ78 logran la compresión reemplazando las ocurrencias repetidas de datos con referencias a un diccionario que se construye en base al flujo de datos de entrada. Cada entrada del diccionario tiene el formato dictionary[...] = {index, character}, donde índice es el índice de una entrada anterior del diccionario y el carácter se agrega a la cadena representada por dictionary[index]. Por ejemplo, "abc" se almacenaría (en orden inverso) de la siguiente manera:, dictionary[k] = {j, 'c'}, dictionary[j] = {i, 'b'}, dictionary[i] = {0, 'a'}donde un índice de 0 especifica el primer carácter de una cadena. El algoritmo inicializa el último índice coincidente = 0 y el siguiente índice disponible = 1. Para cada carácter del flujo de entrada, se busca en el diccionario una coincidencia: {último índice coincidente, carácter}. Si se encuentra una coincidencia, el último índice coincidentese establece en el índice de la entrada coincidente y no se emite nada. Si no se encuentra una coincidencia, se crea una nueva entrada de diccionario: diccionario [siguiente índice disponible] = {último índice coincidente, carácter}, y el algoritmo genera el último índice coincidente , seguido de un carácter , luego restablece el último índice coincidente = 0 y incrementa el siguiente índice disponible . Una vez que el diccionario está lleno, no se agregan más entradas. Cuando se alcanza el final del flujo de entrada, el algoritmo genera el último índice coincidente . Tenga en cuenta que las cadenas se almacenan en el diccionario en orden inverso, con lo que un decodificador LZ78 tendrá que lidiar.

LZW es un algoritmo basado en LZ78 que utiliza un diccionario preinicializado con todos los caracteres (símbolos) posibles o la emulación de un diccionario preinicializado. La principal mejora de LZW es que cuando no se encuentra una coincidencia, se supone que el carácter del flujo de entrada actual es el primer carácter de una cadena existente en el diccionario (ya que el diccionario se inicializa con todos los caracteres posibles), por lo que solo la última coincidencia se emite el índice (que puede ser el índice del diccionario preinicializado correspondiente al carácter de entrada anterior (o inicial)). Consulte el artículo de LZW para obtener detalles sobre la implementación.

BTLZ es un algoritmo basado en LZ78 que fue desarrollado para su uso en sistemas de comunicaciones en tiempo real (originalmente módems) y estandarizado por CCITT / ITU como V.42bis . Cuando el diccionario trie- estructurado está lleno, se utiliza un algoritmo de reutilización / recuperación simple para garantizar que el diccionario pueda seguir adaptándose a los datos cambiantes. Un contador recorre el diccionario. Cuando se necesita una nueva entrada, el contador recorre el diccionario hasta que se encuentra un nodo hoja (un nodo sin dependientes). Esto se elimina y el espacio se reutiliza para la nueva entrada. Esto es más sencillo de implementar que LRU o LFU y logra un rendimiento equivalente.

Ver también [ editar ]

  • Lempel – Ziv – Stac (LZS)
  • Transformada de coseno discreta (DCT), un algoritmo de compresión con pérdida utilizado en los estándares de codificación JPEG y MPEG

Referencias [ editar ]

  1. ^ Ziv, Jacob ; Lempel, Abraham (mayo de 1977). "Un algoritmo universal para la compresión de datos secuencial". Transacciones IEEE sobre teoría de la información . 23 (3): 337–343. CiteSeerX  10.1.1.118.8921 . doi : 10.1109 / TIT.1977.1055714 .
  2. ^ Ziv, Jacob ; Lempel, Abraham (septiembre de 1978). "Compresión de secuencias individuales mediante codificación de tasa variable". Transacciones IEEE sobre teoría de la información . 24 (5): 530–536. CiteSeerX 10.1.1.14.2892 . doi : 10.1109 / TIT.1978.1055934 . 
  3. ^ Patente de EE. UU. N. ° 5532693 Sistema de compresión de datos adaptativo con lógica de coincidencia de cadenas sistólica
  4. ^ "Compresión de datos" El concepto " " .
  5. ^ "Hitos: algoritmo de compresión de datos de Lempel-Ziv, 1977" . Red de historia global IEEE . Instituto de Ingenieros Eléctricos y Electrónicos . 22 de julio de 2014 . Consultado el 9 de noviembre de 2014 .
  6. ^ Joanna, Goodrich. "La medalla de honor del IEEE es para el pionero de la compresión de datos Jacob Ziv" . IEEE Spectrum: Noticias de tecnología, ingeniería y ciencia . Consultado el 18 de enero de 2021 .
  7. ^ Peter Shor (14 de octubre de 2005). "Notas de Lempel-Ziv" (PDF) . Consultado el 9 de noviembre de 2014 .
  8. ^ "Compresión QFS (RefPack)" . Niotso Wiki . Consultado el 9 de noviembre de 2014 .
  9. ^ Feldespato, Anteo (23 de agosto de 1997). "Una explicación del algoritmo de desinflado" . grupo de noticias comp.compression . zlib.net . Consultado el 9 de noviembre de 2014 .

Enlaces externos [ editar ]

  • "El algoritmo LZ77" . Centro de referencia de compresión de datos: grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica y Computación, Universidad de Zagreb . 1997. Archivado desde el original el 7 de enero de 2013 . Consultado el 22 de junio de 2012 .
  • "El algoritmo LZ78" . Centro de referencia de compresión de datos: grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica y Computación, Universidad de Zagreb. 1997. Archivado desde el original el 7 de enero de 2013 . Consultado el 22 de junio de 2012 .
  • "El algoritmo LZW" . Centro de referencia de compresión de datos: grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica y Computación, Universidad de Zagreb. 1997. Archivado desde el original el 7 de enero de 2013 . Consultado el 22 de junio de 2012 .