Compactação de Dados

---

Eliminação de repetições

Ex.:    Entrada:  AAA333333333BBBBBBBBCCCC555555
           Saída:      3A939B4C65.

Problemas:  (Refletir sobre possíveis soluções)
1) E se houverem mais do que 10 caracteres em seqüência ?
2) E se houverem muitos caracteres que aparecem apenas uma única vez ?
3) Existem tipos de arquivos cuja compactação seria mais eficiente ? (.jpg , .txt, .doc, .bmp, .xpm ?)
 

Utilização de menos bits

Em arquivos do tipo "texto", o espaço gasto para armazer um único caracter é, geralmente, de um byte (8 bits). No entanto, é fácil perceber que a grande maioria dos textos não utiliza todas as 256 opções de símbolos que um byte pode representar. Um texto que utilize, por exemplo,  apenas letras minúsculas, sem acentos e alguns sinais de pontuação, não precisará mais do que 5 bits para representar cada diferente caracter. O compactador, nesse caso, realiza um mapeamento do símbolo inicial para símbolos de 5 bits. Esse mesmo mapeamento é usado pelo descompactador. Note que o total de bits a ser utilizado no armazenamento de cada caracter pode ser calculado dinamicamente, através de um "pré-processamento" no arquivo a ser compactado, para saber quantos símbolos diferentes aparecem no texto.

Problemas:
1) Além dos bits resultantes da compactação do texto original, o que mais deverá ser armazenado no arquivo compactado ?
2) Podemos utilizar a eliminação de repetições juntamente com a utilização de menos bits ?
3) Existem tipos de arquivos cuja compactação seria mais eficiente ? (.jpg , .txt, .doc, .bmp, .xpm ?)

Dicas:
1) Estudar operador "bitwise" para manipulação de bits em C ( & , | , << , >> , ~)

Algoritmo de Huffman

Exemplo:

Entrada: AAABCBAABAZX  (96 bits)

Freqüências:
A - 6
B - 3
C - 1
Z - 1
X - 1

Passo 2) Encontrar símbolos binários para representar os símbolos originais de forma que os símbolos de maior freqüência sejam representados pelos símbolos binários com menor quantidade de bits.

• Criar uma árvore digital binária com o total de folhas igual ao total de diferentes simbolos que aparecem no arquivo original. (No exemplo anterior, o total de diferentes simbolos é 5.).
• Associar os simbolos de maior frequencia às folhas mais próximas à raiz.

Para resolver o passo 2, Huffman criou e provou que o seguinte algoritmo gera a melhor árvore digital possível:

Seja n o total de diferentes símbolos do arquivo original.
Crie n ADBs (árvores digitais binárias) , com apenas 1 nó cada.
Guarde na raiz de cada uma dessas árvores a freqüência e o "nome" de um dos símbolos do arquivo original.
Seja f(T) a freqüência do símbolo armazenado na raiz da arvore T.
Para i de 1 até n - 1 faça
    Escolha as duas árvores T1 e T2 com os menores valores para f(T).
    Crie uma nova arvore T de forma que f(T) = f(T1) + f(T2).
    Transforme T1 e T2 em filhos direito e esquerdo da raiz de T.
 

Exemplo:

X(1)    Z(1)     C(1)       B(3)     A(6)

-------------------------------
       (2)             C(1)      B(3)     A(6)
      /    \
   /         \
X(1)     Z(1)
-------------------------------
                (3)                  B(3)     A(6)
               /      \
           /             \
       (2)             C(1)
      /    \
   /         \
X(1)     Z(1)
-------------------------------
                           (6)                    A(6)
                         /       \
                     /               \
                (3)                 B(3)
               /      \
           /             \
       (2)             C(1)
      /    \
   /         \
X(1)     Z(1)
----------------------------------
                                      (12)
                                    /        \
                                /                \
                           (6)                   A(6)
                         /       \
                     /               \
                (3)                 B(3)
               /      \
           /             \
       (2)             C(1)
      /    \
   /         \
X(1)     Z(1)
------------------------------
Novos Codigos:
A - 1
B - 01
C - 001
Z - 0001
X - 0000

Gravar informações sobre Árvore Digital Binária, calculada no passo anterior, para que o descompactador possa "recuperar" as associações entre símbolos originais e novos.

Utilizar as associações para "substituir" os simbolos originais.

Exemplo de um arquivo compactado: [Dados sobre a ADB] 11101001011101100010000
 

Material de Apoio