53
edits
Changes
Jump to navigation
Jump to search
no edit summary
A codificação de Huffman é um método para construir um código prefixo eficiente para um conjunto de caractéres. Nesse algoritmo, em cada passo os vértices com menos peso são examinados. A codificação de Huffman pode produzir códigos de prefixo em condições ideais. O seguinte pseudocódigo descreve um algoritmo para codificação de Huffman. (Para uma discussão mais completa sobre a codificação de Huffman, veja Cormen, Leiserson, e Rivest, Introduction to Algorithms, MIT Press, 1989.)
Comece criando uma lista ordenada de elementos a serem codificados, onde a que tem ordenação é com respeito a frequência de ocorrência desses elementos. Considere cada elemento da lista como um vértice com peso igual a sua frequência de ocorrência.
1. Remove os dois primeiros elementos, x e y, dessa lista;
2. Atribua x como o filho a à esquerda e y como o filho a à direita de um novo vértice em nossa árvore;
3. Atribua o peso de z para ser a soma dos pesos de x e y;
</pre>
Por examploexemplo, descobrimos que [b,10] < [a,15].
<pre>
</pre>
O tipo listlist denota uma lista de listas. O eval no final é incluído para garantir que o resultado retornado pelo procedure é a própria árvore, e não apenas seu nome.
Teste esse novo procedure na seguinte lista de caractéres em inglês emparelhados com uma frequência relativa de ocorrência;
<pre>
</pre>
Os pesos adicionados aos vértices aqui representam o número que desse vértice em termos de relação a seu pai. Por exemplo, d é o terceiro filho de a. Como nas seções anteriores, tais pesos poderiam ser usados para ordenação, apesar de que em fatona verdade, a ordenação por baixo é simplesmente alfabético alfabética nos nomes dos vértices. Primeiro implementamos o algaritmo algoritmo de percurso em pré-ordem. Esse algoritmo visita a raiz e então cada sub-árvore da esquerda a direita em uma maneira de percurso em pré-ordem. Em forma de pseudocódigo, o algoritmo para pré-ordem é:
1. Visite a raiz de T. Ponha Coloque o atua atual vértice para ser a raiz.
2. Considere os filhos do vértice atual como raízes das árvores T_1, T_2, ... T_m, pegos em ordem da esquerda para a direita. Repita o passo (1) em cada sub-árvore em ordem.
</pre>
Nós implementamos o percurso em ordem de maneira similar. Simplesmente alteramos a sequência na qual os vértices são visitados. Especificamente, olhamos na sub-árvore mais a esquerda dos vértices, seguida pela raiz, e em seguida pela a sub-árvore mais a direita dos vértices. Em pseudocódigo, temos:
1. Se a árvore T tem apenas um vértice, r então visite r
