> shannon | fano | entropia <
// Shannon-Fano – Codificação por entropia top-down para compressão de dados
Baseado em entropia
Usa teoria da informação para criar códigos eficientes de comprimento variável.
Abordagem top-down
Divide recursivamente os símbolos em grupos com probabilidades semelhantes.
Algoritmo histórico
Método pioneiro que influenciou muitos esquemas modernos de compressão.
>> informações técnicas
Como funciona o Shannon-Fano:
A codificação Shannon-Fano ordena os símbolos por frequência e os divide recursivamente em dois grupos com probabilidades totais o mais próximas possível. Cada divisão adiciona um bit ao código (0 à esquerda, 1 à direita). O resultado é um código de prefixo com comprimento variável.
Processo de codificação:
Texto: "AAABBCD" Frequências: A:3, B:2, C:1, D:1 Divisão: [A] | [B,C,D] Códigos: A: 0 B: 10 C: 110 D: 111 Codificado: 0 0 0 10 10 110 111
Por que usar Shannon-Fano:
- >Simples de implementar
- >Boas taxas de compressão
- >Importância histórica
- >Útil para ensino
- >Códigos de prefixo
>> perguntas frequentes
O que é a codificação Shannon-Fano?
A codificação Shannon-Fano é uma técnica de codificação por entropia desenvolvida por Claude Shannon e Robert Fano na década de 1940. Foi um dos primeiros algoritmos a usar códigos de comprimento variável baseados na probabilidade dos símbolos.
Shannon-Fano vs. Huffman?
Ambos produzem códigos de comprimento variável, mas Huffman é ótimo e gera o menor comprimento médio de código. Shannon-Fano é mais simples, mas pode gerar códigos um pouco mais longos. Huffman constrói a árvore de baixo para cima; Shannon-Fano, de cima para baixo.
Como funciona a divisão dos símbolos?
Os símbolos são ordenados por frequência e divididos em dois grupos com probabilidades totais o mais próximas possível. Esse processo se repete de forma recursiva até que cada grupo contenha apenas um símbolo.
Shannon-Fano ainda é usado?
Hoje, Shannon-Fano é usado principalmente com fins históricos e educacionais. Na prática, foi em grande parte substituído pela codificação de Huffman, que garante a optimalidade. Ainda assim, é valioso para aprender os conceitos de compressão.
// Exemplo resolvido
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// Exemplos de código
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> Mais perguntas
P: Como o Shannon-Fano difere do Huffman?
R: O Shannon-Fano divide a lista ordenada de cima para baixo em duas metades de frequência o mais iguais possível; o Huffman constrói a árvore de baixo para cima unindo os símbolos mais raros. O Huffman é comprovadamente ótimo; o Shannon-Fano nem sempre.
P: O Shannon-Fano é sempre ótimo?
R: Não. No exemplo precisa de 89 bits contra 87 do Huffman. Ambos geram códigos livres de prefixo, mas a regra de divisão do Shannon-Fano pode escolher cortes desfavoráveis.
P: Onde o Shannon-Fano é usado?
R: Principalmente como método histórico e didático (Claude Shannon e Robert Fano, 1948/49). Uma variante está no algoritmo IMPLODE do ZIP; compressores modernos usam Huffman ou codificação aritmética.