informe compresion lz77 albino huertas

7/26/2019 Informe Compresion Lz77 Albino Huertas

1/11

TPICOS I

Compresin de Archivos usando LZ77

Milla

VII

Albino Huertas Eder Alberto

0201214015

2015


2/11

TPICOS I

Pgina 1 de 10

COMPRESIN LZ77

INDICE

Historia:............................................................................ 2

Funcionamiento:.............................................................. 2

Algoritmo de Comprensin.............................................. 2

Ejemplo de compresin:................................................ 3

Algoritmo de Descompresin.......................................... 6

Ejemplo de descompresin:.......................................... 6Ventajas del LZ77............................................................. 9

Problemas De LZ77........................................................... 9

Actualidad........................................................................ 9

Bibliografa..................................................................... 10


3/11

TPICOS I

Pgina 2 de 10

Historia:

Los creadores de este clsico algoritmo de compresin fueron Abraham Lempel y Jakob

Ziv;1977Abraham Lempel yJacob Ziv presentaron su modelo decompresin basado en

diccionario, esta compresin de texto se refiere a la compresin sin prdida para

cualquier tipo de datos. Hasta la fecha todos losalgoritmos de compresin desarrolladoseran bsicamente compresores estticos. El nuevo modelo fue llamado lz77 (lz son la

iniciales de sus creadores y 77 el ao en que se cre).

Funcionamiento:

En este algoritmo el codificador analiza el texto como una secuencia de caracteres,

mediante una ventana deslizablecompuesta por dos partes; unbuffer de anticipacin

que es la opcin que est a punto de ser codificada y unbuffer de bsqueda(la ventana

en s), que es la parte dnde se buscan secuencias iguales a las existentes en elbuffer

de anticipacin. Para codificar el contenido, o parte de l, delbuffer de anticipacin, sebusca la secuencia igual en elbuffer de bsqueda y la codificacin resulta en indicar esta

repeticin como una tripleta:

[Puntero, longitud, carcter siguiente]

[p, l, s]

Ventana de bsqueda:Contiene los caracteres que han sido codificados recientemente

y es en s misma el diccionario.

Ventana en Anticipacin (avance):Est a continuacin de la ventana de bsqueda ycontiene los caracteres a ser codificados.

Algoritmo de Comprensin

Se tiene una ventana de texto previamente ledo.

Se tiene un buffer de texto sin codificar.

Se busca la coincidencia mayor del buffer en la ventana.

Se codifica la coincidencia como un desplazamiento, una longitud dentro de la

ventana y el siguiente carcter del buffer.

Se desplaza la ventana la longitud coincidente.
http://www.ecured.cu/index.php/1977http://www.ecured.cu/index.php?title=Abraham_Lempel&action=edit&redlink=1http://www.ecured.cu/index.php?title=Jacob_Ziv&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_basado_en_diccionario&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_basado_en_diccionario&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_de_texto&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_sin_p%C3%A9rdida&action=edit&redlink=1http://www.ecured.cu/index.php/Algoritmohttp://www.ecured.cu/index.php/Algoritmohttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Bufferhttp://www.ecured.cu/index.php/Algoritmohttp://www.ecured.cu/index.php/Algoritmohttp://www.ecured.cu/index.php?title=Compresi%C3%B3n_sin_p%C3%A9rdida&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_de_texto&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_basado_en_diccionario&action=edit&redlink=1http://www.ecured.cu/index.php?title=Compresi%C3%B3n_basado_en_diccionario&action=edit&redlink=1http://www.ecured.cu/index.php?title=Jacob_Ziv&action=edit&redlink=1http://www.ecured.cu/index.php?title=Abraham_Lempel&action=edit&redlink=1http://www.ecured.cu/index.php/1977


4/11

TPICOS I

Pgina 3 de 10

Los pasos para el desarrollo del algoritmo son los siguientes:

1. El codificador recorre la ventana de bsqueda hacia atrs, de derecha a

izquierda. Busca una cadena de caracteres que sea igual a la cadena de

