Otvorena biblioteka - otvorena biblioteka obrazovnih informacija. Teorija informacija

Sada postoji mnogo algoritama za komprimiranje informacija. Većina njih je nadaleko poznata, ali postoje neki vrlo efikasni, ali ipak malo poznati algoritmi. Ovaj članak govori o metodi aritmetičko kodiranje, što je najbolja od entropije, ali ipak malo ljudi zna za to.
Prije nego što govorimo o aritmetičkom kodiranju, moramo reći nekoliko riječi o Huffman algoritmu. Ova metoda je efikasna kada je broj znakova proporcionalan 1/2 n (gdje je n prirodno pozitivan broj). Ova izjava postaje očigledna ako se prisjetimo da se Huffmanovi kodovi za svaki znak uvijek sastoje od cijelog broja bitova. Razmotrimo situaciju kada je učestalost pojavljivanja znaka 0,2, tada bi optimalni kod za kodiranje ovog znaka trebao imati dužinu –log 2 (0,2)=2,3 bita. To je jasno kod prefiksa Huffman ne može imati takvu dužinu, tj. ovo na kraju rezultira lošijom kompresijom podataka.
Aritmetičko kodiranje je dizajnirano da riješi ovaj problem. Osnovna ideja je da se kodovi ne dodijele pojedinačni likovi, ali njihove sekvence.
Prvo, pogledajmo ideju iza algoritma, a zatim pogledajmo mali praktični primjer.
Kao iu svim entropijskim algoritmima, imamo informacije o učestalosti upotrebe svakog znaka abecede. Ova informacija je početna tačka za metodu koja se razmatra. Sada da uvedemo koncept radnog segmenta. Polu-interval se naziva radni interval Koliko trocifrenih heksadecimalnih brojeva postoji za koje će istovremeno postojati

Predavanje 13 Tehnike i metode rada sa komprimiranim podacima Predavač St. nastavnik Kupo A.N. Karakteristična karakteristika većine "klasičnih" tipova podataka s kojima ljudi tradicionalno rade je izvjesna

Federalna državna obrazovna budžetska ustanova visokog stručnog obrazovanja Volga Državni univerzitet za telekomunikacije i informatiku Odsjek SARS Zadatak i metodologija

UDC 519.6 Značajke kodiranja teksta pomoću Huffmanovog algoritma Kizyanov Anton Olegovich Priamur State University po imenu Sholom Aleichem Student Kuzmina Bogdana Sergeevna Priamursky

LABORATORIJSKI RAD Metode za postavljanje i glavne karakteristike konvolucionih kodova Konvolucijski kodovi se široko koriste u različitim oblastima tehnologije za prenos i skladištenje informacija. Najvidljiviji

UDK 004.8 PRIMJENA GENETIČKOG ALGORITMA ZA UPRAVLJANJE DIZAJNOM ŠKOLSKOG RASPOREDA Gushchina OA Genetski algoritam (GA) adaptivni algoritam pretraživanja zasnovan na evolucijskim faktorima

Diskretna matematika 2. deo Jurij Andrejevič Kočetov http://www.math.nsc.ru/lbrt/k5/dm.html Predavanje 1 Algoritmi, sortiranja, AVL stabla 1 Algoritmi i njihova složenost Računari rade (do sada) samo ispravno

Hafmanova metoda je jednostavna, ali efikasna samo kada su verovatnoće pojavljivanja simbola jednake brojevima, gde je bilo koji pozitivan ceo broj. To je zato što Huffmanov kod svakom znaku abecede dodjeljuje kod s cijelim brojem bitova. U isto vrijeme, u teoriji informacija je poznato da, na primjer, ako je vjerovatnoća pojavljivanja simbola 0,4, idealno bi mu trebalo dati kod dužine bit. Jasno je da je prilikom konstruisanja Huffmanovih kodova nemoguće postaviti dužinu koda na 1,32 bita, već samo na 1 ili 2 bita, što će rezultirati lošijom kompresijom podataka. Aritmetičko kodiranje rješava ovaj problem dodjeljivanjem koda cijeloj, obično velikoj, datoteci koja se prenosi, umjesto kodiranja pojedinačnih znakova.

Ideju aritmetičkog kodiranja najbolje je vidjeti na jednostavnom primjeru. Pretpostavimo da je potrebno kodirati tri karaktera ulaznog toka, radi određenosti, ovo je niz SWISS_MISS sa datim frekvencijama znakova: S - 0,5, W - 0,1, I - 0,2, M - 0,1 i _ - 0, jedan. U aritmetičkom koderu, svaki znak je predstavljen intervalom u rasponu brojeva), i interval za /-ti kodirani simbol toka kao ; b[c]), uključujući 0,341. Nabrajanjem svih mogućih simbola prema gornjoj tabeli nalazimo da je samo interval - (fti-j - li-i); zdravo= li!+ b ■ (zdravo! - li.i); ako ((lt<= value) && (value < zdravo)) break; ); DataFile.WriteSymbol(c^) ;

