Koristeći RLE algoritam, kodirajte niz znakova BBBBBBACCCABBBBBB

Zapišite rezultat kao heksadecimalne kodove (svaki znak je kodiran kao bajt, koji je predstavljen sa dvije heksadecimalne cifre). Provjerite rezultat pomoću RLE programa.

Dešifrirajte sekvencu upakovanu korištenjem RLE algoritma (dati su heksadecimalni kodovi): 01 4D 8E 41 01 4D 8E 4116. Koristite ASCII tablicu da odredite znakove prema njihovom heksadecimalnom kodu. U gornjoj tabeli, prvi red sadrži prvu cifru heksadecimalnog koda znakova, a drugi red sadrži drugu. Na primjer, znak "&" ima heksadecimalni kod 2616.

Odredite broj bajtova u originalnom i dekomprimiranom nizu i izračunajte omjer kompresije: Provjerite rezultat dobiven u prethodni stav, koristeći RLE program. Predložite dva načina za provjeru. Konstruirajte sekvence koje su komprimirane RLE algoritmom tačno 2 puta, 4 puta, 5 puta. Provjerite svoje odgovore pomoću RLE programa. Zamislite tri sekvence koje se ne mogu komprimirati pomoću RLE algoritma: Koristeći RLE program, primijenite RLE kompresiju na sljedeće datoteke i pronađite omjer kompresije za svaku od njih: Objasnite rezultate dobivene u prethodnom paragrafu:

Zašto ne mogu komprimirati slike JPEG format? zašto za dva crteža BMP format omjeri kompresije iste veličine prema RLE algoritmu su toliko različiti? Savjet: otvorite ove crteže u bilo kojem pregledniku.

Procijenite maksimalno dostižni omjer kompresije koristeći udžbeničku varijantu RLE algoritma. U kom slučaju se to može postići?
Procijenite omjer kompresije koristeći najgori RLE algoritam. Opišite ovaj najgori slučaj.

• tutorial

Davno, dok sam još bio naivan školarac, odjednom sam postao strašno znatiželjan: kako podaci u arhivama na magičan način zauzimaju manje prostora? Vozeći se svojim vjernim dialup-om, počeo sam surfati internetom u potrazi za odgovorom i pronašao mnogo članaka s prilično detaljnim prikazom informacija koje su me zanimale. Ali nijedno od njih tada nije izgledalo lako za razumjeti – popisi kodova su izgledali kao kineska slova, a pokušaji razumijevanja neobične terminologije i raznih formula bili su neuspješni.

Stoga je svrha ovog članka dati ideju o najjednostavnijim algoritmima kompresije onima kojima znanje i iskustvo još ne dopuštaju da odmah razumiju stručnu literaturu, ili čiji je profil potpuno daleko od takvih tema. One. Govorit ću o nekim od najjednostavnijih algoritama i navesti primjere njihove implementacije bez kilometarskih lista kodova.

Odmah ću vas upozoriti da neću razmatrati detalje implementacije procesa kodiranja i takve nijanse kao što je efikasna pretraga pojavljivanja niza. Članak će se dotaknuti samo samih algoritama i načina predstavljanja rezultata njihovog rada.

RLE - Kompaktnost uniformnosti

RLE algoritam je vjerovatno najjednostavniji od svih: njegova suština leži u kodiranju ponavljanja. Drugim riječima, uzimamo nizove identičnih elemenata i „slažemo“ ih u parove broj/vrijednost. Na primjer, niz poput "AAAAAAABCCCC" može se konvertirati u unos kao što je "8xA, B, 4xC". Ovo je, općenito, sve što trebate znati o algoritmu.

Primjer implementacije

Pretpostavimo da imamo skup nekih cjelobrojnih koeficijenata koji mogu imati vrijednosti od 0 do 255. Logično, došli smo do zaključka da je razumno pohraniti ovaj skup kao niz bajtova:
unsigned char podaci = ( 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2 , 2, 2, 255, 255, 255, 255, 255, 0, 0);

Mnogima će biti mnogo poznatije vidjeti ove podatke kao heksadecimalni dump:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF 00 00

Razmišljajući, odlučili smo da bi bilo dobro nekako komprimirati takve setove kako bismo uštedjeli prostor. Da bismo to učinili, analizirali smo ih i identificirali obrazac: vrlo često postoje podsekvence koje se sastoje od istih elemenata. Naravno, RLE je savršen za ovo!

Kodiramo naše podatke koristeći novostečeno znanje: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

Vrijeme je da nekako predstavimo naš rezultat na kompjuterski prilagođen način. Da bismo to učinili, u toku podataka moramo nekako odvojiti pojedinačne bajtove od kodiranih stringova. Budući da naši podaci koriste cijeli raspon vrijednosti bajta, neće biti moguće jednostavno dodijeliti bilo koji raspon vrijednosti ​​​za naše svrhe.

Postoje najmanje dva izlaza iz ove situacije:

1. Kao indikator komprimovanog lanca, izaberite jednu vrednost bajta, a u slučaju kolizije sa stvarnim podacima, pobegnite od njih. Na primjer, ako koristimo vrijednost 255 za "zvanične" svrhe, onda kada se ova vrijednost naiđe u ulaznim podacima, morat ćemo napisati "255, 255" i koristiti maksimalno 254 nakon indikatora.
2. Strukturirajte kodirane podatke, ukazujući na broj ne samo ponovljenih, već i narednih pojedinačnih elemenata. Tada ćemo unaprijed znati gdje su koji podaci.

