Demo del compresor LZ77

Observa cómo la ventana deslizante avanza de izquierda a derecha: en cada paso encuentra la referencia hacia atrás más larga dentro de la ventana de búsqueda y emite un token (desplazamiento, longitud, literal).

Ejemplo resuelto — Demo del compresor LZ77

Anticipación	[0..7] "abracada"
Tokens emitidos: 1 de 6	5.18×
Tokens de salida	(0,0,'a')

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Una ventana más grande ayuda menos de lo que cuesta 🖖

Parece obvio que una ventana de búsqueda mayor comprime mejor, ya que más historial significa más ocasiones de encontrar una coincidencia. El problema es que cada puntero debe poder direccionar cualquier punto de esa ventana, así que ensancharla alarga el campo de distancia de todas las referencias que emites — incluidas las miles que solo necesitaban retroceder unos pocos bytes. Duplica la ventana y añades un bit a todas ellas, tanto si compró una coincidencia más larga como si no. Ese compromiso es la razón de que DEFLATE, el algoritmo dentro de ZIP, PNG y gzip, se fijara en 32 KB y ahí se quedara durante décadas: lo bastante atrás para captar repetición real en texto ordinario, lo bastante cerca para que los desplazamientos sigan siendo baratos.

Copiar en vez de repetir 🖖

Cuando el algoritmo encuentra un texto que ya ha leído, no vuelve a escribirlo. Anota una indicación breve: «retrocede offset caracteres y copia length». Cada token tiene aquí la forma (offset, length, literal): una referencia hacia atrás más un carácter nuevo. Los textos llenos de palabras o patrones repetidos se reducen mucho; los datos que ya son aleatorios apenas se comprimen.

Cuando un token se vuelve una serie larga 🖖

Una coincidencia puede apuntar solo un carácter atrás y aun así copiar más caracteres de los que existen todavía allí. Con offset 1, el decodificador copia cada byte en el mismo instante en que lo escribe, así que un único token como (1, 5, ...) despliega aaaaaa a partir de una sola a. Por eso la clásica codificación por longitud de series (RLE) surge gratis de LZ77: la «copia» se solapa con texto que aún se está generando. Prueba el ejemplo repetitivo para ver cómo una región de coincidencia se extiende más allá de la posición actual.

Problema resuelto al detalle

Seis tokens de "abracadabra" con una ventana de búsqueda de 16 caracteres 5 pasos
El panel marca 5,18× tras un token. Calcule cuánto marcará tras los seis. La entrada es "abracadabra", la ventana de búsqueda es de 16 caracteres y el búfer de anticipación es de 8.
1. Un token consta de tres campos de ancho fijo, por lo que su coste viene determinado por los dos ajustes y no por los datos. El desplazamiento tiene que poder direccionar cualquier posición de la ventana, la longitud cualquier valor hasta el tamaño del búfer, y el literal es un byte sin procesar.
  
  $⌈ lo g_{2} (W + 1)⌉ + ⌈ lo g_{2} (B + 1)⌉ + 8 = ⌈ lo g_{2} 17 ⌉ + ⌈ lo g_{2} 9 ⌉ + 8 = 5 + 4 + 8 = 17 bits$
2. El codificador escanea de izquierda a derecha y toma la coincidencia más larga que ofrece la ventana. No hay nada detrás de los tres primeros caracteres, por lo que 'a', 'b' y 'r' cuestan cada uno un token entero para emitirse una sola vez. Solo el último token rinde lo que cuesta, copiando "abra" desde la posición 0.
  
  $(0, 0, a) (0, 0, b) (0, 0, r) (3, 1, c) (5, 1, d) (7, 4, \emptyset)$
3. La proporción del panel es una cifra acumulada y divide toda la entrada entre la salida producida hasta el momento. Tras un token, está pesando once caracteres frente a diecisiete bits, razón por la cual empieza tan alta.
  
  $\frac{11 \times 8}{1 \times 17} = \frac{88}{17} = 5.18 \times$
4. Seis tokens de diecisiete bits cada uno suman 102 bits, frente a una entrada de 88. La codificación es más grande que el objeto que codifica.
  
  $\frac{11 \times 8}{6 \times 17} = \frac{88}{102} = 0.86 \times$
5. El punto de equilibrio se reduce a una división. Un token cuesta 17 bits y compra un cierto número de caracteres que valen 8 bits cada uno, de modo que el esquema solo gana cuando el token medio avanza más de 17/8 caracteres, y de estos seis, solo el último lo hace.
  
  $\frac{N}{T} > \frac{17}{8} = 2.125, \frac{N}{T} = \frac{11}{6} = 1.83$
Respuesta

El panel muestra 5,18× tras el primer token y 0,86× tras el sexto: la misma cadena, la misma codificación, a ambos lados de 1,0. La cifra que conviene recordar es 2,125 caracteres por token, que es simplemente el ancho del token dividido entre ocho, y constituye la prueba definitiva de si el LZ77 ayuda a una entrada determinada. También pone precio a un mando que parece gratuito. Ampliar la ventana de búsqueda a 64 añade dos bits a cada campo de desplazamiento, y en esta cadena no encuentra ninguna coincidencia más larga (el análisis resulta en los mismos seis tokens), por lo que la proporción cae a 0,77×. Cada duplicación del alcance cuesta un bit más en cada token, se use o no.

$\frac{N}{T} > \frac{⌈ lo g _{2} ( W + 1 )⌉ + ⌈ lo g _{2} ( B + 1 )⌉ + 8}{8}$

Ruta de aprendizaje

Compresión a mano

Lleva a Burrows-Wheeler la repetición medida en frases en lugar de símbolos: una referencia hacia atrás que indica cuánto retroceder y cuánto copiar.

Referencias (1)

The algorithm, and the offset-1 trick block 3 turns on: J. Ziv and A. Lempel, "A universal algorithm for sequential data compression." IEEE Transactions on Information Theory 23(3), 337–343, 1977.

Por el equipo de 42Math · Actualizado 2026-08-17

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

abracadabra → 6 tokens - «abracadabra»: 6 tokens para 11 caracteres. El último retrocede 7 posiciones y copia 4 caracteres: «abra» entero en una sola referencia.
aabaabaabaab → 3 tokens - «aabaabaabaab»: 4 tokens para 12 caracteres. Uno de ellos copia 7 desde solo 3 posiciones atrás, así que la coincidencia rebasa el carácter que se está escribiendo. Codificación por longitud de rachas, sin coste adicional.
the quick brown fox → 16 tokens - «the quick brown fox»: 16 tokens para 19 caracteres. La coincidencia más larga es de una sola letra. Un texto tan breve apenas ofrece nada a lo que remitirse.
ATGATCGATCG → 5 tokens - «ATGATCGATCGATCG»: 6 tokens para 15 bases. La quinta referencia copia 7 desde 4 posiciones atrás y se solapa consigo misma, porque ATCG se repite con un período menor que la coincidencia que está completando.