MAC0338   Análise de Algoritmos

Códigos de Huffman

Esta página é um resumo da discussão que está no capítulo 17 (algoritmos gulosos), seção 3, de CLR.

Introdução

• compressão de arquivos
  
  
• alfabeto do arquivo = conjunto de caracteres do arquivo
  
  
• codificação dos caracteres por meio de seqüências de bits
  
  
• códigos de comprimento fixo; códigos de comprimento variável
  
  
• códigos prefixos (prefix-free); codificação e decodificação de um arquivo
  
  
• freqüência:  f(c) = número de ocorrências do caracter c no arquivo
  
  
• um código prefixo é ótimo (para um dado alfabeto e correspondente freqüência f) se minimiza o número de bits do arquivo comprimido
  
  
• problema: determinar código ótimo
  
  
• árvore de um código
  
  
• árvores "cheias" (cada nó interno tem exatamente 2 filhos):  n folhas e n-1 nós internos
  
  
• d(c) = número de bits do código do caracter c = profundidade da folha c na árvore do código
  
  
• número de bits do arquivo comprimido = SOMA _c (d(c)f(c)) ,
  onde a soma é efetuada sobre todas as folhas c
  
  
• representação da árvore do código: cada nó z tem um campo c[z] (caracter do nó), um campo f[z] (freqüência do caracter), um ponteiro esq[z] para filho esquerdo e um ponteiro dir[z] para filho direito
  
  
• o algoritmo guloso de Huffman: recebe um alfabeto C e a freqüência f[c] de cada caracter c; devolve a árvore de um código ótimo
  
  
• implementação eficiente do algoritmo de Huffman: "fila" com prioridades (baseada em heap)

Algoritmo guloso de Huffman

O algoritmo constroi uma árvore ótima. Vamos supor que cada nó da árvore tem 4 campos: ch, fr, esq e dir. Se z é o endereço de um nó então

• esq[z] = endereço do filho esquerdo do nó z (vale NIL se z não tem filho esquerdo)
• dir[z] = endereço do filho direito do nó z (vale NIL se z não tem filho direito)
• ch[z] = caracter associado ao nó z (só é relevante se esq[z]=dir[z]=NIL)
• fr[z] = freqüência de z (se esq[z]=dir[z]=NIL então fr[z] = f[ch[z]]; senão fr[z] = fr[esq[z]]+fr[dir[z]])

Vamos supor que o algoritmo recebe um conjunto C de nós; cada nó z corresponde a um dos caracteres do meu alfabeto e tem esq[z]=dir[z]=NIL. Esses nós serão as folhas da árvore. O algoritmo contrói o resto da árvore e devolve o endereço da raiz da árvore.

HUFFMAN (C)
  Q := C
  para i := 1 até |C|-1 faça     comentário: cada iteração constrói um nó interno da árvore
    z := ALOCA ()
    x := EXTRACT-MIN (Q)
    y := EXTRACT-MIN (Q)
    esq[z] := x
    dir[z] := y
    fr[z] := fr[x]+fr[y]
    Q := Q+{z}
  devolve EXTRACT-MIN (Q)

O comando "Q := C" cria uma "fila" com prioridades com o conjunto de todos os nós. Os detalhes da implementação da fila ficam por conta do leitor, mas tudo se passa como se Q fosse uma seqüência de nós em ordem decrescrescente de fr. O subalgoritmo EXTRACT-MIN retira da fila com prioridades um nó que tem fr mínimo. O sub-algoritmo ALOCA gera um novo nó e devolve o endereço desse nó.

Observe que no início de cada iteração temos uma floresta composta de diversas árvores. Em cada iteração, duas árvores são reunidas. No fim da última iteração, a floresta tem uma única árvore.

É óbvio que o algoritmo produz uma árvore que minimiza o tamanho do arquivo codificado? Não. Isso não é nada óbvio. Veja capítulo 17 do CLR.

Exercícios