Prva metoda u našem slučaju se ne čini efikasnom, pa ćemo, možda, pribjeći drugom.

Dakle, sada imamo dvije vrste sekvenci: nizove pojedinačnih elemenata (poput "4, 2, 0") i nizove identičnih elemenata (kao "0, 0, 0, 0, 0, 0"). Dodijelimo jedan bit u "servisnim" bajtovima za tip sekvence: 0 - pojedinačni elementi, 1 - identični. Uzmite za ovo, recimo, najznačajniji dio bajta.

U preostalih 7 bitova pohranit ćemo dužine sekvenci, tj. maksimalna dužina kodirane sekvence je 127 bajtova. Mogli bismo dodijeliti, recimo, dva bajta za uslužne svrhe, ali u našem slučaju su tako dugi nizovi izuzetno rijetki, pa ih je lakše i ekonomičnije jednostavno razbiti na kraće.

Ispostavilo se da ćemo u izlaznom toku prvo napisati dužinu niza, a zatim ili jednu ponovljena vrijednost, ili lanac neponavljajućih elemenata određene dužine.

Prva stvar koja bi vam trebala upasti u oči je da u ovoj situaciji imamo nekoliko neiskorišćenih vrijednosti. Ne mogu postojati sekvence nulte dužine, tako da možemo povećati maksimalna dužina do 128 bajtova, oduzimanjem jednog od dužine prilikom kodiranja i dodavanjem prilikom dekodiranja. Dakle, možemo kodirati dužine od 1 do 128 umjesto dužine od 0 do 127.

Druga stvar koju treba napomenuti je da ne postoje nizovi identičnih elemenata jedinične dužine. Stoga ćemo prilikom kodiranja od dužine takvih sekvenci oduzeti još jednu, čime ćemo povećati njihovu maksimalnu dužinu na 129 (maksimalna dužina lanca pojedinačnih elemenata je i dalje 128). One. lanci identičnih elemenata mogu imati dužinu od 2 do 129.

Hajdemo ponovo da kodiramo naše podatke, ali sada u obliku razumljivom računaru. Uslužne bajtove ćemo napisati kao , gdje je T tip sekvence, a L dužina. Odmah ćemo uzeti u obzir da dužine zapisujemo u modifikovanom obliku: pri T=0 oduzimamo jedan od L, pri T=1 - dva.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Pokušajmo dekodirati naš rezultat:

• . T=1, tada će se sljedeći bajt ponoviti L+2 (4+2) puta: 0, 0, 0, 0, 0, 0.
• . T=0, pa samo pročitajte L+1 (2+1) bajtova: 4, 2, 0.
• . T=1, ponovite sljedeći bajt 5+2 puta: 4, 4, 4, 4, 4, 4, 4.
• . T=1, ponovite sljedeći bajt 2+2 puta: 80, 80, 80, 80.
• . T=0, čitanje 0+1 bajtova: 0.
• . T=1, ponoviti bajt 2+2 puta: 2, 2, 2, 2.
• . T=1, ponovi bajt 3+2 puta: 255, 255, 255, 255, 255.
• . T=1, ponoviti bajt 0+2 puta: 0, 0.

I sada poslednji korak: pohraniti rezultat kao niz bajtova. Na primjer, par upakovan u bajt bi izgledao ovako:

Kao rezultat, dobijamo sljedeće:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

na tako jednostavan način, ovaj primjer od ulaznih podataka dobili smo 18 od 32 bajta.Nije loš rezultat, pogotovo ako se uzme u obzir da može biti mnogo bolji na dužim lancima.

Moguća poboljšanja

Efikasnost algoritma zavisi ne samo od samog algoritma, već i od načina na koji se implementira. Stoga je za različite podatke moguće razviti različite varijacije kodiranja i prezentacije kodiranih podataka. Na primjer, kada kodirate slike, možete napraviti lance promjenjive dužine: dodijeliti jedan bit za označavanje dugog lanca, a ako je postavljen na jedan, pohraniti dužinu iu sljedeći bajt. Na ovaj način žrtvujemo dužinu kratkih lanaca (65 elemenata umjesto 129), ali s druge strane omogućavamo kodiranje lanaca dužine do 16385 elemenata (2 14 + 2) sa samo tri bajta!

Dodatna efikasnost se može postići upotrebom heurističkih tehnika kodiranja. Na primjer, kodirajmo sljedeći lanac na naš način: "ABBA". Dobijamo " , A, , B, , A" - tj. Pretvorili smo 4 bajta u 6, naduvali originalne podatke za čak jedan i po puta! I što je više takvih kratkih naizmjeničnih heterogenih sekvenci, to je više suvišnih podataka. Ako ovo uzmemo u obzir, onda bismo rezultat mogli kodirati kao ", A, B, B, A" - potrošili bismo samo jedan dodatni bajt.

LZ77 - kratkoća u ponavljanju

LZ77 je jedan od najjednostavnijih i najpoznatijih algoritama u LZ porodici. Ime je dobio po svojim tvorcima: Abraham Lempel (Abraham L empel) i Jacob Ziv (Jacob Z iv). Brojevi 77 u naslovu znače 1977. godinu u kojoj je objavljen članak koji opisuje ovaj algoritam.

