Esta página trata do problema de encontrar uma árvore binária de custo mínimo sob uma peculiar definição de custo. O problema admite um interessante algoritmo guloso. A principal aplicação do algoritmo é o cálculo de códigos de Huffman para compressão de arquivos. Essa aplicação será discutida no final da presente página.
O texto desta página é uma versão melhorada da seção 3, capítulo 16, de CLRS. Veja também a seção 4.8 de KT e a página Data Compression de Lelewer e Hirschberg. Veja ainda o verbete Huffman coding na Wikipedia.
Convém definir o conceito de árvore binária de maneira mais abstrata que a usual. (Em particular, convém ignorar a distinção entre filho esquerdo e filho direito de um nó da árvore).
Uma árvore binária cheia, ou ábch, sobre o conjunto {1,2,…,n} é qualquer coleção B de subconjuntos de {1,2,…,n} que tenha as seguintes propriedades:
(Um elemento X de B é minimal se nenhum subconjunto próprio de X pertence a B.) Os elementos de B são chamados nós. O nó {1,2,…,n} é a raiz de B. Os nós minimais são folhas e os demais nós são internos.
Se X, Y e X ∪ Y são elementos de B, dizemos que X e Y são os filhos de X ∪ Y. Dizemos também que X ∪ Y é o pai de X e de Y. Um ancestral de X é qualquer nó W tal que W ⊇ X. A profundidade de um nó X é o número de ancestrais de X que são diferentes de X. (A profundidade da raiz, por exemplo, é 0.)
Toda ábch com mais de dois nós tem pelo menos duas folhas X e Y tais que X ∪ Y é também um nó. Dizemos que X e Y são folhas irmãs. Se X e Y são folhas irmãs de uma ábch B então B − {X,Y} também é uma ábch.
O conjunto de todas as folhas de uma ábch é uma partição de {1,2,…,n}. Reciprocamente, dada qualquer partição F de {1,2,…,n} existe pelo menos uma ábch que tem F como conjunto de folhas.
Diremos que uma ábch sobre {1,2,…,n} tem folhas unitárias se suas folhas são {1},{2},…,{n}.
Exemplo: {{1}, {2,3}, {4}, {5}, {6}, {5,6}, {4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}} é uma ábch com raiz {1,2,3,4,5,6} e folhas {1}, {2,3}, {4}, {5} e {6}. O nó {4,5,6} é pai dos nós {4} e {5,6}. As folhas {5} e {6} são irmãs; ambas têm profundidade 4. Essa ábch pode ser representada graficamente assim:
•
┌────┴────┐
1 •
┌───┴───┐
3 2 •
┌─┴─┐
• 4
┌─┴─┐
5 6
Dados números p1,…,pn e uma parte X de {1,2,…,n}, denotaremos por p(X) a soma de todos os pi com i em X. Portanto, p(X) = ∑i∈X pi . Diremos que p(X) é o peso de X.
Seja B uma ábch sobre {1,2,…,n}. O custo de B em relação a uma família p1,…,pn de números é a soma dos pesos de todos os nós exceto a raiz:
custo(B, p) = ∑X ∈ B−{{1,…,n}} p(X) .
(O números p1,…,pn são arbitrários. Você pode supor que são inteiros, se desejar.) O custo de B pode ser calculado a partir dos pesos de suas folhas:
| custo(B, p) = ∑F∈F p(F)d(F) , | (*) |
sendo F o conjunto das folhas de B e d(F) a profundidade da folha F. (Veja exercício abaixo.)
Podemos agora formular o problema central desta página:
Problema da ábch de custo mínimo: Dada uma família p1,…,pn de pesos e uma partição F de {1,2,…,n}, encontrar, dentre as ábchs cujo conjunto de folhas é F, uma que tenha custo mínimo em relação a p.
Diremos que uma ábch B é ótima para p1,…,pn se custo(B, p) ≤ custo(B′, p) para toda ábch B′ que tenha o mesmo conjunto de folhas que B. Nosso problema é, portanto, encontrar uma ábch ótima dentre as que têm um conjunto especificado de folhas. (Estamos especialmente interessados no conjunto de folhas {{1},{2},…,{n}}.)
Nosso problema tem uma propriedade estrutural simples e natural. Seja B uma ábch ótima para uma família de pesos p1,…,pn. Sejam X e Y duas folhas irmãs de B e seja B′ a ábch B − {X,Y}.
Propriedade recursiva: A ábch B′ é ótima para p1,…,pn.
Prova: Observe que custo(B, p) = custo(B′, p) + p(X) + p(Y). Se F é o conjunto de folhas de B então o conjunto de folhas de B′ é F′ = (F − {X,Y}) ∪ {X∪Y}. Suponha, por um momento, que B′ não é ótima. Então existe uma ábch com conjunto de folhas F′ tal que custo(, p) < custo(B′, p). Defina a ábch a partir de da maneira óbvia:
= ∪ {X,Y}.
Observe que o conjunto de folhas de é F e que
custo(, p) = custo(, p) + p(X) + p(Y) .
Como custo(, p) < custo(B′, p), temos custo(, p) < custo(B, p). Isso contradiz a suposta otimalidade de B. Portanto, B′ é, de fato, ótima.
Podemos supor, sem perder generalidade, que em qualquer solução do nosso problema as duas folhas mais leves são também as mais profundas. Mais precisamente, temos a seguinte
Propriedade gulosa: Dados números p1,…,pn e uma partição F de {1,2,…,n}, sejam X e Y dois elementos de F tais que p(X) ≤ p(Y) e p(Y) ≤ p(U) para todo U em F−{X,Y}. Então existe uma ábch ótima B para p1,…,pn, com folhas F, na qual X e Y são folhas irmãs de profundidade máxima.
Prova: Seja B uma ábch ótima com folhas F. Seja U uma folha de profundidade máxima. Como B é cheia, U é irmã de uma outra folha, digamos V. É claro que d(U) = d(V), que d(U) ≥ d(X) e que d(V) ≥ d(Y). Ajuste a notação (trocando os papéis de U e V se necessário) de modo que p(U) ≤ p(V). Teremos então
p(X) ≤ p(U) e p(Y) ≤ p(V).
Troque X e U de posição em B produzindo assim uma ábch B′. Mais precisamente, B′ é definida assim:
Observe que B′ é, de fato, uma ábch e que seu conjunto de folhas é F. Denote por d′ as profundidades em B′ e observe que d′(X) = d(U) e d′(U) = d(X). Ademais, d′(Z) = d(Z) para toda folha Z distinta de X e U. De acordo com (*),
| custo(B, p) − custo(B′, p) | = | ∑F∈F p(F)d(F) − ∑F∈F p(F)d′(F) |
| = | p(X)d(X) + p(U)d(U) − p(X)d′(X) − p(U)d′(U) | |
| = | p(X)d(X) + p(U)d(U) − p(X)d(U) − p(U)d(X) | |
| = | (p(U) − p(X)) (d(U) − d(X)) | |
| ≥ | 0 . |
Portanto, custo(B, p) ≥ custo(B′, p) e assim a ábch B′ é tão ótima quanto B. Ademais, X é uma folha de profundidade máxima em B′.
Agora troque Y e V de posição em B′ produzindo assim uma ábch B″ com conjunto F de folhas. Um argumento análogo ao que fizemos para X e U mostra que B″ também é ótima. Finalmente, observe que em B″ as folhas X e Y são irmãs e têm profundidade máxima.
O algoritmo de Huffman [David A. Huffman, 1952] usa a propriedade gulosa e a estrutura recursiva discutidas acima para calcular uma ábch de custo mínimo. O algoritmo tem caráter guloso. Ao receber números p1,…,pn e uma partição F de {1,2,…,n}, o algoritmo devolve uma ábch B com folhas F que tem custo mínimo em relação a p:
| 1Huffman (n, p1,…,pn, F) |
| 11 . se |F| = 1 |
| 12 .___ então devolva F e pare |
| 13 .___ senão seja X um elemento de F que minimiza p(X) |
| 14 .___ senão F ← F − {X} |
| 15 .___ senão seja Y um elemento de F que minimiza p(Y) |
| 16 .___ senão F ← F − {Y} |
| 17 .___ senão F ← F ∪ {X ∪ Y} |
| 18 .___ senão B ← Huffman (n, p1,…,pn, F) |
| 19 .___ senão devolva B ∪ {X,Y} |
Na linha 2, é claro que o único elemento de F é {1,2,…,n}. Na linha 3, como de hábito, p(X) é a soma ∑i∈X pi. Na linha 8, o conjunto F é menor que o da linha 1 e portanto o algoritmo é finito.
Exemplo [copiado da página 389 do CLRS]: Considere a família de pesos dada pela tabela:
| i | 1 | 2 | 3 | 4 | 5 | 6 |
| pi | 45 | 13 | 12 | 16 | 9 | 5 |
Para a partição F = {{1},{2},…,{6}} do conjunto de índices, o algoritmo de Huffman produz a ábch {{1}, {2}, {3}, {4}, {5}, {6}, {6,5}, {6,5,4}, {2,3}, {2,3,4,5,6}, {1,2,3,4,5,6}}. Essa ábch pode ser representada pela figura abaixo:
•
┌────┴────┐
1 •
┌───┴───┐
• •
┌─┴─┐ ┌─┴─┐
3 2 • 4
┌─┴─┐
6 5
A árvore poderia também ser representada pela expressão (1,((3,2),((6,5),4))). Um diagrama ainda mais sugestiva indica o peso de cada nó:
100
┌────┴────┐
45 55
┌───┴───┐
25 30
┌─┴─┐ ┌─┴─┐
12 13 14 16
┌─┴─┐
5 9
Essa ábch tem custo 224. Para fazer contraste, considere a ábch ((1,2),((5,6),(3,4))) que tem custo 242 e portanto não é ótima.
A essência da prova da correção do algoritmo está na propriedade gulosa e na recíproca da estrutura recursiva discutidas acima.
É natural usar uma árvore binária comum como estrutura de dados para representar uma ábch. Para uma implementação não recursiva do algoritmo de Huffman, basta representar ábchs com folhas unitárias. Cada nó da ábch será representado por uma célula dotada de quatro campos: esq, dir, índice e peso. Para cada célula z, esq[z] é o endereço do filho esquerdo de z e dir[z] é o endereço do filho direito de z. Se z representa uma folha então esq[z] = dir[z] = nil. Se z não representa uma folha então índice[z] é irrelevante. Se z representa uma folha {i} então índice[z] = i. Para cada z, peso[z] = p(Z), sendo Z o nó da ábch que z representa.
Podemos agora reescrever o algoritmo de Huffman em estilo iterativo. O algoritmo recebe números p1,…,pn e devolve o endereço da raiz de uma árvore binária que representa uma ábch ótima com folhas unitárias.
| 1Huffman (n, p1,…,pn) |
| 11 _ Q ← Cria-Fila-Vazia ( ) |
| 12 _ para i crescendo de 1 até n faça |
| 13 ____ z ← Cria-Célula ( ) |
| 14 ____ índice[z] ← i |
| 15 ____ peso[z] ← pi |
| 16 ____ esq[z] ← dir[z] ← nil |
| 17 ____ Insere-na-Fila (Q, z) |
| 18 _ enquanto Q tiver 2 ou mais células faça |
| 19 ____ x ← Extrai-Min (Q) |
| 10 ____ y ← Extrai-Min (Q) |
| 11 ____ z ← Cria-Célula ( ) |
| 12 ____ esq[z] ← x |
| 13 ____ dir[z] ← y |
| 14 ____ peso[z] ← peso[x] + peso[y] |
| 15 ____ Insere-na-Fila (Q, z) |
| 16 _ r ← Extrai-Min (Q) |
| 17 _ devolva r |
A operação Cria-Fila-Vazia cria uma fila de prioridades vazia. Os elementos da fila serão células e a prioridade de cada célula z será dada por peso[z]. A operação Cria-Célula gera uma nova célula e devolve o endereço dessa célula. A operação Insere-na-Fila (Q, z) insere a célula z na fila Q.
As linhas 1 a 7 constroem as folhas da árvore. As demais linhas constroem os nós internos e a estrutura da árvore. A operação Extrai-Min (Q) nas linhas 9 e 10 retira da fila de prioridades Q uma célula que tem peso mínimo.
No início de cada iteração temos uma floresta composta de duas ou mais árvores. (No início da primeira iteração, cada árvore tem apenas um nó.) Durante a iteração, o algoritmo escolhe duas raízes e funde as correspondentes árvores. No fim da última iteração, a floresta tem uma única árvore. O invariante principal do algoritmo é o seguinte: no início de cada iteração do bloco de linhas 9 a 15,
a floresta faz parte de alguma árvore ótima.
A prova do invariante segue da propriedade gulosa e da recíproca da estrutura recursiva discutidas acima.
Se a fila de prioridades for implementada como um vetor ordenado, cada execução de Insere-na-Fila e Extrai-Min consumirá Ο(m) unidades de tempo, sendo m o número de células na fila Q. Como m ≤ n e há n repetições do bloco de linhas 1 a 7 e n−1 repetições do bloco de linhas 9 a 15, o consumo de tempo total do algoritmo será Ο(n2).
Se a fila de prioridades for implementada como um min-heap (veja um dos exercícios abaixo), cada execução de Insere-na-Fila e Extrai-Min consumirá Ο(lg n) unidades de tempo. Com isso, o consumo total será de
Ο(n lg n)
unidades de tempo.
A principal aplicação prática do algoritmo de Huffman é o cálculo de códigos binários para compressão de arquivos, ou seja, a transformação de um arquivo de caracteres em um arquivo de bits que ocupa pouco espaço. A ideia da compressão é usar poucos bits para representar os caracteres mais frequentes e mais bits para representar os mais raros.
Uma tabela de códigos para um conjunto C de caracteres é uma bijeção entre C e algum conjunto de sequências de bits. A sequência de bits que corresponde a um dado caractere é o código do caractere.
Uma tabela de códigos é livre de prefixos (= prefix-free) se tem a seguinte propriedade: para quaisquer dois caracteres x e y, o código de x não é prefixo do código de y. (Um prefixo de um sequência de bits b1,b2,…,bk é qualquer segmento inicial b1,b2,…,bi com i ≤ k.)
| A | 0 |
| B | 101 |
| C | 100 |
| D | 111 |
| E | 1101 |
| F | 1100 |
Exemplo [extraído da página 386 do CLRS]: Uma tabela de códigos para o conjunto de caracteres {A,…,F}. A tabela é livre de prefixos. Para essa tabela, a sequência de caracteres ABACAFE é representada pela sequência de bits 01010100011001101. Nenhuma outra sequência de caracteres corresponde a essa sequência de bits.
Um arquivo (= file) é uma sequência de caracteres. O conjunto de caracteres do arquivo é o alfabeto do arquivo. O peso (ou frequência) de um caractere c num arquivo é o número de ocorrências de c no arquivo. O peso de um caractere c será denotada por p(c). Assim, o número de caracteres do arquivo é igual a ∑c∈C p(c).
Dada uma tabela de códigos para o alfabeto de um arquivo, a codificação do arquivo é a substituição de cada caractere pelo correspondente código. Durante a codificação, os códigos dos caracteres são simplesmente concatenados, sem quaisquer separadores, de modo que o arquivo codificado é uma longa sequência de bits. Se a tabela de códigos for livre de prefixos, a codificação não introduz ambiguidades, pois a sequência de bits só pode ser decodificada de uma maneira.
O comprimento do arquivo codificado é o número total de bits do arquivo. Temos, então, o seguinte
Problema de compressão: Dado um arquivo de caracteres, encontrar uma tabela de códigos que produza um arquivo codificado de comprimento mínimo.
Vamos restringir nossa atenção às tabelas de códigos que podem ser representadas por árvores de códigos. Uma árvore de códigos para um conjunto C de caracteres é uma árvore binária em que
O código de um caractere c é dado pelo caminho que vai da raiz da árvore até c: cada vez que o caminho vai de um nó interno para o seu filho esquerdo temos um bit 0 e cada vez que o caminho vai para o filho direito temos um bit 1. É claro que o número de bits do código de c é igual à profundidade de c na árvore. É claro também que a tabela de códigos assim obtida é livre de prefixos.
Exemplo: A tabela do exemplo acima pode ser representada pela seguinte árvore:
•
┌────┴────┐
A •
┌───┴───┐
• •
┌─┴─┐ ┌─┴─┐
C B • D
┌─┴─┐
F E
Para decodificar uma sequência de bits, basta percorrer a árvore a partir da raiz usando a sequência como guia. Comece na raiz da árvore; para cada bit 0, vá para a esquerda; para cada bit 1, vá para a direita; continue até atingir uma folha.
Para cada caractere c, denotaremos por d(c) a profundidade de c na árvore. É claro que d(c) é também o comprimento (ou seja, o número de bits) do código de c. O número total de bits do arquivo codificado é então
∑c∈C d(c)p(c) ,
sendo p(c) a peso de c no arquivo. Como vimos acima, esta soma é igual ao custo da ábch que corresponde à árvore de códigos. (Para obter a ábch, basta ignorar a distinção entre filho esquerdo e filho direito de cada nó interno da árvore de códigos.)
Nosso problema de compressão de arquivos se reduz, assim, ao problema da ábch de custo mínimo. O algoritmo de Huffman pode ser usado, portanto, para comprimir arquivos.
| a | b | c | d | e | f |
| 00 | 010 | 0110 | 0111 | 10 | 11 |