Codare aritmetică

Codarea aritmetică  este unul dintre algoritmii de compresie a entropiei .

Spre deosebire de algoritmul Huffman , acesta nu are o corespondență constantă a caracterelor de intrare cu grupuri de biți din fluxul de ieșire. Acest lucru oferă algoritmului mai multă flexibilitate în reprezentarea frecvențelor caracterelor fracționale.

De regulă, depășește algoritmul Huffman în ceea ce privește eficiența compresiei, vă permite să comprimați datele cu entropie mai mică de 1 bit per caracter codificat, dar unele versiuni au restricții de brevet de la IBM . [unu]

Caracteristici

Oferă un raport de compresie aproape optim în ceea ce privește estimarea entropiei de codificare Shannon. Este necesar aproape un bit pentru fiecare simbol, unde  este entropia informațională a sursei.

Spre deosebire de algoritmul Huffman , metoda de codificare aritmetică arată o eficiență ridicată pentru intervalele fracționale neuniforme ale distribuției de probabilitate a simbolurilor codificate. Totuși, în cazul unei distribuții echiprobabile a caracterelor, de exemplu, pentru un șir de biți 010101…0101 de lungime s , metoda de codificare aritmetică se apropie de codul prefix Huffman și poate chiar să dureze un pic mai mult. [2]

Cum funcționează

Să existe un anumit alfabet, precum și date despre frecvența de utilizare a caracterelor (opțional). Apoi luați în considerare segmentul de linie de la 0 la 1 pe linia de coordonate.

Să numim acest segment funcțional. Să aranjam punctele pe el în așa fel încât lungimile segmentelor formate să fie egale cu frecvența utilizării simbolului și fiecărui astfel de segment să corespundă unui simbol.

Acum să luăm un simbol din flux și să găsim un segment pentru acesta printre cele nou formate, acum segmentul pentru acest simbol a devenit funcțional. Să-l împărțim în același mod în care împărțim segmentul de la 0 la 1. Să efectuăm această operație pentru un anumit număr de caractere consecutive. Apoi alegem orice număr din segmentul de lucru. Biții acestui număr, împreună cu lungimea înregistrării sale de biți, sunt rezultatul codificării aritmetice a simbolurilor de flux utilizate.

Un exemplu despre cum funcționează metoda de codificare aritmetică

Model probabilistic

Folosind metoda de codificare aritmetică, se poate obține o reprezentare aproape optimă pentru un anumit set de simboluri și probabilitățile acestora (conform teoriei de codificare a entropiei sursei a lui Shannon, reprezentarea optimă va tinde să fie -log 2 P biți pe simbol a cărui probabilitate este P ). Algoritmii de comprimare a datelor care utilizează metoda de codificare aritmetică în activitatea lor, înainte de codificarea directă, formează un model de date de intrare bazat pe caracteristici cantitative sau statistice, precum și orice informație suplimentară găsită în secvența codificată de repetiții sau modele - orice informație suplimentară care permite tu pentru a clarifica probabilitatea apariției simbolului P în procesul de codificare . Evident, cu cât probabilitatea simbolului este determinată sau prezisă mai precis, cu atât eficiența compresiei este mai mare.

Luați în considerare cel mai simplu caz al unui model static pentru codificarea informațiilor care provin de la un sistem de procesare a semnalului. Tipurile de semnal și probabilitățile lor corespunzătoare sunt distribuite după cum urmează:

• 60% șansă de o valoare a semnalului neutru sau NEUTRAL.
• 20% șansă de o valoare a semnalului pozitivă sau POZITIV.
• 10% șansă de o valoare a semnalului negativă sau NEGATIVE.
• 10% șansă de un semn de sfârșit de secvență sau END-OF-DATA.

Apariția ultimului simbol pentru decodor înseamnă că întreaga secvență a fost decodificată cu succes (ca o abordare alternativă, dar nu neapărat cu mai mult succes, poate fi utilizat un algoritm de bloc cu lungime fixă) .

De asemenea, trebuie remarcat faptul că orice set de simboluri poate fi considerat ca fiind alfabetul modelului probabilistic al metodei, pe baza caracteristicilor problemei care se rezolvă. Mai multe abordări euristice , folosind schema de bază a metodei de codificare aritmetică, aplică modele dinamice sau adaptive . Ideea acestor metode este de a rafina probabilitatea caracterului codificat ținând cont de probabilitatea contextului anterior sau viitor (adică probabilitatea de apariție a caracterului codificat după un anumit număr k-lea de caractere la stânga sau la dreapta, unde k este ordinea contextului).

Codificarea mesajelor

Să luăm următoarea secvență ca exemplu:

NEUTRAL NEGATIV sfârșitul datelor

Mai întâi, să împărțim segmentul de la 0 la 1 în funcție de frecvențele semnalelor. Vom sparge segmentul în ordinea indicată mai sus: NEUTR - de la 0 la 0,6; NEGATIV - de la 0,6 la 0,8; SFÂRȘITUL DATELOR - de la 0,8 la 1.

Acum să începem codificarea de la primul caracter. Primul caracter - NEUTR corespunde unui segment de la 0 la 0,6. Să împărțim acest segment în același mod ca și segmentul de la 0 la 1.

Să codificăm al doilea caracter - NEGATIV. Pe segmentul de la 0 la 0,6, corespunde segmentului de la 0,48 la 0,54. Să împărțim acest segment în același mod ca și segmentul de la 0 la 1.

Să codificăm al treilea caracter - END-OF-DATA. Pe segmentul de la 0,48 la 0,54, corespunde segmentului de la 0,534 la 0,54.

Deoarece acesta a fost ultimul caracter, codificarea este completă. Mesajul codificat este un segment de la 0,534 la 0,54 sau orice număr din acesta, de exemplu, 0,538.

Decodarea mesajelor

Să presupunem că trebuie să decodificăm un mesaj folosind metoda de codificare aritmetică conform modelului descris mai sus. Mesajul codificat este reprezentat de valoarea fracțională 0,538 (pentru simplitate, se folosește reprezentarea zecimală a fracției în locul bazei binare). Se presupune că mesajul codificat conține exact atâtea caractere în numărul considerat necesar pentru a restabili în mod unic datele originale.

Starea inițială a procesului de decodare coincide cu procesul de codificare și se ia în considerare intervalul [0,1). Pe baza modelului probabilistic cunoscut, valoarea fracțională 0,538 se încadrează în intervalul [0, 0,6). Acest lucru vă permite să determinați primul caracter care a fost ales de codificator, astfel încât valoarea acestuia este scoasă ca prim caracter al mesajului decodat.

Note

1. ↑ Istoria dezvoltării teoriei compresiei informației Copie de arhivă din 28 decembrie 2010 la Wayback Machine / Compression.ru, Sarmin Alexey, 10 martie 2011
2. ↑ Dr. Buletinul informativ Dobb's Data Compression Arhivat 11 decembrie 2017 la Wayback Machine , 13 august 2001

Link -uri

• (13 august 2001) Buletinul informativ al lui Dobb pentru compresia datelor