Árvores de Huffman

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.

Árvores binárias cheias

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:

  1. para cada X e cada Y em B, tem-se X ∩ Y = { } ou X ⊆ Y ou X ⊇ Y;
  2. {1,2,…,n} está em B;
  3. { } não está em B;
  4. todo elemento não minimal de B é união de dois outros elementos de B.

(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
     

Exercícios

  1. Seja B uma ábch com mais de dois nós. Mostre que B tem pelo menos duas folhas irmãs.
  2. Sejam X e Y duas folhas irmãs de uma ábch B.  Mostre que B − {X,Y} também é uma ábch.
  3. Mostre que toda ábch com m folhas tem exatamente m−1 nós internos e portanto exatamente 2m−1 nós no total.
  4. Seja F o conjunto de todas as folhas de uma ábch sobre {1,2,…,n}.  Mostre que F é uma partição de {1,2,…,n}.
  5. Seja F uma partição de {1,2,…,n}.  Mostre que existe uma ábch sobre {1,2,…,n} cujo conjunto de folhas é F.
  6. [Importante]  Mostre que toda ábch com m folhas tem uma folha de profundidade ≥ ⌈lg m⌉  (veja a definição de teto).  Mostre que toda ábch com N nós tem uma folha de profundidade ≥ ⌊lg N⌋.  (Veja a página Estrutura Heap.)

O custo de uma ábch

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) = ∑iX 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(Bp)  =  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(Bp)  =  FF p(F)d(F) , (*)

sendo F o conjunto das folhas de B e d(F) a profundidade da folha F.  (Veja exercício abaixo.)

Exercícios

  1. Prove a igualdade (*).  (Sugestão: use o caráter recursivo das ábch indicado acima.)

O problema da ábch de custo mínimo

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(Bp) ≤ 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}}.)

Exercícios

  1. [Importante]  Suponha que B é uma ábch ótima para a família de pesos p1,…,pn e folhas unitárias.  Mostre que custo(Bp)  ≤  ⌈lg n⌉ · (p1+…+pn).
  2. Seja p1,…,pn uma família de pesos.  Seja {K,L} uma partição de {1,2,…,n} tal que p(K) e p(L) são tão próximos quanto possível.  Seja BK uma ábch ótima, com folhas unitárias, para a família (pkk ∈ K).  Seja BL uma ábch ótima, com folhas unitárias, para a família (pll ∈ L).  Funda as duas ábchs, ou seja, faça com que a raiz K de BK e a raiz L de BL sejam os dois filhos de um novo nó {1,2,…,n}.  A ábch resultante é ótima para p1,…,pn?  (Se a resposta for afirmativa, a construção que descrevemos é a base de um algoritmo de divisão-e-conquista para resolver o problema da ábch de custo mínimo.)

A estrutura recursiva do problema

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(Bp) = 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}) ∪ {XY}.  Suponha, por um momento, que B′ não é ótima.  Então existe uma ábch B′ com conjunto de folhas F′ tal que custo(B′p) < custo(B′p).  Defina a ábch B a partir de B′ da maneira óbvia:

B = B′ ∪ {X,Y}.

Observe que o conjunto de folhas de B é F e que

custo(Bp) = custo(B′p)  +  p(X) + p(Y) .

Como custo(B′p) < custo(B′p), temos custo(Bp) < custo(Bp).  Isso contradiz a suposta otimalidade de B.  Portanto, B′ é, de fato, ótima.

A estrutura gulosa do problema

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 XU.  De acordo com (*),

