Wikipédia

Codificação aritmética: diferenças entre revisões

Explorar interativamente o histórico
← Ver a alteração anteriorVer a alteração posterior →
Conteúdo apagado Conteúdo adicionado
VisualTexto wiki
Alexg (discussão | contribs)
38 326 edições
Linha 1:
{{Wikificação|data=julho de 2010}}
[[Algoritmo]] para compressão de dados, não-baseado em tabelas de símbolos., Oo 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:
Linha 10:
onde <math>P(\sigma)</math> é a probabilidade de ocorrência do símbolo <math>\sigma</math>, <math>n_{\sigma}</math> é o número de ocorrências desse símbolo e <math>N</math> é 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 respectivamenterespetivamente de <math>\sigma_1, \sigma_2, ..., \sigma_N</math> e <math>I(\sigma_n)</math> o intervalo do n-ésimo símbolo:
 
<math>
Linha 18:
[[Imagem:Arithmetic encoding.svg|thumb|300px|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 caracterecarácter de acordo com esses intervalos. Parte-se do intervalo <math>[0, 1)</math> e nele identifica-se o subintervalosub-intervalo ao qual corresponde o primeiro símbolo lido do arquivo. Para cada símbolo subseqüentesubsequente, 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.
Linha 27:
# Cria-se um intervalo corrente iniciado com [0,1)
# Para cada elemento da mensagem:
## Particiona-se o intervalo corrente em subintervalossub-intervalos, um para cada letra do [[alfabeto]]. O tamanho do subintervalosub-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.
## O subintervalosub-intervalo correspondente à letra que é realmente o próximo elemento é selecionado como novo intervalo corrente.
#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.
 
Linha 45:
'''low''' = 0000
 
Representando nosso intervalo inicial. Para cada caracterecarácter lido, devemos estreitar esse intervalo proporcionalmente a probabilidade do caracterecará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 respectivamenterespetivamente o início e o fim do intervalo das probabilidades cumulativas de ocorrência do caracterecarácter <ref name="prob_cumul">A probabilidade cumulativa de ocorrência de um caracterecarácter é 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 caracterecarácter na ordenação.</ref>. A cada caracterecará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á<ref name="prova" /> e com isso podemos eliminá-lo dos nossos cálculos e escrevê-lo na saída do nosso programa.
Linha 80:
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üênciasequê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 semrpesempre que ocorrer um ''underflow''.
 
== Exemplo ==
O quadro abaixo mostra um exemplo de codificação aritmeticaaritmética da cadeia <code>A_ASA_DA_CASA</code>. 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:
 
{|
Obtida de "https://pt.wikipedia.org/wiki/Codificação_aritmética"