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:
|
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 no próximo artigo, ele poderia também reescrever o dicionário para conseguir a organização mais eficiente possível.