Buscando modelos

No exemplo na página anterior, pegamos todas as palavras repetidas e as colocamos no dicionário. Para nós, esta é a maneira mais óbvia de escrever um dicionário. Mas um programa de compressão vê isso de uma forma um pouco diferente. Ele não tem qualquer noção de palavras separadas e procura somente modelos. Para reduzir o tamanho do arquivo tanto quanto possível, ele seleciona cuidadosamente quais modelos incluir no dicionário.

Se observamos a frase por este ângulo, acabamos com um dicionário completamente diferente.

Se o programa de compressão explorasse a frase de Kennedy, a primeira redundância que encontraria seria apenas um par de letras distantes. Em "ask not what your" existe um modelo repetido da letra "t" seguida por espaço em "not" e "what". Se o programa de compressão gravou isso no dicionário, ele pode escrever um "1" toda a vez que um "t" for seguido por espaço. Nessa pequena frase, esse modelo não ocorre o suficiente para torná-lo uma entrada conveniente e o programa poderá sobrescrevê-lo.

A próxima coisa que o programa pode perceber é o "ou", que aparece tanto em "your" como em "country". Se fosse um documento longo, colocar este modelo no dicionário poderia salvar muito espaço, porque "ou" é uma combinação bastante comum na língua inglesa. Mas como o programa de compressão trabalhou a sentença, ele descobriria rapidamente uma melhor opção para uma entrada no dicionário: não apenas o "ou" é repetido, mas as palavras completas "your" e "country" são ambas repetidas e, na verdade, são repetidas juntas, como no termo "your country". Nesse caso, o programa poderia sobrescrever a entrada no dicionáro de "ou" para "your country".

A frase "can do for" também é repetida, uma vez seguida por "your" e uma vez por "you", dando-nos um modelo repetido de "can do for you". Isso nos permite escrever 15 caracteres (incluindo os espaços) com um único valor numérico, enquanto "your country" nos permite escrever apenas 13 caracteres (com espaços) com um único valor numérico, de modo que o programa poderia sobrepor a entrada "your contry" a "r country" e depois escrever uma entrada separada para "can do for you". O programa prossegue nesse caminho, pegando todos os bits de informação repetidos e calculando quais modelos poderia gravar no dicionário. A capacidade de regravar o dicionário é a parte "adaptável" do algoritmo adaptável de compressão baseado em dicionário LZ. O modo como um programa realmente faz isso é meio complicado, como podemos ver pelos debates no Data-Compression.com (em inglês).

Não importa qual método específico usamos, essa pesquisa elaborada nos permite comprimir o arquivo de modo muito mais eficiente do que poderíamos fazer escolhendo somente palavras. Usando os modelos que escolhemos acima e adicionando "__" para espaços, obtemos este grande dicionário:

ask__ what__ you r__country __can__do__for__you

E esta sentença menor:

"1not__2345__--__12354"

A sentença agora utiliza 18 unidades de memória e nosso dicionário ocupa 41 unidades. Assim temos o tamanho total do arquivo comprimido de 79 para 59 unidades! Esta é apenas uma maneira de comprimir a frase, não necessariamente a mais eficiente.

Quão vantajoso é esse sistema? A proporção da redução do arquivo depende de vários fatores, incluindo o tipo, o tamanho do arquivo e o esquema de compressão.

Na maioria das línguas do mundo, certas letras e palavras aparecem freqüentemente juntas no mesmo modelo. Em vista dessa alta taxa de redundância, arquivos de texto são comprimidos muito bem. Uma redução de 50% ou mais é comum para um arquivo de texto de bom tamanho. A maioria das linguagens de programação são também muito redundantes porque usa um conjunto relativamente pequeno de comandos, que freqüentemente estão juntos em um grupo de modelos. Arquivos que incluem um conjunto de informações únicas, como gráficos ou arquivos MP3, não podem ser muito comprimidos com este sistema porque não repetem muitos modelos.

Se um arquivo possui muitos modelos repetidos, a média de redução normalmente aumenta com o tamanho do arquivo. Você pode perceber isso olhando nosso exemplo. Se tivéssemos mais do discurso de Kennedy, poderíamos nos referir mais freqüentemente aos modelos em nosso dicionário e, com isso, extrair mais de cada entrada do arquivo. Modelos mais difundidos poderiam surgir de um trabalho mais extensivo, permitindo-nos criar um dicionário mais eficiente.

Essa eficiência depende do algoritmo usado pelo programa de compressão. Alguns programas são mais apropriados para escolher modelos em certos tipos de arquivos, podendo comprimi-los de modo mais conciso. Outros possuem dicionários dentro de dicionários, que podem comprimir eficientemente arquivos mais longos, mas não os menores. Embora todos os programas de compressão deste tipo trabalhem com a mesma idéia básica, existe, na verdade, uma grande variação quanto à forma de execução. Programadores estão sempre tentando construir um sistema melhor.

Com perdas e sem perdas
O tipo de compressão que estivemos discutindo aqui é chamado de compressão sem perda, porque nos permite recriar o arquivo original em seu formato inicial. A compressão sem perda está baseada na idéia de quebrar o arquivo em um formato "menor" para transmissão ou armazenamento e depois juntá-lo novamente para que possa ser usado outra vez.

A compressão com perda trabalha de forma bem diferente. Esses programas simplesmente eliminam bits de informação "desnecessários", reconstruindo o arquivo de uma maneira menor. Este tipo de compressão é muito usado para reduzir o tamanho de arquivos de figuras tipo bitmap, que tendem a ser bastante volumosos. Para ver como trabalham, vamos considerar como o seu computador pode comprimir uma fotografia escaneada.

Um programa de compressão sem perdas não pode fazer muito com este tipo de arquivo. Embora grandes partes da figura possam parecer a mesma (todo o céu é azul, por exemplo), muitos dos pixels individuais são um pouco diferentes entre si. Para tornar esta figura menor, sem comprometer a resolução, você terá de mudar o valor da cor de certos pixels. Se a figura contém muito céu azul, o programa pode escolher um tipo de azul que possa ser usado por cada pixel. Então o programa regrava o arquivo, de forma que o valor para cada pixel se refira à informação anterior. Se o esquema de compressão trabalha bem, você não notará a mudança, mas o tamanho do arquivo será reduzido de forma significativa.

Claro que com a compressão com perda, você não pode restaurar o arquivo original após a compressão. Você fica perplexo com a reinterpretação do original pelos programas de compressão. Por esta razão, não podemos usar este tipo de compressão para algo que necessite ser reproduzido como o original, incluindo aplicativos, bancos de dados e discursos presidenciais de posse.

Para mais informações sobre compressão de arquivos e assuntos relacionados, confira os links na próxima página.