Compressão de dados

Livro de SW: sec.5.5, p.810-852.  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.

Esta página trata de conceitos básicos de compressão e do algoritmo de comprimento-de-carreira (run-length encoding).  O algoritmo de Huffman é discutida na página seguinte.

Introdução

• Problema:  Representar um arquivo (= file) grande por outro menor.
• Possível porque em geral os arquivos contêm muita redundância.
• Exemplo:
  • arquivo grande:   abababababababababababab
  • arquivo menor:   12ab
• Por que comprimir? 
  • Menor espaço de armazenamento.
  • Menor tempo de transmissão.
• Software:  gzip, bzip, 7z, etc.

Exercícios 1

1. (SW 5.5.6)  Quantos bits são necessários para codificar N cópias do símbolo  a  (em função de N)?  Quantos bits são necessários para codificar N cópias da sequência  abc?

Regras do jogo

• Vamos encarar os fluxos a comprimir como simples fluxo de bits, sem dar atenção ao significado que os blocos de 8 bits (ou 16 bits, ou 32 bits) possam ter para o usuário.
• Nosso problema:  comprimir um fluxo de bits, ou seja, representar um dado fluxo de bits por outro mais curto.
• Esquema básico de compressão de dados:
  • um compressor transforma um fluxo de bits B em um fluxo C(B)  e
  • um expansor transforma C(B) de volta em B.

  

• Diremos que o fluxo de bits B é original e o fluxo C(B) é codificado.  Diremos que o fluxo produzido pelo expansor é decodificado.  Assim, codificar é sinônimo de comprimir e decodificar é sinônimo de expandir.  (A ideia é que o usuário sabe ler o fluxo original mas não sabe ler o fluxo codificado.)
• Como o fluxo decodificado é idêntico ao original, a compressão não perde informação (lossless compression).   (Não vamos estudar compressão com perdas (lossy compression), como a feita por jpeg, gif, png, mp3, FFT, etc.)
• Notação:  |B| é o número de bits de B.
• Taxa de compressão:  |C(B)|/|B|.   Espera-se que a taxa seja estritamente menor que 1.
• Desafio: obter a menor taxa de compressão possível.

Considerações teóricas

• Proposição S: Nenhum algoritmo pode garantir taxa de compressão estritamente menor que 1 para todo e qualquer fluxo de bits.
• Exemplo: fluxos de bits aleatórios são pouco compressíveis.  Mesmo fluxos pseudo-aleatórios podem ser difíceis de comprimir.
• A propósito, muitos fluxos de bits (ou de caracteres, ou de números) parecem aleatórios mas não são.  Exemplo:  o fluxo de bits abaixo (figura produzida com PictureDump) parece aleatório…

  

  … mas foi produzido pelo programa a seguir. Portanto, o código do programa é uma versão comprimida do fluxo de bits da figura (com taxa de compressão inferior a 2%)!

  public class RandomBits {public static void main(String[] args)
  {int x=11111; for(int i=0;i<1000000;i++){x=x*314159+218281;
  BinaryStdOut.write(x>0);} BinaryStdOut.close();}}
  

