Codificação aritmética
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 codificação aritmética pode ser descrita como se segue: 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: 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 ) {\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 0 , 999... {\displaystyle 0,999...} é equivalente a 1 {\displaystyle 1} . Então podemos representar (considerando base decimal e precisão de 4 dígitos): Representando nosso intervalo inicial. Para cada carácter lido, devemos estreitar esse intervalo proporcionalmente a probabilidade do carácter. Assim teremos a cada passada:
Underflow
Nessa abordagem temos ainda um problema: 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: 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: 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.