caracteres de la ventana de adelante o a un prefijo de esta cadena. Si en el search

buffer hay 2 o ms cadenas iguales se pueden elegir cualquiera ya que esto noafecta al decodificador.

a) Si el codificador encuentra una cadena coincidente como se explic

antes, entonces genera una terna (tripleta) del tipo (puntero, longitud,

carcter). Puntero es la distancia que hay (contada en caracteres) desde

el final de la ventana de bsqueda (el extremo derecho) hacia atrs, hasta

el comienzo de la cadena que se ha encontrado. Longitud es la longitud

de la cadena hallada. Carcter es, el carcter dentro de la ventana look -

ahead, que sigue a la cadena coincidente.b) Si no se encontr ninguna cadena coincidente entonces se genera una

terna en donde puntero y longitud valen 0 y carcter es el primer carcter

de la ventana de adelante.

2. Las dos ventanas (buffers) se desplazan hacia adelante una distancia igual a

longitud + 1.

El tamao de la ventana de bsqueda es mucho mayor que el tamao de la

ventana en avance, lo cual resulta lgico teniendo en cuenta que la ventana de

bsqueda es el diccionario en s. En la prctica la ventana de bsqueda puede

tener algunos miles de caracteres de longitud mientras que la ventana en avancetiene algunas decenas de caracteres.

Ejemplo de compresin:

Ejemplo 1

La cadena es: AAACCCDDDAAABCCDD Tiene: 17*8= 136 bits

Ventana de Bsqueda: 9

Ventana de avance: 3


5/11

TPICOS I

Pgina 4 de 10

Ventana de Bsqueda Ventanade Avance

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

A A A C C C D D D A A A B C C D D9 8 7 6 5 4 3 2 1

Buscamos la coincidencia ms larga, en este caso la primera coincidencia se da en la

posicin 7 luego en el 8 y ltimo en el 9, escogemos el 9 por que es el que tiene la

coincidencia ms larga. AAA (Ventana de avance) y AAA (de la posicin 9, 8 y 7)

Generamos el primer triplete que sera

[9, 3, B]

Ahora corremos longitud + 1 (3+1) posiciones para establecer la nueva ventana de

bsqueda y ventana de avance.

Ventana de Bsqueda Ventanade Avance

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

A A A C C C D D D A A A B C C D D9 8 7 6 5 4 3 2 1

La subcadena coincidente esta desde la 9,8 y 7 que es CCDcon coincide con la ventana

de avance.

Generamos el segundo triplete que sera

[9, 3, D]

Ya no podemos desplazarnos ms porque ya llegamos al tope de la cadena.

El comprimido seria:

La ventana de Bsqueda + los tripletes

9 + (2*3)=15

15*8 = 120 bits.

Su ganancia es:

Ganancia= ((136-120)/136)*100

Ganancia = 11.7647%


6/11

TPICOS I

Pgina 5 de 10

Ejemplo 2

La cadena es:ACCBADACCBACCBACCGI Tiene: 19*8= 152 bits

Ventana de Bsqueda: 9

Ventana de avance: 6

Ventana de Bsqueda Ventana de Avance1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19A C C B A D A C C B A C C B A C C G I

9 8 7 6 5 4 3 2 1

La coincidencia ms larga es de la posicin 6 y 5 que es BA

Generamos el primer triplete que sera

[6, 2, C]

El desplazamiento seria longitud ms 1 (2+1):

Ventana de Bsqueda Ventana de Avance1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19A C C B A D A C C B A C C B A C C G I

9 8 7 6 5 4 3 2 1

Entonces se ha hallado la mxima cadena coincidente (hay otra letra C en la posicin 5

pero slo genera una coincidencia de un carcter). Es decir que el valor del puntero es

4, la longitud coincidente es 5 y el prximo carcter (el que est inmediatamente

despus de la cadena coincidente en la ventana en avance) es la letra G. Por lo tanto:

Generamos el segundo triplete que sera

[4, 5, G]

