Codificare aritmetică

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Codificarea aritmetică este o tehnică de compresie fără pierderi . În mod normal, în informatică datele sunt reprezentate ca un set fix de biți, de exemplu, caracterele sunt adesea reprezentate cu opt biți. Codificarea aritmetică presupunând că unele simboluri tind să apară mai frecvent decât altele atribuie coduri de lungime variabilă simbolurilor pentru a minimiza numărul total de biți care trebuie transmiși. Această strategie este utilizată și de alte sisteme de codificare, cum ar fi codarea Huffman , dar în timp ce codarea Huffman asociază o codificare specifică cu fiecare simbol unic, codificarea aritmetică asociază o singură codificare cu întregul mesaj sau blocurile acestuia.

Funcționarea sistemului de codare

Definiția modelului

Codificarea aritmetică produce compresie sub-optimă (conform teoriei compresiei datelor, valoarea optimă este −log 2 P biți pentru fiecare simbol cu ​​probabilitate P). Algoritmul de compresie începe prin definirea unui model al datelor, distribuția probabilistică a acestora, aceasta influențând predominant bunătatea compresiei.

De exemplu, un model static simplu ar putea defini:

  • 60% șanse de a avea un simbol NEUTRU
  • 20% șanse de a avea un simbol POZITIV
  • 10% șanse de a avea un simbol NEGATIV
  • 10% șanse de a avea un simbol END-OF-FILE (acest simbol este folosit de decodor pentru a spune că fluxul care urmează să fie decodificat este terminat)

Exemplul de model folosește doar patru simboluri și este un model didactic, dar cunoscând contextul pot fi dezvoltate modele mai sofisticate, de exemplu, dacă știi că trebuie să codezi un text în engleză știi că litera „u” este mult mai frecventă decât litera „Q” sau „q” și apoi probabilitățile pot fi atribuite corespunzător. Modelele pot fi, de asemenea, adaptive, în acest caz adaptează probabilitățile simbolurilor la tendința datelor. Evident, decodorul trebuie să cunoască modelul folosit de codificator.

Un exemplu simplu

Pentru a clarifica vom discuta un exemplu simplu. Să presupunem că avem o secvență de simboluri, care provin dintr-un alfabet cu trei elemente: A, B, C. Un codificator de bloc simplu ar putea transforma fiecare simbol într-o secvență de doi biți, dar ar fi o risipă, doi biți pot exprima patru combinații și, prin urmare, o combinație nu ar fi folosită niciodată.

Ne putem gândi să reprezentăm simbolurile ca un număr rațional între 0 și 1 în baza 3 și să reprezentăm fiecare simbol ca o cifră a numărului. De exemplu, secvența "ABBCAB" ar fi convertită la 0,011201 3 . Acest lucru ar putea fi apoi convertit la baza doi și ar putea deveni de exemplu 0.001011001 2 - această secvență folosește 9 biți și în loc de cei 12 biți necesari de un codificator naiv și, prin urmare, ocupă cu 25% mai puțin. Decodificatorul ar trebui, evident, să facă pașii opuși pentru a obține secvența de pornire.

Codificare și decodificare

În această secțiune vom generaliza ideea tocmai prezentată, cu toate acestea pașii de bază sunt aceiași, cu excepția ultimului. Practic aveți trei pași:

  • Noul simbol este preluat
  • Intervalul de codare curent este definit (la început intervalul de codare este maxim deci [0,1), dar în timpul codării este redus)
  • Probabilitatea simbolurilor este calculată, acest pas este necesar dacă algoritmul estimează probabilitățile în timpul codificării, dacă acestea sunt fixate într-un mod fix acest pas nu este realizat.

Codificatorul împarte intervalul curent într-un sub-interval care este calculat luând în considerare probabilitatea ca un anumit simbol să apară.

Urmând exemplul anterior împărțim intervalele la o probabilitate fixă.

  • Simbolul NEUTR are intervalul [0, 0,6)
  • Simbolul POZITIV are intervalul [0.6, 0.8)
  • Simbolul NEGATIV are intervalul [0.8, 0.9)
  • Simbolul END-OF-FILE are intervalul [0.9, 1)

