Codificare aritmetică

De codificare aritmetică este o entropie de codificare utilizată în compresie a datelor , fără pierderi. Oferă o compresie mai bună decât codarea Huffman , cu excepția cazului în care toate greutățile pentru frunzele / nodurile / rădăcinile arborelui Huffman sunt puteri de 2 , caz în care cele două metode sunt echivalente.

În ciuda acestui avantaj, acesta a fost greu utilizat deoarece implementarea sa a fost prea complexă; metodele de implementare au fost în cele din urmă găsite pe măsură ce compresia dicționarului ( mult mai bună decât Huffman sau codarea aritmetică ) a început să câștige popularitate.

Rețineți, totuși, utilizarea sa la compresia imaginilor la standardele JPEG 2000 și JBIG2 .

Principiu

Codarea aritmetică (ca Huffman codificarea ) este un cod de lungime variabilă, adică că un simbol de mărime fixă (în biți ) va fi codificat de un număr variabil de biți, de preferință mai mică sau egală cu dimensiunea sa inițială. Prin urmare, densitatea simbolurilor nu este modificată, ci codarea lor pentru a reduce spațiul pe care îl ocupă.

Ceea ce diferențiază codificarea aritmetică de alte codificări sursă este că codifică mesajul în bucăți (teoretic poate codifica un mesaj întreg de orice dimensiune, dar în practică putem codifica doar bucăți de aproximativ cincisprezece simboluri în medie) și reprezentăm fiecare dintre aceste bucăți cu un număr (virgulă mobilă) unde Huffman codifică fiecare simbol printr-un cod specific. Problema rezultată pentru codificarea Huffman este că un caracter cu o probabilitate foarte mare de apariție va fi codat pe cel puțin un bit. De exemplu, dacă se urmărește codificarea unui caracter reprezentat la 90%, dimensiunea optimă a codului de caractere va fi de 0,15 biți, în timp ce Huffman va codifica acest simbol pe cel puțin 1 bit, adică de 6 ori prea mult. Codul aritmetic îl umple datorită unui algoritm apropiat de codificarea intervalului . $nu$

Proprietăți

Comprimare

Compresia necesită un tabel statistic (cât mai aproape posibil de statisticile observabile în fișierul care conține simbolurile care trebuie comprimate) care include: $Fn$ $nu$

