Algoritmo de Huffman para compressão de dados

Livro de SW: sec.5.5, p.826-838.  Website do livro: resumo sec.5.5, slides. Veja também a página http://algs4.cs.​princeton.edu/​code/, que tem o código fonte, a API, e dados de teste de todos os programas do livro.

Ideias básicas

• O algoritmo de Huffman recebe um fluxo de bits e devolve um fluxo de bits comprimido que representa o fluxo original. Em geral, o fluxo comprimido é mais curto que o original.
• O fluxo de bits original é lido de 8 em 8 bits, como se fosse um fluxo de caracteres:

  010000010100001001010010010000010100001100000010100010001000001001000010010100100100000100100001
         A       B       R       A       C       A       D       A       B       R       A       !
  

• Tudo se passa como se o algoritmo transformasse uma string em uma cadeia de bits.  Exemplo: transforma  ABRACADABRA!  em  011111110011001000111111100101 .
• Cada caractere da string original é convertido em uma pequena cadeia de bits, que é o seu código.  Por exemplo,  C  é convertido em  110.
• Ideia do algoritmo de Huffman: usar códigos curtos para os caracteres que ocorrem com frequência e deixar os códigos mais longos para os caracteres mais raros.  Os códigos são, portanto, de comprimento variável.

Compressão (codificação)

• A tabela de códigos leva cada caractere (de 8 bits) no seu código.   Dois exemplos, um com códigos de comprimento fixo e outro com códigos de comprimento variável:

  !  001                 !  1010
  A  010                 A  0
  B  011                 B  111
  C  100                 C  1011
  D  101                 D  100
  R  110                 R  110
  ...                    ...
  

• A escolha da melhor tabela de códigos é o segredo do algoritmo de Huffman e será discutida abaixo.
• A tabela de códigos é uma TS em que as chaves são os caracteres e os valores são os códigos.
• A tabela de códigos será repesentada por um simples vetor de strings  st[0..255]  indexado pelos 256 caracteres ASCII.  Cada st[c] é uma string de  0s  e  1s  que será convertida na correspondente cadeia de bits no momento apropriado.
• É fácil produzir o fluxo de bits codificado a partir da tabela st[]:

  public static void compress() {
     String s = BinaryStdIn.readString();
     char[] input = s.toCharArray();
  
     // cálculo da tabela de códigos st[]
     // discutido mais adiante
  
     for (int i = 0; i < input.length; i++) {
        String code = st[input[i]];
        for (int j = 0; j < code.length(); j++)
        if (code.charAt(j) == '1')
             BinaryStdOut.write(true);
        else BinaryStdOut.write(false);
     }
     BinaryStdOut.close();
  }
  

Expansão (decodificação)

• Na decodificação, cada código de caractere deve ser convertido no correspondente caractere.  A tabela de códigos deve ser injetiva (caracteres diferentes devem ter códigos diferentes).  Mas isso não basta.
• Exemplo:  A tabela de códigos abaixo transforma   ABRACADABRA!   em    01000010100100011 .  Mas essa cadeia de bits também representa  CRRDDCRCB.  Isso contraria a regra do jogo!

  !  11
  A  0
  B  1
  C  01 
  D  10
  R  00
  

• A tabela deve ser livre de prefixos.  Uma tabela de códigos é livre de prefixos (prefix-free) se nenhum código é prefixo de outro.
• Exemplo: A tabela abaixo é livre de prefixos.  Assim,   ABRACADABRA!   é a única decodificação possível de   011111110011001000111111100101 .

  !  101
  A  0
  B  1111
  C  110 
  D  100
  R  1110
  

Exercícios 1

1. Qual a diferença entre código de comprimento fixo e código de comprimento variável? Por que código de comprimento variável precisa ser livre de prefixos? Código de comprimento fixo precisa ser livre de prefixos?
2. (SW 5.5.1)  Quais das tabelas de códigos abaixo são livres de prefixos?

   A   0    0   1     1
   B   100  1   01    01
   C   10   00  001   001
   D   11   11  0001  000
   

Tabelas inversas e suas tries

