Codificacion LEMPEL ZIV

Nombre: Diego Mera
NRC: 4495
Fecha: 17/04/2019
CODIFICACIÓN LEMPEL-ZIV
 Los creadores de este clásico algoritmo de compresión fueron Abraham Lempel y
Jacob Ziv en el año 1977, nacía el LZ77.
 Un año después crearon el compresor de imágenes o cualquier dato que fuera
binario llamado LZ78.
 El compresor LZW es un sistema de compresión/descompresión muy rápido que se
basa en la multiplicidad de los caracteres en la cadena que se va a codificar. A partir
de la cadena creaba unos patrones que los integraba en un diccionario. El LZW
trabaja con bits y no con bytes, lo que consigue gran compatibilidad a la hora de
procesar datos
COMPRESIÓN DE DATOS
La compresión de datos es la reducción del volumen de datos tratables para representar
una determinada información empleando una menor cantidad de espacio.
La compresión es un caso particular de la codificación cuya característica principal es que el
código resultante tiene menor tamaño que el original.
La compresión de datos se basa fundamentalmente en buscar repeticiones en series de
datos para después almacenar solo el dato junto al número de veces que se repite, para ello
se utilizan algoritmos de compresión como el de Lempel Ziv.
El objetivo de la compresión es siempre reducir el tamaño de la información, intentando
que esta reducción de tamaño no afecte al contenido. No obstante, la reducción de datos
puede afectar o no a la calidad de la información:
 Compresión sin pérdidas: en esta compresión los datos antes y después de

comprimirlos son exactos, pero una mayor compresión implica más tiempo de
proceso.
 Compresión con pérdidas: puede eliminar datos para reducir aún más el tamaño,
con lo que se suele reducir la calidad. En este tipo de compresión no se obtiene la
señal original una vez realizada la compresión. Se utiliza principalmente en la
compresión de imágenes, videos y sonido.
COMPRESIÓN Y ARCHIVOS DE IMAGEN.
Ya vimos que en el formato JPEG había una compresión con pérdidas debida al tratamiento
de los coeficientes de Fourier. Pero el proceso necesita algún método de compresión sin
pérdidas para disminuir el tamaño que ocupan los coeficientes de Fourier cuantificados,
que son muchas veces nulos o números pequeños. Aunque el método no está especificado
en el formato, lo habitual es usar la codificación Huffman después de llevar a cabo una
ordenación previa que tiende a agrupar los ceros y aplicar RLE. Para completar esta
información, damos unas indicaciones acerca de otros de los formatos más empleados en
el almacenamiento digital de imágenes:
 BMP: No lleva compresión o RLE.

 PNG: LZ77 y Huffman después de un filtrado de los datos para que la compresión se
produzca en mejores condiciones.
 GIF: Se fija una paleta de a lo más 256 colores para que cada pixel sólo requiera un
byte y después se aplica LZW.
 TIFF: No lleva compresión o RLE o RLE combinado con Huffman. Es curioso que el
formato PNG nació no tanto por una evolución natural, sino por una polémica por
la posible aplicación en los años 90 de una patente sobre LZW (ya expirada en 2004).
Las especificaciones del formato GIF requieren que sea éste su método de
compresión y la empresa propietaria de la patente, anunció que el uso comercial de
GIF estaría sujeto al pago de licencias. Aunque nunca se puso en práctica esta
medida (por las protestas generalizadas), PNG surgió para escapar de su aplicación.
En términos generales, PNG es mucho mejor que GIF, pero inicialmente no tuvo
mucha acogida, sobre todo porque los navegadores principales no lo reconocían, e
incluso hoy en día no ha sustituido a GIF.
EJEMPLO Y EXPLICACIÓN
Código: A|AB|ABB|B|ABA|ABAB|BB|ABBA|BB
1. La secuencia de origen se basa secuencialmente en cadenas que no han aparecido
hasta ahora.
2. Después de cada separación, observamos la secuencia de entrada hasta que
llegamos a la cadena más corta que no se ha marcado antes.
3. Codificamos esta frase dando la ubicación del prefijo y el valor del bit perdido.
𝑨→𝟎
𝑩→𝟏
Posición 1 2 3 4 5 6 7 8 9
Secuencia A AB ABB B ABA ABAB BB ABBA BB
Rep. 0A 1B 2B 0B 2A 5B 4B 3A 7
Numérica
Código ,0 1,1 010,1 ,1 010,0 101,1 100,1 011,0 0111
O bien esta secuencia original era demasiado aleatoria para ser comprimida mucho o puede
que haya sido muy corta.
Conclusión: Como se Observa el mensaje presenta 18 bits, pero cuando se codifica el
mensaje pasa a tener una combinación de 9 bits, por lo que se demuestra que se tiene algún
ahorro de recursos si se utiliza la codificación.
Bibliografía:
Robinson, L. (17 de 03 de 2012). ATOM. Obtenido de http://lempel-ziv-proyecto-tic.blogspot.com/
D. J. C. MacKay. Information theory, inference and learning algorithms. Cambridge University Press,
New York, 2003

Codificacion LEMPEL ZIV

Cargado por

Copyright:

Formatos disponibles

Codificacion LEMPEL ZIV

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Codificacion LEMPEL ZIV

Cargado por

Copyright:

Formatos disponibles

Nombre: Diego Mera

 Compresión sin pérdidas: en esta compresión los datos antes y después de

 BMP: No lleva compresión o RLE.

También podría gustarte