Toate simbolurile care se găsesc în mesaj să fie comprimate. $s$
Probabilitățile de a întâlni simbolul din mesaj. $p$ $s$
Intervalul împărțit în intervale proporționale cu probabilitatea ca simbolul apare în mesaj ( de exemplu: în cazul în care există o șansă de 50% care apare, intervalul său va fi de lungime 0,5). $[0; 1 [$ $p$ $s$ $s$

Scopul va fi acum de a aplica o serie de operații la un anumit interval (de obicei se alege intervalul ) pentru a-și modifica limitele de fiecare dată când se adaugă un simbol și pentru a limita cât mai mult numărul de posibilități. . $[0; 1 [$ $s$

Iată operațiile de efectuat la adăugarea unui simbol : $s$

Se înregistrează diferența dintre limita superioară (BS) și limita inferioară (BI). Această valoare va fi notată BB.
BS ia următoarea valoare: BI + BB * (BS_du_symbole_s)
BI ia următoarea valoare: BI + BB * (BI_du_symbole_s)

După adăugarea primului simbol, intervalul va avea aceleași limite ca intervalul simbolului adăugat, apoi fiecare adăugare își va converti limitele. Când a fost stocat un număr suficient de simboluri, algoritmul va returna un număr plutitor aflat în acest interval. Acest număr reprezintă întregul fișier de intrare.

Observăm că o serie de simboluri cu o mare probabilitate de apariție va face ca intervalul să convergă mult mai încet decât dacă avem de-a face cu o serie de simboluri care par puțin. Un număr dintr-un interval care converge lent va fi, prin urmare, codificat cu mai puține cifre semnificative decât un număr într-un interval extrem de precis, de unde și câștigul.

De asemenea, este necesar să ne gândim la adăugarea unui simbol care va fi folosit doar pentru a indica sfârșitul fișierului, altfel algoritmul de decompresie riscă să ruleze la nesfârșit, producând fișierul urmat de o secvență pseudo-aleatorie de biți.

Decompresie

Pentru a decomprima un fișier (reprezentat printr-un număr ), trebuie să utilizați același tabel care a fost utilizat pentru compresie, apoi efectuați pașii următori până la sfârșitul fișierului: $nu$

Observați în interval care simbol este numărul, adăugați la fișierul decomprimat și păstrați în memorie probabilitatea ca și BI-ul său. $s$ $s$ $p$ $s$
$nu$ ia valoare . $n = (n-BI) / p$

Odată ce marcajul final este atins, algoritmul se oprește și fișierul este considerat necomprimat.

Exemplu

Comprimare

Se va aplica aici algoritmul de compresie aritmetică pe textul „WIKI”. Prin urmare, obținem următorul tabel:

Scrisoare	Probabilitate	Interval
W	1/4	[0; 0,25 [
Eu	2/4	[0,25; 0,75 [
K	1/4	[0,75; 1 [

Prin convenție, algoritmul este inițializat cu o limită inferioară egală cu 0 și o limită superioară egală cu 1. Rămâne doar să aplicăm seria de operații văzute anterior la fiecare adăugare a unui caracter.

Caracter adăugat	Limita inferioară	Limită superioară
	0	1
W	0	0,25
Eu	0,0625	0,1875
K	0,15625	0,1875
Eu	0,1640625	0,1796875

Deci, orice număr din gamă va fi o versiune comprimată a șirului „WIKI”. Numărul 0,17 fiind inclus în acest interval, poate fi potrivit pentru reprezentarea „WIKI” comprimat. În schimb, 0,16 sau 0,1796875 nefiind în interval, nu se vor potrivi și vor provoca erori în timpul decodării. $[0,1640625; 0,1796875 [$

Decompresie

Să presupunem că primim mesajul comprimat 0.17, așa ar fi decodat:

(În mod evident, folosim același tabel ca înainte pentru a cunoaște intervalele fiecărei litere și probabilitățile lor de apariție).

Cod comprimat	Interval	Scrisoare corespondentă	Text recuperat
0,17	[0; 0,25 [	W	W
0,68	[0,25; 0,75 [	Eu	WI
0,86	[0,75; 1 [	K	WIK
0,44	[0,25; 0,75 [	Eu	WIKI

Prin urmare, găsim șirul de caractere corect comprimat anterior.

Puncte slabe

Această metodă de compresie întâmpină două defecte principale care sunt acum cunoscute și corectate:

Primul este faptul că se folosește un tabel fix de statistici, cauzând aceleași probleme ca și pentru codarea Huffman, adică comprimarea unui fișier cu statistici atipice (simbolurile care trebuie să fie puțin prezente se găsesc cu o probabilitate mare de apariție) să fie mai mare după compresie decât înainte. Cea mai eficientă soluție este, prin urmare, și aici, să se utilizeze un tabel adaptiv ale cărui frecvențe încep toate egale atunci, la fiecare întâlnire a unui simbol, ale cărui statistici sunt actualizate și intervalele adaptate.

A doua problemă majoră este că, în termeni de calcul, numerele virgulelor sunt mai complexe de gestionat, dar pot produce erori de rotunjire (datorită numărului finit de cifre după punctul zecimal pe care îl poate suporta un computer) care se poate dovedi fatală. Pentru a depăși această problemă, este posibil să se inițializeze intervalul de pornire cu o limită inferioară egală cu 00000 ... și o limită superioară egală cu 99999 ... Calculele sunt aceleași ca și pentru numerele zecimale, dar pe numere întregi. O nouă problemă poate apărea în continuare atunci când ambele terminale devin prea apropiate, de exemplu . De fapt, acest interval nu conține nicio valoare întreagă și nici o adăugare de simboluri noi nu îl va modifica. Când ajungem la acest punct, trebuie fie să oprim algoritmul înainte, fie, dacă primele cifre au o diferență între ele doar 1 și următoarea cifră valorează 9 pentru limita inferioară și 0 pentru cea superioară., Ștergeți-le mai întâi cifre și deplasați următoarele cifre la stânga. Ultimele cifre vor fi apoi egale cu 0 pentru limita inferioară și 9 pentru limita superioară, făcând posibilă găsirea unui număr nou în acest interval. $[6999 ...; 7000 ... [$

Articole similare

Bibliografie

(ro) David MacKay, Teoria informației, inferența și algoritmii de învățare , Cambridge University Press ,2003( ISBN 0-521-64298-1 ) [ detaliu ediții ]

Referințe

Mark Nelson ( trad. Hervé Soulard), Compresia datelor: texte, imagini și sunete , Dunod ,1993, 421 p. ( ISBN 2-10-001681-4 )
„ COMPRESIE - compresie aritmetică ” (accesat la 17 ianuarie 2015 )
„ Compresia datelor - Codificare aritmetică ” (accesat la 17 ianuarie 2015 )
„ Capitolul 1: Codificare aritmetică ” (accesat la 18 ianuarie 2015 )