• A tabela de códigos inversa leva cada código no correspondente caractere.   (Caso especial de índice invertido de ST.)  Exemplo:

  101   !
  0     A
  1111  B
  110   C
  100   D
  1110  R
  

• A tabela inversa é uma TS de strings:  as chaves são strings de 0s e 1s e os valores são caracteres.
• A tabela inversa será representada por uma trie binária (sobre o alfabeto 0 1).  Como a tabela é livre de prefixos, as chaves estão somente nas folhas. (Portanto, não há nós com apenas um filho.) Diremos que essa é a trie do código.
• Dois exemplos de tabelas de códigos livres de prefixos e suas tries.  As taxas de compressão de  ABRACADABRA!  são diferentes nos dois exemplos:

  

• Nós da trie:

  private static class Node implements Comparable<Node> {
     private char ch;   // usado só nas folhas
     private int freq;  // usado só para construção da trie
     private final Node left, right;
  
     Node(char ch, int freq, Node left, Node right) {
         this.ch = ch;
         this.freq = freq;
         this.left = left;
         this.right = right;
     }
  
     public boolean isLeaf() { 
        return left == null && right == null; 
     }
  
     public int compareTo(Node that) { 
        return this.freq - that.freq; 
     }
  }
  

• Dada a trie do código, como decodificar o fluxo de bits?  Basta fazer uma busca por cada uma das N chaves:

  public static void expand() {
     Node root = readTrie();        // discutido abaixo
     int N = BinaryStdIn.readInt(); // comprimento da string original
  
     for (int i = 0; i < N; i++) {  // decodifica próximo caractere
        Node x = root;
        while (!x.isLeaf())
           if (BinaryStdIn.readBoolean())
                x = x.right;
           else x = x.left;
        BinaryStdOut.write(x.ch);
     }
     BinaryStdOut.close();
  }
  

Exercícios 2

1. Qual a relação entre tries binárias e códigos livres de prefixos? Qualquer trie binária representa um código livre de prefixos?
2. Todos os códigos livre de prefixo produzem strings codificadas de comprimento mínimo?

Construção da trie de Huffman

• O segredo do algoritmo de Huffman está na maneira de escolher a tabela de códigos.
• A tabela de códigos de Huffman não é universal. Ela é construída sob medida para a string a ser codificado de tal modo que o comprimento da cadeia codificada seja o menor possível (quando comparado com outros códigos livres de prefixos).
• Primeiro, construímos a trie do código, depois extraímos dela a tabela de códigos. Dada a string a ser codificada, a trie é construída assim:
  1. determine a frequência (ou seja, o número de ocorrências) de cada caractere da string original,
  2. para cada caractere, crie um nó e armazene o caractere e sua frequência nos campos ch e freq;
  3. organize o conjunto de nós em uma trie conforme o seguinte algoritmo.
• Algoritmo de construção da trie do código:
  1. no início de cada iteração temos um conjunto de tries mutuamente disjuntas (no início da primeira iteração, cada trie tem um único nó);
  2. escolha duas tries cujas raízes, digamos x e y, tenham freq mínima;
  3. crie um novo nó parent e faça com que x e y sejam filhos desse nó;
  4. faça parent.freq igual a x.freq + y.freq;
  5. repita esse processo até que o conjunto de tries tenha uma só trie.
• Exemplo: Veja o algoritmo em ação aplicado à string  ABRACADABRA! .  Qual o comprimento da string codificada? Compare com as tabelas de código no início da página.

  

• Outro exemplo: Considere a string   it was the best of times it was the worst of timesLF   (sendo LF o caractere 10, ou 0A em hexadecimal, que indica fim de linha).  As frequências dos caracteres são

  a  b  e  f  h  i  m  o  r  s  t  w  LF  SP
  2  1  5  2  2  4  2  3  1  6  8  3  1  11
  

  (Aqui, SP é o caractere 32, ou 20 em hexadecimal, que representa um espaço.)   Segue a construção da trie de Huffman:

  

• Trie de Huffman do exemplo:

  

