Codificarea intervalului - Range coding
Codificarea intervalului (sau codarea intervalului ) este o metodă de codificare a entropiei definită de G. Nigel N. Martin într-o lucrare din 1979, care a redescoperit efectiv codul aritmetic FIFO introdus pentru prima dată de Richard Clark Pasco în 1976. Având în vedere un flux de simboluri și probabilitățile lor, un codor de gamă produce un flux de biți eficient din punct de vedere spațial pentru a reprezenta aceste simboluri și, având în vedere fluxul și probabilitățile, un decodor de gamă inversează procesul.
Codificarea intervalului este foarte asemănătoare cu codificarea aritmetică , cu excepția faptului că codificarea se face cu cifre în orice bază, în loc de biți, și astfel este mai rapidă atunci când se utilizează baze mai mari (de exemplu, un octet ) cu un cost mic în eficiența compresiei. După expirarea primului brevet de codare aritmetică (1978), codificarea de gamă părea să fie în mod clar lipsită de sarcini de brevet. Acest lucru a determinat în special interesul pentru tehnică în comunitatea open source . De atunci, brevetele pentru diverse tehnici aritmetice de codificare cunoscute au expirat.
Cum funcționează codarea intervalului
Codificarea intervalului codifică conceptual toate simbolurile mesajului într-un singur număr, spre deosebire de codificarea Huffman care atribuie fiecărui simbol un tipar de biți și concatenează toate tiparele de biți împreună. Astfel, codificarea intervalului poate obține rapoarte de compresie mai mari decât limita inferioară de un bit pe simbol pe codul Huffman și nu suferă ineficiențele pe care Huffman le face atunci când se ocupă de probabilități care nu sunt o putere exactă de două .
Conceptul central din spatele codificării intervalului este următorul: având în vedere un interval suficient de mare de numere întregi și o estimare a probabilității pentru simboluri, intervalul inițial poate fi ușor împărțit în subgrupuri ale căror dimensiuni sunt proporționale cu probabilitatea simbolului pe care îl reprezintă. Fiecare simbol al mesajului poate fi apoi codificat la rândul său, prin reducerea intervalului curent la doar acel sub-interval care corespunde următorului simbol care urmează să fie codificat. Decodorul trebuie să aibă aceeași estimare a probabilității codificatorului utilizat, care poate fi trimis în avans, derivat din datele deja transferate sau să facă parte din compresor și decompresor.
Atunci când toate simbolurile au fost codificate, simpla identificare a subgrupului este suficientă pentru a comunica întregul mesaj (presupunând desigur că decodificatorul este cumva notificat atunci când a extras întregul mesaj). Un singur număr întreg este de fapt suficient pentru a identifica subgama și poate să nu fie chiar necesar să transmitem întregul număr întreg; dacă există o secvență de cifre astfel încât fiecare număr întreg care începe cu acel prefix se încadrează în sub-interval, atunci prefixul este tot ceea ce este necesar pentru a identifica sub-intervalul și, astfel, pentru a transmite mesajul.
Exemplu
Să presupunem că dorim să codificăm mesajul „AABA <EOM>”, unde <EOM> este simbolul de sfârșit de mesaj. Pentru acest exemplu, se presupune că decodorul știe că intenționăm să codificăm exact cinci simboluri în sistemul numeric de bază 10 (permițând 10 5 combinații diferite de simboluri cu intervalul [0, 100000)) folosind distribuția de probabilitate {A:. 60; B: .20; <EOM>: .20}. Codificatorul descompune domeniul [0, 100000) în trei subintervaluri:
A: [ 0, 60000) B: [ 60000, 80000) <EOM>: [ 80000, 100000)
Deoarece primul nostru simbol este un A, acesta reduce intervalul nostru inițial până la [0, 60000). A doua alegere a simbolului ne lasă trei subgrupuri din acest interval. Le arătăm urmând „A” deja codificat:
AA: [ 0, 36000) AB: [ 36000, 48000) A<EOM>: [ 48000, 60000)
Cu două simboluri codificate, gama noastră este acum [0, 36000), iar al treilea nostru simbol duce la următoarele opțiuni:
AAA: [ 0, 21600) AAB: [ 21600, 28800) AA<EOM>: [ 28800, 36000)
De data aceasta este a doua dintre cele trei opțiuni care reprezintă mesajul pe care dorim să îl codificăm, iar gama noastră devine [21600, 28800]. Poate arăta mai greu să ne determinăm subintervalele în acest caz, dar nu este de fapt: putem doar să scădem limita inferioară din limita superioară pentru a determina că există 7200 de numere în intervalul nostru; că primele 4320 dintre ele reprezintă 0,60 din total, următorul 1440 reprezintă următorul 0,20, iar restul de 1440 reprezintă restul de 0,20 din total. Adăugarea înapoi a limitei inferioare ne oferă gamele noastre:
AABA: [21600, 25920) AABB: [25920, 27360) AAB<EOM>: [27360, 28800)
În cele din urmă, cu gama noastră redusă la [21600, 25920), mai avem doar un simbol de codificat. Folosind aceeași tehnică ca înainte pentru împărțirea intervalului între limita inferioară și superioară, găsim că cele trei subintervaluri sunt:
AABAA: [21600, 24192) AABAB: [24192, 25056) AABA<EOM>: [25056, 25920)
Și din moment ce <EOM> este simbolul nostru final, gama noastră finală este [25056, 25920). Deoarece toate numerele întregi din cinci cifre începând cu „251” se încadrează în domeniul nostru final, este unul dintre prefixele din trei cifre pe care le-am putea transmite, care ar transmite fără ambiguitate mesajul nostru original. (Faptul că există de fapt opt astfel de prefixe în toate implică faptul că avem încă ineficiențe. Acestea au fost introduse prin utilizarea noastră a bazei 10 mai degrabă decât a bazei 2 ).
Problema centrală poate părea a fi selectarea unui interval inițial suficient de mare încât, indiferent de câte simboluri trebuie să codificăm, vom avea întotdeauna un interval de curent suficient de mare pentru a ne împărți în sub-intervale diferite de zero. În practică, totuși, aceasta nu este o problemă, deoarece, în loc să înceapă cu o gamă foarte mare și să o îngusteze treptat, codificatorul funcționează cu o gamă mai mică de numere la un moment dat. După ce a fost codificat un număr de cifre, cifrele din stânga nu se vor schimba. În exemplul după codificarea a doar trei simboluri, știam deja că rezultatul nostru final va începe cu „2”. Mai multe cifre sunt schimbate în dreapta, deoarece cifrele din stânga sunt trimise. Acest lucru este ilustrat în următorul cod:
int low = 0;
int range = 100000;
void Run()
{
Encode(0, 6, 10); // A
Encode(0, 6, 10); // A
Encode(6, 2, 10); // B
Encode(0, 6, 10); // A
Encode(8, 2, 10); // <EOM>
// emit final digits - see below
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
}
void EmitDigit()
{
Console.Write(low / 10000);
low = (low % 10000) * 10;
range *= 10;
}
void Encode(int start, int size, int total)
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
EmitDigit();
// readjust range - see reason for this below
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
}
Pentru a termina, este posibil să trebuiască să emitem câteva cifre în plus. Cifra de sus a loweste probabil prea mică, așa că trebuie să o incrementăm, dar trebuie să ne asigurăm că nu o incrementăm în trecut low+range. Deci, mai întâi trebuie să ne asigurăm că rangeeste suficient de mare.
// emit final digits
while (range < 10000)
EmitDigit();
low += 10000;
EmitDigit();
O problemă care poate apărea cu Encodefuncția de mai sus este că rangear putea deveni foarte mică, dar lowși low+rangesă aibă încă diferite cifre. Acest lucru ar putea duce la un interval de precizie insuficient pentru a distinge între toate simbolurile din alfabet. Când se întâmplă acest lucru, trebuie să fudgeți puțin, să scoatem primele două cifre, chiar dacă am putea fi opriți una, și să reglați intervalul pentru a ne oferi cât mai mult spațiu posibil. Decodorul va urma aceiași pași, așa că va ști când trebuie să facă acest lucru pentru a se menține sincronizat.
// this goes just before the end of Encode() above
if (range < 1000)
{
EmitDigit();
EmitDigit();
range = 100000 - low;
}
Baza 10 a fost utilizată în acest exemplu, dar o implementare reală ar folosi doar binare, cu gama completă a tipului de date întregi nativ. În loc de 10000și 1000ați folosi probabil constante hexazecimale precum 0x1000000și 0x10000. În loc să emiteți o cifră la un moment dat, ați emite un octet la un moment dat și ați utiliza o operație de schimbare a octetului în loc să multiplicați cu 10.
Decodarea folosește exact același algoritm cu adăugarea de a urmări codevaloarea curentă constând din cifrele citite de la compresor. În loc să emiteți cifra de sus a lowdvs., aruncați-o, dar, de asemenea, schimbați cifra de sus codeși schimbați o nouă cifră citită de la compresor. Folosiți AppendDigitmai jos în loc de EmitDigit.
int code = 0;
int low = 0;
int range = 1;
void InitializeDecoder()
{
AppendDigit(); // with this example code, only 1 of these is actually needed
AppendDigit();
AppendDigit();
AppendDigit();
AppendDigit();
}
void AppendDigit()
{
code = (code % 10000) * 10 + ReadNextDigit();
low = (low % 10000) * 10;
range *= 10;
}
void Decode(int start, int size, int total) // Decode is same as Encode with EmitDigit replaced by AppendDigit
{
// adjust the range based on the symbol interval
range /= total;
low += start * range;
range *= size;
// check if left-most digit is same throughout range
while (low / 10000 == (low + range) / 10000)
AppendDigit();
// readjust range - see reason for this below
if (range < 1000)
{
AppendDigit();
AppendDigit();
range = 100000 - low;
}
}
Pentru a determina ce intervale de probabilitate să se aplice, decodificatorul trebuie să se uite la valoarea curentă din codeintervalul [low, low + range) și să decidă ce simbol reprezintă acest lucru.
void Run()
{
int start = 0;
int size;
int total = 10;
InitializeDecoder(); // need to get range/total >0
while (start < 8) // stop when receive EOM
{
int v = GetValue(total); // code is in what symbol range?
switch (v) // convert value to symbol
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5: start=0; size=6; Console.Write("A"); break;
case 6:
case 7: start=6; size=2; Console.Write("B"); break;
default: start=8; size=2; Console.WriteLine("");
}
Decode(start, size, total);
}
}
int GetValue(int total)
{
return (code - low) / (range / total);
}
Pentru exemplul AABA <EOM> de mai sus, aceasta ar returna o valoare cuprinsă între 0 și 9. Valorile de la 0 la 5 ar reprezenta A, 6 și 7 ar reprezenta B și 8 și 9 ar reprezenta <EOM>.
Relația cu codificarea aritmetică
Codificarea aritmetică este aceeași cu codificarea intervalului, dar cu numerele întregi luate ca numărători ai fracțiilor . Aceste fracții au un numitor comun implicit, astfel încât toate fracțiile se încadrează în intervalul [0,1). În consecință, codul aritmetic rezultat este interpretat ca începând cu un „0” implicit. Deoarece acestea sunt doar interpretări diferite ale acelorași metode de codificare și întrucât aritmetica rezultată și codurile de gamă sunt identice, fiecare codificator aritmetic este codificatorul său de gamă corespunzător și invers. Cu alte cuvinte, codificarea aritmetică și codificarea intervalului sunt doar două moduri ușor diferite de a înțelege același lucru.
În practică, totuși, așa-numiții codificatori de gamă tind să fie implementați cam așa cum este descris în lucrarea lui Martin, în timp ce codificatorii aritmetici, în general, nu tind să fie numiți codificatori de gamă. O caracteristică adesea remarcată a unor astfel de codificatoare de gamă este tendința de a efectua renormalizarea unui octet la un moment dat, mai degrabă decât un bit pe rând (așa cum se întâmplă de obicei). Cu alte cuvinte, codificatoarele de gamă tind să folosească octeți ca cifre de codare, mai degrabă decât biți. Deși acest lucru reduce cantitatea de compresie care poate fi realizată cu o cantitate foarte mică, este mai rapid decât atunci când se efectuează renormalizarea pentru fiecare bit.
Vezi si
- Codificare aritmetică
- Sisteme numerice asimetrice
- Comprimarea datelor
- Codificare entropie
- Codificare Huffman
- Format de electrofiziologie cu mai multe scale
- Codificare Shannon – Fano
Referințe
- ^ a b G. Nigel N. Martin, Range encoding: Un algoritm pentru eliminarea redundanței dintr-un mesaj digitalizat , Video & Data Recording Conference, Southampton , Marea Britanie, 24-27 iulie, 1979.
- ^ "Algoritmi de codare sursă pentru compresie rapidă a datelor" Richard Clark Pasco, Stanford, CA 1976
- ^ " Pe cheltuielile generale ale codificatorilor de gamă ", Timothy B. Terriberry, Notă tehnică 2008
- ^ Brevet SUA 4.122.440 - (IBM) Depus la 4 martie 1977, acordat la 24 octombrie 1978 (expirat acum)
