Aula03c-compressao-Lempel-Ziv

Prévia do material em texto

1
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.
• Omé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
apenas um deles [LZ78]. 2
Compressão de Dados- Lempel-Ziv
• 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
3
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.
aaababbbaaabaaaaaaabaabb
Index: 0 1 2 3 4 5 6 7 8 9 10
0 aaababbbaaabaaaaaaabaabb
0���� null
4
Compressão de Dados- Lempel-Ziv
Codificação Lempel-ZIV
Index: 0 1 2 3 4 5 6 7 8 9 10
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
1 3
2 4
6 9
7 5
108
b
a
a a
a
a
b
b
b
b
A árvore não 
é binária
5
Compressão de Dados- Lempel-Ziv
Exercício:
Codifique a seguinte mensagem: ARARAQUARA
1 A
2 R
3 AR
4 AQ
5 U
6 ARA
2
3
1
4
6
5
Q
A
R
A
R
U
6
Compressão de Dados- Lempel-Ziv
Exercício:
Decodifique a seguinte mensagem:
0A0 1N 1 1M4O2N3D0O
1 A
2 b
3 AN
4 Ab
5 AM
6 AbO
7 bN
8 AND
9 O
bb
A ANA AMA O NANDO
7
Compressão de Dados- Lempel-Ziv
O número de bits requerido para codificar o arquivo
• Cada letra é representada por 8 bits
• Cada índice é representado pelo maior número de bits
possível
• Quantos bits são necessário para representar os n índices?
1 2 3 4 5 6 7 8 9 10
a1a0b1b3b2a3a6a2b9b
Índice 1: nenhum bit
Índice 2: no máximo 1 bit ����pode apontar para 0 ou 1
Índice 3: no máximo 2���� pode apontar para 0, 1 ou 2
Índice 4: no máximo 2���� pode apontar para 0, 1, 2 ou 3
Índice 5-8: no máximo 3���� pode apontar para índice entre 0 e 7
Índice 9-16: no máximo 4���� pode apontar p/ índice entre 0 e 17
8
Compressão de Dados- Lempel-Ziv
• Exemplo: no. de bits são necessário para representar a cadeia
aaababbbaaabaaaaaaabaabb
1 2 3 4 5 6 7 8 9 10
a1a0b1b3b2a3a6a2b9b
seqüência enviada: a1a0b1b11b10a11a110a10b1001b
índice Ind
binário
frase código
0 0 null
1 1 a a
2 10 aa 1a
3 11 b 0b
4 100 ab 1b
5 101 bb 11b
6 110 aaa 10a
7 111 ba 11a
8 1000 aaaa 110a
9 1001 aab 10b
10 1010 aabb 1001b
n.o total de bits no arquivo codificado:
No. Bits para caracteres= (10letras x 8bits)=80
No. Bits para índices= 3x1+4x2+1x3+1x4=18
Total de bits no arquivo = 24 letras x 8 bits=192 bits
Total de bits no arquivo codificado=98 bits
9
Compressão de Dados- Lempel-Ziv
Exercício: 
calcule o espaço para armazenar a mensagem do 
exercício:A ANA AMA O NANDO
cadeias: null AbANAbAMAbObNANDO
Índices: 0 1 2 3 4 5 6 7 8 9
codificado � A0b1N1b1M100O10N11D0O
NORMAL=17 letras X 8 BITS =136 BITS
COMPACTADO=(9cadeias x8bits)+ 5 x 1 + 2 x 2 + 1 x 4 =13 bits
10
Compressão de Dados- Lempel-Ziv
• utilizam os códigos Lempel-Ziv
• zip e unzip do Windows e
• compress e uncompress do Unix
11
Compressão de Dados- Lempel-Ziv
Exercícios
1. Qual é o número de bits necessários para codificar a 
string (ABCAACDDEAACCCDAECDE) usando Lempel-
Ziv?
2. Mostre a decodificação de uma cadeia de uma cadeia de 
DNA que foi codificada utilizando Lempel-Ziv. Cada base 
foi representada por dois bits como segue:
A ���� 00 C ���� 01 G ���� 10 T ���� 11
O resultado da codificação de arquivo é:
000100110001101011100010110100101
12
Compressão de Dados- Lempel-Ziv
Exercício-1 – Solução
A cadeia é parcionada em 12 frases como segue:
A|B|C|AA|CD|D|E|AAC|CC|DA|EC|DE|
As frses serão codoficados utilizando 12 índices:
1 2 3 4 5 6 7 8 9 10 11 12
|A|0B|0C|1A|3D|0D|0E|4C|3C|6A|7C|6E
número de bits por índice:0 1 1 1 2 1 1 2 2 3 3 3 =20
Número de bits para codificar o arquivo 
= (nº de bits para 12 caracteres) + (nº de bits para os 12 índices)
= (12x8) + 20= 96 +21=116
13
Compressão de Dados- Lempel-Ziv
Exercício-2 – Solução
A ���� 00 C ���� 01 G ���� 10 T ���� 11 
Separando as bases dos índices: 
índices ���� vermelho e bases���� azul
1 2 3 4 5 6 7 8
|00|010|110|011|1011|10001|1101|101|
Convertendo as bases:
1 2 3 4 5 6 7 8
|A |0G |1G |0T |2T | 4C |3C |1C|
Decodificando: A G AG T GT TC AGC AC
Resultado: AGAGTGTTCAGCAC
14
Compressão de dados
Bibliografia:
• Introduction to Data Compression, Khalid Sayood, ed Morgan 
Kaufmann, Feb/ 2000.
• Lossless Compression Handbook, Khalid Sayood - ed Elsevier-
Science, 2003.