• O seguinte método implementa o algoritmo de construção da trie de Huffman a partir do vetor de frequências freq[].  O método usa uma fila priorizada e devolve a raiz da trie:

  private static Node buildTrie(int[] freq) {
     MinPQ<Node> pq = new MinPQ<Node>();
     for (char c = 0; c < R; c++)
        if (freq[c] > 0)
           pq.insert(new Node(c, freq[c], null, null));
  
     while (pq.size() > 1) { 
        Node x = pq.delMin();
        Node y = pq.delMin();
        Node parent = new Node('\0', x.freq + y.freq, x, y);
        pq.insert(parent);
     }
     return pq.delMin();
  }
  

• A tabela de códigos st[] (usada na codificação) é calculada a partir da trie que acabamos de construir:

  private static String[] buildCode(Node root) { 
     String[] st = new String[R];
     buildCode(st, root, "");
     return st;
  }
  
  private static void buildCode(String[] st, Node x, String s) { 
     if (x.isLeaf()) { 
        st[x.ch] = s; 
        return; 
     }
     buildCode(st, x.left, s + '0');
     buildCode(st, x.right, s + '1');
  }
  

Exercícios 3

1. Escreva a cadeia de bits que codifica a string   ABRACADABRA!   usando o código de Huffman calculado acima.  Quantos bits tem a cadeia?  Insira espaços para facilitar a leitura.
2. Escreva a cadeia de bits que codifica a string   it was the best of times it was the worst of timesLF   usando o código de Huffman calculado acima.  Quantos bits tem a cadeia?  Qual a taxa de compressão?  Insira espaços e quebras de linha para facilitar a leitura.
3. Suponha dada a tabela de códigos Huffman de uma string s.  Dê a tabela de códigos de uma permutação de s.
4. Unicidade. Mostre que a trie de Huffman não é unica.  Use a string  ABRACADABRA!  como exemplo.  Faça um exemplo mais interessante que a mera troca de 0 por 1 e vice-versa.
5. (SW 5.5.14)  Suponha que as frequências dos caracteres de uma string são todas diferentes. A trie de Huffman é única?
6. (SW 5.5.19)  Mostre que há pelo menos 2^N−1 diferentes códigos de Huffman para cada string de N caracteres.
7. (SW 5.5.10)  Construa a trie de Huffman para a string  it was the age of foolishness .  Quantos bits tem a cadeia codificada?
8. (SW 5.5.11)  Como é o código de Huffman de uma string sobre um alfabeto de duas letras? Dê um exemplo para mostrar o número máximo de bits na versão codificada de uma string de N letras sobre um alfabeto de duas letras?
9. (SW 5.5.12)  Suponha que as frequências relativas dos caracteres (número de ocorrências dividido pelo número total de caracteres) sejam potências negativas de 2 (ou seja, 2⁻¹, 2⁻², etc.)  Descreva o código de Huffman.
10. Suponha que o alfabeto de uma string s tem apenas 6 caracteres diferentes e que todos os caracteres têm a mesma frequência. Submeta s ao algoritmo de compressão de Huffman e seja h(s) a string de bits que resulta da substituição de cada caractere de s pelo seu código. (Portanto, h(s) não inclui a representação da trie de Huffman, nem a representação do comprimento de s, nem qualquer enchimento.)  Calcule a taxa m/n, sendo m o número de bits de h(s) e n é o número de bits de s. Repita o exercício com 5 no lugar de 6. 
11. (SW 5.5.13)  Suponha que todos os caracteres de uma string têm a mesma frequência. Descreva o código de Huffman.
12. (SW 5.5.18)  Seja F_k o k-ésimo número de Fibonacci.  (Lembrete: F₁ = 1.)  Considere um conjunto de n caracteres tal que a frequência do k-ésimo é F_k.  Note que F₁ + F₂ + … + F_n = F_n+2 − 1.  Descreva o código de Huffman. Dica: o código mais longo tem n−1 bits.
13. (SW 5.5.20)  Dê uma cadeia codificada de Huffman que tenha muito mais 0s que 1s.
14. (SW 5.5.21)  Prove que o código mais longo e o segundo mais longo de uma tabela de Huffman têm o mesmo comprimento.
15. (SW 5.5.22)  Suponha que a frequência de um caractere c é estritamente maior que a frequência de um caractere d. Mostre que o código de Huffman de c tem comprimento menor ou igual que o comprimento do código de d.
16. (SW 5.5.9b)  Estime a taxa de compressão da codificação de Huffman de uma sequência de N de caracteres ASCII aleatórios (em cada posição, todos os caracteres são igualmente prováveis).

