Introducere

IntroducereCodarea aritmetica elimina necesitatea codarii fiecarui simbol al alfabetului surseiIn timpul codarii algoritmul genereaza un cod pentru intreg mesajul de intrare, lucru ce este facut in mod secvential, simbol cu simbolIn comparatie cu alte campuri din sfera codarii, codarea aritmetica este foarte tanara (1970), matura si completa si eficienta in compresia fara pierdere de informatie

Codarea aritmetica lucreaza in timp liniar ci o folosire constanta a memorieiFolosirea reprezentarii binare pe un numar fix de simboluri este suficienta pentru toate calculeleRaportul de compresie obtinut este mai bun decat in cazul folosirii codului Huffman si exista implementari hardware ale algoritmului de compresie, cum sunt cele din protocoalele G3 si G4 din Fax. 1IntroducereLa memorarea intervalului se pot memora capetele intervalului sau la fel de bine numai mijlocul acestuiaDin cauza ca mesajele foarte mari vor conduce la intervale din ce in ce mai mici, apare problema reprezentarii intervalelor foarte mici pentru a asigura unicitatea codarii, si deci o decodare corectaProblema este rezolvata prin folosirea scalariiSalvarea codului aritmetic (in reprezentare zecimala sau binara) intr-un fisier presupune specificarea sfarsitului reprezentariiAcest lucru se poate face intr-un fisier prin scrierea unui antet cu lungimea inregistrarii, pentru a putea fi refacuta la decodareIn cazul transmisiilor continue, cum este cazul fax-ului, se folosesc simboluri speciale si atunci in secventa de codat trebuie adaugat un simbol marcator sfarsit de secventa El trebuie sa aiba probabilitatea minimala2Aspecte esentialeIn codarea aritmetica o sursa este reprezentata de un interval intre 0 si 1 pe axa numerelor realeFiecare simbol al ansamblului micsoreaza acest intervalPe masura ce intervalul devine mai mic, numarul de biti necesar pentru specificare este mai mareCodarea aritmetica presupune in mod explicit un model probabilistic al sursei Este o schema bazata pe cuvinte de cod ce utilizeaza probabilitatile mesajelor sursei pentru a ingusta intervalul utilizat in reprezentarea ansambluluiUn mesaj cu probabilitate mare ingusteaza intervalul mai putin decat un mesaj cu probabilitate mica, astfel incat probabilitatile mari contribuie mai putin la cresterea lungimii cuvintelor de codMetoda incepe cu o lista neordonata a mesajelor sursei si a probabilitatilor asociateNumarul liniei este partitionat in subintervale folosind probabilitatile cumulate

3Algoritmul de bazaSe considera intervalul curent [L,H) initializat cu [0,1)

Pentru fiecare simbol, ai, din fisier, se parcurg doi pasi:Se imparte intervalul curent in subintervale, cate unul pentru fiecare simbol din alfabetul sursei; marimea subintervalului unui simbol din alfabet este proportional cu probabilitatea estimata, considerata in cadrul modelului

Se selecteaza subintervalul corespunzator simbolului care apare in fisierul de comprimat, si se considera ca fiind noul interval curent

Se scriu in fisierul comprimat suficiente simbolui binare pentru a putea identifica (reconstitui) intervalul curent final din multimea tuturor intervalelor finale, posibil a fi considerate

4Algoritmul de bazaDiviziunea intervalului curent este bazata pe probabilitatea simbolului de intrare ai, care apare in fisierul de comprimat:5

DecodareaPentru a decoda o secventa, trebuie aplicate operatiile efectuate la codare insa in ordine inversa

Se cunosc:modelul sursei, prin alfabet si probabilitati;secventa/mesajul codat sub forma de interval sau sub forma mediei intervalului, V;numarul de simboluri primare din secventa codata

6Compresia aritmetica cu scalareProblema implemenatrii codarii aritmetice este data de precizia finita a operatiilor cu numere realeSolutia consta in inlocuirea intervalului [0,1) al numerelor reale cu intervalul numerelor intregi, unde N este un numar intreg, cu semnificatie de numarul de cifre binare al registrelor numericeIdeea consta in selectarea prefixului comun la capetelor intervalelor, L si H, si apoi completarea capatului din stanga, L, cu simboluri 0 si al capatului dreapta, H, cu 1Nu este nevoie de un model al sursei, ci numai de alfabetul surseiFrecventele simbolurile sunt construite dinamic, deci se poate considera apartenenta metodei la clasa metodelor dinamice(adaptive)