Când toate simbolurile sunt codificate, rezultatul este un interval care identifică fără echivoc secvența simbolurilor care l-au generat. Deci, orice sistem care cunoaște modelul și gama este capabil să reconstruiască secvența simbolurilor.

Cu toate acestea, nu este necesar să transmiteți intervalul, transmiteți doar o fracție care se află în interval. În special, este suficient să se transmită suficiente cifre ale fracției pentru a elimina celelalte intervale.

Exemplu

Diagrama arată decodarea numărului 0,538 în modelul nostru de exemplu, pentru simplitate folosim notația zecimală în locul celei binare. După cum puteți vedea din diagramă, intervalele sunt împărțite în sub-intervale până când se întâlnește simbolul END-OF-FILE.

Să presupunem că trebuie să decodăm seria de simboluri asociate cu valoarea 0,538, începem decodarea începând cu un interval [0, 1) și folosind modelul indicat mai sus împărțim intervalul în patru subintervale. Primul simbol conform modelului nostru este NEUTRU, deoarece numărul este mai mic de 0,6 și, prin urmare, se încadrează în intervalul NEUTRU.

Acum împărțim intervalul [0, 0,6) în sub-intervale în funcție de probabilitățile indicate la început și obținem:

  • Simbolul NEUTR are intervalul [0, 0,36) "60% din intervalul [0, 0,6)"
  • Simbolul POZITIV are intervalul [0,36, 0,48) "20% din intervalul [0, 0,6)"
  • Simbolul NEGATIV are intervalul [0,48, 0,54) "10% din intervalul [0, 0,6)"
  • Simbolul END-OF-FILE are intervalul [0,54, 0,6) "10% din domeniul [0, 0,6)"

Numărul 0,538 se încadrează în intervalul [0,48, 0,54) și, prin urmare, al doilea simbol este NEGATIV.

Repetăm ​​din nou subdiviziunea noului interval și obținem:

  • Simbolul NEUTR are intervalul [0,48, 0,516) "60% din intervalul [0,48, 0,54)"
  • Simbolul POZITIV are intervalul [0,516, 0,528) "20% din intervalul [0,48, 0,54)"
  • Simbolul NEGATIV are intervalul [0,528, 0,534) "10% din intervalul [0,48, 0,54)"
  • Simbolul END-OF-FILE are intervalul [0.534, 0.540) "10% din domeniul [0.48, 0.54)"

Numărul 0,538 se încadrează în intervalul [0,535, 0,54) care aparține simbolului END-OF-FILE, astfel încât am ajuns la sfârșitul fluxului de simboluri care urmează să fie decodificat. Trebuie remarcat faptul că și numerele 0.534, 0.535, 0.536, 0.537 sau 0.539 s-ar fi descurcat bine. Acest lucru ar putea sugera că sistemul suferă de unele ineficiențe, în realitate acest lucru se realizează deoarece în exemplul am lucrat în bază zecimală, convertind totul în bază binară am fi folosit .10001010 ca număr de decodare (care în zecimal este 0,5390625) care costă 8 pic.

Codificarea noastră ocupă 8 biți, ceea ce este mai bun decât cei 12 biți utilizați de un codificator trivial, dar totuși mult mai mulți biți decât cei definiți teoretic. Conform teoriei entropiei, fiecare simbol ar trebui să ocupe 1,57 biți care înmulțit cu cele trei simboluri transmise face 4,71 biți. Această diferență între cel mai bun rezultat teoretic și rezultatul codificatorului se datorează numărului redus de simboluri codificate, creșterii numărului de simboluri care urmează a fi codificate, diferența cu rezultatul teoretic este considerabil mai subțire. Mai mult, probabilitățile indicate în exemplu sunt foarte diferite de cele prezente în mesajul codificat. Probabilitățile reale ale mesajului sunt [0,33, 0, 0,33, 0,33], folosind aceste probabilități intervalele ar fi [0, 1/3); [1/9, 2/9); [5/27, 6/27); în binar ar deveni [1011110, 1110001] și, prin urmare, numai valoarea 111 ar putea fi trimisă pentru a indica succesiunea simbolurilor. Acest lucru arată, de asemenea, că o statistică greșită poate degrada semnificativ performanța codării.

