Use a codificação de Huffman para codificar estes símbolos com as freqüências dadas: A: 0,10, \mathrm{~B}: 0,25, \mathrm{C}: 0,05, \mathrm{D} : 0,15, \mathrm{E}: 0,30, \mathrm{~F}: 0,07, \mathrm{G}: 0,08. Qual o número médio de bits necessários para codificar um caractere?

Passo 1

O enunciado nos dá sete símbolos \{A,B,C,D,E,F,G\} com frequências
p_A=0,10,\;p_B=0,25,\;p_C=0,05,\;p_D=0,15,\;p_E=0,30,\;p_F=0,07,\;p_G=0,08
e pede o número médio de bits por caractere usando codificação de Huffman. Vamos construir a árvore de Huffman, extrair os comprimentos de código e calcular
L_\text{média}=\sum_{X\in\{A,\dots,G\}} p_X\,\ell_X.é

Passo 2

Ordenando os símbolos por frequência crescente:
C(0,05),\;F(0,07),\;G(0,08),\;A(0,10),\;D(0,15),\;B(0,25),\;E(0,30).

Passo 3

Construímos a árvore de Huffman juntando sempre os dois nós de menor peso:
  1. C(0,05)+F(0,07)\to CF(0,12)
  2. G(0,08)+A(0,10)\to GA(0,18)
  3. CF(0,12)+D(0,15)\to CFD(0,27)
  4. GA(0,18)+B(0,25)\to GAB(0,43)
  5. CFD(0,27)+E(0,30)\to CFDE(0,57)
  6. GAB(0,43)+CFDE(0,57)\to\text{Raiz}(1,00)

Passo 4

Cada símbolo fica em uma folha cuja profundidade é o comprimento \ell_X do código:
\begin{aligned} &\ell_B=2,\quad \ell_E=2,\\\ &\ell_A=3,\quad \ell_G=3,\quad \ell_D=3,\\\ &\ell_C=4,\quad \ell_F=4. \end{aligned}

Passo 5

Calculamos o número médio de bits:
L_\text{média} =0,30\cdot2+0,25\cdot2+0,15\cdot3+0,10\cdot3+0,08\cdot3+0,05\cdot4+0,07\cdot4 =2,57\\ \text{bits}.é

Resposta

O número médio de bits por caráter na codificação de Huffman é aproximadamente
2,57\\ \text{bits por caractere.}

Exercícios de Livros Relacionados