Jednostavna metoda kodiranja ( KODIRANJE DUŽINE RADA), koji uspješno koriste popularni arhivisti.
Ova metoda se zasniva na brojanju dužine ponovljenih znakova u nizu i pisanju u upakovanu datoteku umjesto niza ovih znakova, ukucajte informacije: broj znakova i sam ponovljeni znak. Na primjer, postoji niz poput " AAAAABBBCCCADDDEEL". Spakovat će se u niz kao što je " 5A3B3CADDEEL". Kao što se vidi iz primjera, niz od 5 slova "A" bio je upakovan u dva znaka "5" i "A", a nizovi "DD", "EE", "L" uopće nisu bili upakovani. , jer nema koristi od zamjene ovih znakova u niz tipa "dužina"+"slovo".
Prilikom implementacije pakovanja datoteke korištenjem ove metode, pojavljuju se poteškoće kao što je način na koji će raspakivač razlikovati kontrolne informacije od upakovane datoteke od raspakovanih podataka. Na primjer, kao u slučaju koji je gore razmotren, hoće li raspakivač razlikovati kontrolni znak "5" od raspakovanog znaka sa istim kodom? Postoje dvije opcije za rješavanje ovog problema:
(ja). Pronađite simbol koji se pojavljuje manje od ostalih ili se uopće ne pojavljuje u upakovanoj datoteci i koristite ga kao kontrolu. Nazovimo ga prefiksom radi pogodnosti u sljedećem objašnjenju. Sada će niz "AAAAA" biti konvertovan od strane pakera u prefiks (8 bitova), "A" (8 bitova), količinu (8 bitova), tj. 5 bajtova će biti zamenjeno sa tri. Ako se u izvornoj datoteci tokom pakiranja naiđe na bit sa prefiksnim kodom, tada se dva bajta s kodom prefiksa upisuju u rezultirajuću datoteku, a pomoću ove funkcije raspakivač će odrediti gdje je prefiks simbol, a gdje je kontrola informacije. Moguće su modifikacije ove metode, na primjer:
1. Broj kodiranih ne sa osam bita, već sa tri, četiri i tako dalje, što će povećati procenat pakovanja, ali će ograničiti maksimalnu dužinu ponovljenih karaktera koja se može spakovati u slučaju kodiranja sa tri bita (od 3 do 10, tj. .000=3, ...,111=10), a ako je dužina veća od 10 karaktera, spakujte po deset znakova.
2. Moguća je i druga modifikacija, kada se broj ponovljenih znakova kodira ne sa osam bita, već sa tri bita, a dužina ponovljenih karaktera je ograničena na 265. Postavlja se pitanje kako kodirati 256 različitih dužina u 3 bita. Ispostavilo se da je moguće, ali samo je raspon od 3 do 9, ako je dužina ponovljenih znakova veća od 9, tada je "111" u binarnom kodu napisano u tri bita, što je jednako "7". To znači da je prava dužina niza u sljedećem bajtu (8 bitova je dodijeljeno za dužine od 10 do 256 karaktera).
Evo nekoliko primjera:
Imamo sekvence:
a) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"
b) "CBBBBBBBBBBEEEEEEEEEEE"
Spakujmo ih:
1. Metodom RLE (engl. run-length encoding - pakovanje ponovljenih bajtova).
a) Uzmimo prefiks jednak "D", dobićemo:
"D", "D", "A", 5, "D", "B", 10, "C", "D", "A", 15.Procenat kompresije = 12 bajtova/32 bajta = 37,5%
U upakovanoj datoteci, bajt prefiksa je prvi bajt tako da raspakivač zna koji je bajt prefiks.
b) Uzmite prefiks jednak "A", iako u stvari paker to neće učiniti, jer u ovom nizu nema mnogo znakova, pa će arhivar uzeti neiskorišteni znak kao prefiks.
Upakovana sekvenca:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"Procenat kompresije = 10 bajtova/22 bajta = 45,5%
2. Pakujmo sada iste linije prema modifikaciji 1 RLE metode sa istim vrijednostima prefiksa kako bismo analizirali efikasnost.
"D" , "D" , "A" , 2 , "D" , "B" , 7 ,
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit"D" , "A" , 7 , "D" , "A" , 2
8 bit 8 bit 3 bit 8 bit 8 bit 3 bitProcenat kompresije=84 bita/(22*8) bita = 32,8%
"A" , "C" , "A" , "B" , 7 , "A" , "E" , 7 , "A" , "A"
8 bit 8 bit 8 bit 8 bit 4 bit 8 bit 8 bit 3 bit 8 bit 8 bitProcenat kompresije=70 bita/(22*8) bita = 39,8%
3. Sada provjerimo efikasnost posljednje modifikacije:
a) Pakovana sekvenca:
"D" , "D" , "A" , 2 , "D" , "B" , 7 , 0
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit 8 bit"D", "A", 7, 5
8 bita 8 bita 3 bita 8 bitaPostotak kompresije = 81 bita/(32*8) bita = 31,6%
b) Pakovana sekvenca:
"A" , "C" , "A" , "B" , 7 , 0 , "A" , "E"
8 bit 8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 8 bit7 , 0 , "A" , "A"
3 bita 8 bita 8 bita 8 bitaPostotak kompresije = 86 bita/(22*8) bita = 48,9%
Ovi primjeri pokazuju da je, ovisno o sadržaju upakovanih podataka, efikasan ili jedan ili drugi algoritam, pa da biste odabrali koji je algoritam efikasniji, potrebno ih je testirati na različitim tipovima datoteka.
(II). Druga opcija za snimanje kontrolnih informacija za raspakivač je sljedeća: ako se u tekstu pojavi jedan znak, tada se jedan kontrolni bit jednak jednom i sam ovaj znak upisuje u izlaznu datoteku. Ako postoji niz ponovljenih bajtova, na primjer "AAAAAA", tada će upakovane informacije izgledati ovako: 0 (1 bit), bajt A (8 bita), count (3-8 bita);
Dajemo primjer radi jasnoće. Da biste to učinili, uzmite sekvence iz prethodnih primjera.
1) Broj ponovljenih bajtova je kodiran u 8 bitova.
a) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C" , 0 , "A" , 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.Procenat kompresije = 71 bita/256 bita = 27,7%
b) 1 , "C" , 0 , "B" , 10 , 0 , "E" , 10 , 1 , "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.Postotak kompresije = 52 bita/176 bita = 29,5%
2) Sada uzmimo 3 bita za kodiranje broja ponovljenih bajtova, u kojima se mogu kodirati vrijednosti od 2 do 8 (0 - 6), ako je dužina ponavljajuće sekvence veća, onda ova tri bita sadrže "111" (7 decimala), a prava dužina je u sljedećem bajtu (dužina od 9 do 264).
a) 0 , "A" , 3 , 0 , "B" , 7 , 1 , 0 , "C" , 0 , 0 , "A" , 7 , 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.Postotak kompresije = 64 bita/256 bita = 20,3%
b) 1 , "C" , 0 , "B" , 7 , 1 , 0 , "E" , 7 , 1 , 1, "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.Postotak kompresije = 58 bita / 176 bita = 33%
Ako je količina kodirana u 4 bita (2..16), onda
1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.Postotak kompresije = 44 bita / 176 bita = 25%
Kao što možete vidjeti iz primjera, druga opcija pakiranja je efikasnija, jer komprimira sekvence koje počinju sa dva znaka, kojih je obično velika većina. Prva varijanta pakuje sekvence počevši od tri karaktera.
Osnovna klasifikacija algoritama reverzibilne kompresije
Postoji mnogo različitih praktičnih metoda kompresije bez gubitaka, koje imaju tendenciju da imaju različitu efikasnost za različite vrste podataka i različite količine. Međutim, ove metode se temelje na tri glavne klasične sheme kompresije:
Kodiranje serije sekvenci (RLE);
Metode statističke kompresije;
Metode kompresije rječnika (heurističke).
Kompresija metodom serijskog kodiranja: RLE algoritam
Najpoznatiji jednostavan pristup i reverzibilni algoritam kompresije je Run Length Encoding (RLE). Suština metoda ovog pristupa je zamjena lanaca ili serija bajtova koji se ponavljaju ili njihovih sekvenci sa jednim bajtom kodiranja i brojačem za broj njihovih ponavljanja. Problem sa svim sličnim metodama je odrediti način na koji bi algoritam za dekompresiju mogao razlikovati kodiranu seriju od drugih nekodiranih bajtova sekvenci u rezultirajućem toku bajtova. Rješenje problema se obično postiže postavljanjem naljepnica na početak kodiranih lanaca. Takve oznake mogu biti, na primjer, karakteristične vrijednosti bita u prvom bajtu kodiranog pokretanja, vrijednosti prvog bajta kodiranog rada i slično. Ove metode su obično prilično efikasne za kompresiju bitmapa. grafičke slike(BMP, PCX, TIF, GIF), jer potonji sadrže dosta dugih serija ponavljajućih sekvenci bajtova. Nedostatak RLE metode je prilično nizak omjer kompresije ili cijena kodiranja datoteka s malim brojem serija i, što je još gore, s malim brojem ponovljenih bajtova u nizu.
RLE algoritam se zasniva na ideji da se identifikuju ponovljeni nizovi podataka i zamene jednostavnijom strukturom koja specificira kod podataka i faktor ponavljanja. Na primjer, neka se da takav niz podataka koji je podložan kompresiji: 1 1 1 1 2 2 3 4 4 4 . U RLE algoritmu se predlaže da se zamijeni sljedećom strukturom: 1 4 2 2 3 1 4 3 , gdje je prvi broj svakog para brojeva šifra podataka, a drugi faktor ponavljanja. Ako je 1 bajt dodijeljen za pohranjivanje svakog elementa podataka ulazne sekvence, tada će cijela sekvenca zauzeti 10 bajtova memorije, dok će izlazna sekvenca (komprimirana verzija) zauzimati 8 bajtova memorije. Jasno je da će RLE algoritam dati bolji efekat kompresije sa većom dužinom niza ponovljenih podataka. U slučaju gornjeg primjera, ako ulazna sekvenca izgleda ovako: 1 1 1 1 1 1 3 4 4 4, tada će omjer kompresije biti 60%. U tom smislu, veća efikasnost RLE algoritma postiže se kompresijom grafičkih podataka (posebno za jednotonske slike).
Heuristički (rječnički) algoritmi kompresije (LZ, LZW) potražite redove u datoteci koji se ponavljaju i napravite rečnik fraza koje ste već naišli. Tipično, takvi algoritmi imaju niz specifičnih parametara (veličina međuspremnika, maksimalna dužina fraze, itd.), čiji izbor ovisi o iskustvu autora djela, a ti parametri se biraju na način da se postigne optimalan odnos vrijeme rada algoritma, omjer kompresije i lista datoteka koje se dobro komprimiraju.
Statistički algoritmi(Huffman, Shannon-Fano, aritmetika) Statistički algoritmi koriste statistički model podataka, a kvalitet kompresije informacija direktno zavisi od toga koliko je ovaj model dobar. Uzimanje u obzir statističkih svojstava podataka u najjednostavnijem slučaju znači korištenje neuniformiranih kodova za kodiranje – znakovi koji se često pojavljuju se kodiraju kratkim kodovima, a rijetko dugim. Odnosno, takvi algoritmi moraju poznavati vjerovatnoće pojavljivanja znakova na slici, koje se u jednostavnom slučaju mogu procijeniti učestalošću pojavljivanja znakova u ulaznim podacima. Ove vjerovatnoće su po pravilu nepoznate. Svrha kodiranja je pretvaranje ulaznog toka u bit stream minimalne dužine, što se postiže smanjenjem entropije (haotičnosti) ulaznog toka uzimajući u obzir frekvencije simbola.
Dužina koda koji predstavlja znakove iz abecede toka mora biti proporcionalna količini informacija u ulaznom toku, a dužina znakova toka u bitovima ne smije biti višekratnik 8 ili čak varijabilna. Ako je poznata distribucija vjerovatnoće učestalosti pojavljivanja znakova iz abecede ulaznog toka, onda je moguće konstruirati optimalni model kodiranja. Međutim, zbog postojanja ogromnog broja različitih formata datoteka, zadatak postaje mnogo složeniji, jer. distribucija frekvencije simbola podataka nije unaprijed poznata. U ovom slučaju koriste se dva pristupa.
Prvo sastoji se u pregledavanju ulaznog toka i izgradnji kodiranja na osnovu prikupljene statistike (ovo zahtijeva dva prolaza kroz datoteku - jedan za pregled i prikupljanje statističke informacije, drugi - za kodiranje, što donekle ograničava obim ovakvih algoritama, jer, samim tim, postoji mogućnost jednoprolaznog kodiranja "u hodu", koji se koristi u telekomunikacionim sistemima, gde količina podataka ponekad nije poznata, a njihova ponovni prijenos ili raščlanjivanje mogu potrajati nerazumno dugo). U tom slučaju, entropijska šema korištenog kodiranja se upisuje u izlazni tok. Ova tehnika je poznata kao statičko Huffmanovo kodiranje. Tablica simbola se prenosi zajedno sa kompresovanom datotekom. Takvi algoritmi dosta dobro komprimiraju većinu datoteka, ali neophodan dodatni prijenos tablice frekvencije simbola, kao i potreba za dva prolaza izvorni fajl za prikupljanje i kompresiju statistike.
Druga metoda- metoda adaptivnog kodiranja. Njegov princip je mijenjanje šeme kodiranja ovisno o prirodi promjena u ulaznom toku. Prilagodljivo - počnite raditi sa fiksnom početnom tablicom frekvencija znakova (obično su svi znakovi u početku jednako vjerovatni) i u procesu rada ova tablica se mijenja ovisno o znakovima koji se pojavljuju u datoteci. Prednosti: algoritam sa jednim prolazom, nema potrebe za prijenosom tablice frekvencije simbola, prilično efikasno komprimira široku klasu datoteka. Ovaj pristup ima algoritam jednog prolaza i ne zahtijeva eksplicitno pohranjivanje informacija o korištenom kodiranju. Adaptivno kodiranje može dati veći stepen kompresije od statičkog kodiranja, budući da se promjene u frekvencijama ulaznog toka potpunije uzimaju u obzir. Ova tehnika je poznata kao dinamičko Huffmanovo kodiranje.
Imajući ovo na umu statistički algoritmi mogu se podijeliti u tri klase:
1. Neprilagodljivi - koristite fiksne, unaprijed određene vjerovatnoće simbola. Tabela vjerovatnoće simbola se ne prenosi sa datotekom jer je poznata unaprijed. Nedostatak: usko područje upotrebe za određenu tablicu frekvencija, za koje se postiže prihvatljiv omjer kompresije.
2. Poluadaptivna - za svaku datoteku se pravi tabela frekvencija znakova i datoteka se kompresuje na osnovu nje. Tablica simbola se prenosi zajedno sa kompresovanom datotekom. Takvi algoritmi prilično dobro komprimiraju većinu fajlova, ali je neophodan dodatni prijenos tablice frekvencije simbola, kao i potreba za dva prolaza izvorne datoteke za prikupljanje statistike i kompresiju.
3. Prilagodljivo - počnite da radite sa fiksnom početnom tabelom učestalosti karaktera (obično su svi karakteri u početku podjednako verovatni) i u procesu rada ova tabela se menja u zavisnosti od karaktera koji se javljaju u datoteci. Prednosti: algoritam sa jednim prolazom, nema potrebe za prijenosom tablice frekvencije simbola, prilično efikasno komprimira široku klasu datoteka.
Huffmanov algoritam je baziran na ideji kodiranja po grupama bitova. Prvo sprovedeno analiza frekvencija Zadaje se ulazni niz podataka, odnosno frekvencija pojavljivanja svakog karaktera koji se u njemu pojavljuje. Nakon toga, znakovi se sortiraju prema opadajućoj učestalosti pojavljivanja.
Osnovna ideja je da što je znak češći, to manje bitova kodira. Rezultat kodiranja se unosi u rečnik potreban za dekodiranje. Razmotrimo jednostavan primjer koji ilustruje rad Huffmanovog algoritma.
U statičkom Huffman kodiranju, ulaznim znakovima (nizovi bitova različite dužine) se dodeljuju nizovi bitova, takođe promenljive dužine - njihovi kodovi. Dužina koda svakog znaka uzima se proporcionalno binarnom logaritmu njegove frekvencije, uzetom sa suprotnim predznakom. ALI zajednički set svih različitih znakova koji se susreću čini abecedu toka. Ovo kodiranje je prefiksno, što ga čini lakim za dekodiranje u rezultujući tok, jer kod prefiksnog kodiranja kod bilo kojeg znaka nije prefiks koda bilo kojeg drugog znaka - abeceda je jedinstvena.
Čak i prije 10-15 godina, arhivari su korišteni uglavnom za uštedu prostora tvrdi diskovi i kako bi se na disketu smjestio maksimum podataka. 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 objavi bilo kakve podatke na mreži (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. Zajedničke karakteristike 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 jako niz podataka se komprimuje primjenom rekompresije na njega prema istom ili 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 za kompresiju podataka, a njihovo razmatranje je također dio našeg zadatka. Stoga ćemo samo kvalitativno opisati nekoliko algoritama koji nam omogućavaju da dobijemo opšta ideja 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. Ova metoda je vrlo jednostavna 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 nastavku ćemo pod informativnom abecedom podrazumijevati skup simbola koji se koriste za kodiranje informacijskog 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 govorimo o tekstualnoj poruci na ruskom, u kojoj nema brojeva, onda su dovoljna 64 znaka (33 mala i 31 veliko slovo). Ako ovome dodamo znakove interpunkcije, pasuse 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 znakove za novi red), tada se može koristiti 5-bitna tablica kodiranja koja sadrži 32 znaka, a zatim omjer kompresije tekstualna poruka postaće 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 dodatnih informacija. 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 varijabilne 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 za njih optimalno koristiti kratke kodove, a za znakove koji se rijetko pojavljuju koristiti 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 istu frekvenciju(jednako vjerovatno), tada sa informativnim alfabetom od N znakova, svaki znak će morati biti kodiran tačno log 2 N bit. U stvari, ovo je slučaj uniformnog koda.
Ako znakovi imaju različitu vjerovatnoću pojavljivanja u informativnoj poruci, onda je, prema teoriji K. Shanona, karakter čija je vjerovatnoća jednaka p optimalan i, što je posebno važno, teorijski je dozvoljeno 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 bitova, 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 pomoću konkretan primjer. 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 činjenici da se kraći kodovi ne mogu poklapati sa početkom dužih kodova, omogućava nedvosmisleno dekodiranje informativne poruke kodirane prefiksnim kodovima promenljive dužine.
Prefiksni kodovi se obično dobijaju pomoću stabala koda (za binarni sistem). Svaki unutrašnji čvor takvog binarnog stabla ima dvije izlazne ivice, a jedna ivica odgovara binarni simbol"0", a drugi - "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 se znakovi koji sačinjavaju datu riječ sortiraju u opadajućem redoslijedu u odnosu na njihovu učestalost pojavljivanja, dobijamo sljedeći niz: (a(5), m(2), b(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 odvojene elemente, oni se više ne dijele i za znak "a" dobijamo šifru 00, a za znak "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 prema dolje, ovaj algoritam podrazumijeva konstrukciju kodnog stabla obrnutim redoslijedom, odnosno odozdo prema gore (od listnih č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 sa novi element S1, kojem je dodijeljena ponovljivost jednaka zbiru ponovljivosti originalnih elemenata. 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. To jest, ako pogledate stablo odozdo prema gore, rubovi stabla kodiranja 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 koda prefiksa.
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 prefiksa za Shannon-Fano41- 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 prave 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 Huffmanovog algoritma najbolji među svima mogući sistemi prefiks kodovi 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 postoje efikasnije metode kodiranja, 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)
