Usando os símbolos 0,1 e 2 , use um código de Huffman ternário ( m=3 ) para codificar estas letras com as freqüências dadas: A: 0,25, \mathrm{E}: 0,30, \mathrm{~N}: 0,10, \mathrm{R}: 0,05, \mathrm{~T} : 0,12, \mathrm{Z}: 0,18.

Passo 1

O enunciado pede um código de Huffman ternário (alfabeto \{0,1,2\}) para as letras com frequências \mathrm{A}:0,25, \mathrm{E}:0,30, \mathrm{N}:0,10, \mathrm{R}:0,05, \mathrm{T}:0,12, \mathrm{Z}:0,18.
Para um código m-ário é preciso que (n-1)\bmod(m-1)=0. Aqui n=6, m-1=2, e (6-1)\bmod2=1\neq0, então adicionamos um símbolo fantasma X com frequência 0.

Passo 2

Listamos todas as frequências, incluindo X, em ordem crescente:
X:0,\quad \mathrm{R}:0{,}05,\quad \mathrm{N}:0{,}10,\quad \mathrm{T}:0{,}12,\quad \mathrm{Z}:0{,}18,\quad \mathrm{A}:0{,}25,\quad \mathrm{E}:0{,}30.
Como é ternário, no primeiro passo juntamos os três menores: X, \mathrm{R} e \mathrm{N}.
Criamos o nó U de frequência
f(U)=0+0{,}05+0{,}10=0{,}15.

Passo 3

Agora a lista é
\mathrm{T}:0{,}12,\quad U:0{,}15,\quad \mathrm{Z}:0{,}18,\quad \mathrm{A}:0{,}25,\quad \mathrm{E}:0{,}30.
Juntamos os três menores novamente: \mathrm{T}, U e \mathrm{Z}, formando o nó V com
f(V)=0{,}12+0{,}15+0{,}18=0{,}45.

Passo 4

Sobram então
\mathrm{A}:0{,}25,\quad \mathrm{E}:0{,}30,\quad V:0{,}45.
Como são exatamente três, juntamos tudo na raiz W com
f(W)=0{,}25+0{,}30+0{,}45=1{,}00.

Passo 5

Agora atribuímos dígitos \{0,1,2\} aos ramos, em cada nó do menor para o maior filho:
  • No nó raiz W:
    \mathrm{A} 0{,}25 \to 0, \mathrm{E} 0{,}30 \to 1, V 0{,}45 \to 2.
  • No nó V:
    \mathrm{T} 0{,}12 \to 0, U 0{,}15 \to 1, \mathrm{Z} 0{,}18 \to 2.
  • No nó U:
    X (fantasma) \to 0, \mathrm{R} 0{,}05 \to 1, \mathrm{N} 0{,}10 \to 2.
Dessa forma cada letra tem o código dado pelo caminho da raiz até ela.

Resposta

\mathrm{A}:0 \mathrm{E}:1 \mathrm{T}:20 \mathrm{Z}:22 \mathrm{R}:211 \mathrm{N}:212

Exercícios de Livros Relacionados