codifica o de huffman

´
Codigos
de Huffman
´
´
˜ de dados.
Codigos
de Huffman: t ecnica de compressao
˜ no tamanho dos arquivos dependem das
Reduc¸oes
caracter´ısticas dos dados contidos nos mesmos. Valores t´ıpicos oscilam entre 20 e 90%.
Exemplo: arquivo texto contendo 100.000 caracteres no
ˆ
de cada alfabeto Σ = {a, b, c, d, e, f }. As frequ¨ encias
˜
caracter no arquivo sao indicadas na tabela abaixo.
ˆ
Frequ¨ encia
(em milhares)
´
Codigo de tamanho fixo
´
Codigo de tamanho vari´avel

a
45
000
0

b
13
001
101

c
12
010
100

d
16
011
111

e
9
100
1101

˜ do arquivo: representar cada caracter por
Codificac¸ao
ˆ uma sequ¨ encia de bits
Alternativas:
1
2

ˆ sequ¨ encias de tamanho fixo.
ˆ
sequ¨ encias de tamanho vari´avel.

C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa
MC448 — P.A.A. I

f
5
101
1100

´
Codigos
de Huffman
Qual o tamanho (em bits) do arquivo comprimido usando
´
os codigos acima ?
´
Codigos de tamanho fixo: 3 × 100.000 = 300.000
´
´
Codigos
de tamanho vari avel:
(45 × 1 + 13 × 3 + 12 × 3 + 16 × 3 + 9 × 4 + 5 × 4)×1.000 = 224.000 a b

c

d

e

f

˜ a` soluc¸ao
˜ anterior.
Ganho de ≈ 25% em relac¸ ao
˜
Problema da Codificac¸ ao:
ˆ
ˆ
Dadas as frequ¨ encias de ocorrencia dos caracteres de um
ˆ
´ arquivo, encontrar as sequ¨ encias de bits (codigos) para ´ representa-los de modo que o arquivo comprimido tenha tamanho m´ınimo.
C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa
MC448 — P.A.A. I

´
Codigos
de Huffman

˜
Definic¸ao:
´
˜ aqueles onde, dados dois
Codigos
livres de prefixo sao
˜ a caracteres quaisquer i e j representados pela codificac¸ ao,
ˆ
ˆ
˜ e´ um prefixo da sequ¨ encia sequ¨ encia de bits associada a i nao associada a j.
Importante:
˜ otima
´
Pode-se provar que sempre existe uma soluc¸ ao do ˜ que e´ dado por um c odigo
´
problema da codificac¸ ao livre de prefixo. C. de Souza, C. da Silva, O. Lee, P. de Rezende, G. Pimentel, F. Miyazawa
MC448 — P.A.A. I

´
˜
Codigos de Huffman – codificac¸ao

˜ i.e, de