Codificação aritmética

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde julho de 2010).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.

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:


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

onde P(\sigma) é a probabilidade de ocorrência do símbolo \sigma, n_{\sigma} é o número de ocorrências desse símbolo e 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 respectivamente de \sigma_1, \sigma_2, ..., \sigma_N e I(\sigma_n) o intervalo do n-ésimo símbolo:


I(\sigma_n) = \left [ \sum_{i=1}^{n-1}{P(\sigma_i)}, \sum_{i=1}^{n}{P(\sigma_i)} \right )

Diagrama representando a subdivisão dos intervalos na codificação aritmética, usando-se quatro símbolos de probabilidades 0.6, 0.2, 0.1, e 0.1. Os círculos negros representam a mensagem codificada, que pode ser decodificada para o primeiro símbolo, depois o terceiro, em seguida o quarto. A primeira linha mostra o intervalo completo [0,1) enquanto as linhas subsequentes mostram as subdivisões proporcionais do intervalo anterior.

O algoritmo de codificação aritmética consiste em representar a probabilidade de ocorrência de cada caractere de acordo com esses intervalos. Parte-se do intervalo [0, 1) e nele identifica-se o subintervalo ao qual corresponde o primeiro símbolo lido do arquivo. Para cada símbolo subseqüente, 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.

Descrição do algoritmo[editar | editar código-fonte]

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 subintervalos, um para cada letra do alfabeto. O tamanho do subintervalo 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 subintervalo 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

Cálculo com precisão finita[editar | editar código-fonte]

Se nos basearmos diretamente na definição da codificação aritmética iremos esbarrar em 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 [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 0,999... é equivalente a 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 caractere lido, devemos estreitar esse intervalo proporcionalmente a probabilidade do caractere. 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 respectivamente o início e o fim do intervalo das probabilidades cumulativas de ocorrência do caractere[2] . A cada caractere 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 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).

Underflow[editar | editar código-fonte]

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 dor 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 seqüê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 semrpe que ocorrer um underflow.

Exemplo[editar | editar código-fonte]

O quadro abaixo mostra um exemplo de codificação aritmetica 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:

Símbolo ocorrências probabilidade acumulada
A 6 0.4615 0.4615
_ 3 0.2308 0.6923
S 2 0.1538 0.8462
C 1 0.0769 0.9231
D 1 0.0769 1.0000

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.

Entrada Low High Saída gerada
0000 9999 -
A 0000 4614 -
_ 2130 3194 -
A 2130 2620 2
1300 6209 -
S 4699 5453 -
A 4699 5046 -
_ 4859 4938 4
8590 9389 -
D 9328 9389 9
3280 3899 3
2800 8999 -
A 2800 5660 -
_ 4120 4779 4
- 1200 7799 -
C 6784 7291 -
A 6784 7017 -
S 6946 6981 6
9460 9819 9
4600 8199 -
A 4600 6260 -

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.

Notas e Referências[editar | editar código-fonte]

  1. a b Para uma prova dessa afirmativa veja SALOMON, David. Data Compression: The Complete Reference. 2 ed. Nova Iorque: Springer, 2000. ISBN 0-387-95045-1 ou qualquer livro de Cálculo diferencial.
  2. A probabilidade cumulativa de ocorrência de um caractere é calculada ordenando-se os caracteres e somando a probabilidade de ocorrência de cada um dos caracteres anteriores a ele. O intervalo de cada caractere inicia-se na soma de todos os anteriores e termina no inicio da probabilidade cumulativa do próximo caractere na ordenação.

Bibliografia[editar | editar código-fonte]

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

Ver também[editar | editar código-fonte]

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