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.

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:
  1. Contar a frequência de cada letra;
  2. Montar uma fila de prioridade (menor frequência primeiro);
  3. Aplicar passo a passo de unir os dois nós de menor frequência para gerar a árvore;
  4. 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
Em notação de conjunto com peso:
(A,5),,(B,2),,(R,2),,(C,1),,(D,1)

Passo 3

Agora vamos construir a árvore de Huffman. A cada passo, pegamos os dois nós com menor peso e unimos:
  1. Menores são C(1) e D(1). Juntando vira um nó “(C,D)” com peso 1+1=2.
    Fila vira: (B,2),,(R,2),,(CD,2),,(A,5).
  2. Pegamos dois dos três nós de peso 2; por exemplo, juntamos (CD,2) e B(2) → nó “(CD,B)” de peso 2+2=4.
    Fila: (R,2),,(CD,B,4),,(A,5).
  3. Pegamos R(2) e (CD,B,4) → nó “(R,CD,B)” de peso 2+4=6.
    Fila: (A,5),,(R,CDB,6).
  4. Por fim, juntamos A(5) e (R,CDB,6) → nó raiz de peso 11.

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

Exercícios relacionados