Open Library este o bibliotecă deschisă de informații educaționale. Teoria informației

Acum există mulți algoritmi pentru comprimarea informațiilor. Cele mai multe dintre ele sunt cunoscute pe scară largă, dar există și unii algoritmi foarte eficienți, dar, totuși, puțin cunoscuți. Acest articol vorbește despre metoda de codificare aritmetică, care este cea mai bună dintre cele cu entropie, dar cu toate acestea foarte puțini oameni știu despre ea.
Înainte de a vorbi despre codificarea aritmetică, trebuie să spun câteva cuvinte despre algoritmul Huffman. Această metodă este eficientă atunci când ratele simbolurilor sunt proporționale cu 1/2 n (unde n este un număr întreg pozitiv). Această afirmație devine evidentă când vă amintiți că codurile Huffman pentru fiecare caracter constau întotdeauna dintr-un număr întreg de biți. Să luăm în considerare situația în care frecvența de apariție a unui simbol este 0,2, atunci codul optim pentru codificarea acestui simbol ar trebui să aibă o lungime de –log 2 (0,2) = 2,3 biți. Este clar că codul de prefix Huffman nu poate avea această lungime, adică. acest lucru duce în cele din urmă la o comprimare slabă a datelor.
Codarea aritmetică este concepută pentru a rezolva această problemă. Ideea principală este de a atribui coduri nu personajelor individuale, ci secvențelor acestora.
Mai întâi, ne vom uita la ideea din spatele algoritmului, apoi ne vom uita la un mic exemplu practic.
Ca în toți algoritmii de entropie, avem informații despre frecvența de utilizare a fiecărui caracter al alfabetului. Aceste informații reprezintă sursa metodei luate în considerare. Acum să introducem conceptul de segment de flanșă. Un semi-interval se numește lucrător. Câte numere hexazecimale din trei cifre există pentru care vor exista în același timp

Curs 13 Tehnici si metode de lucru cu date comprimate Lector Art. profesor Coupeau A.N. O trăsătură caracteristică a majorității tipurilor de date „clasice” cu care lucrează în mod tradițional oamenii este o anumită

Instituția bugetară educațională de stat federală de învățământ profesional superior Universitatea de stat de telecomunicații și informatică Povolzhskiy Departamentul SARS Atribuire și metodologie

UDC 519.6 Particularități ale codificării textului folosind algoritmul Huffman Kizyanov Anton Olegovich Priamursky State University numită după Sholem Aleichem Student Kuzmina Bogdana Sergeevna Priamursky

LUCRĂRI DE LABORATOR Metode de stabilire și caracteristici de bază ale codurilor convoluționale Codurile convoluționale sunt utilizate pe scară largă în diverse domenii ale tehnologiei de transmitere și stocare a informațiilor. Cel mai ilustrativ

UDC 004.8 APLICAREA UNUI ALGORITM GENETIC PENTRU GESTIONAREA PROIECTULUI PROGRAMULUI SCOLAR Gushchina O. A. Algoritm de căutare adaptivă al algoritmului genetic (GA) bazat pe factori evolutivi

Matematică discretă Partea 2 Kochetov Yuri Andreevich http://www.math.nsc.ru/lbrt/k5/dm.html Curs 1 Algoritmi, sortare, arbori AVL 1 Algoritmi și complexitatea lor Calculatoarele funcționează (până acum) doar corect

Metoda lui Huffman este simplă, dar eficientă numai atunci când probabilitățile de apariție a simbolurilor sunt egale cu numerele, unde este orice număr întreg pozitiv. Acest lucru se datorează faptului că codul Huffman atribuie un număr întreg de biți fiecărui caracter din alfabet. În același timp, în teoria informației se știe că, de exemplu, atunci când probabilitatea apariției unui simbol este egală cu 0,4, în mod ideal ar trebui să i se atribuie un cod de lungime. pic. Este clar că la construirea codurilor Huffman, lungimea codului nu poate fi setată la 1,32 biți, ci doar la 1 sau 2 biți, ceea ce va duce la o comprimare slabă a datelor. Codarea aritmetică rezolvă această problemă prin atribuirea unui cod întregului fișier transmis, de obicei mare, în loc de codificarea caracterelor individuale.