Mais detalhes do método de compressão

• Agora que temos os métodos buidTrie() e buildCode(), podemos completar o método de compressão (já exibido parcialmente acima).

  public static void compress() {
     String s = BinaryStdIn.readString();
     char[] input = s.toCharArray();
  
     int[] freq = new int[R];
     for (int i = 0; i < input.length; i++)
        freq[input[i]]++;
  
     Node root = buildTrie(freq);
  
     String[] st = new String[R];
     buildCode(st, root, "");
  
     writeTrie(root);  // discutido abaixo
  
     BinaryStdOut.write(input.length);
  
     for (int i = 0; i < input.length; i++) {
        String code = st[input[i]];
        for (int j = 0; j < code.length(); j++)
        if (code.charAt(j) == '1')
             BinaryStdOut.write(true);
        else BinaryStdOut.write(false);
     }
     BinaryStdOut.close();
  }
  

Exercícios 4

1. Discuta a seguinte maneira alternativa de calcular as frequências:

      int[] freq = new int[R];
      for (int c = 0; c < R; c++)
         for (int i = 0; i < input.length; i++)
            if (input[i] == c) freq[c]++;
   

A trie de Huffman é ótima

• Proposição U. A cadeia de bits produzida pelo algoritmo de Huffman é mínima no seguinte sentido:  nenhuma outra cadeia produzida por um código livre de prefixos é mais curta que a cadeia produzida pelo algoritmo de Huffman.

A história ainda não terminou

• A cadeia de bits produzida pelo algoritmo de Huffman não pode ser decodificada sem a correspondente trie. É preciso acrescentar a trie à cadeia codificada.
• Como descrever a trie de Huffman por meio de uma cadeia de bits?  Resposta: percorra a trie em pré-ordem (visite a raiz, depois a subtrie esquerda, depois a subtrie direita). Sempre que visitar um nó interno, escreva um bit 0. Sempre que visitar uma folha, escreva um bit 1 seguido pelos 8 bits do caractere associado. Esse representação da trie é fácil produzir e fácil decodificar.
• Exemplo:

  

• Cálculo da cadeia de bits que representa a trie:

  private static void writeTrie(Node x) {
     if (x.isLeaf()) {
        BinaryStdOut.write(true);
        BinaryStdOut.write(x.ch);
        return;
     }
     BinaryStdOut.write(false);
     writeTrie(x.left);
     writeTrie(x.right);
  }
  

• Reconstrução da trie a partir da cadeia de bits:

  private static Node readTrie() {
     if (BinaryStdIn.readBoolean()) {
        char c = BinaryStdIn.readChar();
        return new Node(c, 0, null, null);
     }
     return new Node('\0', 0, readTrie(), readTrie());
  }
  

Exercícios 5

1. Quantos nós internos tem uma trie de Huffman para n caracteres?
2. O fluxo de bits produzido pelo algoritmo de Huffman começa com uma string de bits t que representa a trie de codificação e é seguido por uma string de bits N que representa o número de caracteres do texto original. Como sei onde termina a string t e começa a string N?
3. Um fluxo de bits produzido pelo método compress da classe Huffman começa assim:

   00010101011010011001110100111100101010000101000001101010010000101110100...
   

   Desenhe a trie do código de compressão.

Classe Huffman completa

• Algoritmo de compressão de Huffman:

  public class Huffman {
  
     private static int R = 256; // alfabeto ASCII
     
     private static class Node implements Comparable<Node> { /* veja acima */ }
  
     public static void expand() { /* veja acima */ }
  
     private static Node buildTrie(int[] freq) { /* veja acima */ }
  
     private static String[] buildCode(Node root) { /* veja acima */ }
  
     public static void compress() { /* veja acima */ } 
  
     private static void writeTrie(Node x) { /* veja acima */ } 
  
     private static Node readTrie() { /* veja acima */ } 
  
  }
  

Exemplos