Glavna ideja je kodiranje identičnih nizova elemenata. Odnosno, ako se neki lanac elemenata pojavljuje više puta u ulaznim podacima, onda se sva njegova naknadna pojavljivanja mogu zamijeniti „vezama“ na njegovu prvu instancu.

Kao i ostali algoritmi ove porodice porodice, LZ77 koristi rečnik koji pohranjuje prethodno naiđene sekvence. Da bi to učinio, primjenjuje princip tzv. " klizni prozor': područje uvijek ispred trenutne pozicije kodiranja unutar koje možemo adresirati veze. Ovaj prozor je dinamički rečnik za ovaj algoritam- svaki element u njemu odgovara dva atributa: pozicija u prozoru i dužina. Iako u fizičkom smislu, ovo je samo dio sjećanja koji smo već kodirali.

Primjer implementacije

Pokušajmo sada nešto kodirati. Hajde da napravimo neki odgovarajući niz za ovo (unaprijed se izvinjavam zbog njegove apsurdnosti):

„Kompresija i dekompresija ostavlja utisak. Hahahahaha!"

Evo kako će to izgledati u memoriji (ANSI kodiranje):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 Kompresija
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 i dekompre
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 godišnji odmor i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 Hahah
0040: 61 68 61 68 61 21 ahaha!

Još se nismo odlučili za veličinu prozora, ali ćemo se složiti da je preko veličine kodirani niz. Pokušajmo pronaći sve nizove znakova koji se ponavljaju. String je niz znakova duži od jednog. Ako je lanac dio dužeg lanca koji se ponavlja, zanemarit ćemo ga.

“Kompresija i t de leave[an] i . Hah!”

Radi veće jasnoće, pogledajmo dijagram, gdje možemo vidjeti korespondenciju ponovljenih sekvenci i njihovih prvih pojavljivanja:

Možda je jedina nejasna točka ovdje sekvenca “Hahahahaha!”, jer niz znakova “ahahaha” odgovara kratkom nizu “ah”. Ali tu nema ničeg neobičnog, koristili smo neki trik koji omogućava algoritmu da ponekad radi kao RLE opisan ranije.

Činjenica je da ćemo prilikom raspakivanja pročitati navedeni broj znakova iz rječnika. A pošto je čitav niz periodičan, tj. podaci u njemu se ponavljaju sa određenim periodom, a simboli prvog perioda će biti neposredno ispred pozicije za raspakivanje, onda možemo ponovo kreirati ceo lanac od njih, jednostavno kopirajući simbole prethodnog perioda u sledeći.

Sredili smo to. Sada zamijenimo pronađena ponavljanja referencama na rječnik. Link ćemo napisati u formatu , gdje je P pozicija prvog pojavljivanja stringa u nizu, L je njegova dužina.

“Kompresija i t de ostavljaju i . Hah!”

Ali ne zaboravite da imamo posla s kliznim prozorom. Radi boljeg razumijevanja, tako da veze ne ovise o veličini prozora, apsolutne pozicije ćemo zamijeniti razlikom između njih i trenutne pozicije kodiranja.

“Kompresija i t de ostavljaju i . Hah!”

Sada samo trebamo oduzeti P od trenutne pozicije kodiranja da bismo dobili apsolutnu poziciju u nizu.

Vrijeme je da odlučite o veličini prozora i maksimalnoj dužini kodirane fraze. Budući da je riječ o tekstu, rijetko će se u njemu nalaziti posebno dugačke sekvence koje se ponavljaju. Dakle, hajde da dodijelimo, recimo, 4 bita za njihovu dužinu - ograničenje od 15 karaktera odjednom nam je sasvim dovoljno.

Ali veličina prozora već ovisi o tome koliko duboko ćemo tražiti iste lance. Budući da se radi o malim tekstovima, bilo bi dobro da broj bitova koje koristimo dopunimo na dva bajta: adresiraćemo veze u rasponu od 4096 bajtova, koristeći 12 bitova za ovo.

Iz iskustva s RLE znamo da se ne mogu koristiti sve vrijednosti. Očigledno, veza može imati minimalnu vrijednost od 1, stoga, da bi se adresa vratila u raspon 1..4096, moramo oduzeti jednu od veze prilikom kodiranja i dodati natrag kada dekodirati. Isto je i sa dužinama sekvenci: umesto 0..15 koristićemo opseg 2..17, pošto ne radimo sa nultim dužinama, a pojedinačni karakteri nisu sekvence.

Dakle, zamislimo naš kodirani tekst, uzimajući u obzir ove izmjene:

“Kompresija i t de ostavljaju i . Hah!”

Sada, opet, moramo nekako odvojiti komprimirane lance od ostatka podataka. Najčešći način je ponovno korištenje strukture i direktno ukazivanje gdje su podaci komprimirani, a gdje ne. Da bismo to učinili, podijelit ćemo kodirane podatke u grupe od osam elemenata (znakova ili linkova), a prije svake od ovih grupa ubacit ćemo bajt, gdje svaki bit odgovara tipu elementa: 0 za znak i 1 za a veza.

Delimo se u grupe:

• "The Comp"
• "remisija"
• "i t de"
• "ostavi"
• "i. hah"

Sastavljanje grupa:

