Hispanopedia Wiki
Articulo de referencia

LZ77 y LZ78

LZ77 y LZ78 son los dos algoritmos de compresión de datos sin pérdida publicados en artículos de Abraham Lempel y Jacob Ziv en 1977 [ 1 ] y 1978. [ 2 ] También se les conoce com...

Hispanopedia WikiContenido en espanolLectura gratuita

LZ77 y LZ78 son los dos algoritmos de compresión de datos sin pérdida publicados en artículos de Abraham Lempel y Jacob Ziv en 1977 [ 1 ] y 1978. [ 2 ] También se les conoce como Lempel-Ziv 1 (LZ1) y Lempel-Ziv 2 (LZ2) respectivamente. [ 3 ] Estos dos algoritmos constituyen la base de muchas variaciones, incluidas LZW , LZSS , LZMA y otras. Además de su influencia académica, estos algoritmos constituyeron la base de varios esquemas de compresión omnipresentes, incluido el utilizado en GIF y el algoritmo DEFLATE utilizado en PNG y ZIP .

En teoría, ambos son codificadores de diccionario . LZ77 mantiene una ventana deslizante durante la compresión. Posteriormente se demostró que esto es 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 a partir de una ventana deslizante sobre caracteres vistos previamente, la descompresión siempre debe comenzar al principio de la entrada. Conceptualmente, la descompresión LZ78 podría permitir el acceso aleatorio a la entrada si se conociera de antemano todo el diccionario. Sin embargo, en la práctica, el diccionario se crea durante la codificación y decodificación mediante la creación de una nueva frase cada vez que se genera un token. [ 4 ]

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

Eficiencia teórica

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 la información para secuencias individuales (a diferencia de los conjuntos probabilísticos). Esta medida proporciona una cota para la relación de compresión de datos que se puede lograr. Se demuestra entonces que existen codificadores finitos sin pérdida para cada secuencia que alcanzan esta cota a medida que la longitud de la secuencia tiende a infinito. En este sentido, un algoritmo basado en este esquema produce codificaciones asintóticamente óptimas. Este resultado se puede demostrar de forma más directa, como por ejemplo en las notas de Peter Shor . [ 7 ]

Formalmente, (Teorema 13.5.2 [ 8 ] ).

LZ78 es universal y entrópico — Siincógnita{\textstyle X}es una fuente binaria que es estacionaria y ergódica, entonceslímite superiornorte1nortelLZ78(incógnita1:norte)≤h(incógnita){\displaystyle \limsup _{n}{\frac {1}{n}}l_{LZ78}(X_{1:n})\leq h(X)}con probabilidad 1. Aquíh(incógnita){\textstyle h(X)}es la tasa de entropía de la fuente.

Teoremas similares se aplican a otras versiones del algoritmo LZ.

LZ77

Los algoritmos LZ77 logran la compresión reemplazando las ocurrencias repetidas de datos con referencias a una única copia de esos datos que existe previamente en el flujo de datos sin comprimir. Una coincidencia se codifica mediante un par de números denominado par longitud-distancia , que equivale a la afirmación "cada uno de los siguientes caracteres longitud es igual a los caracteres exactamente distancia detrás de él en el flujo sin comprimir". (A veces, la distancia se denomina desplazamiento ).

Para detectar coincidencias, el codificador debe mantener un registro de los datos más recientes, como los últimos 2 KB , 4 KB o 32 KB. La estructura en la que se almacenan estos datos se denomina ventana deslizante , razón por la cual LZ77 a veces se conoce como compresión de ventana deslizante . El codificador necesita conservar estos datos para buscar coincidencias, y el decodificador necesita conservarlos para interpretar las coincidencias a las que hace referencia el codificador. Cuanto mayor sea la ventana deslizante, más atrás podrá buscar el codificador las referencias de creación.   

No solo es aceptable, sino que con frecuencia resulta útil, permitir que los pares longitud-distancia especifiquen una longitud que en realidad supere la distancia. Como comando de copia, esto es desconcertante: "Retrocede cuatro caracteres y copia diez caracteres desde esa posición a la posición actual". ¿Cómo se pueden copiar diez caracteres si solo cuatro de ellos están realmente en el búfer? Al procesar byte a byte, no hay problema en atender esta solicitud, ya que a medida que se copia un byte, se puede volver a introducir como entrada al comando de copia. Cuando la posición de origen llega a la posición de destino inicial, se le proporcionan los datos que se pegaron desde el principio de la posición de origen. La operación es, por lo tanto, equivalente a la instrucción "copia los datos que te dieron y pégalos repetidamente hasta que quepan". Como 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: Durante la codificación, 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 desde la primera coincidencia en el desplazamiento D y hacia adelante hasta el final de la ventana de búsqueda deben tener una entrada coincidente, y estos son los caracteres (vistos previamente) que componen una sola unidad de ejecución de 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 hacia adelante, hasta donde el patrón de ejecución se repite en la entrada, los punteros de búsqueda y de entrada estarán sincronizados y coincidirán caracteres hasta que el patrón de ejecución se interrumpa. Entonces se han encontrado L caracteres coincidentes en total, L > D , y el código es [ D , L , c ].

