Complejidad Temporal
Mejor: O(n)
Prom: O(n · W)
Peor: O(n · W)
LZ77 es un compresor por diccionario inventado por Abraham Lempel y Jacob Ziv en 1977. En lugar de un libro de códigos fijo, usa una ventana deslizante de datos vistos recientemente como diccionario dinámico.
Cómo funciona:
1. Mantener un buffer de búsqueda (ventana ya codificada) y un buffer de look-ahead
2. Encontrar el prefijo más largo del look-ahead que también aparece en la ventana
3. Emitir un triple (offset, longitud, siguiente):
- offset — cuánto atrás empieza la coincidencia
- longitud — cuántos caracteres copiar
- siguiente — el carácter literal que sigue a la coincidencia (o vacío al EOF)
4. Deslizar la ventana hacia adelante en longitud + 1 y repetir
Por qué funciona:
Las frases repetidas (palabras, patrones, subcadenas) son comunes en texto y datos estructurados. Apuntar atrás en la ventana guarda una secuencia larga como una referencia corta. El flujo de triples se decodifica sin ambigüedad: copiar desde el offset y luego añadir el literal.
Complejidad Temporal:
Mejor: O(n) con hashes rodantes / buscadores avanzados
Promedio: O(n · W) búsqueda ingenua (W = tamaño de ventana)
Peor: O(n · W)
Complejidad Espacial: O(W) para la ventana
Propiedades:
- Método de diccionario sin pérdida con ventana deslizante
- Base de DEFLATE (gzip, ZIP, PNG), que combina LZ77 con Huffman
- El tamaño de ventana intercambia ratio de compresión por memoria y costo de búsqueda
- Maneja bien subcadenas repetidas; la pure aleatoriedad no se comprime
LZ77 convirtió "buscar repeticiones cercanas" en el motor práctico detrás de la mayoría de archivos sin pérdida del día a día.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es LZ77?
- LZ77 es un compresor por diccionario inventado por Abraham Lempel y Jacob Ziv en 1977. En lugar de un libro de códigos fijo, usa una ventana deslizante de datos vistos recientemente como diccionario dinámico.
- ¿Cuál es la complejidad de LZ77?
- Tiempo (promedio): O(n · W) búsqueda ingenua (W = tamaño de ventana) · Espacio: O(W)
- ¿Para quién es este visualizador de LZ77?
- La visualización de LZ77 está pensada para nivel intermedio, dentro de la categoría Compresión. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con LZ77?
- En la misma categoría (Compresión) puedes explorar: Run-Length Encoding, LZW, Huffman Coding. Todos tienen visualización interactiva.