Algoritmo LZ77 explicado: ¿cómo funciona la compresión de diccionario?

Conclusión primero: LZ77 es un algoritmo de compresión de diccionario basado en ventana deslizante, cuya idea central es "usar los datos históricos como diccionario y referenciar hacia atrás cuando se encuentra contenido repetido". Al codificar, se emite un triplete (distance, length, next_char): se retrocede distance caracteres para encontrar una coincidencia, la longitud de coincidencia es length, seguida de un carácter no coincidente next_char. Tomando como ejemplo los 11 caracteres de "abracadabra", la codificación LZ77 solo necesita 5 tripletes para representarlos, con un efecto de compresión significativo. LZ77 es un componente central de DEFLATE (ZIP/GZIP/PNG) y el ancestro común de algoritmos de compresión modernos como LZSS/LZMA/LZ4. A continuación se explica el principio de la ventana deslizante y se demuestra paso a paso el proceso de codificación.

Si aún no está familiarizado con los principios de la codificación Huffman, le recomendamos leer primero Principios de la codificación Huffman: la base de los algoritmos de compresión.

1. ¿Qué es la compresión de diccionario?

Los algoritmos de compresión se dividen en dos grandes corrientes: la codificación estadística (como la codificación Huffman) asigna códigos de longitud variable según la frecuencia de caracteres; la compresión de diccionario sustituye el contenido repetido por "referencias de puntero". LZ77 pertenece a la corriente de compresión de diccionario: no construye una tabla de diccionario previamente, sino que usa los datos históricos ya procesados como diccionario implícito — cuando encuentra contenido repetido, usa un "puntero de retroceso" para señalar una posición donde apareció anteriormente.

Corriente de compresión	Principio central	Algoritmos representativos	Ventaja	Desventaja
Codificación estadística	Asigna códigos de longitud variable por frecuencia	Huffman, codificación aritmética	Aproxima el límite entrópico	No maneja bien repetición de largo alcance
Compresión de diccionario	Sustituye contenido repetido por referencias	LZ77, LZW, LZMA	Maneja bien patrones repetidos	Ineficaz con datos aleatorios
Codificación híbrida	Diccionario + estadística en dos fases	DEFLATE, ZSTD	Óptimo global	Implementación más compleja
Codificación por transformada	Transforma al dominio frecuencial y cuantiza	DCT(JPEG), DWT	Alta eficiencia en compresión con pérdida	Pérdida de información

En la práctica, los algoritmos de compresión más populares son casi todos "codificación híbrida" — primero usan LZ77 para eliminar patrones repetidos, luego Huffman para comprimir los residuos por frecuencia. DEFLATE es la combinación clásica de LZ77 + Huffman, ampliamente utilizada por ZIP, GZIP y PNG.

2. Principios del algoritmo LZ77 en detalle

El núcleo de LZ77 es el mecanismo de ventana deslizante. La ventana se divide en dos partes: el buffer de búsqueda (datos históricos ya procesados) y el buffer de previsualización (datos futuros por procesar). Al codificar, se toma un segmento del buffer de previsualización y se busca la coincidencia más larga en el buffer de búsqueda; si se encuentra, se emite un triplete; si no, se emite el carácter original.

1. Estructura de la ventana deslizante

El tamaño de la ventana deslizante determina directamente el efecto de compresión — cuanto mayor sea la ventana, más datos históricos se pueden buscar en retroceso y mayor será la probabilidad de coincidencia. Los tamaños de ventana varían mucho entre diferentes algoritmos.

Algoritmo	Buffer de búsqueda	Buffer de previsualización	Longitud máxima de coincidencia	Escenario típico
LZ77 original	Algunos KB	Decenas de bytes	16 bytes	Ejemplo didáctico
DEFLATE	32KB	258 bytes	258 bytes	ZIP/GZIP/PNG
LZMA	8MB (configurable)	273 bytes	273 bytes	Archivado 7z/xz
LZ4	64KB	Sin límite	Sin límite	Compresión en tiempo real
ZSTD	8MB (máx. 1GB)	Sin límite	Sin límite	Uso general moderno

2. Formato de codificación de triplete

La unidad de salida de LZ77 es el triplete (distance, length, next_char), cuyos tres campos se explican en la siguiente tabla.

Campo	Significado	Rango de valores (DEFLATE)	Bits de codificación	Ejemplo
distance	Distancia de retroceso (cuántos caracteres hacia atrás buscar)	1–32768	15 bit	distance=10 → 10 caracteres hacia atrás
length	Longitud de coincidencia (cuántos caracteres coinciden consecutivamente)	3–258	8 bit	length=5 → 5 caracteres coincidentes
next_char	El siguiente carácter tras la coincidencia	0–255	8 bit	next_char='d' → ASCII 100

La genialidad del triplete radica en que, tras la coincidencia, se emite un next_char adicional, garantizando que el codificador siempre avance al menos 1 carácter y no se bloquee. Si no se encuentra ninguna coincidencia (length=0), tanto distance como length son 0 y solo se emite next_char — equivalente a degenerar en almacenamiento de carácter original.

