Considere a cadeia de caracteres ABRACADABRA. Cada caractere é representado por 8 bits.
Determine a razão de compressão obtida com o método utilizado.

Passo 1

Beleza, a questão diz: “Considere a cadeia de caracteres ABRACADABRA. Cada caractere é representado por 8 bits. Determine a razão de compressão obtida com o método utilizado.”
Conteúdo: codificação de Huffman (compressão sem perdas)
O que vamos precisar:
  • Contar frequência de cada símbolo
  • Montar a árvore de Huffman
  • Calcular quantos bits ficamos usando após a codificação
  • Comparar com os 8 bits originais por símbolo para achar a razão de compressão

Passo 2

Primeiro, vamos contar quantas vezes cada letra aparece em “ABRACADABRA” (11 caracteres no total):
A: 5 vezes
B: 2 vezes
R: 2 vezes
C: 1 vez
D: 1 vez
Essa frequência é a base pra montar o código de Huffman – quanto mais frequente o símbolo, menor o código em bits.

Passo 3

Agora, construímos a árvore de Huffman de baixo pra cima, sempre juntando os dois nós de menor frequência até sobrar um só:
  1. Juntamos C(1) + D(1) → nó CD(2)
  2. Temos agora [A(5), B(2), R(2), CD(2)]
  3. Juntamos dois nós de peso 2 (por exemplo B + R) → nó BR(4)
  4. Agora [A(5), BR(4), CD(2)]
  5. Juntamos CD(2) + BR(4) → nó X(6)
  6. Finalmente juntamos A(5) + X(6) → raiz(11)
Dessa forma, cada letra ganha um código binário de acordo com o caminho na árvore (esquerda/0, direita/1). Um exemplo de atribuição possível:
A: 0
R: 10
B: 110
C: 1110
D: 1111

Passo 4

Com esses códigos, agora calculamos quantos bits usamos no total:
– A (5 vezes) usa 1 bit cada → 5×1 = 5 bits
– R (2 vezes) usa 2 bits cada → 2×2 = 4 bits
– B (2 vezes) usa 3 bits cada → 2×3 = 6 bits
– C (1 vez) usa 4 bits → 1×4 = 4 bits
– D (1 vez) usa 4 bits → 1×4 = 4 bits
Total de bits comprimidos =
5 + 4 + 6 + 4 + 4 ;=; 23 bits
Originalmente, cada caractere ocupava 8 bits e eram 11 caracteres, ou seja:
tamanho original = 11 times 8 = 88 bits

Passo 5

Agora definimos a razão de compressão como
Razão = tamanho originaltamanho comprimido ã
Logo:
Razão = 8823 approx 3,83 ã

Resposta

A razão de compressão obtida é aproximadamente .

Exercícios relacionados