"(0,0,0,0,0,0,0,0) Rezija komp(0,0,0,0,0,0,0,0) (0,0,0,0,0,1 ,0,0) i t de(1,0,0,0,0,0,1,0) ostavljaju (0,1,0,0,0,0,0,1) i . Hah(0)!"

Dakle, ako naiđemo na bit 0 tokom raspakivanja, onda jednostavno čitamo karakter u izlazni tok, ako je bit 1, čitamo vezu i referencom čitamo sekvencu iz rječnika.

Sada samo moramo grupisati rezultat u niz bajtova. Složimo se da koristimo bitove i bajtove redoslijedom od visokog prema nižem. Pogledajmo kako se veze pakuju u bajtove koristeći primjer:

Kao rezultat toga, naš komprimirani stream će izgledati ovako:

0000:00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Moguća poboljšanja

U principu, ovdje će biti istina sve što je opisano za RLE. Konkretno, da biste pokazali korisnost heurističkog pristupa u kodiranju, razmotrite sljedeći primjer:

„Dugo goooooong. Looooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooomnoga."

Nađimo sekvence samo za riječ "looooooower":

„Dugo goooooong. Vezani."

Da bismo kodirali takav rezultat, potrebna su nam četiri bajta po linku. Međutim, bilo bi ekonomičnije učiniti ovo:

„Dugo goooooong. Bio sam vezan."

Tada bismo potrošili jedan bajt manje.

Umjesto zaključka

Uprkos svojoj jednostavnosti i, čini se, ne prevelikoj efikasnosti, ovi algoritmi se i dalje široko koriste u različitim oblastima IT sfere.

Njihova prednost je jednostavnost i brzina, a složeniji i efikasniji algoritmi se mogu zasnivati ​​na njihovim principima i njihovim kombinacijama.

Nadam se da će suština ovih ovako navedenih algoritama pomoći nekome da shvati osnove i krene u pravcu ozbiljnijih stvari.

Čak i prije 10-15 godina, arhivatori su se uglavnom koristili za uštedu prostora na tvrdim diskovima i za smještaj što veće količine podataka na disketu. Međutim, vremena su se promijenila. Već duže vrijeme niko ne koristi flopi diskove kao sredstvo za prijenos i pohranjivanje informacija, a cijena drajvova je toliko niska da niko i ne pomišlja na komprimiranje podataka radi uštede prostora. Osim toga, količine podataka postale su toliko velike da njihovo arhiviranje i dearhiviranje radi uštede prostora jednostavno nije praktično, jer oduzima puno vremena. Pa, zaista, danas se količina podataka na diskovima korisnika mjeri u terabajtima. Sada zamislite koliko bi vremena trebalo da se arhivira jedan terabajt podataka. To će trajati ne jedan ili čak dva sata, već najmanje 10-12 sati, odnosno računar će morati ostati uključen cijelu noć.

Čini se da bi arhivisti danas trebali postepeno gubiti svoju relevantnost. Ali ništa slično se ne dešava. Velika većina korisnika, između ostalih programa, ima instalirane arhivatore ili koriste arhivator ugrađen u Windows operativni sistem (druge operativne sisteme ne razmatramo u ovoj publikaciji).

Činjenica je da je promijenjeno imenovanje arhivara. Danas se koriste prvenstveno za postavljanje podataka na web. Većina drajvera na web stranicama proizvođača nalazi se u arhivama, a većina programa na različitim resursima je također arhivirana. Usput, sam korisnik, prije nego što pošalje bilo kakve podatke na mrežu (na primjer, na resurse za dijeljenje datoteka), pakuje podatke u arhivu.

U vezi Rusko tržište, tada imamo najčešća tri arhivatora: WinRAR, WinZip i 7-Zip, predstavljena u 32- i 64-bitnoj verziji. Upravo njih ćemo uporediti u ovom članku. Međutim, prvo da pogledamo neke od njih teorijski aspekti arhivski rad.

Algoritmi kompresije informacija

Suština svakog algoritma kompresije informacija je da se nekom transformacijom početnog skupa bitova informacija na izlazu dobije određeni skup manji. Štaviše, svi algoritmi transformacije podataka mogu se uslovno podijeliti u dvije klase: reverzibilne i nepovratne.

Nepovratni algoritam kompresije informacija znači takvu transformaciju originalne sekvence bita, u kojoj izlazna sekvenca manje veličine ne dozvoljava da se ulazna sekvenca tačno vrati. Algoritmi nepovratne kompresije se koriste, na primjer, u odnosu na grafičke, video i audio podatke, a to uvijek dovodi do gubitka njihovog kvaliteta. Naravno, algoritmi za ireverzibilnu kompresiju podataka se ne koriste u arhivarima, pa ih stoga nećemo dalje razmatrati.

Algoritmi reverzibilne kompresije podataka omogućavaju vam da tačno vratite originalni niz podataka iz komprimovanog niza. Upravo ovi algoritmi se koriste u arhivarima. Opće karakteristike od svih algoritama kompresije su omjer kompresije (omjer volumena originalnog i komprimiranog niza podataka), stopa kompresije (vrijeme utrošeno na arhiviranje određene količine podataka) i kvalitet kompresije (vrijednost koja pokazuje koliko je jak niz podataka se komprimuje primjenom ponovne kompresije na njega prema ovom ili nekom drugom algoritmu).