La ventana completa se desplaza 6 lugares (longitud + 1).

Ventana de Bsqueda VentanadeAvance

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

A C C B A D A C C B A C C B A C C G I9 8 7 6 5 4 3 2 1

Vemos que nuestra ventana de avance solo puede tener un solo elemento.

Adems tambin vemos que no hay ninguna coincidencia por la tanto:


7/11

TPICOS I

Pgina 6 de 10

Generamos el tercer triplete que sera

[0, 0, I]

El comprimido seria:

La ventana de Bsqueda + los tripletes

9 + (3*3) = 18 18*8 = 144 bits.

Su ganancia es:

Ganancia= ((152-144)/152)*100

Ganancia = 5.2631%

Algoritmo de Descompresin

Es mucho ms sencilla que la compresin.

No necesita hacer comparaciones.

Slo necesita una ventana igual que la del compresor.

Cuando lee genera la salida segn le indica el par desplazamiento longitud.

Mantiene la ventana aadiendo lo generado.

El decodificador lee cada tripleta T = [P, L, C].Se dan dos casos para L:

a. L es igual a cero:

C se escribe al archivo de salida

El buffer se recorre a la izquierda una posicin y se rellena con C

b. L es diferente de cero:

La subcadena S en el buffer iniciando en la posicin P (contando

de derecha a izquierda) y de longitud L se copia al archivo de

salida.

C se escribe al archivo de salida.

Si P < L entonces:

Se copia letra por letra empezando desde la posicin P (dederecha a izquierda) y que se copien L veces.

Ejemplo de descompresin:

Para este ejemplo tomamos el valor comprimido del ejemplo de compresin 2 que serael siguiente:


8/11

TPICOS I

Pgina 7 de 10

La cadena codificada:

A C C B A D A C C

Los tripletes son: [6, 2, C], [4, 5, G], [0, 0, I]

Pasamos a decodificar:

A C C B A D A C C6 5 4 3 2 1

Nos ubicamos en la posicin 6 contando de derecha a izquierda, luego vemos cuantas

coincidencias existen en este caso son 2, y esas dos coincidencias lo ponemos al final de

la cadena, luego agregamos el tercer valor(C) de nuestro triplete al final de cadena.

Quedando de la siguiente manera:

A C C B A D A C C B A C

6 5 4 3 2 1

Luego a esta cadena le sumamos el siguiente triplete:

A C C B A D A C C B A C

4 3 2 1

En este caso se cumple la siguiente condicin en el algoritmo

Que si la posicin (4) es menor que la longitud (5) entonces se va reemplazando letra

por letra 5 veces que es la longitud, como veremos a continuacin:

Iteracin 1:

A C C B A D A C C B A C C4 3 2 1

Iteracin 2:

[6, 2, C]

[4, 5, G]


9/11

TPICOS I

Pgina 8 de 10

A C C B A D A C C B A C C B4 3 2 1

Iteracin 3:

A C C B A D A C C B A C C B A4 3 2 1

Iteracin 4:

A C C B A D A C C B A C C B A C4 3 2 1

Iteracin 5:

A C C B A D A C C B A C C B A C C4 3 2 1

Ahora se suma el tercer valor del triplete que es G:

A C C B A D A C C B A C C B A C C G

4 3 2 1

Y quedara de la siguiente manera y sumamos el siguiente triplete:

A C C B A D A C C B A C C B A C C G

En este caso la posicin y la longitud son ceros entonces solo se suma el tercer valor del

triplete quedando la cadena de la siguiente manera:

A C C B A D A C C B A C C B A C C G I

La cadena final de seria:

A C C B A D A C C B A C C B A C C G I

La efectividad de un compresor basado en LZ77 depende del tamao de ventana

considerado. Con tamaos ms grandes de ventana se mantiene un histrico mayor de

informacin y, por tanto, se aumenta la probabilidad de que secuencias de mayor

[0, 0, I]


10/11

TPICOS I

Pgina 9 de 10