• Exemplo baseado no código de Huffman calculado acima:

  % more abra.txt
  ABRACADABRA!
  
  % java Huffman - < abra.tx | java BinaryDump 60
  010100000100101000100010000101010100001101010100101010000100
  000000000000000000000000000110001111100101101000111110010100
  120 bits
  

  Eis a repetição dos 120 bits produzidos por BinaryDump com espaços e quebras de linha inseridos para facilitar a leitura:

  0 1 01000001 0 0 1 01000100 0 1 00001010 1 01000011 0 1 01010010 1 01000010
  00000000000000000000000000001100 
  0 111 110 0 1011 0 100 0 111 110 0 1010 
  0
  

  Os 59 bits da primeira linha descrevem a trie, os 32 bits da segunda linha dão o número de caracteres da string original (12), os 28 bits da terceira linha são a string codificada propriamente dita, o bit da última é enchimento para que o número total de bits seja um múltiplo de 8.

• Exemplo:  Codificação de Huffman do arquivo tinytinyTale.txt:

  % more tinytinyTale.txt
  it was the best of times it was the worst of times 
  
  % java Huffman - < tinytinyTale.txt | java BinaryDump 64
  0001011001010101110111101101111100100000001011100110010111001001
  0000101010110001010110100100010110011010110100001011011011011000
  0110111010000000000000000000000000000110011101111101001011011100
  0111111001000011010110001001110100111100001111101111010000100011
  0111110100101101110001111110010000100100011101001001110100111100
  00111110111101000010010101000000
  352 bits
  

  Os primeiros 139 bits representam a trie. Os 32 bits seguintes representam o número de caracteres, 51, da string original. Os 176 bits seguintes são a cadeia de bits codificada. Os últimos 5 bits são enchimento para completar um múltiplo de 8. Taxa de compressão: (139+32+176+5)/(51×8) = 352/408 = 0.86.  Segue a cadeia de bits codificada com espaços e quebras de linha inseridas para facilitar a leitura:

  0 0 0 1 01100101 0 1 01110111 1 01101111 1 00100000 
  0 0 1 01110011 0 0 1 01110010 0 1 00001010 1 01100010 1 01101001 
  0 0 0 1 01100110 1 01101000 0 1 01101101 1 01100001 1 01110100 
  00000000000000000000000000110011
  1011 111 01 0010 11011 100 01 111 11001 000 01 
  101011 000 100 111 01 0011 11000 01 111 1011 11010 000 100 01 
  1011 111 01 0010 11011 100 01 111 11001 000 01
  0010 0011 10100 100 111 01 00111 1000 01 111 1011 11010 000 100 101010 
  00000
  

  A decodificação reproduz a string original:

  % java Huffman - < tinytinyTale.txt | java Huffman +
  it was the best of times it was the worst of times
  

• Exemplo: A taxa de compressão para medTale.txt (primeiro capítulo de Tale of Two Cities) é de 23912/45056 = 0.53:

  % java PictureDump 512 88 < medTale.txt
  
  45056 bits
  
  % java Huffman - < medTale.txt | java PictureDump 512 47
  
  23912 bits
  

• Exemplo: A taxa de compressão para tale.txt é de 3043928/5812552 = 0.52:

  % java BinaryDump 0 < tale.txt
  5812552 bits
  
  % java Huffman - < tale.txt > tale.txt.huf
  % java BinaryDump 0 < tale.txt.huf
  3043928 bits
  

Comparação com outros algoritmos

• A compressão de Huffman é bastante flexível: para genomeVirus.txt (50000 bits) usa apenas 40 bits a mais que o código sob medida de 2 bit:

  % java Genome - < genomeVirus.txt | java PictureDump 512 25
  
  12536 bits
  
  % java Huffman - < genomeVirus.txt | java PictureDump 512 25
  
  12576 bits
  

• A compressão de Huffman ganha da compressão de comprimento de carreira:

  % java RunLength - < q32x48.bin | java BinaryDump 0
  1144 bits
  
  % java Huffman - < q32x48.bin | java BinaryDump 0
  816 bits
  
  % java RunLength - < q64x96.bin | java BinaryDump 0
  2296 bits
  
  % java Huffman - < q64x96.bin | java BinaryDump 0
  2032 bits