Esta aula foi particularmente curta uma vez que a maior parte do capítulo,
15, foi coberto na aula passada o que implicou em uma maior carga de exercícios
que foram corrigidos no mesmo dia em que essa aula foi dada.
Discutimos assim nesta aula sobre o Código de Huffman. Fizemos uma
introdução, uma explicação geral sobre o funcionamento,
sua entrada e saída e sua complexidade.
Os códigos de Huffman são utilizados para codificar uma seqüência
de caracteres objetivando minimizar o espaço de armazenamento delas
de forma a maximizar a compactação(1).
Foram citados outros exemplos de códigos utilizados atualmente, como
o código Morse e o código de área da telefonia(2).
O código de Huffman é binário de tamanho variável
e tal que o código de um caractere não é o prefixo do código de outro
caractere. Estas são
as três características principais, mais facilmente compreendidas
com a explicação de como é feita a codificação
em termos gerais.
Em uma certa coletânea de caracteres, tipicamente representada por
um arquivo, é feita uma verificação de quantas repetições
de cada elemento existem. A idéia é atribuir aos caracteres mais
freqüentes os códigos mais curtos. Todo código de prefixo pode ser
representado como uma árvore binária, onde as folhas são os
caracteres a serem codificados. A profundidade de uma folha
corresponde então ao tamanho do seu código.
O problema em sí tem como entrada um conjunto de caracteres e a
freqüência de cada caractere e como saída uma árvore
que representa o código, minimizando a soma de f(c)*dT(c),
estendida a todos os caracteres c, onde f(c) é a freqüência de c e
dT(c) é a profundidade de c na árvore.
Desta forma é gerada uma tabela
onde os elementos que aparecem maior número de vezes recebem
códigos mais curtos, que
vão ocupar menos espaço para armazenamento.
O código de Huffman implementado a seguir é o que está
na página 310 do livro texto (Introdução à algorítimos),
transcrito para facilitar o entendimento.
HUFFMAN (C)
n recebe |C|
Q recebe C for i recebe 1 to n - 1 do alocar um novo nó z
esquerda[z] recebe x recebe EXTRACT-MIN(Q)
direita[z] recebe y recebe EXTRACT-MIN(Q)
f[z] recebe f[x] + f[y]
INSERT(Q,z) return EXTRACT-MIN(Q)
Em uma estrutura de HEAP binário, há para cada invocação
da função EXTRACT-MIN, o custo de O(lg n), e também
O(lg n) para cada
invocação de INSERT. A inicialização de Q requer tempo
O(n). As operações sobre Q requerem no total O(n lg n). Sendo os outros custos constantes, este algoritmo apresenta um custo total de
O(n lg n).
(1) Enfatizada a diferença entre compactação
e compressão. Na compactação toda informação,
redundante ou não, deve estar presente. Já na compressão,
informações podem ser suprimidas desde que o produto final
mantenha seus aspectos iniciais. Um texto pode ser compactado, e todos os
caracteres precisam estar presentes para sua compreensão posteiror.
Já uma imagem pode ter elementos suprimidos, pois ainda que haja uma
certa perda de qualidade, ainda será possível identificá-la
como imagem e a informação nela contida.
(2) O sistema de atribuição de códigos
para as áreas de telefonia possue certa semelhança com o código
de Huffman pelo aspecto estatístico de escolha dos elementos. Procura-se
escolher os códigos de área com o menor valor para as regiões
mais densamente povoadas pois é onde consequentemente haverá
mais pontos da rede telefônica, e para onde espera-se mais ligações.
Esse critério foi pensado quando os aparelhos telefônicos utilizavam
um disco perfurado que deveria ser girado no sentido horário para
fornecer o número de telefone com o qual desejava-se contato. Havia
um furo para cada dígito, e os dígitos de menor valor eram
os que precisavam de um giro com um menor ângulo no disco, logo, gerando
menor esforço. no Brasil, São Paulo possue o código
11 e o Rio de Janeiro o código 21. O número 0 não era
considerado pois serve de controle (para iniciar chamadas de longa distância).