Como funciona a compressão de ficheiros

No nosso exemplo anterior, escolhemos todas as palavras repetidas e colocamos aquelas num dicionário. Para nós, esta é a forma mais óbvia de escrever um dicionário. Mas um programa de compressão vê-o de forma bastante diferente: Não tem qualquer conceito de palavras separadas – procura apenas padrões. E, a fim de reduzir ao máximo o tamanho do ficheiro, selecciona cuidadosamente os padrões a incluir no dicionário.

Se abordarmos a frase a partir desta perspectiva, acabamos com um dicionário completamente diferente.

Se o programa de compressão digitalizar a frase de Kennedy, a primeira redundância com que se depararia seria de apenas um par de letras. Em “não pergunte o seu”, há um padrão repetido da letra “t” seguida de um espaço — em “não” e “o quê”. Se o programa de compressão escrevesse isto no dicionário, poderia escrever um “1” cada vez que um “t” fosse seguido por um espaço. Mas nesta frase curta, este padrão não ocorre o suficiente para que valha a pena, pelo que o programa acabaria por sobregravá-lo.

A próxima coisa que o programa poderá notar é “ou”, que aparece tanto em “seu” como em “país”. Se este fosse um documento mais longo, escrever este padrão no dicionário poderia poupar muito espaço — “ou” é uma combinação bastante comum na língua inglesa. Mas como o programa de compressão funcionava através desta frase, rapidamente descobriria uma melhor escolha para a entrada de um dicionário: Não só “ou” é repetido, mas as palavras completas “your” e “country” são ambas repetidas, e na realidade são repetidas em conjunto, como a frase “your country”. Neste caso, o programa substituiria a entrada de dicionário para “ou” com a entrada para “o seu país”

A frase “pode fazer por” também é repetida, uma vez seguida de “seu” e uma vez seguida de “você”, dando-nos um padrão repetido de “pode fazer por si”. Isto permite-nos escrever 15 caracteres (incluindo espaços) com um valor numérico, enquanto “o seu país” apenas nos permite escrever 13 caracteres (com espaços) com um valor numérico, pelo que o programa escreveria por cima da entrada “o seu país” como apenas “r país”, e depois escreveria uma entrada separada para “pode fazer por si”. O programa procede desta forma, recolhendo todas as informações repetidas e depois calculando que padrões deve escrever no dicionário. Esta capacidade de reescrever o dicionário é a parte “adaptável” do algoritmo baseado no dicionário LZ adaptativo. A forma como um programa realmente o faz é bastante complicada, como se pode ver pelas discussões em Data-Compression.com.

Independentemente do método específico utilizado, este sistema de pesquisa aprofundada permite comprimir o ficheiro de forma muito mais eficiente do que se pudesse apenas escolher palavras. Usando os padrões que escolhemos acima, e adicionando “__” para espaços, chegamos a este dicionário maior:

E esta frase mais pequena: “1não__2345__–__12354”

A frase ocupa agora 18 unidades de memória, e o nosso dicionário ocupa 41 unidades. Assim, comprimimos o tamanho total do ficheiro de 79 unidades para 59 unidades! Esta é apenas uma forma de comprimir a frase, e não necessariamente a mais eficiente. (Veja se consegue encontrar uma maneira melhor!)

Então quão bom é este sistema? A relação ficheiro-redução depende de uma série de factores, incluindo tipo de ficheiro, tamanho do ficheiro e esquema de compressão.

Na maioria das línguas do mundo, certas letras e palavras aparecem frequentemente juntas no mesmo padrão. Devido a esta elevada taxa de redundância, os ficheiros de texto comprimem-se muito bem. Uma redução de 50 por cento ou mais é típica para um ficheiro de texto de bom tamanho. A maioria das linguagens de programação são também muito redundantes porque utilizam uma colecção relativamente pequena de comandos, que frequentemente aparecem juntos num padrão definido. Os ficheiros que incluem muita informação única, tais como gráficos ou ficheiros MP3, não podem ser muito comprimidos com este sistema porque não repetem muitos padrões (mais sobre isto na próxima secção).

Se um ficheiro tiver muitos padrões repetidos, a taxa de redução aumenta tipicamente com o tamanho do ficheiro. Pode ver isto apenas olhando para o nosso exemplo — se tivéssemos mais do discurso de Kennedy, seríamos capazes de nos referir aos padrões no nosso dicionário com mais frequência, e assim obter mais do espaço de arquivo de cada entrada. Além disso, podem emergir mais padrões generalizados no trabalho mais longo, permitindo-nos criar um dicionário mais eficiente.

Esta eficiência depende também do algoritmo específico utilizado pelo programa de compressão. Alguns programas são particularmente adequados à recolha de padrões em certos tipos de ficheiros, pelo que podem comprimi-los de forma mais sucinta. Outros têm dicionários dentro de dicionários, que podem comprimir eficientemente para ficheiros maiores, mas não para os mais pequenos. Embora todos os programas de compressão deste tipo funcionem com a mesma ideia básica, existe na realidade uma grande variação na forma de execução. Os programadores estão sempre a tentar construir um sistema melhor.