Algoritmo de Compressão

Esta pesquisa deve fornecer um conteúdo atualizado sobre o tema acima. Não esqueça de incluir as  
referëncias (fontes) no último item, reforçando que não deve ser um Copy/Paste e sim uma síntese 
das pesquisas que fizer.

Conceito

Um algoritmo de compressão de dados é um código que tem como finalidade diminuir a quantidade de dados de um determinado arquivo, sem prejudicar sua integridade. Tais algoritmos são importantes na medida em que diminuem o espaço de armazenamento de um arquivo, bem como o tempo para sua transmissão.

Sendo necessário menos espaço para armazenar um arquivo, obtemos um melhor aproveitamento de recursos computacionais, bem como também ganhamos em eficiência e rapidez no compartilhamento desses arquivos.

Os algoritmos para compactação / descompactação de dados (texto, áudio, vídeo) são chamados CODECS. Geralmente, sistemas operacionais como WINDOWS ou distribuições LINUX possuem alguns CODECS nativos, o que faz com que o usuário possa reproduzir alguns tipos de áudio/vídeo. Entretanto, em alguns casos, é necessário que se instale algum CODEC específico.

Basicamente, um algoritmo de compressão recebe um arquivo A e apresenta como saída um arquivo C(A), de modo que a quantidade de bits de A é menor que C(A). A taxa de compressão é dada pela razão: (bits em C(A)) / (bits em A). O desafio é tentar obter a menor taxa de compressão possível.

Algoritmos

Existem alguns algoritmos que são comumente utilizados para compressão de dados, conforme explicitado a seguir:

• Frequência de caracteres: Esse algoritmo é bastante eficaz quando utilizado para compactação de arquivos em que se observa cadeias de caracteres que se repetem. O algoritmo converte as repetições em símbolos numéricos, fazendo com que o número de bytes utilizados seja reduzido. Quanto maior forem as cadeias de caracteres repetidos, maior é a eficácia do algoritmo. Por exemplo, dada a sequência de 26 caracteres AAAHHHHYYYRGHFFFIOOPPPAAAA. Utilizando o algoritmo, podemos representá-la da seguinte maneira: 3A4H3Y1R1G1G3F1I2O3P4A Note que a taxa de compressão, nesse caso, é de 22/26 = 0,85. Podemos melhorar a eficácia do algoritmo se suprimirmos o dígito “1” do código. Outrossim, caso o texto contenha caracteres numéricos, deve-se utilizar um símbolo identificador nesses caracteres, para que não haja confusão com os números que representam as frequências das repetições. Por exemplo, a cadeia de caracteres GHHOOOPYYY6666990000DDDGTYYFHF77777JJJJJ, ao ser submetida ao Algoritmo de Frequência de Caracteres, teria a seguinte saída: G2H3OP3Y4@62@94@03DGT2YFHF5@75J onde a taxa de compressão é de 31/40 = 0,77. Note que quanto maior a frequência de repetição de caracteres, maior é a eficácia do algoritmo.

• Algoritmo de Huffman Este algoritmo foi desenvolvido na década de 1950 por David Huffman. Ele tenta representar os caracteres que aparecem com maior frequência em um dado texto pela menor quantidade de bits possível, deixando os códigos mais longos para os caracteres mais raros, usando o conceito de árvore binária, uma estrutura de dados onde um dado nó tem um endereço e dois ponteiros para dois outros nós. Geralmente, um caractere é representado por um conjunto de 8 bits. Ao mapear os caracteres que aparecem com maior frequência, podemos atribuir um conjunto menor que 8 bits para representa-lo. Na medida em que reduzimos o tamanho da representação do caractere, estamos comprimindo o texto. Por exemplo, digamos que iremos armazenar um texto com a seguinte mensagem: ABRACADABRA. Quando codificamos esse texto (considerando que cada caractere ocupa um espaço de 8 bits), são necessários 88 bits para representá-la. Utilizando o algoritmo de Huffman, temos que mapear a frequência dos caracteres: A = 5 B = 2 C = 1 D = 1 R = 2 Para cada caractere, é necessário atribuir um nó. O algoritmo combina os nós disponíveis e cria novos nós, da seguinte maneira: 1. No início de cada iteração, temos um conjunto de nós distintos: A = 5 B = 2 C = 1 D = 1 R = 2 2. Escolha dois nós com as menores frequências e combine-os. Esse nó combinado será pai dos outros dois nós. A frequência desse novo nó é a soma dos dois que foram combinados. A = 5 B = 2 CD = 2 R = 2 3. Repita a operação até que tenhamos somente um nó pai. Ao fim das iterações, teremos uma nova codificação para os caracteres, de modo que o caractere mais frequente será codificado com uma quantidade pequena de bits, ao passo que aos caracteres menos frequentes será atribuído cadeias de bits maiores. Para o exemplo apresentado, é possível reescrever a mensagem usando um total de 23 bits, o que representa uma taxa de compressão de 23/88 = 0,26. É fácil ver que o algoritmo recodifica os caracteres de acordo com as características de cada arquivo, ou seja, a tabela gerada não é universal.

• Algoritmo LZW O algoritmo em questão utiliza um dicionário de símbolos ou palavras, o qual vai sendo atualizado na medida em que o arquivo é percorrido. Essas entradas no dicionário são utilizadas para codificar outras partes do arquivo, gerando, desta forma, uma economia considerável de espaço.