Uma fonte
produz símbolos com probabilidades
. Para esta fonte:
(a) Calcule a sua entropia;
(b) Ache um código de Shannon-Fano binário e calcule seu comprimento médio e eficiência;
(c) Ache um código de Huffman binário e calcule seu comprimento médio e eficiência.
(d) Ache um código de Huffman ternário e calcule seu comprimento médio e eficiência;
(e) Compare os resultados obtidos nos ítens (b)-(d) com aquele obtido no item (a).
(a) Calcule a sua entropia;
(b) Ache um código de Shannon-Fano binário e calcule seu comprimento médio e eficiência;
(c) Ache um código de Huffman binário e calcule seu comprimento médio e eficiência.
(d) Ache um código de Huffman ternário e calcule seu comprimento médio e eficiência;
(e) Compare os resultados obtidos nos ítens (b)-(d) com aquele obtido no item (a).
Passo 1
O enunciado dá uma fonte
com sete símbolos cujas probabilidades, em ordem, são
As perguntas são:
(a) Calcular a entropia da fonte (em bits/símbolo).
(b) Construir um código de Shannon–Fano binário e calcular seu comprimento médio e eficiência.
(c) Construir um código de Huffman binário e calcular seu comprimento médio e eficiência.
(d) Construir um código de Huffman ternário e calcular seu comprimento médio (em trits e em bits) e eficiência.
(e) Comparar os resultados dos itens (b)–(d) com a entropia do item (a).
(a) Calcular a entropia da fonte (em bits/símbolo).
(b) Construir um código de Shannon–Fano binário e calcular seu comprimento médio e eficiência.
(c) Construir um código de Huffman binário e calcular seu comprimento médio e eficiência.
(d) Construir um código de Huffman ternário e calcular seu comprimento médio (em trits e em bits) e eficiência.
(e) Comparar os resultados dos itens (b)–(d) com a entropia do item (a).
Lista explícita das probabilidades (vou chamar os símbolos de
na mesma ordem):
Passo 2
(a) Entropia: fórmula e interpretação.
A entropia de uma fonte discreta é
A entropia de uma fonte discreta
onde
é o logaritmo na base 2 e
tem unidades de bits por símbolo. Cada termo
mede a “incerteza” associada ao símbolo
.
Vou calcular termo a termo (mostrando os passos de cálculo):
Para
:
Para
:
Para
:
Para
(os dois símbolos com
darão o mesmo termo):
Como há dois símbolos com
, a contribuição total desses dois é
.
Para
:
Para
:
Agora somo todos os termos para obter
:
Portanto a entropia da fonte é aproximadamente
Passo 3
(b) Código de Shannon–Fano (binário): explicação do método e construção.
Breve explicação do método Shannon–Fano: ordenar símbolos por probabilidade decrescente; dividir a lista em dois grupos com somas de probabilidade o mais próximas possível; atribuir aos dois grupos bits distintos (por exemplo 0 e 1); repetir recursivamente em cada grupo até que cada símbolo tenha um código. Não é garantidamente ótimo, mas é um esquema direto.
Breve explicação do método Shannon–Fano: ordenar símbolos por probabilidade decrescente; dividir a lista em dois grupos com somas de probabilidade o mais próximas possível; atribuir aos dois grupos bits distintos (por exemplo 0 e 1); repetir recursivamente em cada grupo até que cada símbolo tenha um código. Não é garantidamente ótimo, mas é um esquema direto.
Aplicando ao nosso vetor ordenado (já ordenado):
- Divisão inicial: melhor separação é after
(soma vs ). Logo recebe prefixo e os demais prefixo . - No grupo com soma
(os outros seis), melhor separação é vs . Então recebe prefixo e o restante . - No grupo com soma
(desde em diante), separar vs (resto). Assim recebe e o restante . - No grupo
(os quatro menores) a melhor separação foi vs — a divisão usada aqui acabou sendo com prefixo e com prefixo . - Dividindo as duplas finais em símbolos individuais, obtém-se códigos finais.
Códigos Shannon–Fano resultantes (associados a
na ordem dada):
Comprimentos
:
.
Agora o comprimento médio
é
Calculando termo a termo:
Somando:
Eficiência do código (definição):
. Então
Passo 4
(c) Código de Huffman binário: algoritmo, construção e cálculo.
Explicação rápida do algoritmo Huffman (binário): combinar repetidamente os dois símbolos/nós de menor probabilidade, formando um nó com probabilidade igual à soma; repetir até restar um nó. Em seguida, atribuir 0/1 a cada bifurcação para obter códigos prefixos ótimos (mínimo comprimento médio possível em código binário prefixo).
Explicação rápida do algoritmo Huffman (binário): combinar repetidamente os dois símbolos/nós de menor probabilidade, formando um nó com probabilidade igual à soma; repetir até restar um nó. Em seguida, atribuir 0/1 a cada bifurcação para obter códigos prefixos ótimos (mínimo comprimento médio possível em código binário prefixo).
Construção passo a passo (probabilidades iniciais):
- Combinar
e nó . - Agora temos
. Combinar e nó . - Lista:
. Combinar e nó . - Lista:
. Combinar e nó . - Lista:
. Combinar e nó . - Finalmente combinar
e raiz .
Atribuindo bits (uma escolha consistente: sempre “esquerda=0, direita=1”) e lendo do topo para as folhas obtemos, por exemplo, os códigos:
(repare que os comprimentos resultam iguais aos do Shannon–Fano neste caso:
).
Comprimento médio
:
os mesmos termos que no passo anterior dão
os mesmos termos que no passo anterior dão
Eficiência:
Observação didática curta: Huffman é ótimo entre códigos prefixos binários, portanto não existe código binário prefixo com comprimento médio menor que
para esta distribuição (exceto empacotamento/variação de blocos). O Shannon–Fano aqui foi quase tão bom quanto o Huffman, produzindo o mesmo comprimento médio.]
Passo 5
(d) Código de Huffman ternário: regra geral, ajuste e construção.
Para Huffman em alfabeto ternário (símbolos do código com 3 valores: por ex. ), a versão geral do algoritmo combina os
menores nós a cada etapa, mas é preciso primeiro verificar a condição para que a árvore fique completa: com
símbolos e alfabeto de ordem
a condição para não precisar inserir símbolos fictícios é
. Aqui
e
, então
e
. Logo não é necessário acrescentar símbolos fictícios.
Para Huffman em alfabeto ternário (símbolos do código com 3 valores: por ex.
Procedimento (combinar três menores a cada passo):
Probabilidades iniciais ordenadas:
- Combinar os três menores
(formando nó ).
Restam. - Combinar os três menores
(formando nó ).
Restam. - Combinar esses três
(raiz). Fim.
Atribuindo os dígitos ternários (por exemplo 0,1,2 em cada nó, da esquerda para a direita), uma possível atribuição de códigos (em trits) é:
- Na raiz: filho correspondente a
→ prefixo ; filho correspondente a (0,26) → prefixo ; filho correspondente a (0,49) → prefixo . Assim e têm códigos de comprimento trit. - No nó
(prefixo ), seus filhos eram (0,04), (0,09) e (0,12). Atribuindo em ordem 0,1,2 temos: -
: (2 trits) - nó
: (prefixo para os três mais pequenos) -
: (2 trits)
-
- No nó
(prefixo ), filhos (0,02), (0,03), (0,04) recebem 0,1,2 respectivamente: -
: (3 trits) -
: (3 trits) -
: (3 trits)
-
Resumo dos códigos ternários (em trits) para
:
Comprimento médio em trits:
Calculando:
Cada trit representa
bits. Portanto o comprimento médio em bits é
Eficiência:
Passo 6
(e) Comparação e interpretação dos resultados.
Resumo numérico (para fácil comparação):
Resumo numérico (para fácil comparação):
- Entropia:
- Shannon–Fano (binário):
bits/símbolo, . Redundância bits/símbolo. - Huffman (binário):
bits/símbolo, . (Huffman é ótimo entre códigos binários prefixo; aqui o comprimento médio coincide com o do SF.) - Huffman (ternário):
trits/símbolo bits/símbolo, . Redundância bits/símbolo.
Interpretação intuitiva e motivação para a diferença:
- A entropia é um limite teórico para o melhor comprimento médio possível em bits por símbolo (sem restrições sobre o alfabeto do código ou estrutura).
- Entre códigos binários prefixo, o código de Huffman é ótimo; aqui ele alcançou
, muito próximo de (diferença bits por símbolo). Isso significa que com código binário simples obteve-se eficiência superior a . - O código ternário tem menos “granularidade” porque trabalha em trits (cada trit =
bits). Mesmo tendo comprimentos médios menores em trits (1,34 trits), ao converter para bits isso ficou mais longe da entropia (≈2,124 bits), portanto eficiência menor. Em outras palavras, a base do código (2 vs 3) influencia a aproximação ao valor real da entropia em bits; escolher alfabetos com tamanho que não se harmoniza bem com a entropia em bits pode produzir maior “espaço desperdiçado”. - Conclusão prática: para esta distribuição a escolha binária com Huffman é quase ideal; o código ternário resulta em maior comprimento médio em bits.
Resposta
(a)
(b) Código Shannon–Fano (associado a ):
. Comprimento médio
. Eficiência
(99,64%).
(c) Código Huffman binário (uma escolha possível): . Comprimento médio
. Eficiência
(99,64%).
(d) Código Huffman ternário (em trits): . Comprimento médio
, que equivale a
. Eficiência
(94,72%).
(e) Comparação: os códigos binários (Shannon–Fano e Huffman) chegam muito perto da entropia (diferença ≈ bits/símbolo, eficiência ≈ 99,64%). O Huffman ternário, quando convertido para bits, fica mais longe da entropia (diferença ≈
bits/símbolo, eficiência ≈ 94,72%). Portanto, para esta distribuição, o código binário Huffman é praticamente ótimo e melhor que a alternativa ternária.
(b) Código Shannon–Fano (associado a
(c) Código Huffman binário (uma escolha possível):
(d) Código Huffman ternário (em trits):
(e) Comparação: os códigos binários (Shannon–Fano e Huffman) chegam muito perto da entropia (diferença ≈