Teorija kompresije informacija, poznata i kao teorija ekonomičnog kodiranja diskretnih informacija, prilično je složena grana matematičke nauke. Naravno, predstavljanje čak i njegovih osnova daleko je izvan okvira ovog članka, te ćemo stoga samo površno razmatrati različite algoritme kompresije informacija ne ulazeći u detalje. Osim toga, danas je razvijeno mnogo algoritama kompresije podataka, a njihovo razmatranje je također dio našeg zadatka. Stoga ćemo na kvalitativnom nivou govoriti samo o nekoliko algoritama koji nam omogućavaju da dobijemo opću predstavu o metodama kompresije informacija.

RLE algoritam

Jedna od najstarijih i najjednostavnijih metoda kompresije informacija je RLE (Run Length Encoding) algoritam, odnosno algoritam za kodiranje niza sekvenci. Ovaj metod je vrlo jednostavan za implementaciju i jedan je od algoritama za arhiviranje, a njegova suština je da se serija (grupa) ponovljenih bajtova zamijeni jednim bajtom kodiranja i brojačem za broj njihovih ponavljanja. Odnosno, grupa identičnih bajtova će biti zamijenjena parom:<счетчик повторений, значение>, što smanjuje redundantnost podataka.

U ovom algoritmu, predznak brojača su oni u gornja dva bita pročitanog bajta. Na primjer, ako su prva dva bita 11, tada se preostalih 6 bitova dodjeljuje brojaču, koji može imati vrijednosti od 1 do 64. Shodno tome, niz od 64 ponovljena bajta može se definirati sa samo dva bajta, tj. je, komprimiran za 32 puta.

Postoji još jedna implementacija ovog algoritma, kada je predznak brojača 1 u prvom bajtu brojača. U ovom slučaju, brojač može uzeti maksimalna vrijednost, jednako 127 - i stoga će maksimalni omjer kompresije biti jednak 64.

Jasno je da je RLE algoritam efikasan samo kada postoji veliki broj dugih grupa identičnih bajtova. Ako se bajtovi ne ponavljaju, tada korištenje RLE metode dovodi do povećanja veličine datoteke.

RLE metoda je općenito vrlo efikasna za komprimiranje bitmap grafike (BMP, PCX, TIF, GIF) jer sadrže vrlo duge serije ponavljajućih sekvenci bajtova.

Ograničenje abecede informacija

Još jedan prilično jednostavan način komprimiranja informacija može se nazvati ograničenjem informativna abeceda. Odmah napominjemo da se u praksi takav algoritam ne implementira, ali će prezentacija ove metode pomoći da se bolje razumije metoda kodova promjenjive dužine.

U daljem tekstu, pod informativnim alfabetom podrazumevaćemo skup simbola koji se koriste za kodiranje informativnog niza. Na primjer, pretpostavimo da postoji neka tekstualna poruka. Svako slovo ove poruke je kodirano pomoću ASCII tabele koja se sastoji od 256 znakova. U ovom slučaju, tačno 8 bitova (1 bajt) je dodijeljeno za kodiranje svakog znaka. U ovom slučaju, informativna abeceda je svih 256 znakova ASCII tablice kodiranja.

Jasno je da se svih 256 karaktera ASCII tabele ne može koristiti u originalnoj tekstualnoj poruci. Na primjer, ako mi pričamo za tekstualnu poruku na ruskom jeziku koja ne sadrži brojeve, dovoljna su 64 karaktera (33 mala i 31 veliko slovo). Ako ovome dodamo znakove interpunkcije, znakove pasusa i znakove za novi red, postaje jasno da broj znakova neće biti veći od 100. U ovom slučaju možete koristiti ne 8-, već 7-bitno kodiranje znakova, što vam omogućava da dobijete tabela od 128 znakova. To jest, mi, takoreći, ograničavamo informativnu abecedu, zbog čega možemo smanjiti bitnu dubinu svakog uporednog znaka. Možete ići dalje - da tačno odredite broj znakova koji se koriste u tekstualnoj poruci. Ako se, na primjer, ispostavi da se u poruci koristi samo 30 znakova (uključujući nove redove), tada se može koristiti 5-bitna tablica kodiranja koja sadrži 32 znaka, a onda će omjer kompresije tekstualne poruke postati još veći. Zaista, ako se u originalnoj poruci koristi 8-bitno kodiranje znakova, a u komprimiranoj poruci 5-bitno, tada će omjer kompresije biti 8/5.

Unatoč prividnoj jednostavnosti metode ograničavanja abecede, u praksi se ne koristi. Činjenica je da opisana metoda ne dozvoljava ispravno dekodiranje originalne poruke bez prijenosa Dodatne informacije. Zaista, bez poznavanja tablica kodiranja koje se koriste za komprimiranje informacija, nemoguće ih je dekodirati. Odnosno, uz kodiranu informacijsku sekvencu, potrebno je prenijeti i tablice kodiranja. Jasno je da je u ovom slučaju dobitak od korištenja ograničene abecede sveden na nulu.

Metoda ograničene abecede ima i druge nedostatke. Ako izvorna informativna poruka sadrži veliki broj različitih znakova, tada neće biti moguće smanjiti bitnu dubinu prikaza abecednih znakova, a ova metoda jednostavno neće raditi. Pretpostavimo, na primjer, da originalna informativna poruka sadrži 129 znakova iz abecede od 256 znakova. U ovom slučaju neće biti moguće koristiti 7-bitno kodiranje znakova, jer će 7 bita kodirati samo 128 znakova. Stoga, za 129 znakova, morat ćete koristiti isto 8-bitno kodiranje kao u originalnoj abecedi od 256 znakova.