custo(Bp) − custo(B′p)  =  FF p(F)d(F)  −  ∑FF 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(Bp) ≥ 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 XU 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

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  FF − {X}
15 .___ senão  seja Y um elemento de F que minimiza p(Y)
16 .___ senão  FF − {Y}
17 .___ senão  FF ∪ {XY}
18 .___ senão  BHuffman (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 ∑iX 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.

O algoritmo está correto

A essência da prova da correção do algoritmo está na propriedade gulosa e na recíproca da estrutura recursiva discutidas acima.

Exercícios

  1. [Importante]  Dê uma prova detalhada da correção do algoritmo Huffman.
  2. Suponha que p1=p2=…=p6.  Dê uma ábch ótima para p1,…,p6 com folhas unitárias.  Dê também uma ábch não ótima. 
  3. [CLRS 16.3-2]  Suponha que p1,…,p8 são os números de Fibonacci 1, 1, 2, 3, 5, 8, 13, 21.  Calcule uma ábch ótima com folhas unitárias para esta família de pesos.
  4. [CLRS 16.3-4]  Suponha que p1 ≤ … ≤ pn.  Mostre que existe uma ábch ótima para p1,…,pn com folhas unitárias tal que d({1}) ≥ … ≥ d({n}).

Implementação do algoritmo

É 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, índicepeso.  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 _ QCria-Fila-Vazia ( )
12 _ para i crescendo de 1 até n faça
13 ____ zCria-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 ____ xExtrai-Min (Q)
10 ____ yExtrai-Min (Q)
11 ____ zCria-Célula ( )
12 ____ esq[z] ← x
13 ____ dir[z] ← y
14 ____ peso[z] ← peso[x] + peso[y]
15 ____ Insere-na-Fila (Q, z)
16 _ rExtrai-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 (Qz) 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.

Consumo de tempo

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.

Exercícios

  1. Que acontece se trocarmos de posição as linhas 9 e 10 no algoritmo de Huffman?
  2. Implemente a fila de prioridades do algoritmo de Huffman como um min-heap residindo em um vetor Q[1..m].  Os elementos do vetor serão endereços de células.  O vetor Q será um min-heap no seguinte sentido:  peso[Q[⌊i/2⌋]] ≤ peso[Q[i]]  para cada i maior que 1.  Escreva o código das operações Insere-na-Fila e Extrai-Min.  (Basta adaptar os algoritmos que discutimos na página Fila de prioridades.)
  3. Suponha que p1 ≤ … ≤ pn.  Mostre que uma ábch ótima pode ser construída em tempo Ο(n).
  4. [Interessante]  Suponha dado um conjunto A1, A2, …, An de vetores numéricos crescentes.  (Você pode trocar vetor por lista encadeada ou por arquivo se desejar.)  Digamos que Ai tem pi elementos.  Suponha dado um algoritmo Merge que recebe dois vetores Ai e Aj e consome pi+pj unidades de tempo para produzir um vetor B que é o resultado da intercalação de Ai e Aj.  (É claro que o vetor B estará em ordem crescente e conterá pi+pj números.)  Queremos usar Merge para intercalar todos os vetores dados, produzindo assim um único vetor em ordem crescente, no menor tempo possível.  Quantas vezes será necessário invocar Merge?  Em que ordem os vetores devem ser submetidos ao Merge para que a soma dos tempos do Merge seja mínima?  (Compare com exercício semelhante na página sobre filas de prioridades.)

 


Aplicação: códigos de Huffman

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.

Códigos binários e compressão de arquivos

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 xy, 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.)

A0
B101
C100
D111
E1101
F1100

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 ∑cC 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.

Árvores de códigos

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

  1. cada folha corresponde a um elemento de C  e
  2. cada nó interno tem exatamente 2 filhos.

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

cC 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.

Exercícios

  1. A tabela abaixo dá os códigos binários dos caracteres a, b, c, d, e, f.  A tabela é livre de prefixos?  Em caso afirmativo, exiba a árvore da tabela.  Se os pesos de a, b, c, d, e, f são 1, 2, 3, 4, 5, 6 respectivamente, qual o custo da tabela de códigos?
    a b c d e f
    00 010 0110 0111 10 11
  2. Suponha dada uma sequência de K bits e uma árvore de códigos. Quanto tempo é necessário para decodificar a sequência?
  3. [Importante]  Seja A um arquivo sobre um alfabeto {c1,…,cn}.  Seja p(ci) o peso do caractere ci em A.  Seja t o tamanho de A, igual à soma ∑i p(ci).  Use uma árvore de códigos ótima para codificar A.  Mostre que o arquivo codificado não tem mais que  t · ⌈lg n⌉  bits.
  4. Suponha dado um arquivo sobre o alfabeto {A, B, C, D, E, F} em que cada caractere ocorre exatamente k vezes no arquivo.   (1) Se usarmos um número fixo de bits por caractere, quantos bits terá o arquivo codificado?  (2) Quantos bits terá o arquivo codificado se usarmos o código de Huffman?
  5. [CLRS 16.3-7]  O alfabeto de um arquivo A tem 256 caracteres.  O peso máximo de um caractere em A é menor que o dobro do peso mínimo (ou seja, pi < 2pj para todo i e todo j).  Mostre que a codificação de Huffman para A não é melhor que a codificação usual, que usa 8 bits por caractere. 


Valid HTML 4.01 Strict Valid CSS!