GORKOFF 24. veljače 2015. u 11.41 sati

Metode kompresije podataka

• Algoritmi

Moj znanstveni savjetnik i ja pripremamo malu monografiju o obradi slika. Odlučio sam podnijeti poglavlje o algoritmima kompresije slike na sud HabraSociety. Kako je teško uklopiti cijelo poglavlje u okvir jednog posta, odlučio sam ga podijeliti u tri posta:
1. Metode kompresije podataka;
2. Kompresija slika bez gubitaka;
3. Kompresija slika s gubitkom.
U nastavku možete pročitati prvi post u nizu.

Trenutno postoji veliki broj algoritama kompresije bez gubitaka, koji se uvjetno mogu podijeliti u dvije velike skupine:
1. Stream i algoritmi rječnika. Ova grupa uključuje algoritme RLE (run-length encoding), LZ * i druge obitelji. Posebnost svih algoritama ove grupe je da kodiranje ne koristi informacije o frekvencijama znakova u poruci, već informacije o sekvencama na koje smo se ranije susreli.
2. Algoritmi za statističku (entropijsku) kompresiju. Ova skupina algoritama komprimira informacije koristeći neujednačenost frekvencija s kojima se različiti znakovi pojavljuju u poruci. Algoritmi u ovoj skupini uključuju aritmetičke i prefiksne algoritme kodiranja (koristeći Shannon-Fanno, Huffman, sekantna stabla).
Algoritmi transformacije informacija mogu se izdvojiti u zasebnu skupinu. Algoritmi ove skupine ne komprimiraju izravno informacije, ali njihova primjena uvelike pojednostavljuje daljnje sažimanje pomoću algoritama toka, rječnika i entropije.

Streaming i algoritmi rječnika

Kodiranje duljine izvođenja

Run-Length Encoding (RLE) jedan je od najjednostavnijih i najčešćih algoritama kompresije podataka. U ovom algoritmu niz znakova koji se ponavljaju zamjenjuje se znakom i brojem ponavljanja.
Na primjer, niz "AAAAA", koji zahtijeva 5 bajtova za pohranu (pod pretpostavkom da je bajt dodijeljen za pohranjivanje jednog znaka), može se zamijeniti s "5A", koji se sastoji od dva bajta. Očito, što je duži niz ponavljanja, to je ovaj algoritam učinkovitiji.

Glavni nedostatak ovog algoritma je njegova iznimno niska učinkovitost na nizovima znakova koji se ne ponavljaju. Na primjer, ako uzmemo u obzir slijed "ABABAB" (6 bajtova), tada će se nakon primjene RLE algoritma pretvoriti u "1A1B1A1B1A1B" (12 bajtova). Postoje različite metode za rješavanje problema znakova koji se ne ponavljaju.

Najjednostavnija metoda je sljedeća modifikacija: bajt koji kodira broj ponavljanja mora pohraniti informacije ne samo o broju ponavljanja, već io njihovoj prisutnosti. Ako je prvi bit 1, sljedećih 7 bitova označava broj ponavljanja odgovarajućeg znaka, a ako je prvi bit 0, sljedećih 7 bitova označava broj znakova koji se moraju uzeti bez ponavljanja. Ako kodirate "ABABAB" koristeći ovu modifikaciju, dobivamo "-6ABABAB" (7 bajtova). Očito, predložena tehnika može značajno poboljšati učinkovitost RLE algoritma na nizovima znakova koji se ne ponavljaju. Provedba predloženog pristupa prikazana je u Listingu 1:

