Introdução

Se você baixa muitos programas e arquivos da Internet, provavelmente já deve ter se deparado com arquivos em formato ZIP. Esse sistema de compressão é uma invenção muito conveniente, especialmente para usuários da web, porque permite reduzir o número total de bits e bytes em um arquivo, para que possa ser transmitido de forma mais rápida pela Internet com conexões lentas ou ocupar menos espaço em disco. Assim que tiver baixado o arquivo, seu computador usa um programa como o WinZip ou Stuffit para expandir o arquivo ao tamanho original. Se tudo correr bem, o arquivo expandido é idêntico ao arquivo original antes da compressão.

À primeira vista, isto parece complicado. Podemos reduzir o número de bits e bytes e depois colocar estes mesmos bits e bytes de volta? A idéia básica por trás desse processo é bem simples. Neste artigo, examinaremos este simples método, selecionando um pequeno arquivo e submetendo-o ao processo de compressão.

A maioria dos arquivos de computador possui a mesma informação registrada repetidas vezes. Os programas de compressão de dados simplesmente se livram dessa redundância. Em vez de registrarem uma parte da informação várias vezes, um programa de compressão de arquivo lista esta informação uma vez, fazendo nova referência a ela sempre que volta a aparecer no programa original.

Como exemplo, vamos observar um tipo de informação que nos é familiar: palavras.

Em 1961, em seu discurso de posse, John F. Kennedy proferiu esta famosa frase:

"Ask not what your country can do for you - ask what you can do for your country" (não pergunte o que o seu país pode fazer por você, mas o que você pode fazer por seu país).

A frase original em inglês possui 17 palavras, 61 letras, 16 epaços, um travessão e um ponto final. Se cada letra, espaço ou pontuação ocupar uma unidade da memória, teremos um tamanho total de arquivo de 79 unidades. Para diminuir o tamanho do arquivo teremos de procurar as redundâncias.

Imediatamente pecebemos, no texto original, que:

• a palavra "ask" aparece duas vezes
• "what" aparece duas vezes
• "your" aparece duas vezes
• "country" aparece duas vezes
• "can" aparece duas vezes
• "do" aparece duas vezes
• "for" aparece duas vezes
• "you" aparece duas vezes

Ignorando a diferença entre maiúsculas e minúsculas, cerca de metade da frase é redundante. Nove palavras: "ask", "not", "what", "your", "country", "can", "do", "for" e "you" nos dão quase tudo de que precisamos para a citação completa. Para construir a segunda parte da frase, devemos apontar para as palavras na primeira parte e preencher os espaços e pontuação.

A maioria dos programas de compressão usa uma variação do algoritmo adaptável de compressão baseado em dicionário LZ para reduzir os arquivos. "LZ" refere-se a Lempel e Ziv, criadores do algoritmo, e "dicionário" refere-se ao método de catalogação das partes dos dados.

O sistema que organiza os dicionários varia, podendo ser tão simples quanto uma lista numerada. Quando passamos pelas famosas palavras de Kennedy, selecionamos as palavras repetidas e as colocamos em um índice numerado. Depois simplesmente redigimos o número, em vez de escrevermos a palavra por extenso.

Se este é nosso dicionário:

ask what your country can do for you

Nossa sentença seria lida assim:

"1 not 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4"

Se você conhecesse o sistema, poderia facilmente recontruir a frase original usando somente este dicionário e o modelo numérico. Isto é o que o programa de expansão faz no seu computador quando baixa e expande um arquivo. Você também pode ter encontrado arquivos comprimidos que se abrem sozinhos. Para criar este tipo de arquivo, o programador inclui um programa simples de expansão junto ao arquivo comprimido. Assim que é baixado, o arquivo original é reconstruído automaticamente.

Mas quanto espaço salvamos com esse sistema? "1 not 2 3 4 5 6 7 8 - 1 2 8 5 6 7 3 4" é certamente menor que "Ask not what your country can do for you; ask what you can do for your country", mas lembre-se de que precisamos salvar o dicionário propriamente dito junto com o arquivo.

Em um esquema de compressão atual, descobrir os diferentes requisitos do arquivo pode ser um pouco complicado, mas, para os nossos propósitos, vamos voltar para à idéia de que cada caractere e cada espaço ocupa uma unidade de memória. Vimos que a frase inteira ocupa 79 unidades. Nossa frase comprimida (incluindo os espaços) ocupa 37 unidades e o dicionário (palavras e números) também ocupa 37 unidades. Isto nos dá um tamanho de arquivo de 74, o que não nos traz uma redução significativa.

Mas isto para uma única sentença. Você pode imaginar que se o programa de compressão se ocupasse do restante do discurso de Kennedy, poderia encontrar estas e outras palavras repetidas muitas outras vezes. Como veremos na próxima seção, ele poderia também reescrever o dicionário para conseguir a organização mais eficiente possível.