Complejidad Temporal
Mejor: O(n)
Prom: O(n)
Peor: O(n)
LZW (Lempel–Ziv–Welch) es un compresor adaptativo por diccionario publicado por Terry Welch en 1984. Codificador y decodificador construyen el mismo diccionario sobre la marcha a partir del flujo de datos — no hace falta transmitir un diccionario aparte.
Cómo funciona:
1. Sembrar el diccionario con cada cadena de un solo carácter
2. Mantener una frase actual w (inicialmente vacía)
3. Para cada siguiente carácter c:
- Si w+c ya está en el diccionario, hacer w = w+c
- Si no, emitir el código de w, añadir w+c al diccionario y hacer w = c
4. Tras el último carácter, emitir el código de la w restante
Por qué funciona:
Cuando las frases se repiten, reciben códigos enteros cortos. Se aprenden frases cada vez más largas de forma automática. El decodificador refleja al codificador: cada código recibido se expande a una cadena y se añade la siguiente frase no vista con la misma regla, así ambos lados se mantienen sincronizados.
Complejidad Temporal:
Mejor: O(n)
Promedio: O(n)
Peor: O(n) con un diccionario hash
Complejidad Espacial: O(d) donde d es el número de entradas del diccionario
Propiedades:
- Codificación de diccionario adaptativa sin pérdida
- Usado históricamente en GIF y en compress de Unix
- No requiere análisis previo de frecuencias
- El crecimiento del diccionario puede limitarse (ancho de código fijo) en formatos en streaming
LZW muestra cómo un libro de códigos que crece convierte la estructura recurrente en códigos enteros más cortos sin un modelo separado de la fuente.
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es LZW?
- LZW (Lempel–Ziv–Welch) es un compresor adaptativo por diccionario publicado por Terry Welch en 1984. Codificador y decodificador construyen el mismo diccionario sobre la marcha a partir del flujo de datos — no hace falta transmitir un diccionario aparte.
- ¿Cuál es la complejidad de LZW?
- Tiempo (promedio): O(n) · Espacio: O(d)
- ¿Para quién es este visualizador de LZW?
- La visualización de LZW 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 LZW?
- En la misma categoría (Compresión) puedes explorar: Run-Length Encoding, LZ77, Huffman Coding. Todos tienen visualización interactiva.