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 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: onde é a probabilidade de ocorrência do símbolo , é o número de ocorrências desse símbolo e é 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 e o intervalo do n-ésimo símbolo: 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 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.