Kodovi promjenjive dužine

Jedan od glavnih nedostataka metode hipotetičke restrikcije alfabeta koju smo razmotrili je da koristi uniformni kod kada svi znakovi informacionog alfabeta imaju istu dužinu (8,7 bita ili manje). Bilo bi logičnije koristiti takav sistem kodiranja u kojem dužina koda karaktera zavisi od učestalosti njegovog pojavljivanja u informativnoj poruci. Odnosno, ako se u originalnoj informativnoj poruci neki znakovi pojavljuju češće od drugih, onda je optimalno da ih koriste kratki kodovi, a za rijetke i duže.

Kao hipotetički primjer, razmotrite sljedeću informativnu poruku: "zračna nesreća" , koji sadrži 14 znakova. Pretpostavimo da imamo abecedu od 14 znakova koja nam omogućava da kodiramo ovu poruku. Ako se koristi uniformni kod, tada su potrebna 4 bita za svaki znak abecede (dužina koda od 4 bita će formirati 16 znakova). Međutim, lako je uočiti da se u našoj informativnoj poruci simbol "a" pojavljuje pet puta, simbol "t" - dva puta, a ostali simboli - jednom. Ako za simbol "a" koristimo kod od 2 bita, za simbol "t" - 3 bita, a za ostale znakove - 4 bita, onda svakako možemo uštedjeti. Potrebno je samo razumjeti kako se točno grade kodovi promjenjive dužine i kako točno dužina koda treba ovisiti o učestalosti simbola u informativnoj poruci.

Ako su svi znakovi uključeni u informativnu poruku sa istom frekvencijom (jednako vjerovatna), tada će s informativnom abecedom od N znakova svaki znak morati biti kodiran tačno log 2 N bit. U stvari, ovo je slučaj uniformnog koda.

Ako simboli imaju različitu vjerovatnoću pojavljivanja u informativnoj poruci, onda je, prema teoriji K. Shanona, simbol čija je vjerovatnoća jednaka p, optimalan i, što je posebno važno, teoretski je moguće pridruže kod dužine -log 2 str. Vraćajući se na naš primjer sa informativnom porukom "zračna nesreća" i s obzirom da je vjerovatnoća pojave znaka "a" (p(a)) 5/14, vjerovatnoća pojavljivanja znaka "t" je 2 /14, a vjerovatnoća pojave svih ostalih znakova je 1 /14, dobijamo da: za karakter "a" optimalna dužina koda je -log 2 (5/14) = 1,48 bita; za karakter "t" - -log 2 (2/14) = 2,8 bita, a za sve ostale znakove je -log 2 (1/14) = 3,8. Kako u našem slučaju dužina koda može imati samo cjelobrojnu vrijednost, onda, zaokružujući, dobijamo da je za simbol “a” optimalno koristiti kod od 2 bita, za simbol “t” - 3 bita, a za ostatak - 4 bita.

Izračunajmo omjer kompresije kada koristimo ovo kodiranje. Ako bi se koristio uniformni kod zasnovan na abecedi od 14 znakova, tada bi bilo potrebno 56 bita da se kodira riječ "zračna nesreća". Kada se koriste kodovi promjenjive dužine, bit će potrebni 5×2 bita + 2×3 bita + 7×4 bita = 44 bita, odnosno omjer kompresije će biti 1,27.

Sada razmotrite algoritme za dobijanje kodova promenljive dužine.

kodiranje prefiksa

Većina jednostavna metoda dobijanje kodova promenljive dužine je takozvano prefiksno kodiranje, koje vam omogućava da primate kodove celobrojne dužine. glavna karakteristika prefiks kodova leži u činjenici da se unutar svakog njihovog sistema kraći kodovi ne poklapaju sa početkom (prefiksom) dužih kodova. Ovo svojstvo prefiksnih kodova čini vrlo lakim dekodiranje informacija.

Objasnimo ovo svojstvo prefiksnih kodova na konkretnom primjeru. Neka postoji sistem od tri prefiksna koda: (0, 10, 11). Kao što vidite, kraći kod 0 se ne poklapa sa početkom dužih kodova 10 i 11. Neka kod 0 specificira znak "a", kod 10 znak "m", a kod 11 znak "p". Zatim se riječ "okvir" kodira sekvencom 110100. Pokušajmo dekodirati ovu sekvencu. Pošto je prvi bit 1, prvi znak može biti samo "m" ili "p" i određen je vrijednošću drugog bita. Pošto je drugi bit 1, prvi znak je "p". Treći bit je 0 i jedinstveno odgovara znaku "a". Četvrti bit je 1, odnosno potrebno je pogledati vrijednost sljedećeg bita, koji je 0, zatim je treći znak "m". Posljednji bit je 0, što se jedinstveno podudara sa znakom "a". Dakle, svojstvo prefiksnih kodova, koje se sastoji u tome da se kraći kodovi ne mogu poklopiti sa početkom dužih kodova, omogućava nedvosmisleno dekodiranje informativne poruke kodirane prefiksnim kodovima promenljive dužine.

