Saltar para o conteúdo

Algoritmos/Compressão de dados

Origem: Wikilivros, livros abertos por um mundo aberto.

Compressão de dados

[editar | editar código-fonte]

Compressão de Dados é uma forma de usar menos espaço para armazenar a maior quantidade de informação, podendo assim reduzir o espaço utilizado, que pode ser uma imagem, um texto, um vídeo ou qualquer tipo de arquivo. Para diminuir o espaço utilizado, usa-se diversos algoritmos cujo objetivo é reduzir a quantidade necessária de Bytes para representar uma determinada informação.

Tipos de Compressão de dados

[editar | editar código-fonte]

Existem dois tipos principais de compressão de dados, as compressões com perdas e as sem perdas.

A compressão sem perdas é aquela na qual o dado permanece o mesmo depois de descompactado, geralmente é usada na compactação de documentos, trabalhos acadêmicos e diversos outros tipos de informações que devem permanecer inalteradas após a descompactação.  Para obter a compressão sem perdas geralmente são usadas duas estratégias, a codificação de redundância mínima e o método do dicionário.

A redundância mínima consiste em representar os símbolos que aparecem com mais frequência utilizando menos bits, um exemplo de algoritmo que utiliza essa tática é a Codificação de Huffman. O método do dicionário utiliza um arquivo como se fosse um dicionário de expressões com os seus valores correspondentes em bits. Essa estratégia é utilizada pelo algoritmo Lempel-Ziv-Welch (LZW).

A compressão com perdas é aquela na qual os detalhes da informação são perdidos durante a descompactação. Geralmente é usada para compactar áudios e vídeos na internet, pois, nesses casos, a perda de precisão é benéfica e não afeta o entendimento da informação. Um exemplo disso, é a perda de qualidade de um vídeo disponibilizado online para evitar que ele demore a carregar caso a conexão com a internet não esteja boa. Alguns exemplos de algoritmos que se baseiam na compressão de imagens com perdas são o JPEG, MP3 e MP4. Já para o uso de animações, alguns dos algoritmos existentes são Flash, VC-1 e H.261. 

Algoritmos de Compressão de Dados

[editar | editar código-fonte]

A codificação de Huffman é um algoritmo de compressão que utiliza as probabilidades da ocorrência de símbolos e palavras em um conjunto de dados para determinar quantos bits serão utilizados para cada simbolo. Esse método foi criado por David A. Huffman em 1952.

Para mostrar o funcionamento da compressão por Huffman,vamos comprimir a sequência de carácteres AAAAAABBBBBCCCCDDDEEF. Se utilizarmos a forma padrão onde cada caractere tem valor fixo,a menor codificação que pode ser usado para que os carácteres fiquem em binário é de 3 bits,como a imagem mostra abaixo:

Caractere A B C D E F
Codigo 000 001 010 011 100 101

A sequencia gerada de bits em binário é 000000000000000000001001001001001010010010010011011011100100101, gerando assim 63 bits de comprimento.

Já para a codificação de Huffman dessa sequência, precisamos primeiro montar uma árvore seguindo os seguintes passos.

1ª etapa: Contar as ocorrências de cada caractere na sequência.

Caractere A B C D E F
Contador 6 5 4 3 2 1

2ª etapa: Agora devemos montar arvóres utilizando sempre os 2 com menor contagem de números para criar essa árvore.

F = 1 E = 2 D = 3 C = 4 B = 5 A = 6

Juntaremos agora os 2 de menor contagem(F e E), em uma árvore e somares suas contagens em um novo nó. Este novo nó é inserido no conjunto novamente na posição de seu novo peso.

D = 3 E+F = 3 C = 4 B = 5 A = 6

Quando esse novo nó é criado,deve-se colocar,no engalhamento dessa arvore,o valor binário pra um dos numeros como 1 e o outro como 0.

         E+F = 3
       /        \
      0            1
   /                  \
F = 1                 E = 2

Depois continue o mesmo processo até ter toda a árvore completa com a soma total dos caracteres no nó principal.

C = 4 B = 5 D+E+F = 6 A = 6
                D + E + F = 6
             /  1             \ 0
          D = 3               E+F = 3
                          / 0        \ 1
                       F = 1           E = 2

Criando nova árvore juntando os 2 menores numeros B e C.

