Codificação aritmética: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 16:
==Aplicações==
Se nos basearmos diretamente na definição da codificação aritmética iremos esbarrar em dois problemas práticos:
▲* nenhuma codificação é produzida antes que toda a mensagem tenha sido processada.
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 <math>[0, 1)</math>. 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. Sabemso também que <math>0,999...</math> é equivalente a <math>1</math><ref name="prova">Para uma prova dessa afirmativa veja {{referência a livro|Autor=SALOMON, David|Título=Data Compression|Subtítulo=The Complete Reference|Editora=Springer|Local de publicação=Nova Iorque|Ano=2000|Edição=2|ID={{ISBN|0-387-95045-1}}}} ou qualquer livro de [[Cálculo diferencial]].</ref>. Então podemos representar (considerando base [[decimal]] e precisão de 4 [[dígito]]s):
'''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<ref name="prob_cumul">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.</ref>. 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á<ref name="prova" /> 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 calor original de '''high''' representava <math>0,999...</math>, 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).
== Notas e Referências ==
<references />
[[Categoria:Algoritmos de compressão de dados]]
| |||