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.
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:
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
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ó:
- Juntamos C(1) + D(1) → nó CD(2)
- Temos agora [A(5), B(2), R(2), CD(2)]
- Juntamos dois nós de peso 2 (por exemplo B + R) → nó BR(4)
- Agora [A(5), BR(4), CD(2)]
- Juntamos CD(2) + BR(4) → nó X(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
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
– 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 =
Originalmente, cada caractere ocupava 8 bits e eram 11 caracteres, ou seja:
Passo 5
Agora definimos a razão de compressão como
Logo:
Resposta
A razão de compressão obtida é aproximadamente
.