Construa um código de Huffman para as letras do alfabeto inglês em que as freqüências das letras em um texto típico em inglês são mostradas na tabela.
Letra
Freqüência
Letra
Freqüência
A
0,0817
N
0,0662
B
0,0145
O
0,0781
C
0,0248
P
0,0156
D
0,0431
Q
0,0009
E
0,1232
R
0,0572
F
0,0209
S
0,0628
G
0,0182
T
0,0905
H
0,0668
U
0,0304
I
0,0689
V
0,0102
J
0,0010
W
0,0264
K
0,0080
X
0,0015
L
0,0397
Y
0,0211
M
0,0277
Z
0,0005
| Letra | Freqüência | Letra | Freqüência |
| A | 0,0817 | N | 0,0662 |
| B | 0,0145 | O | 0,0781 |
| C | 0,0248 | P | 0,0156 |
| D | 0,0431 | Q | 0,0009 |
| E | 0,1232 | R | 0,0572 |
| F | 0,0209 | S | 0,0628 |
| G | 0,0182 | T | 0,0905 |
| H | 0,0668 | U | 0,0304 |
| I | 0,0689 | V | 0,0102 |
| J | 0,0010 | W | 0,0264 |
| K | 0,0080 | X | 0,0015 |
| L | 0,0397 | Y | 0,0211 |
| M | 0,0277 | Z | 0,0005 |
Passo 1
O enunciado pede para construir um código de Huffman para o alfabeto inglês usando as frequências típicas de cada letra. O conteúdo envolve o algoritmo de Huffman, que gera um código binário de comprimento médio mínimo ao combinar repetidamente os dois símbolos de menor frequência em uma árvore binária. Vamos precisar ordenar as letras por frequência, aplicar as fusões do algoritmo e depois atribuir bits 0/1 aos ramos para ler os códigos finais.
Passo 2
Primeiro, listamos as letras com suas frequências e ordenamos em ordem crescente de frequência:
Letra – Freqüência
Z – 0,0005
Q – 0,0009
J – 0,0010
X – 0,0015
K – 0,0080
V – 0,0102
B – 0,0145
P – 0,0156
G – 0,0182
F – 0,0209
Y – 0,0211
C – 0,0248
W – 0,0264
M – 0,0277
U – 0,0304
L – 0,0397
D – 0,0431
R – 0,0572
S – 0,0628
N – 0,0662
H – 0,0668
I – 0,0689
O – 0,0781
A – 0,0817
T – 0,0905
E – 0,1232
Z – 0,0005
Q – 0,0009
J – 0,0010
X – 0,0015
K – 0,0080
V – 0,0102
B – 0,0145
P – 0,0156
G – 0,0182
F – 0,0209
Y – 0,0211
C – 0,0248
W – 0,0264
M – 0,0277
U – 0,0304
L – 0,0397
D – 0,0431
R – 0,0572
S – 0,0628
N – 0,0662
H – 0,0668
I – 0,0689
O – 0,0781
A – 0,0817
T – 0,0905
E – 0,1232
Passo 3
Aplicamos o algoritmo de Huffman, que consiste em:
- Repetidamente tomar os dois nós (iniciais: letras) de menor frequência e fundi-los num novo nó cujo peso é a soma das duas frequências.
- Reinserir esse novo nó na lista, mantendo-a ordenada.
- Continuar até restar um único nó (a raiz da árvore).
Cada fusão corresponde a um nó interno da árvore que une dois ramos.
Com a árvore completa, atribuímos 0 ao ramo esquerdo e 1 ao ramo direito em cada bifurcação.
Para cada letra, seu código é obtido lendo-se a sequência de bits do root até a folha correspondente. A seguir apresentamos uma das possíveis soluções ótimas (código canônico para os comprimentos gerados pelo algoritmo).
Com a árvore completa, atribuímos 0 ao ramo esquerdo e 1 ao ramo direito em cada bifurcação.
Para cada letra, seu código é obtido lendo-se a sequência de bits do root até a folha correspondente. A seguir apresentamos uma das possíveis soluções ótimas (código canônico para os comprimentos gerados pelo algoritmo).
Resposta
E :
T :
A :
H :
I :
O :
D :
L :
M :
N :
R :
S :
U :
C :
F :
G :
P :
W :
Y :
B :
J :
K :
Q :
V :
X :
Z : Esse é um código de Huffman ótimo (médio comprimento esperado mínimo) para as frequências fornecidas.
T :
A :
H :
I :
O :
D :
L :
M :
N :
R :
S :
U :
C :
F :
G :
P :
W :
Y :
B :
J :
K :
Q :
V :
X :
Z :