7Compresia aritmetica cu scalareIntervalelele asociate simbolurilor alfabetului se calculeaza cu ajutorul frecventelor simbolurilor, in mod dinamic; fiecare frecventa a unui caracter este initializata cu 1 si este incrementata de fiecare data cand apare simbolul in mesajul de comprimatFie frecventa simbolului in alfabetFrecventa cumulata a simbolurilor este

unde Ns este numarul de simboluri din alfabetul surseiRezulta ca este frecventa cumulata a tuturor simbolurilorDe retinut ca este lungimea prefixului intrarii scanateSimbolurile sunt mentinute in ordinea descrescatoare a frecventelor lor8

Compresia aritmetica cu scalareCand un simbol este citit din sursa text, intervalul curent [L,H) este ajustat la

La fiecare ajustare a intervalului, se verifica conditia

9

Compresia aritmetica cu scalareIn caz contrar, intervalul este expandat cu relatia

Efectuarea acestei transformari este memorata prin incrementarea unui numarator (waiting_counter)Operatia se repata atat timp cat intervalul este prea scurtDupa salvarea mesajului comprimat, se trimite contunutul numaratoruluiDupa trimiterea ultimului bit al numaratorului, se transmite bitul invers de un numar de ori dat de continutul numaratorului de asteptare

10

AlgoritmCodare_simbol(ai) L=L+(H-L+1)*cum_freq(i)/cum_freq(0); H=L+(H-L+1)*cum_freq(i-1)/cum_freq(0)-1; WC =0; // waiting_counter REPEAT IF (L and H au bit comun in stanga) THEN code = code + bit_comun; L=L*2; H=2*H+1; ELSE IF (H-L)= cum_freq(0).END.Procedura de codare se incheie cu scrierea bitilor de asteptare (daca sunt) conform codului :Write(bit,fout); WHILE (waiting_counter>0) DO IF bit >0, THEN Write 1 in fout; Write 0 in fout; Waiting_counter = --1; End while;END.

11DecompresiaDecodarea este exact inversul procesului de codareSe utilizeaza o fereastra alunecatoare pe fisierul comprimat, de lungime NMai intai, se initializeaza fereastra cu primele N simboluri binareSe calculeaza valoarea ei zecimala prin conversia succesiunii binare, din baza 2 in baza 10Intervalul curent este initializat ci l=0 si Simbolul este produs ca urmare a evaluarii expresiei

unde l si h sunt ajustate cu aceleasi relatii din timpul procesului de codare si i cea mai mica valoare intreaga12

DecompresiaDaca reprezentarile binare ale capetelor intervalului au un prefix comun de lungime p, ele sunt deplasate cu p pozitii spre stangaPozitiile ramase libere se completeaza cu zerouri pentru l si cu 1 pentru hFereastra de citire este deplasata cu (p) pozitii inspre dreapta si variabila value este ajustata corespunzatorSe actualizeaza tabelele freq si cum_freq astfel incat simbolurile sa fie mentinute in ordine descrescatoare a frecventelor, exact ca la procesul de codareOperatiile se repeta pana cand se produce simbolul END

13AlgoritmDecodare(fin) cum_freq = ((value-l+1)*cum_freq(0)-1) / (h-l+1); Define i=; While cum_freq(i)>cum_freq DO i =i++; l = l + (h-l+1)*cum_freq(i)/cum_freq(0); h = l + (h-l+1)*cum_freq(i-1)/cum_freq(0) - 1; REPEAT IF common_left_bits(l,h), THEN l = 2*l; h = 2*h +1; Read_bit(fin); value = 2*value + b; ELSE IF (h-l) < cum_freq(0), THEN l = 2*(l-2N-2) H = 2*(h-2N-2) + 1 Read_bit(fin); value = 2*(value 2N-2) + b; UNTIL no common_left_bits(l,h) and (H-L) >= cum_freq(0);END.

14ConcluziiCodarea aritmetica are ca rezultat un sir de simboluri care permite obtinerea unor rate de compresie mult mai buneDe obicei este mai performanta decat codarea Huffman din acest punct de vedereCodarea aritmetica a unui sir de simboluri de lungime l, S={s1, s2,, sl} este obtinuta prin l impartiri iterative in sub-intervale, partitionari facute pe baza proprietatilor statistice ale setului de simboluri considerat, adica distributia de probabilitate si probabilitatile conditionateLungimea fiecarui sub-interval este egala cu probabilitatea sirului de simboluri care ii corespundeCuvantul de cod aritmetic pentru un sir de simboluri S este format din primii W biti din reprezentarea binara a valorii de mijloc a sub-intervalului corespunzator, I(S), unde W=[log21/|I(S)|]+1, iar |I(S)| este lungimea intervalului I(S)15