Lempel - Ziv

UFF – Universidade Federal Fluminense
Graduação em Ciência da Computação

Trabalho de Pesquisa

Lempel - Ziv

Alonso Leonardo
Lais Dina

Rio das Ostras
2012.2

UFF – Universidade Federal Fluminense
Graduação em Ciência da Computação

O QUE É LEMPEL - ZIV, COMO SURGIU E QUAL
SUA RELAÇÃO COM A COMPACTAÇÃO

Trabalho apresentado a Universidade
Federal Fluminense como requisito de nota parcial em Programação Com
Arquivo, sob a orientação do professor
Dalessandro.

Alonso Leonardo
Lais Dina

Rio das Ostras
2012.2
1

S U M Á R IO

1 Introdução……………………………………………………………3
2 Modelo do Lempel-Ziv (LZ78)…………………………………….3
3 Compactação……………………………………………………….4
3.1 Funcionamento……………………………………………………….4
3.2 Diagrama……………………………………………………………….6
3.3 Algoritmo……………………………………………………………….7

4 Descompactação……………………………………………………8
4.1 Funcionamento………………………………………………………..8
4.2 Diagrama………………………………………………………………..9
4.3 Algoritmo………………………………………………………………10

5 Curiosidades……………………………………………………….11
6 Referencias Bibliográficas………………………………………11

2

1. Introdução
Com o crescimento da Internet, passou a ser necessário a utilização de compressores, pois a comunicação entre sistemas e a transferência de grandes quantidades de dados se tornaram cada vez mais frenquentes. Como os sistemas dedicados não permitiam a utilização de compressores que utilizavam modelos estatísticos como a codificação Huffman, então em 197778, Jacob Ziv e Abraham Lempel propuseram um método de compressão baseado em modelo de dicionário designado por Lempel-Ziv.
O Lempel-Ziv é um algoritmo de compressão de dados, sem perda de informação e é mais eficiente em arquivos com grupos de repetições de caracteres, como em arquivos binários e imagens. Este modelo de compressão funciona a partir da leitura de um arquivo substituindo seus caracteres por códigos que utilizam menos bits.

2. Modelo do Lempel-Ziv (LZ78)
O método de compressão Lempel-Ziv é baseado no modelo de