Precizie și renormalizare

Exemplele de mai sus conțin simplificări, dintre care una este că decodorul funcționează mai întâi cu cifre de precizie infinite și apoi caută fracția binară. În realitate, majoritatea decodoarelor funcționează cu un număr de cifre finite egal cu numărul maxim de simboluri care urmează să fie decodate, astfel încât să nu fie nevoie să facă conversii. Prin urmare, în exemplul anterior, decodorul ar fi folosit imediat 8 biți de precizie.

Simbol Probabilitate (exprimată ca fracție) Gama indicată cu opt biți de precizie (sub formă de fracție) Gama indicată cu opt biți de precizie (în binar) Extreme în binar
LA 1/3 [0, 85/256) [0,00000000, 0,01010101) 00000000 - 01010100
B. 1/3 [85/256, 171/256) [0.01010101, 0.10101011) 01010101 - 10101010
C. 1/3 [171/256, 1) [0.10101011, 1.00000000) 10101011 - 11111111

Procesul numit „renormalizare” servește la menținerea preciziei finite la codificarea simbolurilor. Ori de câte ori intervalul de valori care specifică intervalele este redus până la punctul de a avea biții de bază ai intervalelor de conducere, aceștia sunt trimiși în partea de jos a numerelor binare. Acest lucru din exemplul discutat mai sus apare în două din trei cazuri.

Simbol Şansă Gamă Număr Gama după renormalizare
LA 1/3 0 0000000 - 0 1010100 0 0000000 0 - 1010100 1
B. 1/3 01010101 - 10101010 Nu este 01010101 - 10101010
C. 1/3 1 0101011 - 1 1111111 1 0101011 0 - 1111111 1

Comparații cu alte sisteme de compresie

Codificare Huffman

Pictogramă lupă mgx2.svg Același subiect în detaliu: codificarea Huffman .

Această codificare se bazează pe principii similare cu cele ale codificării aritmetice și, de fapt, poate fi văzută ca un caz special de codificare aritmetică, deoarece codificarea aritmetică transformă întregul mesaj într-un număr bazat pe N, în timp ce codificarea Huffman reprezintă fiecare simbol ca element de bază N.

Codificarea Huffman poate fi considerată o codificare aritmetică care rotunjește frecvența fiecărui simbol la cea mai apropiată putere de jumătate (0,5). Din acest motiv, codificarea Huffman prezintă rezultate modeste atunci când este aplicată alfabetelor cu distribuții de tipul 0,75 sau 0,375. Distribuțiile de acest tip sunt răspândite în special în alfabete cu puține simboluri.

De exemplu, luați în considerare alfabetul {a, b, c} cu o distribuție la fel de probabilă de 1/3. Codificarea Huffman produce următoarele coduri:

  • a → 0 : 50%
  • b → 10 : 25%
  • c → 11 : 25%

Aceste coduri ocupă (2 + 2 + 1) / 3 ≈ 1.667 biți per simbol cu ​​codificare Huffman. Codificarea aritmetică produce 1.585 biți pe simbol și, prin urmare, ineficiența este de 5%.

Dar dacă luăm în considerare un alfabet binar de tipul {0, 1} cu distribuție 0,625 și 0,375, codarea Huffman atribuie fiecărui simbol probabilitatea de 50% și, prin urmare, generează un alfabet cu două simboluri, în esență, nu comprimă datele. Codificarea aritmetică, pe de altă parte, obține o creștere de:

1 - (0,625 (−log 2 0,625) + 0,375 (−log 2 0,375)) ≈ 4,6%.

Dacă un simbol este mult mai probabil, de exemplu, presupunând că are o probabilitate de 95%, obținem o creștere de:

1 - (0,95 (−log 2 0,95) + 0,05 (−log 2 0,05)) ≈ 71,4%.

O modalitate ușoară în acest sens este de a crea un nou alfabet concatenând simbolurile pentru a obține simboluri noi cu o distribuție mai bună pentru algoritm. De exemplu, puteți concatena simbolurile pentru a obține:

  • 000 : 85,7%
  • 001 , 010 , 100 : 4,5%
  • 011 , 101 , 110 : .24%
  • 111 : 0,0125%

