7182019 Codificaccedilatildeo aritmeacutetica

httpslidepdfcomreaderfullcodificacao-aritmetica 14

Codificaccedilatildeo aritmeacutetica

Algoritmo para compressatildeo de dados natildeo-baseado em

tabelas de siacutembolos O codificador aritmeacutetico elimina a

associaccedilatildeo entre siacutembolos individuais e palavras-coacutedigos

de comprimento inteiro e com isto eacute capaz de pratica-

mente igualar a entropia da fonte em todos os casos

A partir de um modelo estatiacutestico constroacutei-se uma tabela

onde satildeo listadas as probabilidades de o proacuteximo siacutem-

bolo lido ser cada um dos possiacuteveis siacutembolos Em geral

esta probabilidade eacute simplesmente a contagem de todas

as ocorrecircncias do siacutembolo no arquivo dividida pelo tama-

nho do arquivo

P (σ) = nσ

N

onde P (σ) eacute a probabilidade de ocorrecircncia do siacutembolo σ

nσ eacute o nuacutemero de ocorrecircncias desse siacutembolo e N eacute o

tamanho do arquivo Em contextos especiacuteficos (ao asso-

ciar a codificaccedilatildeo aritmeacutetica com outros meacutetodos de com-

pressatildeo como o BWT por exemplo) outros modelos mais

apropriados podem ser adotados que desprezam parte do

contexto ou usam probabilidades determinadas dinami-

camente a medida que o arquivo eacute processado

Esta tabela eacute expressa na forma de intervalos cumulativos

de tal forma que se ordenarmos os siacutembolos em uma or-dem qualquer o iniacutecio do intervalo de um siacutembolo coin-

cide com o final do intervalo do siacutembolo anterior O pri-

meiro siacutembolo tem seu intervalo comeccedilado em 0 e o uacutel-

timo siacutembolo tem seu intervalo terminado em 1 Sejam

os siacutembolos ordenados de 1 a N chamados respectiva-

mente de σ1 σ2σN e I (σn) o intervalo do n-eacutesimo

siacutembolo

I (σn) =983131sum

nminus1

i=1 P (σi)

sumn

i=1P (σi)

983081

[[ImagemArithmetic enco-

dingsvg|thumb|300px|Diagrama representando a

subdivisatildeo dos intervalos na codificaccedilatildeo aritmeacuteticausando-se quatro siacutembolos de probabilidades 06 02

01 e 01 Os ciacuterculos negros representam a mensagem

codificada que pode ser decodificada para o primeiro

siacutembolo depois o terceiro em seguida o quarto A

primeira linha mostra o intervalo completo [01) en-

quanto as linhas subsequentes mostram as subdivisotildees

proporcionais do intervalo anterior]]

O algoritmo de codificaccedilatildeo aritmeacutetica consiste em repre-

sentar a probabilidade de ocorrecircncia de cada caractere de

acordo com esses intervalos Parte-se do intervalo [0 1)e nele identifica-se o subintervalo ao qual corresponde o

primeiro siacutembolo lido do arquivo Para cada siacutembolo sub-

sequumlente subdivide-se o intervalo atual em sub-intervalos

proporcionais agraves probabilidades da tabela de intervalos

e encontra-se novamente o intervalo que corresponde ao

proacuteximo siacutembolo Ao final do processo teremos um in-

tervalo que corresponde a probabilidade da ocorrecircncia de

todos os siacutembolos na ordem correta A figura ao lado ilus-

tra essa divisatildeo e subdivisatildeo sucessiva dos intervalos

A saiacuteda do algoritmo eacute entatildeo um valor que esteja contido

neste intervalo e possa ser representado com o menor nuacute-

mero possiacutevel de diacutegitos Na praacutetica natildeo se tenta encon-

trar o menor nuacutemero de diacutegitos mas apenas um nuacutemero

razoaacutevel de diacutegitos

1 Descriccedilatildeo do algoritmo

A codificaccedilatildeo aritmeacutetica pode ser descrita como se segue

1 Cria-se um intervalo corrente iniciado com [01)

2 Para cada elemento da mensagem

(a) Particiona-se o intervalo corrente em subinter-

valos um para cada letra do alfabeto O tama-nho do subintervalo associado a uma dada letra

eacute proporcional agrave probabilidade de que esta le-

tra seja o proacuteximo elemento da mensagem de

acordo com o modelo assumido

(b) O subintervalo correspondente agrave letra que eacute

realmente o proacuteximo elemento eacute selecionado

como novo intervalo corrente

3 Codifica-se a mensagem com o menor nuacutemero de

bits necessaacuterio para distinguir o intervalo corrente

final de todos os outros possiacuteveis intervalos correntes

finais

