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]
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 da un límite a 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]
Los algoritmos LZ77 logran la compresión reemplazando las ocurrencias repetidas de datos con referencias a una sola copia de esos datos existente anteriormente en el flujo de datos sin comprimir. Una coincidencia se codifica mediante 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 ).