3. Estrategia de búsqueda de coincidencias

La búsqueda de coincidencias es el cuello de botella de rendimiento de LZ77 — se toma un segmento del buffer de previsualización y se busca la coincidencia más larga en el buffer de búsqueda. La búsqueda por fuerza bruta tiene complejidad O(n×m); las implementaciones reales usan tablas hash o árboles de sufijos para acelerar.

Estrategia de búsqueda	Estructura de datos	Complejidad de búsqueda	Coste espacial	Aplicación típica
Búsqueda por fuerza bruta	Ninguna	O(n×m)	Ninguno	Ejemplo didáctico
Cadena hash	Tabla hash + lista enlazada	O(n) promedio	Bajo	zlib (DEFLATE)
Cubeta hash	Tabla hash + array	O(1) promedio	Medio	LZ4
Árbol de sufijos	Árbol de sufijos / array de sufijos	O(n) peor caso	Alto	LZMA

3. Caso práctico: demostración de codificación de "abracadabra"

Se realiza una codificación completa de "abracadabra" (11 caracteres) con LZ77. El estado inicial tiene el buffer de búsqueda vacío y el buffer de previsualización contiene toda la cadena. Se escanea posición por posición, buscando la coincidencia más larga en los datos históricos.

Texto original: a b r a c a d a b r a

Proceso de codificación:

Paso	Posición actual	Contenido de previsualización	Búsqueda en buffer	Triplete de salida	Descripción
1	Posición 1	abracadabra	Vacío, sin coincidencia	(0, 0, 'a')	Primer carácter, salida directa
2	Posición 2	bracadabra	"a", sin coincidencia "b"	(0, 0, 'b')	Primera aparición, salida directa
3	Posición 3	racadabra	"ab", sin coincidencia "r"	(0, 0, 'r')	Primera aparición, salida directa
4	Posición 4	acadabra	Encontrado "a" en "abr"	(0, 0, 'a')	"a" aparece pero no coincide después
5	Posición 5	cadabra	Sin "c" en "abra"	(0, 0, 'c')	Primera aparición, salida directa
6	Posición 6	adabra	Encontrado "a" en "abrac"	(0, 0, 'a')	"a" coincide pero no después
7	Posición 7	dabra	Sin "d" en "abraca"	(0, 0, 'd')	Primera aparición, salida directa
8	Posición 8	abra	Retroceso 7, coincide "abra"	(7, 4, end)	Coinciden 4 caracteres "abra"

Comparación de eficiencia de codificación:

Método de codificación	Nº de unidades de salida	Bits por unidad	Bits totales	Ahorro vs original
ASCII original	11 caracteres	8	88	— (base)
LZ77 (sin optimización de coincidencia)	8 tripletes	31 (promedio)	248	-182% (expansión)
LZ77 (optimización de bits de marca)	8 unidades	12 (promedio)	96	-9% (ligera expansión)
LZ77+Huffman	8 unidades	4.5 (promedio)	36	59%

Análisis de resultados: El LZ77 puro puede expandir cadenas cortas (el triplete ocupa más espacio que el carácter original), por eso LZ77 se suele combinar con codificación Huffman — DEFLATE es LZ77 + Huffman. En el caso de "abracadabra", la coincidencia en la posición 8 "abra" (distance=7, length=4) es el punto de compresión clave: 4 caracteres representados por un solo triplete. Para textos más largos con más patrones repetidos (como archivos de código, logs), el efecto de compresión de LZ77 mejora significativamente.

4. Variantes de LZ77 y evolución moderna

Desde su propuesta en 1977, LZ77 ha dado lugar a numerosas variantes, cada una optimizando una dimensión para un escenario específico. La siguiente tabla compara los miembros principales de la familia LZ77.

Algoritmo	Mejora clave	Tasa de compresión	Velocidad de compresión	Velocidad de descompresión	Aplicación típica
LZ77 (original)	Codificación de triplete	Baja	Lenta	Media	Docencia
LZSS	Usa bits de marca para distinguir coincidencia/literal	Media	Media	Rápida	Sistemas antiguos
DEFLATE	LZSS + Huffman en dos fases	Media-alta	Media	Rápida	ZIP/GZIP/PNG
LZMA	Ventana grande + codificación de intervalos + análisis óptimo	Alta	Lenta	Media	Archivado 7z/xz
LZ4	Sacrifica tasa de compresión por velocidad extrema	Baja	Muy rápida	Muy rápida (4GB/s)	Tiempo real / kernel
LZW	Tabla de diccionario explícita (no ventana deslizante)	Media	Rápida	Rápida	GIF/TIFF
ZSTD	Variante LZ77 + FSE + diccionario preestablecido	Alta	Rápida	Muy rápida	Uso general moderno