D+E+F = 6 A = 6 B+C = 9
                      D+E+F = 6                                      A = 6                         B+C = 9
                  /  1          \ 0                                                              /0       \1
               D = 3            E+F = 3                                                       C = 4        B = 5
                              / 0        \ 1
                           F = 1          E = 2

Juntando agora D+E+F com A.

B+C = 9 A+D+E+F = 12
                      B+C = 9                                                     A+D+E+F = 12
                   /0         \1                                                /0            \1
                C = 4        B = 5                                           A = 6           D+E+F = 6
                                                                                          / 0          \ 1
                                                                                       D = 3         E+F = 3
                                                                                                 / 0          \ 1
                                                                                                F = 1          E = 2

Juntando todos os caracteres agora.

A + B + C + D + E + F = 21
                                                               A+B+C+D+E+F = 21
                                                          / 0                   \ 1
                                                      B+C = 9                A+D+E+F = 12
                                                   / 0    \ 1               /0            \1
                                                C = 4     B = 5          A = 6        D+E+F = 6
                                                                                   / 0          \ 1
                                                                                 D = 3         E+F = 3
                                                                                           / 0          \ 1
                                                                                         F = 1          E = 2

3ª etapa: Depois de construída a árvore final,basta percorrer a árvore e ir "anotando" os bits correspondentes de cada aresta para descobrir quantos bits valerá cada caractere.Por exemplo, para chegar a letra D percorremos os bits 1 até o nó A+D+E+F, depois o bit 1 para chegar em D+E+F e depois o bit 0 novamente, chegando a letra D. Assim o código Huffman para a letra D será 110.Confira a tabela de quanto valerá cada caractere em binário.

A = 10 B = 01 C = 00 D = 110 F = 1110 E = 1111

Percebe-se que depois da compressão de Huffman o valor da sequência adquirido no final foi de 51 bits, antes da compressão tinha sido 63 bits, com a utilização dessa metodo de compressão foi economizado 12 bits ,cerca de 20% do valor original da sequência.

Lempel-Ziv-Welch

[editar | editar código-fonte]

Lempel-Ziv-Welch é um algoritmo de compressão criado por Terry Welch no ano de 1984 e que foi baseado no LZ77 criada por Lempel e Ziv. O método utiliza a estratégia de dicionário na qual cada símbolo ou conjunto de símbolos é armazenado em um arquivo junto com o seu respectivo índice que possui um valor fixo de bits. Esse valor fixo é definido no algoritmo LZW como sendo de 12 bits. 

Codificação

[editar | editar código-fonte]

Para codificar é necessário seguir as etapas:

1°etapa: Inicializar o dicionário com símbolos básicos. Geralmente esses símbolos correspondem aos 256 caracteres da tabela ASCII. No entanto, no exemplo será usado menos caracteres para facilitar a compreensão.

Frase a ser codificada: GVCAABPQGVABC

Dicionário:

Símbolo Índice
a 0
b 1
c 2
g 3
u 4
v 5

2°etapa: Identificar o símbolo na primeira posição da frase e juntá-lo ao próximo símbolo. Depois inserir o conjunto formado no Dicionário

Frase a ser codificada: GVCAABPQGVABC

Primeira letra: G

Segunda letra: V

Conjunto a ser inserido no Dicionário: GV

Dicionário:

Símbolo Índice
a 0
b 1
c 2
g 3
u 4
v 5
gv 6

3°etapa: Identificar o segundo símbolo, juntá-lo com o terceiro e inserir no Dicionário

Frase a ser codificada: GVCAABPQGVABC

Primeira letra: V

Segunda letra: C

Conjunto a ser inserido no Dicionário: VC

Dicionário:

Símbolo Índices
a 0
b 1
c 2
g 3
u 4
v 5
gv 6
vc 7

4°etapa: Repetir o processo até que o conjunto formado já esteja no dicionário. Nesse caso, o conjunto junta-se com a próxima letra:

Frase a ser codificada: GVCAABPQGVABC

O símbolo GV já está no dicionário

Conjunto a ser inserido no Dicionário: GVA

Dicionário:

Símbolo Índice
a 0
b 1
c 2
g 3
u 4
v 5
gv 6
vc 7
ca 8
aa 9
ab 10
bp 11
qg 12
gva 13

5°etapa: O processo se repete até a frase acabar

Ligações externas

[editar | editar código-fonte]