Pode-se ver uma implementaccedilatildeo em linguagem python

deste algoritmo ao final do artigo na seccedilatildeo Exemplo de

implementaccedilatildeo

2 Caacutelculo com precisatildeo finita

Se nos basearmos diretamente na definiccedilatildeo da codificaccedilatildeo

aritmeacutetica iremos esbarrar em dois problemas praacuteticos

1 nenhuma codificaccedilatildeo eacute produzida antes que toda a

mensagem tenha sido processada

1

7182019 Codificaccedilatildeo aritmeacutetica

httpslidepdfcomreaderfullcodificacao-aritmetica 24

2 3 EXEMPLO

2 o caacutelculo dos limites do intervalo corrente para men-

sagens geneacutericas exige aritmeacutetica de altiacutessima preci-

satildeo

Entretanto a soluccedilatildeo para tal problema eacute relativamente

simples Um codificador aritmeacutetico praacutetico usa apenas dearitmeacutetica inteira para ldquosimularrdquo a aritmeacutetica de nuacutemeros

reais Para isso ele trabalha da seguinte maneira

Definem-se dois valores que chamaremos de high e low

que representam o intervalo atual No iniacutecio esse inter-

valo eacute entre [0 1) Entretanto estamos trabalhando ape-

nas com inteiros de precisatildeo finita Entatildeo vamos con-

siderar que high e low satildeo apenas os primeiros diacutegitos

apoacutes da viacutergula no nosso intervalo Sabemos tambeacutem que

0 999 eacute equivalente a 1 [1] Entatildeo podemos representar

(considerando base decimal e precisatildeo de 4 diacutegitos)

high = 9999 low = 0000

Representando nosso intervalo inicial Para cada carac-

tere lido devemos estreitar esse intervalo proporcional-

mente 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 satildeo os novos valores para low

e high e prob_inicial e prob_final satildeo respectivamente

o iniacutecio e o fim do intervalo das probabilidades cumu-

lativas de ocorrecircncia do caractere[2] A cada caractere

lido reaplica-se essa foacutermula ateacute que tenham sido lidos

todos os caracteres Entretanto isto ainda natildeo resolve oproblema da precisatildeo finita da nossa aritmeacutetica caso o

resultado desejado tenha mais de 4 diacutegitos depois da viacuter-

gula natildeo seremos capazes de calcular este valor O passo

a seguir soluciona os dois problemas listados no inicio

dessa seccedilatildeo

bull Caso o primeiro diacutegito (o diacutegito mais a esquerda)

dos dois valores low e high venha a se tornar idecircn-

tico sabemos que ele natildeo mais mudaraacute[1] e com isso

podemos eliminaacute-lo dos nossos caacutelculos e escrevecirc-lo

na saiacuteda do nosso programa

Assim caso os diacutegitos mais significativos do nosso inter-

valo se igualem escrevemos o diacutegito na saiacuteda (resolvendo

o problema 1) e atualizamos nosso intervalo para ignorar

esse diacutegito (ie nossos valores low e high passam a ser

os diacutegitos da segunda casa apoacutes a viacutergula em diante) Os

novos valores para low e high nesse caso seratildeo

ultimo_digito = 1000 (high 1000) high = (high - ul-

timo_digito) 10 + 9 low = (low - ultimo_digito) 10

No caso de high somamos 9 pois o valor original de high

representava 0 999 uma diacutezima perioacutedica cujo proacute-

ximo diacutegito que vamos ldquobuscarrdquo sempre seraacute 9 em am-bos os casos multiplicamos por 10 para poder ldquoganharrdquo

um diacutegito na nossa precisatildeo

No final deste processo emitimos o valor de low na saiacuteda

que representa os uacuteltimos diacutegitos do nosso coacutedigo aritmeacute-

tico (os outros diacutegitos jaacute foram emitidos durante o pro-

cesso)

21 Underflow

Nessa abordagem temos ainda um problema

bull O que acontece se nosso intervalo se aproxima cada

vez mais mas o uacuteltimo digito natildeo se torna o mesmo

Por exemplo

low = 4999 high = 5000

Nessa situaccedilatildeo apenas se a probabilidade dor proacuteximo

siacutembolo for 100 eacute que conseguimos emitir um diacutegito

na saiacuteda Entretanto podemos observar que quando essa

situaccedilatildeo acontece temos

bull o primeiro diacutegito de low eacute um a menos que o pri-

meiro diacutegito de high

bull o segundo diacutegito de low eacute 9

bull o segundo diacutegito de high eacute 0

Essa situaccedilatildeo eacute chamada de underflow A soluccedilatildeo para

esse caso tambeacutem eacute simples mantemos um contador para

as vezes onde ela acontece e eliminamos o segundo diacutegito