Ideea de codificare aritmetică este cel mai bine ilustrată cu un exemplu simplu. Să presupunem că este necesar să se codifice trei caractere ale fluxului de intrare, pentru claritate, acesta este șirul SWISS_MISS cu frecvențele specificate ale caracterelor: S - 0,5, W - 0,1, I - 0,2, M - 0,1 și _ - 0, unu. Într-un codificator aritmetic, fiecare caracter este reprezentat printr-un interval într-un interval de numere),și intervalul pentru simbolul i-lea de flux codificat ca; B [c]), inclusiv 0,341. Enumerând toate simbolurile posibile conform tabelului de mai sus, constatăm că doar intervalul este (fti-j - li-i); Salut= li.!+ b ■ (hi.! - li.i); dacă ((l t<= value) && (value < Salut)) pauză; ); DataFile.WriteSymbol (c ^);

unde valoare este numărul (fracția) citit din flux și Cu - caractere despachetate scrise în fluxul de ieșire. Când utilizați un alfabet de 256 de caractere Cj bucla interioară durează mult timp, dar o puteți accelera. Rețineți că din moment ce B [c ^ (\ = a; II delitel = 10

First_qtr - (h 0 + l) / 4; // - 16384

Jumătate = First_qtr * 2; // - 32768

Third_qtr - First_qtr * 3; // = 49152

bits_to_follow = 0; // Câți biți să ștergeți

în timp ce (nu DataFile.EOFO) (

c = DataFile.ReadSymbol (); // Citiți simbolul
j= IndexForSymbol (s); i ++; // Găsește-i indexul
li= li.j + b * (h i. 1 - li-x+ l) / delitel;
Salut= li.!+ b;
First_qtr = (h 0 + l) / 4; // = 16384

Jumătate = First_qtr * 2; // = 32768

Third_qtr = First_qtr * 3; // = 49152

valoare = CompressedFile.Readl6Bit ();

pentru (i = l; i< CompressedFile.DataLengthO; i++){

frecvență = ((valoare-2 i. 1 + l) * delitel-l) / (h i. I - 1 ±. X+ 1) ;

pentru (j = l; b<=freq; j++); // Поиск символа

li = 1y+ blj-l] * (bi.!- li- u + l) / delitel;

Salut= Sunt+ b * (h i. 1 - li.!+ l) / delitel - 1;

pentru (;;) (// Opțiuni de procesare

dacă (bună< Half) // переполнения

; // Nimic altceva ifdi> = Jumătate) (

2i- = Jumătate; hi- = Jumătate; valoare- = Jumătate; )

altfel dacă (di> = First_qtr) && (hi< Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2 i; hi+= hi+1;

valoare + = valoare + CompressedFile.ReadBit (); } DataFile.WriteSymbol (c););

Exercitiul. Sugerați exemple de secvențe comprimate de algoritm cu coeficienții maxim și minim.

După cum puteți vedea, ne luptăm cu inexactitățile aritmetice prin efectuarea de operații separate pe / și A, sincron în compresor și decompresor.

Pierderea nesemnificativă a preciziei (fracții de procent pentru un fișier suficient de mare) și, în consecință, o scădere a raportului de compresie în comparație cu algoritmul ideal are loc în timpul operațiunii de divizare, când frecvențele relative sunt rotunjite la un întreg, când ultimul biții sunt scrieți în fișier. Algoritmul poate fi accelerat prin reprezentarea frecvențelor relative, astfel încât divizorul să fie o putere de doi (adică, înlocuirea diviziunii cu o operație de deplasare pe biți).

Pentru a estima raportul de compresie prin algoritmul aritmetic al unui anumit șir, trebuie să găsiți numărul minim N, astfel încât lungimea intervalului de lucru la comprimarea ultimului caracter al lanțului ar fi mai mică de 1/2 ^ .. Acest criteriu înseamnă că în intervalul nostru există cu siguranță cel puțin un număr în reprezentarea binară a căruia după N-ro vor fi doar semne 0. Lungimea intervalului este ușor de citit, deoarece este egală cu produsul probabilităților tuturor simbolurilor.

Luați în considerare exemplul anterior al unui șir de două caractere l și B cu probabilităţi 253/256 şi 3/256. Lungimea ultimului interval de lucru pentru un șir de 256 de caractere Ași B cu probabilitățile indicate egale. Este ușor de calculat că necesarul N = 24 (1/2 24 = 5,96-10 "8), deoarece 23 oferă un interval prea mare (de 2 ori mai larg), iar 25 nu este minim un număr care îndeplinește criteriul. S-a arătat mai sus că algoritmul Huffman codifică acest șir pe 256 de biți. Adică, pentru exemplul considerat, algoritmul aritmetic oferă un avantaj de zece ori față de algoritmul Huffman și necesită mai puțin de 0,1 biți pe caracter.

Exercitiul. Calculați estimarea raportului de compresie pentru linia "COV.KOROBA".

Ar trebui spuse câteva cuvinte despre algoritmul de compresie aritmetică adaptivă. Ideea sa este de a reconstrui tabelul de probabilitate b [f]în timpul împachetarii și despachetarea imediat după primirea următorului caracter. Un astfel de algoritm nu necesită stocarea valorilor probabilităților caracterelor în fișierul de ieșire și, de regulă, oferă un raport de compresie ridicat. Deci, de exemplu, un fișier precum un 1000 £ 1000 cu 1000 b / 1000 (unde gradul înseamnă numărul de repetări ale unui anumit caracter), algoritmul adaptiv va putea să se comprima mai eficient decât cheltuind 2 biți pe caracter. Algoritmul de mai sus se transformă pur și simplu într-unul adaptiv. Anterior, am salvat tabelul intervalelor într-un fișier, iar acum calculăm chiar în cursul compresorului și decompresorului, recalculăm frecvențele relative, ajustând tabelul intervalului în conformitate cu acestea. Este important ca modificările din tabel să aibă loc în compresor și decompresor în mod sincron, adică, de exemplu, după codificare lanțuri de lungime 100 tabelul de gamă ar trebui să fie exact același ca după decodare lanțuri de lungime 100. Această condiție este ușor de îndeplinit dacă schimbați masa după codificarea și decodificarea următorului caracter. Pentru mai multe detalii despre algoritmii adaptivi, vezi cap. 4.

Caracteristicile algoritmului aritmetic:

Cel mai bun și cel mai rău raport de compresie: cel mai bun> 8 (este posibilă codificarea mai puțin de un bit per simbol), cel mai rău - 1.

Avantajele algoritmului: Oferă un raport de compresie mai bun decât ritmul Algo-I Huffman (pe datele tipice cu 1-10%).

Caracteristici: precum și codarea Huffman, nu crește dimensiunea datelor originale în cel mai rău caz.

Codare pe intervale

Spre deosebire de algoritmul clasic, codarea pe intervale presupune că avem de-a face cu valori întregi discrete care pot lua un număr limitat de valori. După cum sa menționat deja, intervalul inițial în aritmetica întregului este scris ca [OD) sau, unde N- numărul de valori posibile pentru variabila utilizată pentru a stoca limitele intervalului.

Pentru a comprima datele cel mai eficient, trebuie să codificăm fiecare caracter s prin -log 2 (Ј) biți, unde f,- frecvența simbolului s. Desigur, în practică, o astfel de precizie este de neatins, dar putem pentru fiecare personaj s atribuiți un interval de valori într-un interval , Prev_freq [c], 10);