Técnicas de codificação de entropia

O conceito de codificação de entropia refere-se às técnicas de compressão e codificação que não têm em conta a natureza da informação a ser comprimida, isto é, estas técnicas de compressão tratam todos os dados como sequências de bits, sem optimizar a compressão através do tipo de informação que se está a comprimir, ignorando, assim, a semântica desta informação.

Todas as técnicas de codificação de entropia proporcionam sempre um modo de compressão sem perdas.

As técnicas de codificação de entropia podem ser divididas em três tipos principais: técnicas de supressão de sequências repetitivas, técnicas de codificação estatística e técnicas baseadas em dicionários.

A técnica de supressão de sequências repetitivas baseia-se na produção de códigos de comprimento fixo e funciona em dois passos. Primeiramente, a detecção de sequências repetitivas de bits ou bytes e posteriormente a consequente substituição destas sequências pelo seu número de ocorrências.

Este método pode assumir uma de duas formas possíveis: Técnica de supressão de zeros ou espaços e Técnica Run-Length Encoding (RLE).

A Supressão de zeros ou espaços é o método de supressão de sequências repetitivas que assume apenas um carácter (byte) predeterminado que aparece frequentemente e é repetido. Este carácter pode ser o zero em dados numéricos ou o espaço em dados textuais. Consequentemente, uma série de n espaços, ou zeros, sucessivos será substituída por um carácter especial (flag ou meta character) imediatamente seguido pelo número de ocorrências (n) desse carácter.

Run-Length Encoding (RLE) permite que qualquer sequência de caracteres repetidos possa ser substituída por uma forma abreviada. Ou seja, permite comprimir qualquer carácter que surja de forma repetitiva, para além dos zeros e espaços. O algoritmo da técnica RLE consiste em substituir uma série de n caracteres “c” consecutivos pelo próprio carácter “c” precedido por um carácter especial (a flag ou escape character) que, por sua vez, é seguido pelo número n de ocorrências do carácter repetido. Este conjunto de 3 caracteres que substitui a sequência repetida designa-se por token, e representa-se do seguinte modo: !. Este método não deve ser utilizado nos casos em que um carácter surge repetido apenas duas vezes visto que originaria uma sequência mais comprida do que a sequência original. De igual modo, a sua utilização para substituir sequências de três caracteres sucessivos não traria qualquer vantagem. Assim, pode concluir-se que a substituição deve apenas ser realizada caso o número de ocorrências sucessivas de um carácter seja igual ou superior a quatro. A forma do método RLE é a forma mais simples e utiliza-se apenas para conteúdos textuais.

No que diz respeito à descompressão, sempre que se encontra a flag no fluxo de dados comprimidos efectua-se uma operação de leitura do valor n e do carácter C que se seguem, escrevendo-se o carácter C no fluxo de dados descomprimidos tantas vezes quantas o valor de n. A técnica RLE, para além de dados textuais, pode também ser aplicada a dados de imagem.

O método de técnicas de codificação estatística baseia-se no seguinte processo genérico:

1. Identificação dos padrões de bits ou bytes que ocorrem mais frequentemente num dado fluxo de dados.

2. Codificação de cada padrão com menos bits do que o número de bits dispendido para o representar no fluxo de dados original.

Na codificação estatística os padrões que ocorrem com menor frequência serão codificados mediante a utilização de mais bits, ao passo que os padrões mais frequentes serão substituídos por códigos menos extensos. A noção fundamental assenta na codificação estatística, os padrões de bits ou bytes são substituídos de acordo com a frequência com que ocorrem, sendo este o motivo porque se designa por estatística. Os padrões mais frequentes utilizam códigos mais curtos, ao passo que os padrões menos frequentes utilizam códigos mais extensos.

No entanto, já que o método da codificação estatística implica a substituição de padrões por outros padrões menos ou mais extensos deve existir uma tabela, normalmente designada por codebook ou tabela de códigos, que estabeleça a correspondência entre os padrões originais e o seu novo código, quer no lado da codificação quer no da descodificação. Em certos casos, a identificação da frequência do padrão e a atribuição de códigos já se encontra disponível ou é predefinida. Neste caso, a frequência de ocorrência dos padrões não necessita de ser determinada de cada vez que se codifica um novo fluxo de dados.

O método de codificação estatística pode ser implementado de várias formas, nas quais se incluem: substituição de padrões, destinada exclusivamente à codificação de informação textual; codificação de comprimento variável onde os métodos mais conhecidos são os de Huffman e de Shannon-Fano; e a codificação aritmética que proporciona uma óptima compressão do ponto de vista do valor de entropia de uma sequencia de dados de entrada, determinado pelos métodos da teoria da informação. Voltando um pouco atrás, relativamente à codificação de Huffman, o seu funcionamento baseia-se na determinação da frequência das ocorrências de cada byte para uma dada porção do fluxo de dados original; determinar, de acordo com o algoritmo de Huffman, o número mínimo de bits a atribuir a cada carácter a partir da tabela de frequências de ocorrências e atribuir um código “óptimo” de acordo com esse cálculo e, por fim, armazenar os códigos atribuídos numa tabela de códigos.

As técnicas baseadas em dicionários utilizam uma selecção de sequências de símbolos e uma codificação destas sequências como um token, recorrendo a um dicionário que armazena as sequências de símbolos. Por outro lado, estes métodos são assimétricos, o que faz com que a compressão seja mais complexa que a descompressão. O dicionário utilizado pode ser estático que permite a adição de novas sequências mas não a eliminação das já existentes, ou dinâmico que se adapta à mensagem a codificar dado que contém as sequências anteriores encontradas na mensagem a codificar.

Fonte: Ribeiro, Nuno; Torres, José. Tecnologias de Compressão Multimédia. 3ª Edição. FCA – Editora de Informática, Lda. 2007.