Codificação aritmética: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 42:
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).
== Exemplo ==
O quadro abaixo mostra um exemplo de codificação aritmetica da cadeia <code>A_ASA_DA_CASA</code>. O modelo que utilizamos considera a probabilidade de ocorrência do símbolo como o numero 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.
{|border="1"
|'''Entrada'''||'''Low'''||'''High'''||'''Saída gerada'''
|-
|||0000||9999||align="center"|-
|-
|align="center"|A||0000||4614||align="center"|-
|-
|align="center"|_||2130||3194||align="center"|-
|-
|align="center"|A||2130||2620||align="center"|2
|-
|||1300||6209||align="center"|-
|-
|align="center"|S||4699||5453||align="center"|-
|-
|align="center"|A||4699||5046||align="center"|-
|-
|align="center"|_||4859||4938||align="center"|4
|-
|||8590||9389||align="center"|-
|-
|align="center"|D||9328||9389||align="center"|9
|-
|||3280||3899||align="center"|3
|-
|||2800||8999||align="center"|-
|-
|align="center"|A||2800||5660||align="center"|-
|-
|align="center"|_||4120||4779||align="center"|4
|-
|align="center"|-||1200||7799||align="center"|-
|-
|align="center"|C||6784||7291||align="center"|-
|-
|align="center"|A||6784||7017||align="center"|-
|-
|align="center"|S||6946||6981||align="center"|6
|-
|||9460||9819||align="center"|9
|-
|||4600||8199||align="center"|-
|-
|align="center"|A||4600||6260||align="center"|-
|}
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 ==
| |||