Algoritmo Y Complejidad

Algoritmo y complejidad de
estructuradas de datos II

INTEGRANTES

: Francesco Moura Macedo.
Miguel Villa Arevalo.
Sandro Garcia Sosa.
Diego Filomeno Guevara.

DOCENTE

: Ing. Hernan Medina.

UNIVERSIDAD

: U.C.P.

CICLO

: V.

TEMA A EXPONER

: Algoritmo LZW.

Iquitos, 26 de abril de 2012.

1

INDICE

1. Descripción del algoritmo
2. Ejemplo del algoritmo

pag4 – 5

3. Usos

pag 6

4. El asunto de las patentes

2

pag 3 - 4

pag 6

ALGORITMO DE LZW
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.

Descripción del algoritmo
La mayoría de los métodos de compresión se basan en un análisisinicial 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.
La clave del método LZW reside en que es posible crear sobre la marcha, de manera automática y
en una única pasada un diccionario de cadenas que se encuentren dentro del texto a comprimir
mientras al mismo tiempo se procede a su codificación. Dicho diccionario no es transmitido con el
texto comprimido, puesto que el descompresor puede reconstruirlousando la misma lógica con
que lo hace el compresor y, si está codificado correctamente, tendrá exactamente las mismas
cadenas que el diccionario del compresor tenía.
El diccionario comienza pre-cargado con 256 entradas, una para cada carácter (byte) posible más
un código predefinido para indicar el fin de archivo. A esta tabla se le van agregando sucesivos
códigos numéricos por cada nuevopar de caracteres consecutivos que se lean (esto no es
literalmente cierto, según se describe más adelante), aun cuando todavía no sea posible prever si
ese código se reutilizará más adelante o no.
Es en este detalle donde se encuentra la brillantez del método: al armar el diccionario sobre la
marcha se evita hacer dos pasadas sobre el texto, una analizando y la otra codificando y dado que
laregla de armado del diccionario es tan simple, el descompresor puede reconstruirlo a partir del
texto comprimido mientras lo lee, evitando así incluir el diccionario dentro del texto comprimido.
Se puede objetar que el diccionario estará plagado de códigos que no se utilizarán y por tanto será
innecesariamente grande, pero en la práctica el diccionario no crece demasiado y aún si lo hiciera
noimporta mucho pues el objetivo es que el archivo comprimido sea pequeño aun cuando los
procesos de compresión y descompresión pudieran ocupar mucha memoria con el diccionario.
Las entradas del diccionario pueden representar secuencias de caracteres simples o secuencias de
códigos de tal forma que un código puede representar dos caracteres o puede representar
secuencias de otros códigospreviamente cargados que a su vez representen, cada uno de ellos,
otros códigos o caracteres simples, o sea que un código puede representar desde uno a un
número indeterminado de caracteres. En realidad, el algoritmo no discrimina entre códigos y
caracteres simples pues el diccionario se carga inicialmente de códigos que representan los
primeros 256 caracteres simples por lo que estos no son más queotros códigos dentro del mismo
diccionario.
Cada vez que se lee un nuevo carácter se revisa el diccionario para ver si forma parte de alguna
entrada previa. Todos los caracteres están inicialmente predefinidos en el diccionario así que
siempre habrá al menos una coincidencia, sin embargo, lo que se busca es la cadena más larga
posible. Si el carácter leído no forma parte de más de una...