Codificação aritmética

Esta página ou se(c)ção precisa ser formatada para o padrão wiki. Por favor ajude a formatar esta página de acordo com as diretrizes estabelecidas. (Julho de 2010)

Algoritmo para compressão de dados, não-baseado em tabelas de símbolos, o codificador aritmético elimina a associação entre símbolos individuais e palavras-códigos de comprimento inteiro e, com isto, é capaz de praticamente igualar a entropia da fonte em todos os casos.

A partir de um modelo estatístico, constrói-se uma tabela onde são listadas as probabilidades de o próximo símbolo lido ser cada um dos possíveis símbolos. Em geral esta probabilidade é simplesmente a contagem de todas as ocorrências do símbolo no arquivo dividida pelo tamanho do arquivo:

${\displaystyle P(\sigma )={\frac {n_{\sigma }}{N}}}$

onde ${\displaystyle P(\sigma )}$ é a probabilidade de ocorrência do símbolo ${\displaystyle \sigma }$, ${\displaystyle n_{\sigma }}$ é o número de ocorrências desse símbolo e ${\displaystyle N}$ é o tamanho do arquivo. Em contextos específicos (ao associar a codificação aritmética com outros métodos de compressão como o BWT por exemplo) outros modelos mais apropriados podem ser adotados, que desprezam parte do contexto, ou usam probabilidades determinadas dinamicamente a medida que o arquivo é processado.

Esta tabela é expressa na forma de intervalos cumulativos, de tal forma que se ordenarmos os símbolos em uma ordem qualquer, o início do intervalo de um símbolo coincide com o final do intervalo do símbolo anterior. O primeiro símbolo tem seu intervalo começado em 0 e o último símbolo tem seu intervalo terminado em 1. Sejam os símbolos ordenados de 1 a N chamados respetivamente de ${\displaystyle \sigma _{1},\sigma _{2},...,\sigma _{N}}$ e ${\displaystyle I(\sigma _{n})}$ o intervalo do n-ésimo símbolo:

${\displaystyle I(\sigma _{n})=\left[\sum _{i=1}^{n-1}{P(\sigma _{i})},\sum _{i=1}^{n}{P(\sigma _{i})}\right)}$

O algoritmo de codificação aritmética consiste em representar a probabilidade de ocorrência de cada carácter de acordo com esses intervalos. Parte-se do intervalo ${\displaystyle [0,1)}$ e nele identifica-se o sub-intervalo ao qual corresponde o primeiro símbolo lido do arquivo. Para cada símbolo subsequente, subdivide-se o intervalo atual em sub-intervalos proporcionais às probabilidades da tabela de intervalos, e encontra-se novamente o intervalo que corresponde ao próximo símbolo. Ao final do processo, teremos um intervalo que corresponde a probabilidade da ocorrência de todos os símbolos na ordem correta. A figura ao lado ilustra essa divisão e subdivisão sucessiva dos intervalos.

A saída do algoritmo é então um valor que esteja contido neste intervalo e possa ser representado com o menor número possível de dígitos. Na prática não se tenta encontrar o menor número de dígitos, mas apenas um número razoável de dígitos.

A codificação aritmética pode ser descrita como se segue:

1. Cria-se um intervalo corrente iniciado com [0,1)
2. Para cada elemento da mensagem:
   1. Particiona-se o intervalo corrente em sub-intervalos, um para cada símbolo do alfabeto. O tamanho do sub-intervalo associado a uma dada letra é proporcional à probabilidade de que esta letra seja o próximo elemento da mensagem, de acordo com o modelo assumido.
   2. O sub-intervalo correspondente à letra que é realmente o próximo elemento é selecionado como novo intervalo corrente.
3. Codifica-se a mensagem com o menor número de bits necessário para distinguir o intervalo corrente final de todos os outros possíveis intervalos correntes finais.

Pode-se ver uma implementação em linguagem python deste algoritmo ao final do artigo, na seção #Exemplo de implementação

Se nos basearmos diretamente na definição da codificação aritmética iremos encontrar dois problemas práticos:

1. nenhuma codificação é produzida antes que toda a mensagem tenha sido processada.
2. o cálculo dos limites do intervalo corrente para mensagens genéricas exige aritmética de altíssima precisão;

Entretanto a solução para tal problema é relativamente simples. Um codificador aritmético prático usa apenas de aritmética inteira para "simular" a aritmética de números reais. Para isso ele trabalha da seguinte maneira:

Definem-se dois valores que chamaremos de high e low que representam o intervalo atual. No início esse intervalo é entre ${\displaystyle [0,1)}$. Entretanto estamos trabalhando apenas com inteiros, de precisão finita. Então vamos considerar que high e low são apenas os primeiros dígitos após da vírgula no nosso intervalo. Sabemos também que ${\displaystyle 0,999...}$ é equivalente a ${\displaystyle 1}$^[1]. Então podemos representar (considerando base decimal e precisão de 4 dígitos):