Prefiksni kodovi se obično dobijaju konstruisanjem koda (za binarni sistem) drveće. Svaki unutrašnji čvor takvog binarnog stabla ima dvije izlazne ivice, pri čemu jedna ivica odgovara binarnom simbolu "0", a druga - "1". Radi određenosti, možemo se složiti da lijevoj ivici treba dodijeliti simbol "0", a desnoj ivici - simbolu "1".

Pošto u stablu ne može biti ciklusa, uvijek može postojati samo jedna ruta od korijenskog čvora do lisnog čvora. Ako su rubovi stabla numerirani, onda svaka takva ruta odgovara nekom jedinstvenom binarnom nizu. Skup svih takvih sekvenci će formirati sistem prefiksnih kodova.

Za razmatrani primjer sistema od tri prefiksna koda: (0, 10, 11), koji definiraju simbole "a", "m" i "p", stablo koda je prikazano na Sl. jedan.

Rice. 1. Stablo koda za sistem
od tri prefiks koda: (0, 10, 11)

Pogodnost stabla predstavljanja prefiksnih kodova leži u činjenici da je struktura stabla ta koja omogućava formiranje kodova promenljive dužine koji ispunjavaju glavni uslov prefiksnih kodova, odnosno uslov da se kraći kodovi ne poklapaju sa početak dužih kodova.

Do sada smo razmatrali samo ideju prefiksnih kodova promenljive dužine. Što se tiče algoritama za dobijanje prefiksnih kodova, oni se mogu razviti dosta, ali najpoznatije su dvije metode: Shannon-Fano i Huffman.

Shannon-Fano algoritam

Ovaj algoritam za dobijanje prefiksnih kodova nezavisno su predložili R. Fano i K. Shannon, a glasi kako sledi. U prvom koraku se svi simboli početnog informacijskog niza sortiraju u opadajućoj ili rastućoj vjerovatnoći njihovog pojavljivanja (učestalosti njihovog pojavljivanja), nakon čega se uređeni niz simbola na nekom mjestu dijeli na dva dijela tako da se u svakom od njih zbir frekvencija simbola je približno isti. Kao demonstraciju, uzmite u obzir već poznatu riječ "zračna nesreća" .

Ako simboli koji čine data reč, poredanih u opadajućem redosledu učestalosti njihovog pojavljivanja, dobijamo sledeći niz: (a(5), m(2), v(1), u(1), k(1), c(1), p(1), o (1), f(1)) (u zagradama je naznačena učestalost ponavljanja simbola u riječi). Zatim, trebamo podijeliti ovaj niz na dva dijela tako da u svakom od njih zbir frekvencija simbola bude približno isti (koliko je to moguće). Jasno je da će sekcija proći između simbola "t" i "c", zbog čega se formiraju dva niza: (a (5), t (2)) i (u (1), u (1) ), k (1), c(1), p(1), o(1), φ(1)). Štaviše, zbroji učestalosti ponavljanja simbola u prvom i drugom nizu bit će isti i jednaki 7.

U prvom koraku dijeljenja niza znakova, dobijamo prvu cifru koda svakog znaka. Ovdje je pravilo jednostavno: za one znakove koji se nalaze u nizu s lijeve strane, kod će početi sa "0", a za one sa desne strane - sa "1".

Konkretno, niz (a(5), m(2)) će se podijeliti na dva odvojena znaka: a(5) i m(2) (nema drugih opcija podjele). Tada je druga cifra koda za simbol "a" "0", a za simbol "t" - "1". Pošto smo, kao rezultat dijeljenja niza, dobili pojedinačni elementi, tada više nisu djeljivi i za simbol "a" dobijamo šifru 00, a za simbol "t" - šifru 01.

Niz (in(1), u(1), k(1), c(1), p(1), o(1), f(1)) može se podijeliti na nizove (in(1), u( 1), k(1)) i (c(1), p(1), o(1), φ(1)), ili na (v(1), u(1), k(1) ), (c(1)) i (p(1), o(1), φ(1)).

U prvom slučaju, zbir frekvencija simbola u prvom i drugom nizu će biti 3 i 4, a u drugom slučaju 4 i 3, respektivno. Radi određenosti koristimo prvu opciju.

Za karaktere rezultirajućeg novog niza (v(1), u(1), k(1)) (ovo je lijevi niz), prve dvije cifre koda će biti 10, a za niz (c( 1), p(1), o(1), f(1)) - 11.

U našem primeru (sl. 2 i 3) dobija se sledeći sistem prefiksnih kodova: "a" - 00, "t" - 01, "c" - 100, "i" - 1010, "k" - 1011, "s" - 1100, "r" - 1101, "o" - 1110, "f" - 1111. Kao što vidite, kraći kodovi nisu početak dužih kodova, odnosno ispunjeno je glavno svojstvo prefiks kodova .

Rice. 2. Demonstracija Shannon-Fano algoritma

Rice. 3. Stablo kodova za riječ "zračna nesreća"
u Shannon-Fano algoritmu

Huffmanov algoritam

Hafmanov algoritam je još jedan algoritam za dobijanje prefiks kodova promenljive dužine. Za razliku od Shannon-Fano algoritma koji predviđa konstrukciju kodno stablo od vrha do dna, ovaj algoritam uključuje izgradnju kodnog stabla obrnutim redosledom, odnosno odozdo prema gore (od lisnih čvorova do korijenskog čvora).

