> lz77 | sliding | window <
// LZ77: compresión con ventana deslizante y referencias de diccionario
>> funciones
Codificación por diccionario
Hace referencia a patrones repetidos usando desplazamiento y longitud.
Ventana deslizante
Mantiene una ventana móvil para buscar el patrón más largo.
Base del algoritmo
Fundamento de ZIP, GZIP, DEFLATE y PNG.
>> información técnica
Cómo funciona LZ77
LZ77 mantiene una ventana deslizante de datos vistos recientemente. En cada posición busca en la ventana la subcadena más larga que coincide. Si la encuentra, emite una referencia (desplazamiento, longitud, siguiente carácter). Si no, emite un literal (0,0,carácter). Así sustituye patrones repetidos por referencias cortas y consigue compresión sin pérdida.
Ejemplo de LZ77
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
¿Por qué usar LZ77?
- Compresión sin pérdida
- No requiere conocer el formato de los datos
- Se adapta a los patrones de los datos
- Implementación relativamente sencilla
- Base de muchos algoritmos de compresión modernos
>> preguntas frecuentes
¿Qué es LZ77?
LZ77 es un algoritmo universal de compresión de datos sin pérdida publicado por Abraham Lempel y Jacob Ziv en 1977. Reemplaza repeticiones en el flujo de datos por referencias a una sola copia que apareció antes en el flujo sin comprimir.
¿Cómo funciona la ventana deslizante?
La ventana deslizante se divide en un búfer de búsqueda (datos ya procesados) y un búfer de anticipación (datos por comprimir). El algoritmo busca en el búfer de búsqueda el match más largo con el inicio del búfer de anticipación y luego emite una referencia o un literal.
¿LZ77 frente a los algoritmos modernos?
LZ77 es la base de muchos algoritmos de compresión actuales. DEFLATE, usado en ZIP y GZIP, combina LZ77 con codificación de Huffman. LZSS mejora LZ77 reduciendo redundancia, mientras que LZ78 y LZW construyen el diccionario de otra forma manteniendo los mismos principios.
¿Cuáles son tamaños de ventana recomendados?
Para datos generales, los tamaños de ventana típicos van de 32 KB a 64 KB. Ventanas más grandes encuentran más coincidencias pero consumen más memoria y tiempo. DEFLATE usa 32 KB. El búfer de anticipación suele ser de 256–512 bytes. El mejor tamaño depende de los patrones de repetición de tus datos.