1. tip
2. funkcija RLEEncode (InMsg: ShortString): TRLEEncodedString;
3. MatchFl: boolean;
4. MatchCount: shortint;
5. EncodedString: TRLEEncodedString;
6. N, i: bajt;
7. početi
8. N: = 0;
9. SetLength (EncodedString, 2 * duljina (InMsg));
10. dok je duljina (InMsg)> = 1 do
11. početi
12. MatchFl: = (duljina (InMsg)> 1) i (InMsg [1] = InMsg [2]);
13. Broj podudaranja: = 1;
14. dok (broj utakmica<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. Broj podudaranja: = Broj podudaranja + 1;
16. ako MatchFl onda
17. početi
18. N: = N + 2;
19. Kodirani niz [N - 2]: = Broj podudaranja + 128;
20. Kodirani niz [N - 1]: = ord (InMsg [1]);
21. drugo
22. početi
23. ako MatchCount<>duljina (InMsg) tada
24. MatchCount: = MatchCount - 1;
25. N: = N + 1 + Broj podudaranja;
26. EncodedString [N - 1 - MatchCount]: = - MatchCount + 128;
27. za i: = 1 do MatchCount do
28. EncodedString [N - 1 - MatchCount + i]: = ord (InMsg [i]);
29. kraj;
30. izbrisati (InMsg, 1, MatchCount);
31. kraj;
32. SetLength (EncodedString, N);
33. RLEEncode: = EncodedString;
34. kraj;

Dekodiranje komprimirane poruke vrlo je jednostavno i svodi se na jedan prijelaz preko komprimirane poruke, pogledajte Listing 2:

1. tip
2. TRLEEncodedString = niz bajtova;
3. funkcija RLEDecode (InMsg: TRLEEncodedString): ShortString;
4. RepeatCount: shortint;
5. i, j: riječ;
6. OutMsg: ShortString;
7. početi
8. OutMsg: = "";
9. i: = 0;
10. dok ja< length(InMsg) do
11. početi
12. Broj ponavljanja: = InMsg [i] - 128;
13. i: = i + 1;
14. ako RepeatCount< 0 then
15. početi
16. Broj ponavljanja: = trbušnjaci (broj ponavljanja);
17. za j: = i do i + Broj ponavljanja - 1 do
18. OutMsg: = OutMsg + chr (InMsg [j]);
19. i: = i + Broj ponavljanja;
20. drugo
21. početi
22. za j: = 1 do RepeatCount do
23. OutMsg: = OutMsg + chr (InMsg [i]);
24. i: = i + 1;
25. kraj;
26. kraj;
27. RLEDecode: = OutMsg;
28. kraj;

Druga metoda za povećanje učinkovitosti RLE algoritma je korištenje algoritama transformacije informacija koji ne komprimiraju podatke izravno, već ih dovode u oblik koji je pogodniji za kompresiju. Kao primjer takvog algoritma razmotrit ćemo BWT permutaciju nazvanu po izumiteljima Burrows-Wheelerova transformacije. Ova permutacija ne mijenja same znakove, već samo mijenja njihov redoslijed u nizu, dok se ponovljeni podnizovi nakon primjene permutacije skupljaju u guste grupe, koje su puno bolje komprimirane pomoću RLE algoritma. Izravna BWT pretvorba svodi se na slijed sljedećih koraka:
1. Dodavanje posebnog znaka za kraj reda izvornom nizu, koji se ne nalazi nigdje drugdje;
2. Dobivanje svih cikličkih permutacija izvornog niza;
3. Razvrstavanje primljenih redaka leksikografskim redom;
4. Vraćanje posljednjeg stupca rezultirajuće matrice.
Implementacija ovog algoritma prikazana je u Listingu 3.

1. konst
2. EOMsg = "|" ;
3. funkcija BWTEncode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: riječ;
7. početi
8. InMsg: = InMsg + EOMsg;
9. N: = duljina (InMsg);
10. ShiftTable [1]: = InMsg;
11. za i: = 2 do N do
12. početi
13. Zadnji znak: = InMsg [N];
14. InMsg: = LastChar + kopija (InMsg, 1, N - 1);
15. ShiftTable [i]: = InMsg;
16. kraj;
17. Sortiraj (ShiftTable);
18. OutMsg: = "";
19. za i: = 1 do N do
20. OutMsg: = OutMsg + ShiftTable [i] [N];
21. BWTEncode: = OutMsg;
22. kraj;

Ovu transformaciju najlakše je objasniti konkretnim primjerom. Uzmimo niz "ANANAS" i dogovorimo se da će znak na kraju reda biti simbol "|". Sve cikličke permutacije ovog retka i rezultat njihova leksikografskog sortiranja prikazani su u tablici. 1.

Oni. rezultat izravne konverzije bit će niz "| NNAAAS". Lako je vidjeti da je ovaj niz mnogo bolji od originalnog; komprimiran je RLE algoritmom, budući da sadrži duge nizove ponovljenih slova.
Sličan učinak može se postići i uz pomoć drugih transformacija, ali prednost BWT transformacije je u tome što je reverzibilna, međutim, inverzna transformacija je teža od izravne. Da biste vratili izvorni niz, morate učiniti sljedeće:
Napravite praznu n * n matricu, gdje je n broj znakova u kodiranoj poruci;
Ispunite krajnji desni prazan stupac kodiranom porukom;
Razvrstaj redove tablice leksikografskim redoslijedom;
Ponavljajte korake 2-3 dok ne bude praznih stupaca;
Vratite redak koji završava znakom za kraj reda.

Na prvi pogled, obrnuta transformacija je jednostavna, a jedna od opcija prikazana je u Listingu 4.

1. konst
2. EOMsg = "|" ;
3. funkcija BWTDecode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. ShiftTable: niz ShortString;
6. N, i, j: riječ;
7. početi
8. OutMsg: = "";
9. N: = duljina (InMsg);
10. SetLength (ShiftTable, N + 1);
11. za i: = 0 do N do
12. ShiftTable [i]: = "";
13. za i: = 1 do N do
14. početi
15. za j: = 1 do N do
16. ShiftTable [j]: = InMsg [j] + ShiftTable [j];
17. Sortiraj (ShiftTable);
18. kraj;
19. za i: = 1 do N do
20. ako je ShiftTable [i] [N] = EOMsg onda
21. OutMsg: = ShiftTable [i];
22. izbrisati (OutMsg, N, 1);
23. BWTDecode: = OutMsg;
24. kraj;

Ali u praksi, učinkovitost ovisi o odabranom algoritmu sortiranja. Trivijalni algoritmi kvadratne složenosti očito će imati izrazito negativan utjecaj na performanse, stoga se preporučuje korištenje učinkovitih algoritama.

Nakon sortiranja tablice dobivene u sedmom koraku, potrebno je iz tablice odabrati redak koji završava znakom "|". Lako je vidjeti da je ovo jedina linija. Da. ispitali smo BWT transformaciju na konkretnom primjeru.

Sumirajući, možemo reći da je glavna prednost RLE grupe algoritama jednostavnost i brzina rada (uključujući brzinu dekodiranja), a glavni nedostatak je neučinkovitost na skupovima znakova koji se ne ponavljaju. Korištenje posebnih permutacija povećava učinkovitost algoritma, ali također uvelike povećava vrijeme rada (osobito dekodiranje).

Kompresija rječnika (LZ algoritmi)

Skupina algoritama rječnika, za razliku od algoritama grupe RLE, ne kodira broj ponavljanja znakova, već prethodno naiđene nizove znakova. Tijekom rada algoritama koji se razmatraju, dinamički se stvara tablica s popisom prethodno naiđenih sekvenci i njihovih odgovarajućih kodova. Ova se tablica često naziva rječnikom, a odgovarajuća skupina algoritama naziva se rječnikom.

Najjednostavnija verzija algoritma rječnika opisana je u nastavku:
Inicijalizirati rječnik sa svim znakovima koji se pojavljuju u ulaznom nizu;
Pronađite u rječniku najduži niz (S) koji odgovara početku kodirane poruke;
Izdajte kod pronađenog niza i uklonite ga s početka kodirane poruke;
Ako ne dođe do kraja poruke, pročitajte sljedeći znak i dodajte Sc u rječnik, prijeđite na korak 2. U suprotnom izađite.

Na primjer, novoinicijalizirani rječnik za izraz "CUCKOOKUCHONKUPILACAPUCHON" prikazan je u tablici. 3:

Tijekom procesa kompresije, rječnik će biti nadopunjen sekvencama koje se nalaze u poruci. Proces nadopunjavanja rječnika prikazan je u tablici. 4.

Pri opisu algoritma namjerno je izostavljen opis situacije kada je rječnik popunjen. Ovisno o varijanti algoritma moguće je različito ponašanje: potpuno ili djelomično pražnjenje rječnika, zaustavljanje punjenja rječnika ili proširenje rječnika s odgovarajućim povećanjem širine koda. Svaki od ovih pristupa ima određene nedostatke. Na primjer, zaustavljanje dovršavanja rječnika može dovesti do situacije kada rječnik pohranjuje sekvence koje se javljaju na početku komprimiranog niza, ali se ne pojavljuju kasnije. Istodobno, brisanjem rječnika možete ukloniti česte sekvence. Većina korištenih implementacija, prilikom popunjavanja rječnika, počinje pratiti omjer kompresije, a kada padne ispod određene razine, rječnik se obnavlja. Zatim ćemo razmotriti najjednostavniju implementaciju koja prestaje nadopunjavati rječnik kada je pun.

Prvo, definirajmo rječnik kao zapis koji ne pohranjuje samo pronađene podnizove, već i broj podnizova pohranjenih u rječniku:

Prethodno susrećene podnizove pohranjuju se u niz Words, a njihovi kodovi su brojevi podnizova u ovom nizu.
Također definiramo funkcije za pretraživanje u rječniku i dodavanje u rječnik:

1. konst
2. MAX_DICT_LENGTH = 256;
3. funkcija FindInDict (D: TDictionary; str: ShortString): cijeli broj;
4. r: cijeli broj;
5. i: cijeli broj;
6. fl: boolean;
7. početi
8. r: = - 1;
9. ako je D. Broj riječi> 0 tada
10. početi
11. i: = D. Broj riječi;
12. fl: = lažno;
13. dok (ne fl) i (i> = 0) rade
14. početi
15. i: = i - 1;
16. fl: = D. Riječi [i] = str;
17. kraj;
18. kraj;
19. ako fl onda
20. r: = i;
21. FindInDict: = r;
22. kraj;
23. procedura AddToDict (var D: TDictionary; str: ShortString);
24. početi
25. ako D. Broj riječi< MAX_DICT_LENGTH then
26. početi
27. D. Broj riječi: = D. Broj riječi + 1;
28. SetLength (D. Words, D. WordCount);
29. D. Riječi [D. Broj riječi - 1]: = str;
30. kraj;
31. kraj;

Koristeći ove funkcije, proces kodiranja prema opisanom algoritmu može se implementirati na sljedeći način:

1. funkcija LZWEncode (InMsg: ShortString): TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: kratki niz;
4. D: TDictionary;
5. i, N: bajt;
6. početi
7. SetLength (OutMsg, duljina (InMsg));
8. N: = 0;
9. InitDict (D);
10. dok je duljina (InMsg)> 0 do
11. početi
12. tmpstr: = InMsg [1];
13. dok (FindInDict (D, tmpstr)> = 0) i (duljina (InMsg)> dužina (tmpstr)) rade
14. tmpstr: = tmpstr + InMsg [duljina (tmpstr) + 1];
15. ako FindInDict (D, tmpstr)< 0 then
16. izbrisati (tmpstr, duljina (tmpstr), 1);
17. OutMsg [N]: = FindInDict (D, tmpstr);
18. N: = N + 1;
19. izbrisati (InMsg, 1, duljina (tmpstr));
20. ako je duljina (InMsg)> 0 tada
21. AddToDict (D, tmpstr + InMsg [1]);
22. kraj;
23. SetLength (OutMsg, N);
24. LZWEncode: = OutMsg;
25. kraj;

Rezultat kodiranja bit će brojevi riječi u rječniku.
Proces dekodiranja svodi se na izravno dešifriranje kodova, pri čemu nema potrebe za prijenosom stvorenog rječnika, dovoljno je da se tijekom dekodiranja rječnik inicijalizira na isti način kao i tijekom kodiranja. Tada će rječnik biti potpuno vraćen izravno tijekom procesa dekodiranja spajanjem prethodnog podniza i trenutnog simbola.

Jedini problem je moguć u sljedećoj situaciji: kada je potrebno dekodirati podniz koji još nije u rječniku. Lako je vidjeti da je to moguće samo kada je potrebno izdvojiti podniz koji se dodaje u trenutnom koraku. To znači da podniz odgovara cSc uzorku, tj. počinje i završava istim znakom. Štoviše, cS je podniz dodan u prethodnom koraku. Razmatrana situacija je jedina kada je potrebno dekodirati redak koji još nije dodan. Uzimajući u obzir gore navedeno, možemo predložiti sljedeću opciju za dekodiranje komprimiranog niza:

1. funkcija LZWDecode (InMsg: TEncodedString): ShortString;
2. D: TDictionary;
3. OutMsg, tmpstr: ShortString;
4. i: bajt;
5. početi
6. OutMsg: = "";
7. tmpstr: = "";
8. InitDict (D);
9. za i: = 0 do duljine (InMsg) - 1 do
10. početi
11. ako je InMsg [i]> = D. Broj riječi tada
12. tmpstr: = D. Riječi [InMsg [i - 1]] + D. Riječi [InMsg [i - 1]] [1]
13. drugo
14. tmpstr: = D. Riječi [InMsg [i]];
15. OutMsg: = OutMsg + tmpstr;
16. ako je i> 0 onda
17. AddToDict (D, D. Riječi [InMsg [i - 1]] + tmpstr [1]);
18. kraj;
19. LZWDecode: = OutMsg;
20. kraj;

Prednosti algoritama rječnika uključuju njihovu veću učinkovitost kompresije u usporedbi s RLE-om. Ipak, treba shvatiti da je stvarna uporaba ovih algoritama povezana s određenim poteškoćama u implementaciji.

Entropijsko kodiranje

Kodiranje sa Shannon-Fano stablima

Shannon-Fano algoritam jedan je od prvih razvijenih algoritama kompresije. Algoritam se temelji na ideji predstavljanja češćih znakova korištenjem kraćih kodova. Štoviše, kodovi dobiveni korištenjem Shannon-Fano algoritma imaju svojstvo prefiksa: tj. nijedan kod nije početak bilo kojeg drugog koda. Svojstvo prefiksa osigurava da je kodiranje jedan prema jedan. Algoritam za konstruiranje Shannon-Fano kodova prikazan je u nastavku:
1. Podijelite abecedu na dva dijela, ukupne vjerojatnosti simbola u kojima su što bliže jedan drugome.
2. Dodajte 0 prefiksnom kodu prvog dijela znakova, dodajte 1 kodu prefiksa drugog dijela znakova.
3. Za svaki dio (u kojem postoje najmanje dva znaka), rekurzivno izvedite korake 1-3.
Usprkos svojoj usporednoj jednostavnosti, Shannon-Fano algoritam nije bez nedostataka, od kojih je najznačajniji neoptimalno kodiranje. Iako je particioniranje u svakom koraku optimalno, algoritam ne jamči optimalan rezultat u cjelini. Razmotrimo, na primjer, sljedeći redak: "AAABVGDEZH". Odgovarajuće Shannon-Fano stablo i kodovi izvedeni iz njega prikazani su na Sl. 1:

Bez kodiranja, poruka će zauzeti 40 bita (pod pretpostavkom da je svaki znak kodiran s 4 bita), a korištenjem Shannon-Fano algoritma 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 bita. Glasnoća poruka smanjena je za 32,5%, ali će se u nastavku pokazati da se ovaj rezultat može značajno poboljšati.

Kodiranje s Huffman Trees

Algoritam Huffmanovog kodiranja, razvijen nekoliko godina nakon Shannon-Fano algoritma, također posjeduje svojstvo prefiksa, a uz to i dokazanu minimalnu redundanciju, upravo zbog toga je iznimno raširen. Za dobivanje Huffmanovih kodova koristi se sljedeći algoritam:
1. Svi simboli abecede su predstavljeni kao slobodni čvorovi, dok je težina čvora proporcionalna učestalosti simbola u poruci;
2. Iz skupa slobodnih čvorova biraju se dva čvora s minimalnom težinom i stvara se novi (roditeljski) čvor s težinom jednakom zbroju težina odabranih čvorova;
3. Odabrani čvorovi se uklanjaju s popisa slobodnih, a roditeljski čvor kreiran na njihovoj osnovi dodaje se na ovaj popis;
4. Koraci 2-3 se ponavljaju sve dok nema više od jednog čvora na popisu slobodnih;
5. Na temelju izgrađenog stabla svakom znaku abecede dodjeljuje se prefiksni kod;
6. Poruka je kodirana primljenim kodovima.

Razmotrimo isti primjer kao u slučaju Shannon-Fano algoritma. Huffmanovo stablo i dobiveni kodovi za poruku "AAABVGDEZH" prikazani su na Sl. 2:

Lako je izračunati da će veličina kodirane poruke biti 26 bita, što je manje nego u Shannon-Fano algoritmu. Zasebno, treba napomenuti da zbog popularnosti Huffmanovog algoritma, u ovom trenutku postoji mnogo opcija za Huffmanovo kodiranje, uključujući adaptivno kodiranje, koje ne zahtijeva prijenos frekvencija simbola.
Među nedostacima Huffmanovog algoritma značajan dio su problemi povezani sa složenošću implementacije. Upotreba stvarnih varijabli za pohranjivanje frekvencija simbola povezana je s gubitkom preciznosti, stoga se u praksi često koriste cjelobrojne varijable, ali budući da težina roditeljskih čvorova stalno raste, prije ili kasnije dolazi do prelijevanja. Stoga, unatoč jednostavnosti algoritma, njegova ispravna implementacija još uvijek može uzrokovati određene poteškoće, posebno za velike abecede.

Kodiranje sa stablima sekantne funkcije

Kodiranje korištenjem sekantne funkcije je algoritam koji su razvili autori koji omogućuje dobivanje prefiksnih kodova. Algoritam se temelji na ideji izgradnje stabla, čiji svaki čvor sadrži funkciju sekante. Za detaljniji opis algoritma potrebno je uvesti nekoliko definicija.
Riječ je uređeni niz od m bitova (broj m naziva se duljina riječi).
Sekantni literal je par tipa znamenka-vrijednost znamenke. Na primjer, literal (4,1) znači da 4 bita riječi moraju biti 1. Ako je literalni uvjet ispunjen, onda se literal smatra istinitim, inače je netočan.
K-bitni sekant je skup od k literala. Ako su svi literali istiniti, tada je i sama sekantna funkcija istinita, inače je lažna.

Stablo je izgrađeno tako da svaki čvor dijeli abecedu na najbliže moguće dijelove. Na sl. 3 prikazuje primjer sekantnog stabla:

Stablo sekantnih funkcija u općem slučaju ne jamči optimalno kodiranje, ali omogućuje iznimno veliku brzinu rada zbog jednostavnosti operacije u čvorovima.

Aritmetičko kodiranje

Aritmetičko kodiranje jedan je od najučinkovitijih načina komprimiranja informacija. Za razliku od Huffmanovog algoritma, aritmetičko kodiranje omogućuje kodiranje poruka s entropijom manjom od 1 bita po simbolu. Jer većina algoritama aritmetičkog kodiranja zaštićena je patentima, u nastavku će biti opisane samo osnovne ideje.
Pretpostavimo da u korištenoj abecedi postoji N simbola a_1, ..., a_N, s frekvencijama p_1, ..., p_N, redom. Tada će algoritam aritmetičkog kodiranja izgledati ovako:
Uzmite kao radni poluinterval)