TEORIA DE LA INFORMACION

LZW (Lempel-Ziv-Welch) es un algoritmo de compresión sin pérdida desarrollado por Terry Welch en 1984 como una versión mejorada del algoritmo LZ78 desarrollado por Abraham Lempel y Jacob Ziv.
La mayoría de los métodos de compresión se basan en un análisis inicial del texto para identificar cadenas repetidas para armar un diccionario de equivalencias, asignando códigos breves a estas cadenas. En una segunda etapa, se convierte el texto utilizando los códigos equivalentes para las cadenas repetidas. Esto requiere dos etapas, una de análisis y una segunda de conversión y también requiere que el diccionario se encuentre junto con el texto codificado, incrementando el tamaño del archivo de salida.
Codificacion Fuente Lempel-Ziv
• Las estadísticas de fuente a menudo no son conocidas
• La mayoría de las fuentes no son independientes

Las letras del alfabeto tienen un alto grado de correlación
P.ej., después de la I va la E, después de la G va la H, etc.
• Se pueden codificar “bloques” de letras, sin embargo, se requeriría un código muy largo y complejo.
• Algoritmo Lempel-Ziv
“Código universal” - funciona sin conocimiento de estadísticas de fuente
Analiza sintácticamente el archivo de entrada en frases unívocas
Codifica frases empleando palabras código de longitud fija
Codificación de longitud variable a fija
 
Algoritmo De Lempel-Ziv
• Analizar el archivo de entrada en frases que aún no han aparecido
Entrar frases en un diccionario
Numerar su ubicación
• Observe que cada frase nueva debe ser una frase vieja seguida por un ‘0’ o un ‘1’.
Puede codificar la nueva frase utilizando la ubicación del diccionario de la frase anterior seguida por el ‘0’ o el ‘1’

Notas Acerca De Lempel-Ziv
• El decodificador sólo puede decodificar unívocamente la secuencia enviada
• El algoritmo no es eficiente para secuencias cortas (datos de entrada)
• El rendimiento del código se aproxima a la entropía de fuente para secuencias largas
• El tamaño del diccionario debe elegirse con antelación para que se pueda establecer la longitud de la palabra código
• Lempel-Ziv se usa frecuentemente para codificar archivos de texto/binarios
Comprimir/descomprimir bajo unix
Mismo software de compresión para PC y MAC