O que significa compactação, compressão ? Como funciona ?
Em informática, a vaga custa caro. As barras de memória e os discos rígidos são caros, então tentamos não sobrecarregá-los.
Se pegarmos 30 letras A:
É preciso
30 bytes na memória do computador.
Podemos fazê-lo de maneira mais concisa: "
30 vezes a letra A":
Agora, isso só ocupa
3 bytes!
Isso é a compressão (ou compactação) ! Para um determinado dado, tentamos encontrar a representação mais compacta possível.
Podemos facilmente alternar de um para o outro:
Existem vários métodos, diferentes e inteligentes, para economizar espaço!
Aqui estão alguns.
RLE (Run Length Encoding)
É exatamente o mesmo exemplo que o anterior. Vemos repetições e as anotamos de forma mais compacta.
Podemos, por exemplo, utilizar um símbolo especial, como o "*" para indicar uma repetição.
Ou seja:
| *5A | repetimos 5 vezes o A |
| BBB | deixamos tal qual (*3B não é mais compacto que BBB) |
| C | deixamos tal qual |
| *4D | repetimos 4 vezes o D (é mais compato que DDDD) |
|
Este sistema de compactação é utilizado, por exemplo, no formato PCX e em algumas variantes do formato TIFF.
Huffman
Huffman é um sistema de codificação estatística.
No Huffman, é preciso contar a frequência de cada caractere.
Vamos imaginar que contamos a frequência das letras em um texto.
(no nosso texto, tinhamos 92 letras A, 30 letras I, etc)
A menor unidade de informação que um computador pode manipular é o bit: ele vale 0 ou 1.
Podemos construir uma árvore binária:
Quanto mais frequente uma letra, menos bits para representá-la.
A letra
A (a mais frequente) é representada por um único bit:
1.
Quanto ao
I (um pouco menos frequente), utilizamos dois bits:
00.
Quanto ao
O (menos frequente ainda), utilizamos 3 bits :
010.
E assim por diante.
Em binário, a palavra
"MAISON" (casa) se escreve normalmente (utilizando o
CódigoASCII):
No Huffman (com nossa árvore acima), ele se torna:
É evidente a economia de lugar!
Antes da compressão, o nosso texto utilizava 48 bits (6 bytes).
Após a compressão, ele utiliza apenas 20 bits (2,5 bytes).
Mas o Huffman tem uma desvantagem: você tem que fazer uma análise estatística de
todo o texto antes da compactação. Isso pode demorar.
O Huffman é relativamente pouco utilizado, sobretudo face ao desempenho de outros algoritmos como o Lempel-Ziv.
Lempel-Ziv
O Lempel-Ziv é construído, gradualmente, como um dicionário numerado de "palavras" já encontradas.
Se ele se deparar com uma palavra que ele já encontrou, ele não a recopia mas nota o seu "número".
Veja o algoritmo de compactação:
Começamos com um dicionário cheio, com todos os caracteres existentes (0-255). (Por exemplo, 65 contém
A, 66 contém
B , etc).
As novas palavras adicionadas ao dicionário começarão pelo número 256.
Exemplo:
A cadeia
/WED/WE/WEE/WEB.
É preciso 15*8 =
120 bits para armazenar esta cadeia na memória.
Vamos compactá-la com o Lempel-Ziv:
| Caracteres lidos | Código de saída | Adição ao dicionário |
|---|
| / | | /já existe no dicionário |
| W | 47 (código ASCII do /) | 256 = /W |
| E | 87 (código ASCII do W) | 257 = WE |
| D | 69 (código ASCII do E) | 258 = ED |
| / | 68 (código ASCII do D) | 259 = D/ |
| W | | /W já existe no dicionário |
| E | 256 (código do /W) | 260 = /WE |
| / | 69 (código ASCII do E) | 261 = E/ |
| W | | /W já existe no dicionário |
| E | | /WE já existe no dicionário |
| E | 260 (código do /WE) | 262 = /WEE |
| / | | E/ já existe no dicionário |
| W | 261 (código do E/) | 263 = E/W |
| E | | WE já existe no dicionário |
| B | 257 (código do WE) | 264 = WEB |
| (fim) | 66 (código ASCII do B) | |
|
O algoritmo sai:
'/WED<256>
E<260><261><257>
B'.
Aqui, basta 4*8 + 6*9 =
86 bits</gras. (Depois <gras>/WED, excedemos 255: é preciso utilizar 9 bits).
Variações deste método de compressão são usados nos formatos ZIP, RAR, ARJ, CAB, GIF, PNG, TIFF...
Este é um método muito utilizado porque:
- Ele é poderoso: ele compacta corretamente todos os tipos de dados.
- Não é muito difícil de programar.
- Ele pode trabalhar com os dados como eles veem: sem precisar analisar todos os dados com antecedência, como com o Huffman.
- Podemos usar dicionários de tamanhos variados, dependendo da memória que temos. (Com pequenos dicionários, compactamos menos bem, mas compactamos mais rapidamente).
Existem muitas variações de LZ: LZ77, LZW, etc.
Outros métodos
Existem outros métodos, como a codificação aritmética, a codificação por dicionário fixo (como o fax) ou o algoritmo Burrows-Wheeler. Alguns teem um desempenho muito melhor do que o LZ, ZIP e o Huffman, em taxa de compressão.
Os métodos que vimos aqui, ditos
não-destrutivos, porque você pode descompactar os dados exatamente como eles eram, antes da compactação.
Existem métodos
destrutivos que destroem uma parte dos dados durante a comressão. Ao descompactá-los, não temos exatamente os mesmos dados originais, mas dados parecidos. Este é o caso do MP3 ou do JPEG.
Artigo
original publicado por
sebsauvage
Tradução feita por Lucia Maurity y Nouira
A ver igualmente
Comunidade de assistência e de conselho.