high = 9999
low  = 0000

Representando nosso intervalo inicial. Para cada carácter lido, devemos estreitar esse intervalo proporcionalmente a probabilidade do carácter. Assim teremos a cada passada:

new_low = low + (high-low+1) * prob_inicial
new_high = low + (high-low+1) * prob_final - 1

onde new_low e new_high são os novos valores para low e high, e prob_inicial e prob_final são respetivamente o início e o fim do intervalo das probabilidades cumulativas de ocorrência do carácter ^[2]. A cada carácter lido reaplica-se essa fórmula até que tenham sido lidos todos os caracteres. Entretanto isto ainda não resolve o problema da precisão finita da nossa aritmética: caso o resultado desejado tenha mais de 4 dígitos depois da vírgula, não seremos capazes de calcular este valor. O passo a seguir soluciona os dois problemas listados no inicio dessa seção:

• Caso o primeiro dígito (o dígito mais a esquerda) dos dois valores, low e high venha a se tornar idêntico, sabemos que ele não mais mudará^[1] e com isso podemos eliminá-lo dos nossos cálculos e escrevê-lo na saída do nosso programa.

Assim, caso os dígitos mais significativos do nosso intervalo se igualem, escrevemos o dígito na saída (resolvendo o problema 1) e atualizamos nosso intervalo para ignorar esse dígito (i.e. nossos valores low e high passam a ser os dígitos da segunda casa após a vírgula em diante). Os novos valores para low e high nesse caso serão:

ultimo_digito = 1000 * (high / 1000)
high = (high - ultimo_digito) * 10 + 9
low = (low - ultimo_digito) * 10

No caso de high somamos 9 pois o valor original de high representava ${\displaystyle 0,999...}$, uma dízima periódica cujo próximo dígito que vamos "buscar" sempre será 9. em ambos os casos multiplicamos por 10 para poder "ganhar" um dígito na nossa precisão.

No final deste processo, emitimos o valor de low na saída, que representa os últimos dígitos do nosso código aritmético (os outros dígitos já foram emitidos durante o processo).

Nessa abordagem temos ainda um problema:

• O que acontece se nosso intervalo se aproxima cada vez mais, mas o último digito não se torna o mesmo? Por exemplo,

low  = 4999
high = 5000

Nessa situação apenas se a probabilidade for próximo símbolo for 100% é que conseguimos emitir um dígito na saída. Entretanto, podemos observar que quando essa situação acontece temos:

• o primeiro dígito de low é um a menos que o primeiro dígito de high
• o segundo dígito de low é 9
• o segundo dígito de high é 0

Essa situação é chamada de underflow. A solução para esse caso também é simples: mantemos um contador para as vezes onde ela acontece e eliminamos o segundo dígito de low e high. Quando o primeiro dígito dos dois números se igualarem, emitimos normalmente o dígito que se igualou e então verificamos:

• se ele se igualou "para cima", ou seja foi o primeiro dígito de low que cresceu para se igualar ao primeiro dígito de high, então emitimos uma seqüência de dígitos 0 do tamanho do contador (se o contador for 3, emitimos 000, se for 4 emitimos 0000 e assim por diante).
• se ele se igualou "para baixo" emitimos a mesma sequência, só que de dígitos 9.

No momento da descompressão basta seguir o mesmo procedimento, ignorando os dígitos introduzidos pela técnica acima sempre que ocorrer um underflow.

O quadro abaixo mostra um exemplo de codificação aritmética da cadeia A_ASA_DA_CASA. O modelo que utilizamos considera a probabilidade de ocorrência do símbolo como o número total de ocorrências do mesmo dividido pelo tamanho da cadeia. Assim temos uma probabilidade fixa durante todo o processo. As probabilidades dessa cadeia são:

Baseado nesse quadro podemos executar os passos da codificação. O quadro abaixo representa a codificação de cada letra. Quando algum dígito é produzido na saída, estes dígitos são indicados na última coluna.

Temos na saída os dígitos 2493469, que acrescidos dos dígitos de low (podemos ignorar os zeros no final) se torna 249346946. Esse é nosso código aritmético para a frase inicial. Esse número pode ser expresso em 28 bits. A frase inicial tem 13 caracteres, que podem ser expressos com 3 bits cada, totalizando 39 bits. Com a compressão aritmética economizamos 11 bits.

Podemos reduzir ainda mais esse valor se repararmos que o número 5000 fica entre os intervalos de low e high finais, economizando assim mais um dígito na codificação: 249346946. Em binário temos agora 25 bits. Isso representa um bit a menos que a codificação de Huffman da mesma cadeia, mostrando que a codificação aritmética é a que mais aproxima a entropia da cadeia de entrada.

• (em inglês) SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1 

• Codificação de Huffman
• Compressão sem perda de dados

Este artigo sobre Algoritmos é um esboço. Você pode ajudar a Wikipédia expandindo-o.