longitud (en el lookahead buffer) estn representadas en la ventana. Sin embargo, el

incremento del tamao de ventana tambin supone un aumento en el rango de valores

utilizado para la representacin de los desplazamientos. Generalmente se utilizan 12

bits para la representacin de la posicin (lo que supone una ventana de 4096

posiciones) y 4 para la longitud de la secuencia. Adems, se debe considerar una

longitud mnima de secuencia con el fin de compensar el coste de representacin del

triple. Generalmente se considera una longitud mnima de 3 caracteres. Esto supone la

utilizacin de 2 bytes para la representacin de los pares desplazamiento-longitud a los

que hay que sumar un tercer byte para la representacin de s.

Ventajas del LZ

Fcil de implementar.

En procesos de descompresin es muy simple lo cual ayuda a afectividad y

rapidez del proceso general.

Problemas De LZ

El principal problema es el proceso de bsqueda de coincidencia ms larga.

Si se intenta mejorar el rendimiento aumentando el tamao de la ventana el

problema anterior aumenta.

El problema de la bsqueda no afecta a la descompresin. El desplazamiento de la ventana tambin supone un problema pero fcilmente

solucionable.

Problema de los smbolos no comprimibles.

EN GENERAL:

Entre las desventajas que presenta el algoritmo podemos decir que asume que

las cadenas que se repiten aparecen relativamente cerca una de otra, cuando en

realidad puede ocurrir que una cadena se repita varias veces aunque en forma

distanciada. Por ejemplo, la palabra mientras normalmente aparece varias veces

en un texto pero en forma uniformemente distribuida lo que hace que cuando

una de estas repeticiones entra en la ventana de adelante la otra repeticin ya

sali de la ventana de bsqueda y la compresin no se efecta.

Actualidad

Es ms utilizado que el LZ78 (posiblemente por tener menos problemas de propiedad).

Es una tcnica presente en multitud de modelos de compresin pues tiene tantas

decisiones de diseo que cada uno es implementado de manera distinta a los dems.

Esto hace que no se puedan patentar o que se puedan saltar de una forma u otra las


11/11

TPICOS I

Pgina 10 de 10

patentes actuales. Como ejemplo de compresores que lo usan sera: ARJ, PKZIP, RAR,

etc.

Bibliografa

Arcgis.com. (s.f.).http://help.arcgis.com/es/arcgisdesktop/10.0/help/index.html#//009t00000021000

000.

Chiral, R. M. (s.f.). http://ocw.udl.cat/enginyeria-i-arquitectura/codificacio-i-transport-de-la-

infomacio/Contenidos/2/CompSinPerd.pdf.

Definicin, A. (s.f.). http://clickdefinicion.com/letra-l/lz77.php.

ecured. (s.f.). http://www.ecured.cu/index.php/Lz77.

estndares, F. d. (s.f.).

https://books.google.com.pe/books?id=cjsHVSwbHwoC&pg=PA169&lpg=PA169&dq=EJEMPLO+LZ77&source=bl&ots=ZnyK14E5PC&sig=L9mjboNo0NyQ1Sk-

Cvyg4ZJ9HoQ&hl=es-

419&sa=X&ei=eGRyVcfeAcKxggTSqIC4Bw&redir_esc=y#v=onepage&q=EJEMPLO%20

LZ77&f=false.

gedlc. (s.f.). http://www.gedlc.ulpgc.es/docencia/seminarios/cd/Diccionarios/tsld015.htm.

Pea, R. S. (s.f.).

http://iaci.unq.edu.ar/materias/comunicacion/archivos/apuntes/Compresion%20po

r%20diccionarios.pdf.

Prieto, M. (s.f.). http://www.infor.uva.es/~migumar2/docs/tesis.pdf.

Sandoval, M. M. (s.f.).

http://www.tamps.cinvestav.mx/~mmorales/documents/Compre.pdf.

wikipedia. (s.f.). http://es.wikipedia.org/wiki/LZSS.

informe compresion lz77 albino huertas

Documents