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.

Compressão de áudio

A compressão de arquivos de áudio é necessária para que se tenha maior facilidade na distribuição e divulgação do conteúdo, visto que o tempo e o tamanho da mídia que será disponibilizada ao usuário são diretamente proporcionais à quantidade de dados do arquivo.

Sabe-se que o ouvido humano não consegue captar todos os sons disponíveis (por exemplo, ao se ouvir uma orquestra, alguns sons são encobertos por outros). Analogamente, ao se distribuir um arquivo de áudio, pode-se remover alguns dados redundantes e irrelevantes, diminuindo, desta forma, o tamanho do arquivo.

Basicamente, pode-se optar pela compressão de áudio com ou sem perdas de dados. É claro que quando há perdas nesse processo, a taxa de compressão é otimizada, em detrimento da qualidade do arquivo.

Quando se admite perda de dados, algumas informações são descartadas antes de se realizar a compressão. Nesse processo, analisa-se o que pode ser considerado redundante ou irrelevante, tais como os sons que estão no limiar de audibilidade do ouvido humano (os quais não serão captados) ou aqueles que ocorrem simultaneamente, de modo que o mais intenso oculte o outro.

Alguns formatos de áudio são comumente utilizados para distribuição desses arquivos, tais como WAV, FLAC, MP3, etc.

O formato MP3 realiza a compressão do áudio de modo a permitir a perda de dados, fazendo com que os arquivos tenham um tamanho reduzido. Já os arquivos do tipo FLAC mantém os dados sem perdas, o que aumenta a qualidade e reduz a taxa de compressão desse arquivo.

Compressão de vídeo

Assim como na compressão de arquivos de áudio, os arquivos de vídeo também são comprimidos de forma a tornar mais eficaz sua transmissão e compartilhamento, sendo necessário que se tenha o CODEC específico para reprodução do vídeo.

Alguns formatos de vídeo são bastante comuns entre os usuários, seja porque são desenvolvidos e oferecidos como nativos de determinado sistema operacional ou porque tem taxas de compressão atrativas, tornando o arquivo pequeno o suficiente para ser reproduzido e distribuído sem maiores problemas.

Por exemplo, o formato WMV (Windows Media Video), assim como o WMA (Windows Media Audio), foi desenvolvido pela Microsoft e acompanha, por padrão, o sistema operacional WINDOWS, não sendo necessária a instalação de outro CODEC para sua reprodução.

Outro formato popular é o AVI, o qual funciona como um contêiner que armazena áudio e vídeo, combinando os dois arquivos. Também, a maioria dos dispositivos já traz esse CODEC nativamente e, pelo fato de ter uma excelente taxa de compressão, se popularizou entre os usuários da internet, sendo um dos formatos mais utilizados para reprodução de vídeo na WEB.

Da mesma forma como ocorre com os arquivos de áudio, existem CODECS específicos que trabalham com perdas de dados, o que faz com que o arquivo tenha uma melhor taxa de compressão (exemplo: RMVB e WMV) e aqueles que comprimem e recuperam o arquivo na sua integralidade, o que mantém a qualidade mas não oferece uma compressão eficiente (exemplo: MPEG).

Exemplo prático de compressão

Vamos utilizar o algoritmo de Huffman para comprimir um pequeno texto: “SO SEI QUE NADA SEI”.

Para armazenar esse texto, geralmente é necessário um byte para cada caractere, ou seja, oito bits de tamanho. Nesse caso, iremos ocupar um espaço relativo a 21 caracteres, ou seja, 168 bits.

Inicialmente, fazemos uma tabela de frequências para os caracteres:

S = 3 // O = 1 // _ = 4 // E = 3 // I = 2 // Q = 1 // U = 1 // N = 1 // A = 2 // D = 1 // “ = 2

Note que o caractere _ representa espaço.

Para aplicar o algoritmo, temos que escolher dois nós com as menores frequências e combiná-los. Esse nó combinado será pai dos outros dois nós. A frequência desse novo nó é a soma dos dois que foram combinados.

Ao final do processo, teremos um nó pai. Atribuímos ao nó filho da esquerda o número 0 e ao nó filho da direita o número 1. Ao fazer isso para todos os nós, temos a codificação para todos os caracteres da mensagem.

S = 000 E = 001 U = 01000 N = 01001 “ = 0101 A = 0110 D = 0111 O = 1000 Q = 1001 I = 101 _ = 11

Logo, o texto codificado em bits, através do algoritmo, ficaria:

0101000100011000001101111001010000011101001011001110110110000011010101

o que totaliza 70 bits, representando uma economia de 98 bits para a mensagem original, ou seja, uma taxa de compressão de 0,41.