gdje je vrijednost broj (razlomak) pročitan iz toka, i sa - raspakovani karakteri upisani u izlazni tok. Kada koristite abecedu od 256 znakova cj Unutrašnjoj petlji je potrebno mnogo vremena da se završi, ali se može ubrzati. Imajte na umu da pošto b[c^ (\=a; II divider=10

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

Pola = Prvi_qtr*2; // - 32768

Third_qtr - First_qtr*3;// = 49152

bits_to_follow=0; // Koliko bitova za resetiranje

dok (ne DataFile.EOFO) (

c = DataFile.ReadSymbol(); // Čitanje karaktera
j= IndexForSymbol(c); i++; // Pronađite njegov indeks
li= li.j + b*(h i. 1 - li-x+l)/razdjelnik;
zdravo= li!+ b;
Prvi_qtr = (h 0 +l)/4; // = 16384

Pola = Prvi_qtr*2; // = 32768

Third_qtr = First_qtr*3; // = 49152

value=CompressedFile.Readl6Bit();

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

freq=((vrijednost-2 i . 1 +l)*delitel-l)/(h i . I - 1±. X+ 1) ;

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

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

zdravo= Ja sam+ b*(h i . 1 - li.!+ l)/razdjelnik - 1;

for(;;) ( // Opcije obrade

ako (zdravo< Half) // переполнения

; // Ništa drugo ifdi >= Pola) (

2i-=Pola; hi=Half; vrijednost-= Polovina; )

inače if (di >= First_qtr)&& (bok< Third_qtr)) { 2i-= First_qtr; hi-= First_qtr; value-= First_qtr,-} else break; 2i+=2 i; hi+= hi+1;

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

Vježba. Navedite primjere nizova komprimiranih algoritmom s maksimalnim i minimalnim koeficijentima.

Kao što vidite, borimo se sa netačnostima aritmetike tako što izvodimo odvojene operacije na /, i A, sinhrono u kompresoru i dekompresoru.

Beznačajni gubici u tačnosti (djelići procenta za dovoljno veliku datoteku) i, shodno tome, smanjenje stepena kompresije u odnosu na idealni algoritam nastaju tokom operacije dijeljenja, kada se relativne frekvencije zaokružuju na cijeli broj, kada je posljednji bitovi se upisuju u datoteku. Algoritam se može ubrzati predstavljanjem relativnih frekvencija tako da je djelitelj potencija dva (tj. zamjenom dijeljenja operacijom pomaka po bitu).

Da biste procijenili stepen kompresije aritmetičkim algoritmom određenog niza, morate pronaći minimalni broj N, tako da bi dužina radnog intervala za vrijeme kompresije posljednjeg karaktera niza bila manja od 1/2^.. Ovaj kriterij znači da unutar našeg intervala sigurno postoji barem jedan broj u čijoj binarnoj predstavi nakon N-ro predznak će biti samo 0. Dužina intervala je lako čitljiva, pošto je jednaka proizvodu vjerovatnoća svih znakova.

Razmotrimo raniji primjer niza od dva znaka l i Kommersant sa vjerovatnoćama 253/256 i 3/256. Dužina posljednjeg radnog intervala za niz od 256 znakova a i b sa naznačenim verovatnoćama jednaka. Lako je izračunati da je traženi N=24 (1/2 24 = 5,96-10" 8), pošto 23 daje preveliki interval (2 puta širi), a 25 nije minimalno broj koji ispunjava kriterijume. Gore je pokazano da Hafmanov algoritam kodira ovaj lanac u 256 bita. To jest, za razmatrani primjer, aritmetički algoritam daje desetostruku prednost u odnosu na Huffman algoritam i zahtijeva manje od 0,1 bita po simbolu.

Vježba. Izračunajte omjer kompresije za niz "BOX.BOX".

Treba reći nekoliko riječi o algoritmu adaptivne aritmetičke kompresije. Njegova ideja je da ponovo izgradi tabelu verovatnoće b[f] u toku pakovanja i raspakivanja direktno po prijemu sledećeg karaktera. Takav algoritam ne zahtijeva pohranjivanje vrijednosti vjerojatnosti simbola u izlaznoj datoteci i, u pravilu, daje visok stupanj kompresije. Tako, na primjer, datoteku oblika a 1000 £ 1000 sa 1000 b/1000 (gdje eksponent znači broj ponavljanja datog znaka) adaptivni algoritam može efikasnije komprimirati nego trošenje 2 bita po karakteru. Gornji algoritam se jednostavno pretvara u adaptivni algoritam. Ranije smo tabelu opsega snimili u datoteku, a sada računamo tačno u toku rada kompresora i dekompresora, preračunavamo relativne frekvencije, prilagođavajući tabelu opsega u skladu sa njima. Važno je da se promene u tabeli dešavaju u kompresoru i dekompresoru sinhrono, tj. kodiranje lanci dužine 100 tabela raspona mora biti potpuno ista kao i poslije dekodiranje lanci dužine 100. Ovaj uslov je lako ispuniti ako promenite tabelu poslije kodiranje i dekodiranje sljedećeg znaka. Za više informacija o adaptivnim algoritmima, pogledajte pogl. četiri.

Karakteristike aritmetičkog algoritma:

Najbolji i najgori omjer kompresije: najbolji > 8 (moguće manje bitova po karakteru), najgori - 1.

Prednosti algoritma: pruža bolji stepen kompresije od Huffmanovog algoritma-I ritma (na tipičnim podacima za 1-10%).

karakteristike: kao i Huffmanovo kodiranje ne povećava veličinu originalnih podataka u najgorem slučaju.

Intervalno kodiranje

Za razliku od klasičnog algoritma, intervalno kodiranje pretpostavlja da imamo posla s diskretnim cijelim brojevima koji mogu poprimiti ograničen broj vrijednosti. Kao što je već napomenuto, početni interval u cjelobrojnoj aritmetici zapisuje se kao [OD) ili , gdje N- broj mogućih vrijednosti za varijablu koja se koristi za pohranjivanje granica intervala.

Da bismo najefikasnije komprimirali podatke, moramo kodirati svaki znak s preko -log 2 (J) bita, gdje f,- frekvencija simbola s. Naravno, u praksi je takva tačnost nedostižna, ali možemo za svaki lik s dodijelite raspon vrijednosti u intervalu , Prev_freq[c], 10) ;