U prvoj fazi, kao u Shannon-Fano algoritmu, početni niz simbola se sortira u opadajućem redoslijedu učestalosti ponavljanja simbola (elemenata niza). Za prethodno razmatrani primjer sa riječju "zračna nesreća" dobijamo sledeći sortirani niz elemenata: (a(5), m(2), b(1), u(1), k(1), c(1), p(1), o(1), f(1)).

Zatim se posljednja dva elementa niza zamjenjuju novim elementom S1, kojem se dodjeljuje ponavljanje jednako zbroju ponavljanja početni elementi. Zatim se vrši novo sortiranje elemenata niza u skladu sa njihovim ponavljanjem. U našem slučaju posljednja dva elementa o(1) i f(1) zamjenjuju se elementom S1(2), a novosređeni niz će imati oblik: (a(5), m(2), S1( 2), c(1) , u(1), k(1), c(1), p(1)).

Nastavljamo ovu proceduru zamjene dva poslednji elementi sekvence do novog elementa sa potpunom ponovljivošću i naknadnim razvrstavanjem niza u skladu sa ponovljivošću elemenata, doći ćemo u situaciju da u nizu ostane samo jedan element (slika 4).

Rice. 4. Demonstracija Huffmanovog algoritma
na primjeru riječi "zračna nesreća"

Istovremeno sa zamjenom elemenata i ponovnim sortiranjem niza, gradi se kodno binarno stablo. Algoritam za konstruisanje stabla je vrlo jednostavan: operacija kombinovanja (zamena) dva elementa niza generiše novi element čvora na stablu koda. Odnosno, ako pogledate stablo odozdo prema gore, rubovi kodnog stabla uvijek dolaze od zamijenjenih elemenata i konvergiraju na novom elementu čvora koji odgovara elementu niza dobivenog zamjenom (slika 5). U tom slučaju, lijevoj ivici kodnog stabla može se dodijeliti vrijednost "0", a desnom rubu - "1". Ove vrijednosti će kasnije poslužiti kao elementi prefiks kod.

Rice. 5. Izgradnja kodnog stabla
u Huffman algoritmu
(zamjena elemenata "o" i "f"
novi element S1)

Kompletno Huffmanovo kodno stablo za jednu riječ "zračna nesreća" prikazano na sl. 6.

Rice. 6. Puno stablo koda za riječ "zračna nesreća",
izgrađen prema Huffman algoritmu

Hodajući po rubovima stabla kodova od vrha do dna, lako je dobiti prefiksne kodove za sve znakove naše informativne abecede:

Sada ako pokušate napisati riječ "zračna nesreća" u Huffman kodiranju, dobijamo 41-bitnu sekvencu 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Zanimljivo je napomenuti da kada se koristi Shannon-Fano prefiks kodova, dobijamo i kodove prefiksa41- riječ "zračna nesreća". To jest, u konkretnom primjeru, efikasnost kodiranja Huffmana i Shannon-Fana je ista. Ali ako uzmemo u obzir da prava abeceda informacija ima 256 znakova (a ne 14, kao u našem primjeru), a stvarne informacijske sekvence su datoteke bilo kojeg sadržaja i dužine, onda se postavlja pitanje o optimalnom kodu prefiksa, tj. , kod koji vam omogućava da dobijete minimalnu dužinu izlaznog niza.

Može se dokazati da je kodni sistem dobiven korištenjem Huffman algoritma najbolji među svim mogućim sistemima prefiksnih kodova u smislu da je dužina rezultirajućeg kodiranog informacijskog niza minimalna. To jest, Hafmanov algoritam je optimalan.

Glavni nedostatak Hafmanovog algoritma je složenost procesa konstruisanja sistema kodova. Ipak, optimalni Hafmanov algoritam je najčešći algoritam za generisanje koda varijabilne dužine i ugrađen je u većinu uslužnih programa za komprimovanje i arhiviranje informacija.

Aritmetičko kodiranje

Kao što smo već napomenuli, prema Šenonovom kriterijumu, optimalan kod je onaj u kome je za svaki znak dodeljen kod dužine –log 2. str bit. A ako je, na primjer, vjerovatnoća određenog znaka 0,2, onda će optimalna dužina njegovog koda biti -log 2 0,2 ​​= 2,3 bita. Jasno je da prefiksni kodovi ne mogu dati takvu dužinu koda, pa stoga nisu optimalni. Općenito, dužina koda određena Šenonovim kriterijem je samo teorijska granica. Pitanje je samo koja metoda kodiranja vam omogućava da se što više približite ovoj teorijskoj granici. Prefiksni kodovi promenljive dužine su efikasni i prilično laki za implementaciju, ali ima ih više efikasne načine kodiranje, posebno algoritam aritmetičkog kodiranja.

Ideja aritmetičkog kodiranja je da umjesto kodiranja pojedinačnih znakova, kod se istovremeno dodjeljuje cijelom nizu informacija. Istovremeno, očito je da dužina koda po jednom pojedinačnom znaku ne mora biti cijeli broj. Zbog toga je ova metoda kodiranja mnogo efikasnija od kodiranja s prefiksom i konzistentnija je sa Šenonovim kriterijumom.

Ideja algoritma aritmetičkog kodiranja je sljedeća. Kao iu svim prethodno razmatranim metodama kodiranja, svaki simbol originalnog informacijskog niza karakterizira njegova vjerovatnoća. Originalnoj nekodiranoj sekvenci je dodijeljen poluinterval)