1. Uma árvore binária é cheia se todo nó tem exatamente 0 ou exatamente 2 filhos; os nós com 0 filhos são folhas. Mostre que toda árvore binária cheia com n folhas tem n-1 nós internos.
   
   
2. [CLR 17.3-1]  Uma árvore binária é cheia se todo nó tem exatamente 0 ou exatamente 2 filhos (os nós com 0 filhos são folhas). Mostre que a árvore de qualquer código prefixo ótimo é necessariamente cheia.
   
   
3. Quantos nós tem a árvore de um código prefixo ótimo que codifica n caracteres?
   
   
4. [BASEADO EM CLR 17.3-2]  Calcule o código de Huffman para o alfabeto A, B, . . , H com freqüências que são os primeiros número de Fibonacci:

   f(A)=1, f(B)=1, f(C)=2, f(D)=3, f(E)=5, f(F)=8, f(G)=13, f(H)=21.

   O arquivo original tem 1+1+ . .+21 = 54 caracteres. Quantos bits tem o arquivo comprimido?
   
   

5. [CLR 17.3-4]  Coloque os caracteres do meu alfabeto em ordem decrescente de freqüência (ou seja, ordem decrescente de f). Mostre que, num código ótimo, a seqüência de caracteres estará em ordem crescente de número de bits (ou seja, ordem crescente de d).
   
   
6. Digamos que tenho um arquivo em que só ocorrem os caracteres "A", "B", "C", "D", "E", "F". Cada caracter ocorre exatamente x vezes.

   1.  Se for necessário representar cada caracter por um número fixo de bits, quantos bits você usaria por caracter? Qual será o tamanho total do arquivo?

   2.  Qual o tamanho (em bits) do arquivo se usarmos um código de Huffman?

   [Solução]

Detalhes da implementação (fila com prioridades)

A descrição acima não explica como implementar os detalhes de maneira eficiente. Eis uma implementação que usa uma fila com prioridades implementada num heap. A fila com prioridades mora em um vetor H[1..N] cujos elementos são endereços de nós. Mais precisamente, para cada i,  H[i] será o endereço da raiz de uma das árvores da floresta. O vetor H será um heap no seguinte sentido:

fr[H[i/2]] <= fr[H[i]]

para cada i maior que 1. Aqui, como no resto desta página, a expressão "i/2" deve ser entendida como "chão(i/2)".

Para simplificar, suporemos que nosso alfabeto é 1, 2, . . , n. Suporemos que a freqüência de um caracter i é f[i] . O algoritmo HUFFMAN-DETALHADO constroi uma árvore ótima relativa ao vetor de freqüências f[1..n]. O algoritmo devolve o endereço da raiz da árvore que construiu.

HUFFMAN-DETALHADO (n, f)
  para i := 1 até n faça
    z := ALOCA ()
    esq[z] := dir[z] := NIL
    fr[z] := f[i]
    H[i] := z
  N := n
  para i := N/2 decrescendo até 1 faça
    PENEIRA (H, N, i)
  comentário: agora H[1..N] é um heap
  para i := 1 até n-1 faça
  comentário: cada iteração constrói um nó interno da árvore
    z := ALOCA ()
    x := EXTRAIMIN (H, N)
    N := N-1
    y := EXTRAIMIN (H, N)
    N := N-1
    esq[z] := x
    dir[z] := y
    fr[z] := fr[x]+fr[y]
    INSERE (z, H, N)
    N := N+1
  devolve H[1]

Procedimentos auxiliares:

EXTRAIMIN (H, N)
  m := H[1]     comentário: fr[m] é mínimo
  H[1] := H[N]
  PENEIRA (H, N, 1)
  devolve m

INSERE (z, H, N)
  i := N+1
  enquanto i > 1   e  fr[H[i/2]] > fr[z] faça
    H[i] := H[i/2]
    i := i/2
  H[i] := z

PENEIRA (H, N, i)
  se 2i <= N   e  fr[H[2i]] < fr[H[i]]
    então m := 2i
    senão m := i
  se 2i+1 <= N   e  fr[H[2i+1]] < fr[H[m]]
    então m := 2i+1
  se m <> i
    então troque H[m] :=: H[i]
        PENEIRA (H, N, m)

Mostre que HUFFMAN-DETALHADO consome O(n lg(n)) unidades de tempo.