Acestea ar fi codificate cu 1,3 biți pentru fiecare grup de trei simboluri apoi cu 0,433 biți pe simbol, o îmbunătățire semnificativă față de bitul pe simbol al codificării inițiale.

Codificare pe intervale

Codificarea pe intervale este un alt mod de a privi codarea aritmetică. Codificarea aritmetică și codarea intervalelor sunt practic același concept implementat într-un mod ușor diferit. Adesea, dacă lucrăm pe biți singuri, vorbim de codificare aritmetică, în timp ce dacă lucrăm pe octeți, vorbim de codificare pe intervale, dar această distincție nu este universal acceptată. Se afirmă adesea că această codificare nu conține brevete, dar având în vedere că conceptul de bază este același, afirmația este cel puțin îndoielnică.

Ideea din spatele codificării este de a lua un interval și de a-l împărți în sub-intervale proporțional cu probabilitatea fiecărui simbol. Cu toate acestea, spre deosebire de codificarea aritmetică, intervalul [0, 1) nu este utilizat, ci un interval mult mai mare, negativ și întreg, de exemplu intervalul de la 000 000 000 000 la 999 999 999 999. Când subintervalele sunt suficient de diferențiat făcând cunoscută prima cifră, aceasta este mutată la sfârșitul intervalului, această operațiune este ca și cum ar fi dus la o multiplicare a intervalului, menținând întotdeauna suficiente numere întregi în interval.

Deci, dacă ignorați faptul că intervalul este mult mai mare și utilizați numere întregi în loc de fracții, cele două tehnici sunt aceleași. Faptul de a aplica înmulțirea intervalului pe octet (codarea aritmetică efectuează renormalizarea pe bit) reduce ușor compresia, dar această compresie funcționează doar pe numere întregi și în medie mai rapidă decât codarea aritmetică.

Brevete

Multe implementări ale codificării aritmetice sunt protejate de brevetele SUA. Mai multe implementări sunt utilizate și în standardele internaționale, dar în mod normal aceste implementări sunt distribuite sub licențe RAND . Uneori, aceste licențe nu prevăd plata brevetului pentru majoritatea utilizărilor sau implică taxe modeste. Acest lucru poate fi acceptabil pentru software-ul comercial, dar în mod normal nu este considerat acceptabil de programele open source și software-ul gratuit în general.

Printre companiile cunoscute pentru posesia brevetelor de codare aritmetică, se remarcă IBM . Se crede că algoritmii codați aritmetic nu pot fi dezvoltați fără încălcarea unui brevet american. Cu toate acestea, unele brevete au expirat și, prin urmare, teoretic aceste implementări ar putea fi utilizate, dar, deoarece nu există certitudinea că aceste implementări sunt, de asemenea, acoperite parțial de brevete ulterioare, majoritatea programatorilor preferă să nu folosească codarea aritmetică.

De exemplu, programul bzip2 a gestionat inițial codarea aritmetică, dar mai târziu, de teama proceselor, programatorii au decis să întrerupă codarea. Codificarea JPEG se ocupă și de această codificare împreună cu codarea Huffman, dar pentru a evita să plătească brevete majoritatea programelor se ocupă doar de codificarea Huffman.

Brevetele privind codificarea aritmetică includ:

Notă: Lista nu este exhaustivă.

Benchmark și alte probleme tehnice

Fiecare tehnică de codificare diferită prezintă un raport de compresie și un timp de compresie diferiți. Factorul de compresie variază în mod normal nesemnificativ (mai puțin de 1% în mod normal) în timp ce timpul de compresie și decompresie variază semnificativ, unele metode sunt de până la zece ori mai rapide decât altele. Alegerea celui mai bun compresor nu este ușoară, deoarece performanțele depind foarte mult de datele de intrare. Unele compresoare funcționează bine cu puține date de intrare, altele cu alfabete complexe, mai multe funcționează numai cu alfabete binare.

Bibliografie

linkuri externe

Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT