Engenharia

Compressão de Dados- Lempel-Ziv

Compressão de Dados- Lempel-Ziv

• Método de compressão baseado em dicionário que codificam strings de símbolos, de comprimentos variáveis, como códigos individuais.
• Esse código formam um índice para um dicionário de frases.
• O algoritmo de Lempel-Ziv utiliza duas áreas de trabalho:
Dicionário onde ficam armazenadas as informações codificadas.
Área de pesquisa onde fica o string a comprimir ou descomprimir. • O método consiste de:
• compressão: identificar, na área de pesquisa, a maior seqüência de símbolos armazenada no dicionário e substituí-la por um código.
• descompressão: os códigos da área de pesquisa devem ser substituídos pelas seqüências de símbolos do dicionário, correspondentes. • Existe variações de algoritmos de Lempel-Ziv, nós vamos estudar
1
apenas um deles [LZ78].

• O algoritmo [LZ78] mantém um dicionário de “frases” já ocorridas no arquivo. • Esse dicionário começa, por definição com o símbolo null. A cada passo é criada uma nova frase, constituída de uma frase já presente no dicionário e um caractere representado explicitamente.
• Desta forma, uma dupla (N,C) é gravada no arquivo compactado
• N número da frase já ocorrida
• C O próximo caractere
• Essa dupla significa, copie a frase N seguida pelo caractere C

2

Compressão de Dados- Lempel-Ziv

Compressão de Dados- Lempel-Ziv

Exemplo: texto utilizando um albabeto de duas letras

aaababbbaaabaaaaaaabaabb
Regra: separar essa cadeia de caracteres em pedaços de texto, tal que cada pedaço é a menor cadeia de caracteres que ainda não apareceu.

Codificação Lempel-ZIV
7 8
9 10
Index: 0 1 2 3 4 5 6
0 aaababbbaaabaaaaaaabaabb
      


Codificação: 1 2 3 4 5 6 7 8 9 10
0a1a0b1b3b2a3a6a2b9b
        

aaababbbaaabaaaaaaabaabb
    
 



a

b

b

a

1

a

Index: 0 1 2 3 4 5
6
7
8
9 10
0 aaababbbaaabaaaaaaabaabb
    
 