Desde la perspectiva de la evolución, los algoritmos modernos (ZSTD, brotli) han mejorado drásticamente la velocidad manteniendo una alta tasa de compresión, reemplazando gradualmente a DEFLATE como nuevo estándar. Pero la idea central de LZ77 — la referencia de diccionario por ventana deslizante — permanece inalterada, y todas las variantes se construyen sobre esta base.

Escenario	Algoritmo recomendado	Motivo	Referencia de tasa de compresión
Archivado de archivos	LZMA (xz)	Tasa de compresión más alta, sin priorizar velocidad	70%–85%
Compresión general	ZSTD	Equilibra tasa de compresión y velocidad	60%–80%
Transmisión en tiempo real	LZ4	Descompresión a 4GB/s, latencia muy baja	50%–65%
Transmisión Web	DEFLATE/GZIP	Mejor compatibilidad, todos los navegadores	50%–70%
Formato de imagen	DEFLATE (PNG)	Compresión sin pérdida, ideal para gráficos	50%–75%
Datos en memoria	LZ4	Bajo uso de CPU, ideal para compresión frecuente	50%–65%

Para más detalles sobre la aplicación específica de DEFLATE en el formato PNG, consulte Principios de compresión PNG explicados. Para la diferencia entre compresión sin pérdida y con pérdida, consulte Compresión sin pérdida vs con pérdida: diferencias clave.

5. Preguntas frecuentes (FAQ)

P1: ¿Qué es el algoritmo LZ77?

LZ77 es un algoritmo de compresión de diccionario basado en ventana deslizante, propuesto por Lempel y Ziv en 1977. La idea central es: usar los datos ya procesados como diccionario; cuando se encuentra contenido repetido, se sustituyen los datos originales por un triplete (distance, length, next_char), donde distance indica la distancia de retroceso, length indica la longitud de coincidencia, y next_char indica el siguiente carácter tras la coincidencia. LZ77 es un componente central de DEFLATE (ZIP/GZIP/PNG) y el ancestro de algoritmos modernos como LZSS/LZMA/LZ4.

P2: ¿Qué significa la ventana deslizante de LZ77?

La ventana deslizante es la estructura de datos central de LZ77, dividida en buffer de búsqueda (datos históricos ya procesados) y buffer de previsualización (datos futuros por procesar). Al codificar, se toma un segmento del buffer de previsualización y se busca la coincidencia más larga en el buffer de búsqueda. El tamaño típico de ventana es 32KB (estándar DEFLATE); cuanto mayor sea la ventana, mayor será la probabilidad de coincidencia, pero también el consumo de memoria. El tamaño de ventana determina el límite superior de la distancia máxima de retroceso (distance).

P3: ¿Cuál es la diferencia entre LZ77 y LZ78?

LZ77 usa una ventana deslizante como diccionario implícito: el contenido coincidente referencia directamente los datos históricos sin almacenar un diccionario separado; LZ78 usa una tabla de diccionario explícita, numerando las cadenas ya vistas y almacenándolas como entradas de diccionario, emitiendo índices de diccionario al codificar. LZ77 es más adecuado para datos con repetición local (como texto), mientras que LZ78 es más adecuado para datos con repetición global. En la práctica, los descendientes de LZ77 (DEFLATE/LZMA/LZ4) son mucho más populares que los de LZ78 (LZW).

P4: ¿Cuál tiene mayor tasa de compresión: LZ77, LZMA o LZ4?

Orden de tasa de compresión: LZMA > LZ77 (DEFLATE) > LZ4. LZMA usa una ventana más grande (8MB por defecto), algoritmos de coincidencia más avanzados y codificación de intervalos, logrando la mayor tasa de compresión pero la velocidad más lenta; DEFLATE usa ventana de 32KB + Huffman, con tasa de compresión y velocidad medias; LZ4 sacrifica la tasa de compresión por velocidad extrema, con la tasa de compresión más baja pero una velocidad de descompresión de hasta 4GB/s. La elección depende del escenario: archivado → LZMA, uso general → DEFLATE/ZSTD, tiempo real → LZ4.

Resumen

LZ77 es el progenitor de los algoritmos de compresión de diccionario, cuyo principio central es "ventana deslizante + referencia de triplete": usa los datos históricos como diccionario implícito y, al encontrar contenido repetido, emite un triplete (distance, length, next_char). El LZ77 puro puede expandir textos cortos, pero combinado con codificación Huffman (DEFLATE) se convierte en el esquema de compresión estándar de ZIP/GZIP/PNG. La variante moderna LZMA persigue la máxima tasa de compresión, LZ4 persigue la máxima velocidad, y ZSTD equilibra ambas.

Tres puntos clave para entender LZ77: primero, la ventana deslizante determina el rango de coincidencia (DEFLATE 32KB, LZMA 8MB); segundo, el triquete es la unidad básica de codificación (retroceso + longitud + siguiente carácter); tercero, la estrategia de búsqueda de coincidencias determina el rendimiento (cadena hash es la más rápida, árbol de sufijos es la más óptima). La codificación híbrida LZ77 + Huffman es el estándar de oro de la compresión sin pérdida moderna.