Kioskea
Recherche
Faça uma pergunta »

O que significa compactação, compressão ? Como funciona ?

Fevereiro 2015


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:

*5Arepetimos 5 vezes o A
BBBdeixamos tal qual (*3B não é mais compacto que BBB)
Cdeixamos tal qual
*4Drepetimos 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.

AIMNOS
92301117283


(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 lidosCódigo de saídaAdição ao dicionário
//já existe no dicionário
W47 (código ASCII do /)256 = /W
E87 (código ASCII do W)257 = WE
D69 (código ASCII do E)258 = ED
/68 (código ASCII do D)259 = D/
W/W já existe no dicionário
E256 (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
E260 (código do /WE)262 = /WEE
/E/ já existe no dicionário
W261 (código do E/)263 = E/W
EWE já existe no dicionário
B257 (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
Para uma leitura offline, é possível baixar gratuitamente este artigo no formato PDF:
O-que-significa-compactacao-compressao-como-funciona.pdf

A ver igualmente

Na mesma categoria

Publicado por pintuda
Este documento, intitulado « O que significa compactação, compressão ? Como funciona ? »a partir de Kioskea (pt.kioskea.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.