Considere a cadeia de caracteres ABRACADABRA. Cada caractere é representado por 8 bits.
Mostre o processo para obter códigos binários para os caracteres da cadeia utilizando o algoritmo de Huffman.
Mostre o processo para obter códigos binários para os caracteres da cadeia utilizando o algoritmo de Huffman.
Passo 1
Então, a questão pede: “Para a string ABRACADABRA, onde cada caractere é 8 bits, mostre todo o processo de criação dos códigos binários usando o algoritmo de Huffman.”
Conteúdo: compressão de dados com árvores de Huffman.
O que vamos precisar:
Conteúdo: compressão de dados com árvores de Huffman.
O que vamos precisar:
- Contar a frequência de cada letra;
- Montar uma fila de prioridade (menor frequência primeiro);
- Aplicar passo a passo de unir os dois nós de menor frequência para gerar a árvore;
- Atribuir 0/1 para gerar cada código.
Passo 2
Primeiro conta as frequências dos caracteres na palavra ABRACADABRA (11 letras):
A: aparece 5 vezes
B: 2 vezes
R: 2 vezes
C: 1 vez
D: 1 vez
A: aparece 5 vezes
B: 2 vezes
R: 2 vezes
C: 1 vez
D: 1 vez
Em notação de conjunto com peso:
Passo 3
Agora vamos construir a árvore de Huffman. A cada passo, pegamos os dois nós com menor peso e unimos:
- Menores são C(1) e D(1). Juntando vira um nó “(C,D)” com peso
.
Fila vira:. - Pegamos dois dos três nós de peso 2; por exemplo, juntamos
e → nó “(CD,B)” de peso .
Fila:. - Pegamos
e → nó “(R,CD,B)” de peso .
Fila:. - Por fim, juntamos
e → nó raiz de peso .
Passo 4
A árvore completa fica assim (com esqueminha de pesos):
(11)
/ \
A(5) X(6)
/ \
R(2) Y(4)
/ \
CD(2) B(2)
/ \
C(1) D(1)
Passo 5
Agora, pra gerar o código de cada letra, basta escolher “0” para ir à esquerda e “1” para ir à direita (ou vice-versa, mas vamos fixar assim):
Da raiz até cada folha:
- A: esquerda → código “0”.
- R: direita, depois esquerda → “1 0”.
- B: direita, depois direita, depois direita → “1 1 1”.
- C: direita, direita, esquerda, esquerda → “1 1 0 0”.
- D: direita, direita, esquerda, direita → “1 1 0 1”.
Resposta
Os códigos de Huffman para ABRACADABRA são:
A: 0
R: 10
B: 111
C: 1100
D: 1101
A: 0
R: 10
B: 111
C: 1100
D: 1101