Rezumat:

Compresia Aritmetica

Cum functioneaza

Abia in ultimii 10 ani, un candidat respectabil pentru a inlocui compresia Huffman, a fost demonstrat cu succes: compresia aritmetica.

Compresia aritmetica depaseste ideea de a inlocui un simbol de intrare cu un cod specific. Aceasta ia un flux de simboluri de intrare si il inlocuieste cu un singur numar in virgula mobila. Cu cat este mai lung (si mai complex) mesajul cu atat mai multi biti sunt necesari pentru numarul de iesire. Recent s-au gasit metode de implementare pe calculator, cu registrii de marime fixa.

Iesirea    compresiei aritmetice este un numar mai mic ca 1 si mai mare sau egal ca 0. Acest numar poate fi in mod unic decomprimat, pentru a crea fluxul exact, care a intrat in constructia lui. Pentru a fi construit numarul de iesire, simbolurile codate trebuie sa aiba probabilitati.

De exemplu

Pentru a coda mesajul "BILL GATES", distributia probabilitatilor este urmatoarea:

Odata stiute probabilitatile caracterelor, fiecarui simbol individual ii este asociat un interval intre 0 si 1. Nu are importanta carui caracter ii este asociat care interval, atata timp cat este facut in acelasi mod la comprimare cat si la decomprimare.

Fiecarui caracter ii este atasata portiunea din intervalul 0-1, care corespunde probabilitatii sale de aparitie.(Aceste portiuni sunt intervale deschise la dreapta! )

Cea mai semnificanta portiune din mesajul comprimarii aritmetice ii apartine primului simbol. Cand comprimam mesajul "BILL GATES", primul simbol este "B". Pentru ca primul caracter sa fie decomprimat corect, mesajul final comprimat, trebuie sa fie un numar mai mare sau egal cu 0.20 si mai mic ca 0.30. Dupa ce primul caracter este decodat, limita inferioara pentru acest interval este 0.20, si limita superioara este 0.30.

Dupa ce primul caracter este decodat, stim ca intervalul nostru pentru numarul de iesire este intre numarul inferior si cel superior.

Ce se intampla in timpul procesului de decodare ramas, este ca fiecare nou simbol de decodat, va restrictiona posibilul interval pentru numarul de iesire.

Urmatorul caracter de codat, "I", are intervalul intre 0.50 si 0.60. Daca acesta ar fi fost primul numar in mesajul nostru, am fi setat limita inferioara si cea superioara, la sceste valori. Dar "I" este al doilea caracter. Deci, spunem ca "I" are intervalul corespunzator 0.50 - 0.60 in noul subinterval 0.2 - 0.3.

Aceasta inseamna ca noul numar codat va trebui sa fie intre 50 % si 60 % din intervalul curent. Aplicand aceasta logica, numarul nostru va fi restrictionat in intervalul 0.25 - 0.26.

Algoritm pentru mesaje de orice lungime:

Seteaza inferior 0.0

Seteaza superior 1.0

While (mai sunt simboluri de intrare) do

Citeste simbol

Cod_interval = superior - inferior

Superior inferior + interval*superior_interval(simbol)

Inferior inferior + interval*inferior_interval(simbol)

End of While

output Inferior

Dupa acest proces, mesajul nostru va arata astfel:

Astfel, valoarea finala, 0.2572167752, va comprima in mod unic mesajul "BILL GATES". Dat fiind procesul de compresie, este relativ usor de scris procesul de decompresie. Gasim primul simbol din mesaj, cautand ce simbol are codul spatiu in care intra mesajul nostru codat. Din moment ce numarul 0.2572167752 intra in intervalul 0.2 - 0.3, stim ca primul caracter trebuie sa fie "B". Acum trebuie sa-l eliminam pe "B" din numarul codat. Din moment ce stim limitele inferioara si superioara ale lui "B", il putem elimina, inversand procesul care il introduce. Mai intai sustragem valoarea inferioara a lui "B" din numar, giving 0.0572167752. Apoi impartim prin intervalul lui "B", care este 0.1. Aceasta ne da valoarea de 0.572167752. Acum putem calcula unde se incadreaza, care va fi intervalul literei urmatoare, "I".

Algoritm pentru decompresie:

Citeste numar comprimat

Do

Gaseste simbol

Output simbol

Interval = valoare inferioara simbol - valoare superioara simbol

Sustrage valoare inferioara simbol din numarul comprimat

Divide numar codat cu interval

Until (nu mai sunt simboluri)

Pentru a afla daca nu mai sunt simboluri, se poate comprima simbolul special EOF, sau retinand lungimea fluxului.

Algoritmul de decodare pentru "BILL GATES", va procesa astfel:

Consideratii practice

Procesul de codare si decodare a unui flux de simboluri folosind compresia aritmetica nu este prea complicat. Dar, la o prima privire, pare impracticabil. Majoritatea calculatoarelor suporta numere in virgula mobila de pana la 80 de biti. Inseamna aceasta sa repornim de fiecare data cand comprimam 10-15 simboluri ? Ne trebuie un procesor pentru numere in virgula mobila ? Poate rula programul pe sisteme cu diferite tipuri de numere in virgula mobila ?

Compresia aritmetica poate fi realizata folosind numere intregi pe 16 sau 32 de biti. In locul numerelor cu virgula mobila folosim o schema de transmitere incrementala, unde intregi de marime fixa primesc biti in capatul inferior si se deplaseaza in afara prin capatul superior, formand un singur numar care este limitat doar de capacitatea de inmagazinare a sistemului.

Cand    incepe , inferior este 0 si superior este 1. Prima simplificare este sa schimbam 1.0 cu 0.999 . ., adica 111 . . In binar; Implementarea este pe 16 biti, deci Sup este 0xFFFF si Inf 0.

Sa revedem exemplu pe un registru zecimal de 5 cifre. Inf = 0, Sup = 99999;

Aplicam tehnica la fiecare calculare de margine superioara a intervalului (decrementam cu 1). Datorita naturii algoritmului limitele Inf si Sup vor tinde una spre alta.

In cazul in care ajungem la o situatie cum ar fi : Sup = 70000 si Inf = 69999, intervalul devine prea mic. Pentru a nu ajunge in situatii de blocare trebuie sa prevenim acest lucru. Algoritmul initial deplasa la iesire cifra cea mai semnificativa a limitelor daca erau egale. Acum, daca cifrele cele mai semnificative sunt adiacente trebuie rulat un al doilea test. Vedem daca a doua cea mai semnificativa cifra a Sup este 0 si a doua cea mai semnificativa cifra a Inf este 9. Daca este asa, inseamna ca trebuie sa actionam.

In loc sa deplasam cifra cea mai semnificativa, stergem a doua cifra din Sup si Inf si deplasam la stanga restul de cifre si incrementam contorul de biti underflow.

Dupa fiecare recalculare, daca cifrele cele mai semnificative ale Sup si Inf nu coincid, verificam din nou. Cand acestea corespund, deplasam valoarea spre iesire urmata de toate cifrele underflow sterse pana acum. Toate cifrele sunt 0 sau 9, in implementare am folosit 0.

Restrictii

Implementare pe 16 biti, marime maxima fisier 65535 octeti.