Al decodificar [ D , L , c ], nuevamente, D = L R . Cuando los primeros L R caracteres se leen a la salida, esto corresponde a una sola unidad de ejecución agregada al búfer de salida. En este punto, se podría pensar que el puntero de lectura solo necesita regresar 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 L R caracteres (o tal vez menos en el último retorno) y repetir hasta que se hayan leído un total de L caracteres. Pero reflejando el proceso de codificación, dado que el patrón es repetitivo, el puntero de lectura solo necesita seguir sincronizado con el puntero de escritura por 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 la compresión de secuencias de datos predomine, la búsqueda en la ventana debería comenzar al final de la misma y avanzar hacia atrás, ya que los patrones de secuencias, si existen, se encontrarán primero y permitirán que la búsqueda finalice, de forma absoluta si se alcanza la longitud máxima de secuencia coincidente actual, o de forma juiciosa 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

El siguiente pseudocódigo reproduce la ventana deslizante del algoritmo de compresión LZ77.

mientras la entrada no esté vacía, haga lo siguiente: coincidencia := ocurrencia repetida más larga de entrada que comienza en la ventana si existe coincidencia entonces d := distancia al inicio del partido l := longitud de la coincidencia c := carácter que sigue a la coincidencia en la entrada demás d := 0 l := 0 c := primer carácter de la entrada fin siSalida (d, l, c) descartar l + 1 caracteres del frente de la ventana s := extrae l + 1 caracteres del principio de la entrada. agregar s en la parte posterior de la ventana repetir

Implementaciones

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 modificar los rangos numéricos de un par longitud-distancia, alterar la cantidad de bits consumidos para un par longitud-distancia y distinguir sus pares longitud-distancia de los literales (datos sin procesar codificados como sí mismos, en lugar de como parte de un par longitud-distancia). Algunos ejemplos:

  • El algoritmo ilustrado en el artículo original de Lempel y Ziv de 1977 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 al usar un indicador de 1 bit para señalar si el siguiente bloque de datos es un literal o un par longitud-distancia, y al usar literales si un par longitud-distancia resultara más largo.
  • En el formato PalmDoc, un par longitud-distancia siempre se codifica mediante una secuencia de dos bytes. De los 16 bits que componen estos dos bytes, 11 se destinan a codificar la distancia, 3 a codificar la longitud y los dos restantes se utilizan para asegurar que el decodificador pueda identificar el primer byte como el inicio de dicha secuencia de dos bytes.
  • En la implementación utilizada para muchos juegos de Electronic Arts , [ 9 ] el tamaño en bytes de un par longitud-distancia se puede especificar dentro del primer byte del propio par longitud-distancia; dependiendo de si el primer byte comienza con un 0, 10, 110 o 111 (cuando se lee en orientación de bits big-endian ), la longitud de todo el par longitud-distancia puede ser de 1 a 4 bytes.
  • A partir de 2008El método de compresión basado en LZ77 más popular es DEFLATE ; combina LZSS con codificación Huffman . [ 10 ] Los literales, las longitudes y un símbolo para indicar el final del bloque de datos actual se colocan juntos en un alfabeto. Las distancias se pueden colocar de forma segura en un alfabeto separado; dado que una distancia solo aparece justo después de una longitud, no se puede confundir con otro tipo de símbolo ni viceversa.

LZ78

Los algoritmos LZ78 comprimen datos secuenciales construyendo un diccionario de secuencias de tokens a partir de la entrada, y luego reemplazando la segunda y subsiguiente ocurrencia de la secuencia en el flujo de datos con una referencia a la entrada del diccionario. La observación es que el número de secuencias repetidas es una buena medida de la naturaleza no aleatoria de una secuencia. Los algoritmos representan el diccionario como un árbol n -ario, donde n es el número de tokens utilizados para formar secuencias de tokens. Cada entrada del diccionario tiene la forma dictionary[...] = {index, token}, donde indexes el índice de una entrada del diccionario que representa una secuencia vista previamente, y tokenes el siguiente token de la entrada que hace que esta entrada sea única en el diccionario. Nótese que el algoritmo es voraz, por lo que no se agrega nada a la tabla hasta que se encuentra un token único. El algoritmo consiste en inicializar el último índice coincidente = 0 y el siguiente índice disponible = 1 y luego, para cada token del flujo de entrada, se busca una coincidencia en el diccionario: {last matching index, token}. Si se encuentra una coincidencia, entonces el último índice coincidente se establece en el índice de la entrada coincidente, no se genera ninguna salida y el último índice coincidente se mantiene representando la entrada hasta el momento. La entrada se procesa hasta que no se encuentra una coincidencia. Luego se crea una nueva entrada en el diccionario, dictionary[next available index] = {last matching index, token}y el algoritmo genera el último índice coincidente, seguido del token, luego restablece el último índice coincidente a 0 e incrementa el siguiente índice disponible. Como ejemplo, considere la secuencia de tokensAABBA, que ensamblaría el diccionario;