• Outro exemplo: a fórmula   4 (\sum_{i=0}^{\infty} (-1)^i (1/(2i+1))   é uma representação muito comprimida da expansão decimal do número π.  (A expansão decimal de π — veja os primeiros 100 mil dígitos — parece aleatória à primeira vista.)
• A teoria da compressão de dados tem fascinantes ligações com a Teoria da Informação e o conceito de Aleatoriedade e Entropia.

Exemplo: genomas

• Ideia:  não precisamos usar 8 bits para representar os caracteres de um alfabeto pequeno.
• Em código ASCII, o genoma   ATAGATGCATAGCGCATAGCTAGATGTGCTAGC   usa 8×33 = 264 bits.  Como o alfabeto dos genomas só tem 4 letras, podemos usar só 2 bits por caractere:

  public static void compress() {
     Alphabet DNA = new Alphabet("ACTG");
     int w = DNA.lgR();                  // w == 2
     String s = BinaryStdIn.readString(); 
     int N = s.length();
     BinaryStdOut.write(N);
     for (int i = 0; i < N; i++) {
        int d = DNA.toIndex(s.charAt(i));
        BinaryStdOut.write(d, w);        // escreve 2 bits
     }
     BinaryStdOut.close();
  }
  

• Taxa de compressão: pouco mais que 2/8 = 25%.
• Correspondente expansor:

  public static void expand() {
     Alphabet DNA = new Alphabet("ACTG");
     int w = DNA.lgR();                    // w == 2
     int N = BinaryStdIn.readInt();
     for (int i = 0; i < N; i++) {   
        char c = BinaryStdIn.readChar(w);  // lê 2 bits e
        BinaryStdOut.write(DNA.toChar(c)); // escreve um char
     }
     BinaryStdOut.close();
  }
  

• Classe Java completa:

  public class Genome {
     public static void compress() { /* veja acima */ }
  
     public static void expand()   { /* veja acima */ }
  
     public static void main(String[] args) {
        if (args[0].equals("-")) compress();  
        if (args[0].equals("+")) expand();
     }
  }
  

• Exemplo: Um pequeno teste (264 bits):

  % more genomeTiny.txt
  ATAGATGCATAGCGCATAGCTAGATGTGCTAGC
  
  % java BinaryDump 64 < genomeTiny.txt
  0100000101010100010000010100011101000001010101000100011101000011
  0100000101010100010000010100011101000011010001110100001101000001
  0101010001000001010001110100001101010100010000010100011101000001
  0101010001000111010101000100011101000011010101000100000101000111
  01000011
  264 bits
  
  % java Genome - < genomeTiny.txt
  ??
  

  Não dá pra ver um fluxo de bits diretamente na saída padrão…  É precisa passar o fluxo por BinaryDump ou HexDump:

  % java Genome - < genomeTiny.txt | java BinaryDump 64
  0000000000000000000000000010000100100011001011010010001101110100
  1000110110001100101110110110001101000000
  104 bits
  
  % java Genome - < genomeTiny.txt | java HexDump 8
  00 00 00 21 23 2d 23 74
  8d 8c bb 63 40
  104 bits
  

  Compressão seguida de expansão reproduz o fluxo original:

  % java Genome - < genomeTiny.txt > genomeTiny.2bit
  
  % java Genome + < genomeTiny.2bit
  ATAGATGCATAGCGCATAGCTAGATGTGCTAGC
  
  % java Genome - < genomeTiny.txt | java Genome +
  ATAGATGCATAGCGCATAGCTAGATGTGCTAGC
  

• Exemplo: Um virus de verdade (taxa de compressão de 12536/50000 = 0.25):

  % java PictureDump 512 100 < genomeVirus.txt
  50000 bits
  
  
  % java Genome - < genomeVirus.txt | java PictureDump 512 25
  
  12536 bits
  

Exercícios 2

1. (SW 5.5.25) Código de comprimento fixo. Implemente uma classe RLE que use codificação de comprimento fixo para comprimir cadeia de bytes ASCII.  O método compress() deve começar por construir uma string alpha com todos os caracteres usados na cadeia de bytes original; essa string é usada para construir um Alphabet a ser usado no código de compressão.  A cadeia comprimida deve começar com alpha (codificação de 8 bits mais seu comprimento).  O método expand() lê alpha antes de executar a expansão.

Codificação de comprimento de carreira

• Em inglês: run-length encoding.
• Exemplo: A cadeia de bits abaixo tem uma carreira de quinze 0s, uma carreira de sete 1s, uma de sete 0s, e uma de onze 1s:

      0000000000000001111111000000011111111111
  

  Assim, a cadeia pode ser representada pela sequência de números  15 7 7 11.  Se usarmos 8 bits para representar cada um desses números em binário, teremos uma cadeia de apenas 32 bits (ignore os espaços):

      00001111 00000111 00000111 00001011
  

• Decisões de projeto:
  • Use 8 bits (valores de 0 a 255) para cada comprimento de carreira.
  • Use carreiras de comprimento 0 para dividir carreiras muito longas em blocos de comprimento menor que 256.
  • A primeira carreira é sempre de 0s (e pode ser vazia).
• Para texto ASCII, a compressão de comprimento de carreira não dá bons resultados.  Exemplo: a string  ABRACADABRA!  tem comprimentos de carreira muito curtos e assim a taxa de compressão atinge ridículos 416/96 = 4.33:

  % java BinaryDump 0 < abra.txt
  96 bits
  % java RunLength - < abra.txt | java HexDump 24
  01 01 05 01 01 01 04 01 02 01 01 01 02 01 02 01 05 01 01 01 04 02 01 01
  05 01 01 01 03 01 03 01 05 01 01 01 04 01 02 01 01 01 02 01 02 01 05 01
  02 01 04 01
  416 bits
  

• Boa aplicação: compressão dos mapas de bits (bitmaps) usados para representar figuras e documentos escaneados.
• Exemplo: O mapa de bits q32x48.bin representa uma letra q em uma tela de 32 por 48 pixels:

  % java PictureDump 32 48 < q32x48.bin
  1536 bits
  
  

  

  [Alguns dos números do lado direito da figura estão errados na linha 32 e seguintes.]  Para produzir a cadeia de bits original, emende cada linha do binary dump com a seguinte.  Os comprimentos de carreira são, portanto,   79 7 22 15 15 4 4 9 13 4 9 ... 19 14 65 .

  % java RunLength - < q32x48.bin > q32x48.bin.rle
  % java HexDump 16 < q32x48.bin.rle
  4f 07 16 0f 0f 04 04 09 0d 04 09 06 0c 03 0c 05
  0b 04 0c 05 0a 04 0d 05 09 04 0e 05 09 04 0e 05
  08 04 0f 05 08 04 0f 05 07 05 0f 05 07 05 0f 05
  07 05 0f 05 07 05 0f 05 07 05 0f 05 07 05 0f 05
  07 05 0f 05 07 05 0f 05 07 06 0e 05 07 06 0e 05
  08 06 0d 05 08 06 0d 05 09 06 0c 05 09 07 0b 05
  0a 07 0a 05 0b 08 07 06 0c 14 0e 0b 02 05 11 05
  05 05 1b 05 1b 05 1b 05 1b 05 1b 05 1b 05 1b 05
  1b 05 1b 05 1b 05 1b 05 1a 07 16 0c 13 0e 41
  1144 bits
  

• Método compress() para codificação de comprimento de carreira:

  public static void compress() {
     char cnt = 0;
     boolean b, old = false;
     while (!BinaryStdIn.isEmpty()) {
        b = BinaryStdIn.readBoolean();
        if (b != old) {
           BinaryStdOut.write(cnt);
           cnt = 0;
           old = !old;
        }
        else {
           if (cnt == 255) {
              BinaryStdOut.write(cnt);
              cnt = 0;
              BinaryStdOut.write(cnt); // indica carreira de 0 bits
           }
        }
        cnt++;
     }
     BinaryStdOut.write(cnt);
     BinaryStdOut.close();
  }
  

• Método expand() para codificação de comprimento de carreira:

  public static void expand() {
     boolean b = false;
     while (!BinaryStdIn.isEmpty()) {
        char cnt = BinaryStdIn.readChar(); // comprimento de uma carreira
        for (int i = 0; i < cnt; i++)
           BinaryStdOut.write(b);          // sai um único bit
        b = !b;
     }
     BinaryStdOut.close();
  }
  

• Para mapas de bits, a taxa de compressão é tanto melhor quanto maior a resolução. Se a resolução dobra,
  • o número de bits original é multiplicado por 4,
  • mas o número de carreiras da cadeia original é multiplicado apenas por 2 (aproximadamente);
  • portanto, o número de bits da cadeia comprimida é multiplicado apenas por 2 (aproximadamente);
  • assim, a taxa de compressão é metade do que era na resolução antiga.

  A taxa de compressão diminui linearmente com o aumento da resolução!

• Exemplo: A taxa de compressão do primeiro mapa de bits é 1144/1536 = 0.74 e a taxa de compressão para o dobro da resolução é de 2296/6144 = 0.37:

  % java PictureDump 32 48 < q32x48.bin
  1536 bits
  
  % java RunLength - < q32x48.bin | java BinaryDump 0
  1144 bits
  
  % java PictureDump 64 96 < q64x96.bin
  6144 bits
  
  % java RunLength - < q64x96.bin | java BinaryDump 0
  2296 bits
  

Exercícios 3

1. (SW 5.5.5)  Aplique o programa RunLength de codificação de comprimento de carreira ao arquivo q128x192.bin que está no website do livro. Quantos bits tem o arquivo comprimido?
2. (SW 5.5.7a)  Mostre a codificação de uma sequência de N a's  (ou seja, a,  aa,  aaa,  etc. )  com codificação de comprimento de carreira.  Qual a taxa de compressão em função de N?
3. (SW 5.5.8a)  Mostre a codificação de uma sequência de N repetições de ab  (ou seja, ab,  abab,  ababab,  etc. )  com codificação de comprimento de carreira.  Qual a taxa de compressão em função de N?
4. (SW 5.5.9a)  Estime a taxa de compressão da codificação de comprimento de carreira de uma sequência de N de caracteres ASCII aleatórios (em cada posição, todos os caracteres são igualmente prováveis).