Algoritmos/Compressão de dados
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.
Sem perdas
[editar | editar código-fonte]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).
Com perdas
[editar | editar código-fonte]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]Huffman
[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.
Compressão
[editar | editar código-fonte]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]- Kutova, Marcos (2017) Slides e Vídeo-aulas no AVA - visitado em 18 de maio de 2017
- Faculdade Unioeste - Slide Show - visitado em 18 de maio de 2017
- Informações da faculdade UFSM - visitado em 18 de maio de 2017