0 {0,_} 1 {0,A} 2 {1,B} 3 {0,B}

y la secuencia de salida de los datos comprimidos sería0A1B0B. Tenga en cuenta que el últimoAaún no está representado, ya que el algoritmo no puede saber qué viene después. En la práctica, se agrega un marcador EOF a la entrada:AABBA$, por ejemplo. Nótese también que en este caso la salida0A1B0B1$es más largo que la entrada original, pero la relación de compresión mejora considerablemente a medida que crece el diccionario, y en binario los índices no necesitan estar representados por más que el número mínimo de bits. [ 11 ]

La descompresión consiste en reconstruir el diccionario a partir de la secuencia comprimida. A partir de la secuencia0A1B0B1$La primera entrada siempre es el terminador.0 {...}y el primero de la secuencia sería1 {0,A}. ElAse agrega a la salida. El segundo par de la entrada es1By da como resultado la entrada número 2 en el diccionario,{1,B}. El token Bse muestra, precedido por la secuencia representada por la entrada 1 del diccionario. La entrada 1 es un A(seguido de "entrada 0" – nada) así queABse añade a la salida. Siguiente0Bse agrega al diccionario como la siguiente entrada,3 {0,B}y B(sin precedido por nada) se agrega a la salida. Finalmente, una entrada de diccionario para1$se crea yA$es la salida, lo que resulta enUn AB BA$, oAABBA, eliminando los espacios y el marcador EOF.

LZW

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

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

Véase también

Referencias

  1. ↑ Ziv, Jacob ; Lempel, Abraham (mayo de 1977). "Un algoritmo universal para la compresión de datos secuenciales". IEEE Transactions on Information Theory . 23 (3): 337– 343. CiteSeerX 10.1.1.118.8921 . doi : 10.1109/TIT.1977.1055714 . S2CID 9267632 .  
  2. ↑ Ziv, Jacob ; Lempel, Abraham (septiembre de 1978). "Compresión de secuencias individuales mediante codificación de tasa variable". IEEE Transactions on Information Theory . 24 (5): 530– 536. CiteSeerX 10.1.1.14.2892 . doi : 10.1109/TIT.1978.1055934 . 
  3. ↑ Patente estadounidense n.° 5532693: Sistema de compresión de datos adaptativo con lógica de coincidencia de cadenas sistólicas.
  4. ↑ "Compresión de datos sin pérdidas: LZ78" . cs.stanford.edu .
  5. ↑ "Hitos: Algoritmo de compresión de datos Lempel–Ziv, 1977" . IEEE Global History Network . 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 se otorga al 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 Lempel–Ziv" (PDF) . Archivado del original (PDF) el 28 de mayo de 2021. Recuperado el 9 de noviembre de 2014 .
  8. ↑ Cover, Thomas M.; Thomas, Joy A. (2006). Elementos de la teoría de la información (2.ª ed.). Hoboken, NJ: Wiley-Interscience. ISBN  978-0-471-24195-9.
  9. ↑ "QFS Compression (RefPack)" . Wiki de Niotso . Consultado el 9 de noviembre de 2014 .
  10. ↑ Feldspar, Antaeus (23 de agosto de 1997). "Una explicación del algoritmo Deflate" . Grupo de noticias comp.compression . zlib.net . Consultado el 9 de noviembre de 2014 .
  11. ^ Goemans, Michel (27 de abril de 2015). «Códigos Lempel-Ziv» (PDF) . Matemáticas del MIT .
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con el algoritmo LZ77 en Wikimedia Commons.
  • Logotipo de Wikimedia CommonsContenido multimedia relacionado con el algoritmo LZ78 en Wikimedia Commons.
  • "El algoritmo LZ77" . Centro de Referencia de Compresión de Datos: Grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica e Informática, Universidad de Zagreb . 1997. Consultado el 22 de junio de 2012 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  • "El algoritmo LZ78" . Centro de Referencia de Compresión de Datos: Grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica e Informática, Universidad de Zagreb. 1997. Consultado el 22 de junio de 2012 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )
  • "El algoritmo LZW" . Centro de Referencia de Compresión de Datos: Grupo de trabajo RASIP . Facultad de Ingeniería Eléctrica e Informática, Universidad de Zagreb. 1997. Consultado el 22 de junio de 2012 .{{cite web}}: CS1 maint: servicio de archivado obsoleto ( enlace )