de low e high Quando o primeiro diacutegito dos dois nuacuteme-

ros se igualarem emitimos normalmente o diacutegito que se

igualou e entatildeo verificamos

bull se ele se igualou ldquopara cimardquo ou seja foi o primeiro

diacutegito de low que cresceu para se igualar ao primeiro

diacutegito de high entatildeo emitimos uma sequumlecircncia de

diacutegitos 0 do tamanho do contador (se o contador for

3 emitimos 000 se for 4 emitimos 0000 e assim por

diante)

bull se ele se igualou ldquopara baixordquo emitimos a mesma

sequumlecircncia soacute que de diacutegitos 9

No momento da descompressatildeo basta seguir o mesmo

procedimento ignorando os diacutegitos introduzidos pela

teacutecnica acima semrpe que ocorrer um underflow

3 Exemplo

O quadro abaixo mostra um exemplo de codificaccedilatildeo arit-

metica da cadeia A_ASA_DA_CASA O modelo que uti-

lizamos considera a probabilidade de ocorrecircncia do siacutem-

bolo como o nuacutemero total de ocorrecircncias do mesmo divi-

dido pelo tamanho da cadeia Assim temos uma proba-bilidade fixa durante todo o processo As probabilidades

dessa cadeia satildeo

7182019 Codificaccedilatildeo aritmeacutetica

httpslidepdfcomreaderfullcodificacao-aritmetica 34

3

Baseado nesse quadro podemos executar os passos da co-

dificaccedilatildeo O quadro abaixo representa a codificaccedilatildeo de

cada letra Quando algum diacutegito eacute produzido na saiacuteda

estes diacutegitos satildeo indicados na uacuteltima coluna

Temos na saiacuteda os diacutegitos 2493469 que acrescidos dos

diacutegitos de low (podemos ignorar os zeros no final) se torna249346946 Esse eacute nosso coacutedigo aritmeacutetico para a frase

inicial Esse nuacutemero 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 compressatildeo

aritmeacutetica economizamos 11 bits

Podemos reduzir ainda mais esse valor se repararmos que

o nuacutemero 5000 fica entre os intervalos de low e high fi-

nais economizando assim mais um diacutegito na codificaccedilatildeo

249346946 Em binaacuterio temos agora 25 bits Isso repre-

senta um bit a menos que a codificaccedilatildeo de Huffman da

mesma cadeia mostrando que a codificaccedilatildeo aritmeacutetica eacute

a que mais aproxima a entropia da cadeia de entrada

4 Notas e Referecircncias

[1] Para uma prova dessa afirmativa veja SALOMON Da-

vid Data Compression The Complete Reference 2 ed

Nova Iorque Springer 2000 ISBN 0-387-95045-1 ou

qualquer livro de Caacutelculo diferencial

[2] A probabilidade cumulativa de ocorrecircncia de um carac-

tere eacute calculada ordenando-se os caracteres e somando a

probabilidade de ocorrecircncia 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 proba-

bilidade cumulativa do proacuteximo caractere na ordenaccedilatildeo

5 Bibliografia

bull (em inglecircs) SALOMON David Data Compres-

sion The Complete Reference 2 ed Nova Iorque

Springer 2000 ISBN 0-387-95045-1

6 Ver tambeacutembull Codificaccedilatildeo de Huffman

bull Compressatildeo sem perda de dados

7182019 Codificaccedilatildeo aritmeacutetica

httpslidepdfcomreaderfullcodificacao-aritmetica 44

4 7 FONTES CONTRIBUIDORES E LICENCcedilAS DE TEXTO E IMAGEM

7 Fontes contribuidores e licenccedilas de texto e imagem

71 Texto

bull Codificaccedilatildeo aritmeacutetica Fonte httpptwikipediaorgwikiCodificaC3A7C3A3o_aritmC3A9ticaoldid=37359573 Contri-

buidores Rnbastos Ziguratt Chobot YurikBot Salgueiro He7d3r Girino Thijsbot Daimore BotMultichill Joaosilvakle DohBot

Ariel CMK Addbot e Anoacutenimo 5

72 Imagens

bull FicheiroNuvola_apps_edu_mathematics-psvg Fonte httpuploadwikimediaorgwikipediacommonscc2Nuvola_apps_edu_

mathematics-psvg Licenccedila GPL Contribuidores Derivative of ImageNuvola apps edu mathematicspng created by self Artista original

David Vignoni (original icon) Flamurai (SVG convertion)

bull FicheiroWikitextsvg Fonte httpuploadwikimediaorgwikipediacommonscceWikitextsvg Licenccedila Public domain Contribuido-

res Obra do proacuteprio Artista original Anomie

73 Licenccedila

bull Creative Commons Attribution-Share Alike 30