SISTEMAS INTERMEDIOS ENTRE LOS COMPRESORES LZ Y LZW



UNIVERSIDAD NACIONAL DE SAN JUAN
















FACULTAD DE CIENCIAS EXACTAS, FÍSICAS Y

NATURALES



REVALIDA

Cátedra: COMPUTACIÓN III



Tema: “SISTEMAS INTERMEDIOS ENTRE LOS COMPRESORES LZ Y LZW”


-2003-




INTRODUCCIÓN



¿ Qué es la compresión?Básicamente la compresión consiste en tomar una trama de símbolos y transformarlos en códigos/claves. Si la compresión es eficiente, las claves resultantes ocuparán menor espacio que los símbolos originales.
Las técnicas de diccionario basan su mecánica en la construcción de una lista de secuencias típicas de símbolos generadas por la fuente, de manera que codifican estas secuencias mediante suposición en la lista, lo que conlleva un ahorro considerable de bits.
Los métodos de compresión basados en técnicas de diccionario se clasifican en métodos con diccionario estático y con diccionario dinámico, dependiendo de si las secuencias de símbolos son conocidas a priori.
Nos centraremos en dos de los denominados Compactadores Dinámicos (ON LINE) como son los métodos LZ y LZW y en susSistemas Intermedios. Se los denomina ON LINE pues comprimen a medida que leen el archivo.

Métodos Basados en el Diccionario

► LZ 77
► LZ SS► LZ 78
► LZW
Estos métodos de la compresión utilizan la característica de muchos tipos de datos para contener la repetición de secuencias del código. La idea es cambiar secuencias de símbolos frecuentes por índice de un diccionario de tales secuencias. Obviamente, el índice deberá ocuparmenos bits que la secuencia de símbolos.
Los buenos ejemplos de tales datos son archivos del texto (las palabras código representan caracteres) e imágenes de la trama (las palabras código representan pixeles). Todos los métodos del diccionario se pueden subdividir en dos grupos principales.
Los métodos del primer grupo, intentan encontrar si la secuencia del carácter que es comprimida actualmenteha ocurrido ya anteriormente en los datos de entrada y entonces, en vez de repetirlo, se hace salir solamente un pointer a la ocurrencia anterior.
Esto se ilustra en el siguiente diagrama:















El diccionario aquí es “implícito”, es representado por los datos previamente procesados. Todos los métodos de este grupo se basan en el algoritmo desarrollado y publicado en1977 por Abraham Lempel y Jakob Ziv, denominado LZ77. Un refinamiento de este algoritmo que es la base para los demás métodos de este grupo es el algoritmo de LZSS desarrollado en 1982 por Storer y Szymanski.
Los algoritmos del segundo grupo crean un diccionario de las frases que ocurren en los datos de entrada. Cuando se encuentran una frase ya presente en el diccionario, se hace corresponder ala salida con el índice de la frase en él diccionario. Esto se explica en el siguiente diagrama.










Por estos métodos, se basa el algoritmo desarrollado y publicado por Lempel y Ziv en 1978, denominado LZ78. El refinamiento que es la base para los demás métodos se llama LZW. Fue desarrollado por Terry Welch en 1984 para la implementación en hardware de controladores de discode alto rendimiento.







El algoritmo LZ77


Términos usados en el algoritmo
Flujo de entradas : secuencia de los caracteres que se comprimirán;
Carácter : elemento de datos básico en el flujo de entradas;
Posición de codificación : posición del carácter en el flujo de entradas que se está cifrando actualmente (el principio del buffer de lookahead );
Buffer de Lookahead...