Jednostavna metoda kodiranja ( KODIRANJE DUŽINE RADA), koji uspješno koriste popularni arhivisti.
Ova metoda temelji se na prebrojavanju duljine ponovljenih znakova u nizu i pisanju u zapakiranu datoteku umjesto informacija o slijedu tih znakova kao što su broj znakova i sam ponovljeni znak. Na primjer, postoji niz poput " AAAAABBBCCCADDDEEL". Bit će upakiran u niz kao što je" 5A3B3CADDEEL". Kao što možete vidjeti iz primjera, niz od 5 slova" A "bio je upakiran u dva znaka" 5 "i" A ", a nizovi "DD "," EE "," L "uopće nisu bili pakirani , budući da nema koristi od zamjene ovih znakova nizom tipa "dužina" + "slovo".
Prilikom realizacije pakiranja datoteke ovom metodom javljaju se sljedeće poteškoće: kako će raspakivač razlikovati kontrolnu informaciju od pakirane datoteke od nepakiranih podataka. Na primjer, kao u gore raspravljenom slučaju, hoće li raspakivač razlikovati kontrolni znak "5" od nepakiranog znaka s istim kodom? Postoje dvije opcije za rješavanje ovog problema:
(ja)... Pronađite simbol koji se susreće manje od ostalih ili se uopće ne pojavljuje u zapakiranoj datoteci i upotrijebite ga kao kontrolu. Nazovimo ga prefiksom radi praktičnosti u sljedećem objašnjenju. Sada će sekvenca "AAAAA" od strane pakera biti pretvorena u prefiks (8 bitova), "A" (8 bita), broj (8 bita), tj. 5 bajtova će biti zamijenjeno s tri. Ako se tijekom pakiranja u izvornoj datoteci naiđe na bit s prefiksnim kodom, tada se u rezultirajuću datoteku upisuju dva bajta s kodom prefiksa, a po ovom znaku raspakivač će odrediti gdje je prefiks simbol, a gdje kontrolne informacije. Moguće su modifikacije ove metode, na primjer:
1. Kodirajte količinu ne u osam bita, već u tri, četiri i tako dalje, što će povećati postotak pakiranja, ali istovremeno ograničiti maksimalnu duljinu ponovljenih znakova koja se može pakirati u slučaju kodiranja s tri bita (od 3 do 10, tj. . 000 = 3, ..., 111 = 10), a ako je duljina veća od 10 znakova, onda pakirajte po deset znakova.
2. Druga modifikacija je moguća, kada je broj ponovljenih znakova kodiran ne s osam bita, već s tri bita, a duljina ponovljenih znakova ograničena je brojem jednakim 265. Postavlja se pitanje kako kodirati 256 različite duljine u 3 bita. Ispada da je moguće, ali samo u rasponu od 3 do 9, ako je duljina ponovljenih znakova veća od 9, tada se tri bita zapisuju "111" u binarnom kodu, što je jednako "7". To znači da je prava duljina niza u sljedećem bajtu (8 bitova je dodijeljeno za duljine od 10 do 256 znakova).
Evo nekoliko primjera:
Imamo sekvence:
a) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"
b) "CBBBBBBBBBBEEEEEEEEEEE"
Spakujmo ih:
1. Korištenje RLE metode (kodiranje dužine trajanja - pakiranje ponovljenih bajtova).
a) Uzmimo prefiks jednak "D", dobivamo:
D, D, A, 5, D, B, 10, C, D, A, 15.Postotak kompresije = 12 bajtova / 32 bajta = 37,5%
U pakiranoj datoteci, prvi bajt je bajt prefiksa, tako da raspakivač zna koji je bajt prefiks.
b) Uzmite prefiks jednak "A", iako to zapravo paker neće učiniti, jer u ovom nizu nema puno znakova, pa će arhivator uzeti neiskorišteni znak kao prefiks.
Pakirani slijed:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"Postotak kompresije = 10 bajtova / 22 bajta = 45,5%
2. Sada zapakirajmo iste retke za modifikaciju 1 RLE metode s istim vrijednostima prefiksa kako bismo analizirali učinkovitost.
"D", "D", "A", 2, "D", "B", 7,
8 bita 8 bita 8 bita 3 bita 8 bita 8 bita 3 bita"D", "A", 7, "D", "A", 2
8 bita 8 bita 3 bita 8 bita 8 bita 3 bitaPostotak kompresije = 84 bita / (22 * 8) bita = 32,8%
"A", "C", "A", "B", 7, "A", "E", 7, "A", "A"
8 bita 8 bita 8 bita 8 bita 4 bita 8 bita 8 bita 3 bita 8 bita 8 bitaPostotak kompresije = 70 bita / (22 * 8) bita = 39,8%
3. Sada provjerimo učinkovitost posljednje izmjene:
a) Pakirani slijed:
"D", "D", "A", 2, "D", "B", 7, 0
8 bita 8 bita 8 bita 3 bita 8 bita 8 bita 3 bita 8 bita"D", "A", 7, 5
8 bita 8 bita 3 bita 8 bitaPostotak kompresije = 81 bita / (32 * 8) bita = 31,6%
b) Pakirani slijed:
"A", "C", "A", "B", 7, 0, "A", "E"
8 bita 8 bita 8 bita 8 bita 3 bita 8 bita 8 bita 8 bita7, 0, "A", "A"
3 bita 8 bita 8 bita 8 bitaPostotak kompresije = 86 bita / (22 * 8) bita = 48,9%
Iz ovih primjera može se vidjeti da je ovisno o sadržaju pakiranih podataka jedan ili drugi algoritam učinkovit, pa ih je, kako bismo odabrali koji je učinkovitiji, potrebno provjeriti na različitim vrstama datoteka.
(Ii)... Druga opcija za snimanje kontrolnih informacija za raspakivač je sljedeća: ako se u tekstu susreće jedan znak, tada se u izlaznu datoteku upisuje jedan kontrolni bit, koji je jednak jedinici i samom tom znaku. Ako se naiđe na slijed ponovljenih bajtova, na primjer "AAAAAA", tada će pakirane informacije izgledati ovako: 0 (1 bit), bajt A (8 bita), broj (3-8 bita);
Navedimo primjer radi jasnoće. Za to uzimamo 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.Postotak 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 uzimamo 3 bita za kodiranje broja ponovljenih bajtova, u koje možete kodirati vrijednosti od 2 do 8 (0 - 6), ako je duljina ponavljajućeg niza veća, tada ova tri bita sadrže "111 " (7-decimalno), a prava duljina je u sljedećem bajtu (duljina 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 učinkovitija jer komprimira sekvence koje počinju s dva znaka, koji su obično velika većina. Prva opcija pakirala je nizove koji počinju s tri znaka.
Osnovna klasifikacija algoritama reverzibilne kompresije
Postoji mnogo različitih praksi kompresije bez gubitaka koje općenito imaju različitu učinkovitost za različite vrste podataka i za različite veličine. Međutim, ove se metode temelje na tri glavne klasične sheme kompresije:
Kodiranje serije sekvenci (RLE);
Metode statističke kompresije;
Metode sažimanja rječnika (heurističke).
Kompresija serijskim kodiranjem: RLE algoritam
Najpoznatiji jednostavan pristup i algoritam za komprimiranje informacija na reverzibilan način je Run Length Encoding (RLE). Bit metoda ovog pristupa je zamijeniti nizove ili nizove bajtova koji se ponavljaju ili njihove sekvence s jednim bajtom kodiranja i brojačem broja njihovih ponavljanja. Problem sa svim analognim metodama je odrediti način na koji dekompresijski algoritam može razlikovati kodirane serije u rezultirajućem toku bajtova od drugih - nekodiranih bajtova. Rješenje problema obično se postiže stavljanjem oznaka na početak kodiranih nizova. Takve oznake mogu biti, na primjer, karakteristične vrijednosti bita u prvom bajtu kodiranog pokretanja, vrijednosti prvog bajta kodiranog pokretanja itd. Ove metode su u pravilu prilično učinkovite za komprimiranje rasterskih grafičkih slika (BMP, PCX, TIF, GIF), jer potonji sadrže dosta dugih serija ponavljajućih nizova 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 temelji se na ideji otkrivanja ponavljajućih nizova podataka i njihove zamjene jednostavnijom strukturom, koja specificira podatkovni kod i stopu ponavljanja. Na primjer, pretpostavimo da vam je dan niz podataka koji je podložan kompresiji: 1 1 1 1 2 2 3 4 4 4 ... RLE algoritam predlaže da se zamijeni sljedećom strukturom: 1 4 2 2 3 1 4 3 gdje je prvi broj svakog para brojeva podatkovni kod, a drugi je stopa ponavljanja. Ako je 1 bajt dodijeljen za pohranu svakog podatkovnog elementa ulaznog niza, tada će cijeli niz zauzeti 10 bajtova memorije, dok će izlazni slijed (komprimirana verzija) zauzimati 8 bajtova memorije. Jasno je da će RLE algoritam dati bolji učinak kompresije kada je duljina niza podataka koji se ponavljaju duža. U slučaju gornjeg primjera, ako ulazni slijed izgleda ovako: 1 1 1 1 1 1 3 4 4 4, tada će omjer kompresije biti 60%. S tim u vezi, veća učinkovitost RLE algoritma postiže se pri kompresiji grafičkih podataka (osobito za jednobojne slike).
Heuristički (rječnički) algoritmi kompresije (LZ, LZW) potražite retke u datoteci koji se ponavljaju i izgradite rječnik fraza koje ste već naišli. Obično takvi algoritmi imaju niz specifičnih parametara (veličina međuspremnika, maksimalna duljina fraze itd.), čiji odabir ovisi o iskustvu autora djela, a ti parametri se biraju na način da se postigne optimalan omjer vremena rada algoritma, omjera kompresije i popisa datoteka koje se dobro skupljaju.
Statistički algoritmi(Huffman, Shannon-Fano, aritmetika) Statistički algoritmi koriste statistički model podataka, a kvaliteta kompresije informacija izravno ovisi o tome koliko je ovaj model dobar. Uzimanje u obzir statističkih svojstava podataka u najjednostavnijem slučaju znači korištenje neuniformiranih kodova za kodiranje - simboli koji se često pojavljuju se kodiraju kratkim kodovima, a rijetko - dugim. Odnosno, takvi algoritmi trebaju poznavanje vjerojatnosti pojavljivanja znakova na slici, čija procjena može biti, u jednostavnom slučaju, učestalost pojavljivanja znakova u ulaznim podacima. Obično su te vjerojatnosti nepoznate. Svrha kodiranja je pretvaranje ulaznog toka u bit stream minimalne duljine, što se postiže smanjenjem entropije (kaosa) ulaznog toka uzimajući u obzir frekvencije simbola.
Duljina koda koji predstavlja znakove iz abecede toka mora biti proporcionalna količini informacija u ulaznom toku, a duljina simbola toka u bitovima ne smije biti višekratnik 8 ili čak varijabilna. Ako je poznata raspodjela vjerojatnosti učestalosti pojavljivanja simbola iz abecede ulaznog toka, tada se može konstruirati optimalni model kodiranja. Međutim, zbog postojanja ogromnog broja različitih formata datoteka, zadatak postaje puno kompliciraniji. frekvencijska raspodjela simbola podataka nije unaprijed poznata. U ovom slučaju koriste se dva pristupa.
Prvi sastoji se u pregledu ulaznog toka i građenju kodiranja na temelju prikupljene statistike (to zahtijeva dva prolaza kroz datoteku - jedan za pregled i prikupljanje statističkih informacija, drugi za kodiranje, što donekle ograničava opseg takvih algoritama, jer, na taj način, eliminira mogućnost jednoprolaznog kodiranja "u hodu" koje se koristi u telekomunikacijskim sustavima gdje se količina podataka ponekad ne zna, a njihov ponovni prijenos ili raščlanjivanje može potrajati nerazumno dugo). U tom slučaju, statistička shema korištenog kodiranja upisuje se u izlazni tok. Ova tehnika je poznata kao statičko Huffmanovo kodiranje. Sa komprimiranom datotekom prenosi se tablica simbola. Takvi algoritmi su prilično dobri u komprimiranju većine datoteka, ali je neophodan dodatni prijenos tablice frekvencije simbola, kao i potreba za dva prolaza izvorne datoteke za prikupljanje statistike i komprimiranje.
Metoda dva- metoda adaptivnog kodiranja. Njegov princip je promjena sheme kodiranja ovisno o prirodi promjena u ulaznom toku. Prilagodljivi - počinju raditi s fiksnom početnom tablicom frekvencija simbola (obično su svi simboli u početku jednako vjerojatni) i pritom se ova tablica mijenja ovisno o simbolima koji se nalaze u datoteci. Prednosti: algoritam s jednim prolazom, ne treba prenositi tablicu frekvencija simbola, prilično učinkovito komprimira široku klasu datoteka. Ovaj pristup ima algoritam s jednim prolazom i ne zahtijeva pohranjivanje informacija o korištenom kodiranju u eksplicitnom obliku. Adaptivno kodiranje može dati veći omjer 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 to na umu, statistički se algoritmi mogu podijeliti u tri klase:
1. Neprilagodljivi - koriste fiksne, unaprijed određene vjerojatnosti simbola. Tablica vjerojatnosti simbola se ne prenosi s datotekom jer je unaprijed poznata. Nedostatak: usko područje uporabe za određenu tablicu frekvencija, za koju se postiže prihvatljiv omjer kompresije.
2. Polu-prilagodljivo - za svaku datoteku se gradi tablica frekvencije simbola i na temelju nje se komprimira datoteka. Sa komprimiranom datotekom prenosi se tablica simbola. Takvi algoritmi su prilično dobri u komprimiranju većine datoteka, ali je neophodan dodatni prijenos tablice frekvencije simbola, kao i potreba za dva prolaza izvorne datoteke za prikupljanje statistike i komprimiranje.
3. Prilagodljivi - počinju raditi s fiksnom početnom tablicom frekvencija simbola (obično su svi simboli u početku jednako vjerojatni) i u procesu rada se ova tablica mijenja ovisno o simbolima koji se nalaze u datoteci. Prednosti: algoritam s jednim prolazom, ne treba prenositi tablicu frekvencija simbola, prilično učinkovito komprimira široku klasu datoteka.
Huffmanov algoritam temelji se na ideji kodiranja u bitnim grupama. Najprije se provodi frekvencijska analiza niza ulaznih podataka, odnosno postavlja se učestalost pojavljivanja svakog simbola koji se u njemu nalazi. Nakon toga, znakovi se razvrstavaju prema opadajućoj učestalosti pojavljivanja.
Osnovna ideja je sljedeća: što se znak češće pojavljuje, to je u manje bitova kodiran. Rezultat kodiranja unosi se u rječnik potreban za dekodiranje. Pogledajmo jednostavan primjer kako bismo ilustrirali kako funkcionira Huffmanov algoritam.
U statičkom Huffmanovom kodiranju, ulazni simboli (bitstrings različite duljine) su povezani s bitstringovima, a također i varijabilne duljine - njihovi kodovi. Duljina koda svakog simbola uzima se proporcionalno binarnom logaritmu njegove frekvencije, uzetom s suprotnim predznakom. A zajednički skup svih različitih simbola koji se susreću čini abecedu toka. Ovo kodiranje je prefiksno, što ga čini lakim za dekodiranje u tok rezultata, jer kod kodiranja s prefiksom kod bilo kojeg znaka nije prefiks koda bilo kojeg drugog znaka - abeceda je jedinstvena.
Još prije 10-15 godina, arhivari su se uglavnom koristili za uštedu prostora na tvrdim diskovima i kako bi stavili maksimalnu količinu podataka na disketu. Međutim, vremena su se promijenila. Nitko već duže vrijeme ne koristi diskete kao sredstvo za prijenos i pohranjivanje informacija, a cijena pogona je toliko niska da nitko niti ne razmišlja o komprimiranju podataka radi uštede prostora. Osim toga, količine podataka postale su toliko velike da je njihovo arhiviranje i dearhiviranje kako bi se uštedio prostor jednostavno nepraktično, jer je potrebno puno vremena. Doista, danas se količina podataka na diskovima korisnika mjeri u terabajtima. Sada zamislite koliko će vremena trebati za arhiviranje jednog terabajta podataka. To će trajati ne jedan ili čak dva sata, već najmanje 10-12 sati, odnosno računalo će morati ostati uključeno cijelu noć.
Čini se da bi arhivisti danas trebali postupno gubiti svoju važnost. Ali ništa od toga se ne događa. Velika većina korisnika, između ostalih programa, ima instalirane arhivatore ili koriste arhivator ugrađen u operacijski sustav Windows (druge operacijske sustave ne razmatramo u ovoj publikaciji).
Činjenica je da se promijenila svrha arhivara. Danas se prvenstveno koriste za učitavanje podataka na web. Većina drajvera na web stranicama proizvođača nalazi se u arhivama, a većina programa na raznim resursima također je arhivirana. Usput, sam korisnik, prije učitavanja bilo kakvih podataka na mrežu (na primjer, na resurse za dijeljenje datoteka), pakira podatke u arhivu.
Što se tiče ruskog tržišta, najčešća su nam tri arhivatora: WinRAR, WinZip i 7-Zip, predstavljeni u 32- i 64-bitnoj verziji. Usporedit ćemo ih u ovom članku. No, najprije, razmotrimo ukratko neke teorijske aspekte rada arhivara.
Algoritmi kompresije informacija
Bit svakog algoritma kompresije informacija sastoji se u činjenici da se nekom transformacijom početnog skupa bitova informacija na izlazu dobije određeni skup manje veličine. Štoviše, svi algoritmi pretvorbe podataka mogu se uvjetno podijeliti u dvije klase: reverzibilne i nepovratne.
Nepovratni algoritam kompresije informacija znači takvu transformaciju izvorne sekvence bitova u kojoj izlazni slijed manje veličine ne dopušta da se ulazna sekvenca precizno rekonstruira. Algoritmi nepovratne kompresije koriste se, primjerice, u odnosu na grafičke, video i audio podatke, a to uvijek dovodi do gubitka njihove kvalitete. Naravno, nepovratni algoritmi kompresije podataka se ne koriste u arhivarima i stoga ih nećemo razmatrati u budućnosti.
Algoritmi reverzibilnog sažimanja podataka omogućuju vam da precizno rekonstruirate izvorni niz podataka iz komprimirane sekvence. Upravo se ti algoritmi koriste u arhivarima. Zajedničke karakteristike svih algoritama kompresije su omjer kompresije (omjer volumena izvornog i komprimiranog niza podataka), stopa kompresije (vrijeme potrebno za arhiviranje određene količine podataka) i kvaliteta kompresije (vrijednost koju pokazuje koliko je niz podataka komprimiran primjenom ponovnog kompresije na njega.prema istom ili drugačijem algoritmu).
Teorija kompresije informacija, također poznata kao teorija ekonomičnog kodiranja diskretnih informacija, prilično je složena grana matematičke znanosti. Naravno, prikaz čak i njegovih osnova daleko nadilazi okvire 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 također je uključeno u naš zadatak. Stoga ćemo govoriti samo na kvalitativnoj razini o nekoliko algoritama koji vam omogućuju da dobijete opću ideju 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 njezina je bit zamijeniti niz (skupinu) ponovljenih bajtova s jednim bajtom kodiranja i brojačem broja njihovih ponavljanja. Odnosno, grupa identičnih bajtova bit će zamijenjena parom:<счетчик повторений, значение>, što smanjuje redundantnost podataka.
U ovom algoritmu, brojač je označen onima 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. Prema tome, niz od 64 ponovljena bajta može se odrediti sa samo dva bajta, da je, komprimiran 32 puta.
Postoji još jedna varijanta implementacije ovog algoritma, kada je atribut brojača 1 u prvom bajtu brojača. U tom slučaju brojač može poprimiti maksimalnu vrijednost od 127, pa će stoga maksimalni omjer kompresije biti 64.
Jasno je da je RLE algoritam učinkovit samo kada postoji veliki broj dugih skupina identičnih bajtova. Ako se bajtovi ne ponavljaju, tada korištenje RLE metode povećava veličinu datoteke.
RLE je općenito vrlo učinkovit za komprimiranje bitmap grafike (BMP, PCX, TIF, GIF) jer sadrže mnogo dugih serija ponavljajućih sekvenci bajtova.
Ograničenje abecede informacija
Druga prilično jednostavna metoda sažimanja informacija može se nazvati ograničavanjem abecede informacija. Odmah napominjemo da takav algoritam nije implementiran u praksi, ali prikaz ove metode pomoći će boljem razumijevanju metode kodova promjenjive duljine.
U nastavku pod informacijskom abecedom podrazumijevamo skup znakova koji se koriste za kodiranje informacijskog niza. Na primjer, recimo da postoji neka SMS poruka. ASCII tablica od 256 znakova koristi se za kodiranje svakog slova ove poruke. U ovom slučaju, točno 8 bitova (1 bajt) dodijeljeno je za kodiranje svakog znaka. U ovom slučaju, informacijska abeceda je svih 256 znakova ASCII tablice kodiranja.
Jasno je da se svih 256 znakova ASCII tablice ne smije koristiti u izvornoj tekstualnoj poruci. Na primjer, ako govorimo o tekstualnoj poruci na ruskom, u kojoj nema brojeva, tada su dovoljna 64 znaka (33 mala i 31 veliko slovo). Ako tome dodate interpunkcijske znakove, znakove odlomaka i nove retke, 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ćuje da dobijete tablica od 128 znakova. To jest, mi na neki način ograničavamo informacijsku abecedu, zbog čega možemo smanjiti bitnu dubinu svakog znaka koji se kolocira. Možete ići dalje - kako biste točno odredili broj znakova koji se koriste u tekstualnoj poruci. Ako se, na primjer, pokaže da je u poruci uključeno samo 30 znakova (uključujući znakove novog retka), tada možete koristiti 5-bitnu tablicu kodiranja koja sadrži 32 znaka, a tada će omjer kompresije tekstualne poruke postati još veći . Doista, ako izvorna poruka koristi 8-bitno kodiranje znakova, a komprimirana koristi 5-bitno, tada će omjer kompresije biti 8/5.
Unatoč naizgled jednostavnosti metode ograničavanja abecede, u praksi se ne koristi. Poanta je da opisana metoda ne dopušta ispravno dekodiranje izvorne poruke bez prijenosa dodatnih informacija. Doista, bez poznavanja tablica kodiranja koje se koriste za komprimiranje informacija, nemoguće ih je dekodirati. Odnosno, uz kodiranu informacijsku sekvencu, potrebno je prenijeti tablice kodiranja. Jasno je da je u ovom slučaju korist od korištenja ograničene abecede svedena 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 broj znamenki znakova abecede, a ova metoda jednostavno neće raditi. Pretpostavimo, na primjer, da izvorna podatkovna poruka sadrži 129 znakova iz abecede od 256 znakova. U ovom slučaju neće biti moguće koristiti 7-bitno kodiranje znakova, budući da će 7 bita dopustiti kodiranje samo 128 znakova. Stoga, za 129 znakova, morat ćete se vratiti na isto 8-bitno kodiranje kao u izvornoj abecedi od 256 znakova.
Kodovi promjenjive duljine
Jedan od glavnih nedostataka hipotetske metode ograničavanja abecede koju smo razmotrili je da koristi ujednačen kod kada svi simboli informacijske abecede imaju istu duljinu (8, 7 bita ili manje). Logičnije bi bilo koristiti takav sustav kodiranja u kojem duljina koda znakova ovisi o učestalosti njegovog pojavljivanja u informativnoj poruci. Odnosno, ako se u izvornoj informativnoj poruci neki znakovi nalaze češće od drugih, onda je optimalno koristiti kratke kodove za njih, a za rijetke, duže.
Kao hipotetski primjer, razmotrite sljedeću informativnu poruku: "Avionska nesreća" koji sadrži 14 znakova. Pretpostavimo da imamo abecedu od 14 znakova koja nam omogućuje kodiranje ove poruke. Ako se koristi ujednačen kod, tada su za svaki znak abecede potrebna 4 bita (duljina koda od 4 bita omogućit će formiranje 16 znakova). Međutim, lako je vidjeti da se u našoj informativnoj poruci simbol "a" pojavljuje pet puta, simbol "t" - dva puta, a ostali simboli - jednom. Ako za znak "a" koristimo kod duljine 2 bita, za znak "t" - duljinu od 3 bita, a za preostale znakove - duljinu od 4 bita, onda svakako možemo uštedjeti. Potrebno je samo razumjeti kako točno konstruirati kodove promjenjive duljine i kako točno duljina koda treba ovisiti o učestalosti pojavljivanja simbola u informativnoj poruci.
Ako svi znakovi ulaze u informacijsku poruku s istom učestalošću (jednako vjerojatnim), tada s informacijskom abecedom od N znakova, za kodiranje svakog znaka, točno log 2 N malo. Zapravo, ovo je slučaj jedinstvenog koda.
Ako simboli imaju različite vjerojatnosti pojavljivanja u informacijskoj poruci, tada je, prema teoriji K. Shannon-a, optimalan simbol s vjerojatnošću pojavljivanja jednakom p i, što je posebno važno, teoretski je dopušteno pridružiti kod duljine – dnevnik 2 str... Vraćajući se na naš primjer s informativnom porukom "avionska nesreća" i s obzirom da je vjerojatnost pojave simbola "a" (p (a)) 5/14, vjerojatnost pojave simbola "t" je 2 /14, a vjerojatnost pojave svih ostalih simbola je 1 / 14, dobivamo da je: za znak "a" optimalna duljina koda –log 2 (5/14) = 1,48 bita; za simbol "t" - –log 2 (2/14) = 2,8 bita, a za sve ostale simbole je –log 2 (1/14) = 3,8. Budući da u našem slučaju duljina koda može imati samo cjelobrojnu vrijednost, onda, zaokružujući, dobivamo da je za znak "a" optimalno koristiti kod duljine 2 bita, za znak "t" - duljina od 3 bita, a za ostatak - duljina od 4 bita.
Izračunajmo omjer kompresije pri korištenju ovog kodiranja. Kada bi se koristio ujednačeni kod baziran na abecedi od 14 znakova, tada bi bilo potrebno 56 bitova za kodiranje riječi "sudar aviona". Kada se koriste kodovi promjenjive duljine, potrebni su 5 × 2 bita + 2 × 3 bita + 7 × 4 bita = 44 bita, tako da je omjer kompresije 1,27.
Pogledajmo sada algoritme za dobivanje kodova promjenjive duljine.
Kodiranje prefiksa
Najjednostavniji način za dobivanje kodova promjenjive duljine je takozvano prefiksno kodiranje, koje vam omogućuje dobivanje kodova cjelobrojne duljine. Glavna značajka prefiksnih kodova je da se unutar svakog njihovog sustava kraći kodovi po dužini ne podudaraju s početkom (prefiksom) dužih kodova. Upravo ovo svojstvo prefiksnih kodova čini vrlo lakim dekodiranje informacija.
Objasnimo ovo svojstvo prefiksnih kodova konkretnim primjerom. Neka postoji sustav od tri prefiksna koda: (0, 10, 11). Kao što vidite, kraći kod 0 ne podudara se s 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 slijedom 110100. Pokušajmo dekodirati ovu sekvencu. Budući da je prvi bit 1, prvi znak može biti samo "m" ili "p" i određen je vrijednošću drugog bita. Budući da je drugi bit 1, prvi znak je "p". Treći bit je 0 i jedinstveno odgovara znaku "a". Četvrti bit je 1, odnosno trebate pogledati vrijednost sljedećeg bita, koji je 0, zatim je treći znak "m". Posljednji bit je 0, što jedinstveno odgovara znaku "a". Dakle, svojstvo prefiksnih kodova da se kraći kodovi ne mogu podudarati s početkom dužih kodova omogućuje nedvosmisleno dekodiranje informacijske poruke kodirane prefiksnim kodovima promjenjive duljine.
Prefiksni kodovi se obično dobivaju izgradnjom kodnih (za binarni sustav) stabala. Svaki unutarnji čvor takvog binarnog stabla ima dva izlazna ruba, pri čemu jedan rub odgovara binarnom znaku "0", a drugi - "1". Radi određenosti, možemo se složiti da lijevi rub treba biti povezan sa simbolom "0", a desni rub - simbolom "1".
Budući da u stablu ne može biti ciklusa, uvijek možete stvoriti jednu rutu od korijenskog čvora do lisnog čvora. Ako su rubovi stabla numerirani, tada svaka takva ruta odgovara nekom jedinstvenom binarnom nizu. Skup svih takvih sekvenci formirat će sustav prefiksnog koda.
Za razmatrani primjer sustava od tri prefiksna koda: (0, 10, 11), koji definiraju simbole "a", "m" i "p", stablo koda prikazano je na Sl. jedan.
Riža. 1. Stablo koda za sustav
od tri prefiksna koda: (0, 10, 11)
Pogodnost prikaza prefiksnih kodova u obliku stabla leži u činjenici da je struktura nalik stablu ta koja omogućuje generiranje kodova promjenjive duljine koji zadovoljavaju glavni uvjet prefiksnih kodova, odnosno uvjet da kraći kodovi ne podudaraju se s početkom dužih kodova.
Do sada smo gledali samo ideju prefiksnih kodova promjenjive duljine. Što se tiče algoritama za dobivanje prefiksnih kodova, njih ima dosta, ali najpoznatije su dvije metode: Shannon-Fano i Huffman.
Shannon-Fano algoritam
Ovaj algoritam za dobivanje prefiksnih kodova neovisno su predložili R. Fano i K. Shannon, a sastoji se u sljedećem. U prvom koraku se svi simboli izvornog informacijskog niza razvrstavaju po opadajućoj ili rastućoj vjerojatnosti njihovog pojavljivanja (učestalosti njihovog pojavljivanja), nakon čega se uređeni red simbola na nekom mjestu dijeli na dva dijela tako da se u svakom od njima je zbroj frekvencija simbola približno isti. Kao demonstraciju, razmotrite riječ koja nam je već poznata "Avionska nesreća" .
Ako se simboli koji sačinjavaju datu riječ razvrstaju silaznim redoslijedom njihove učestalosti pojavljivanja, tada dobivamo sljedeći niz: (a (5), t (2), u (1) i (1), do ( 1), c (1), p (1), o (1), f (1)) (u zagradama je navedena učestalost ponavljanja simbola u riječi). Zatim ovaj niz trebamo podijeliti na dva dijela tako da u svakom od njih zbroj frekvencija simbola bude približno isti (što je više moguće). Jasno je da će dio proći između simbola "t" i "b", zbog čega se formiraju dva niza: (a (5), t (2)) i (u (1) i (1) ), do (1), c (1), p (1), o (1), φ (1)). Štoviše, zbroji učestalosti ponavljanja simbola u prvom i drugom nizu bit će isti i jednaki 7.
U prvom koraku dijeljenja niza znakova dobivamo prvu znamenku koda svakog znaka. Pravilo je jednostavno: za one znakove koji se pojavljuju u slijedu s lijeve strane, kod će početi s "0", a za one s desne strane - s "1".
Konkretno, niz (a (5), m (2)) će se podijeliti na dva zasebna znaka: a (5) i m (2) (nema drugih podjela). Tada je druga znamenka koda za simbol "a" "0", a za simbol "t" - "1". Budući da smo kao rezultat dijeljenja niza dobili pojedinačne elemente, oni se više ne dijele i za simbol "a" dobivamo šifru 00, a za simbol "t" - šifru 01.
Niz (u (1), u (1), do (1), c (1), p (1), o (1), f (1)) može se podijeliti na nizove (u (1), i ( 1), k (1)) i (c (1), p (1), o (1), φ (1)), ili na (u (1), u (1), k (1) ), (c (1)) i (p (1), o (1), φ (1)).
U prvom slučaju, zbroji stopa ponavljanja simbola u prvom i drugom nizu bit će 3 odnosno 4, au drugom slučaju 4 odnosno 3. Radi jasnoće, koristit ćemo prvu opciju.
Za znakove rezultirajućeg novog niza (u (1) i (1), do (1)) (ovo je lijevi niz), prve dvije znamenke koda bit će 10, a za niz (c ( 1), p (1), o (1), φ (1)) - 11.
U našem primjeru (sl. 2 i 3) dobiva se sljedeći sustav prefiksnih kodova: "a" - 00, "t" - 01, "b" - 100, "u" - 1010, "k" - 1011, " c" - 1100, "p" - 1101, "o" - 1110, "f" - 1111. Kao što vidite, kraći kodovi nisu početak dužih kodova, odnosno ispunjeno je glavno svojstvo prefiksnih kodova.
Riža. 2. Demonstracija Shannon-Fano algoritma
Riža. 3. Stablo koda za riječ "avionska nesreća"
u Shannon-Fano algoritmu
Huffmanov algoritam
Huffmanov algoritam je još jedan algoritam za dobivanje prefiksnih kodova promjenjive duljine. Za razliku od Shannon-Fano algoritma, koji predviđa konstrukciju stabla kodiranja od vrha prema dolje, ovaj algoritam podrazumijeva konstrukciju stabla kodiranja obrnutim redoslijedom, odnosno odozdo prema gore (od čvorova lista do korijena). čvor).
U prvoj fazi, kao u Shannon-Fano algoritmu, izvorni slijed znakova se sortira u silaznom redoslijedu učestalosti ponavljanja znakova (elementa niza). Za gornji primjer s riječju "Avionska nesreća" dobivamo sljedeći sortirani niz elemenata: (a (5), t (2), u (1), u (1), k (1), c (1), p (1), o (1), φ (1 )).
Nadalje, posljednja dva elementa niza zamjenjuju se novim elementom S1, kojemu je dodijeljena ponovljivost jednaka zbroju ponovljivosti izvornih elemenata. Zatim se elementi niza ponovno sortiraju u skladu s njihovom ponovljivošću. U našem slučaju posljednja dva elementa o (1) i φ (1) zamjenjuju se elementom S1 (2), a novosređeni niz će imati oblik: (a (5), m (2), S1 ( 2), u (1) , u (1), k (1), c (1), p (1)).
Nastavljajući ovaj postupak zamjene posljednja dva elementa niza novim elementom s potpunom ponovljivošću i naknadnim razvrstavanjem niza u skladu s ponovljivošću elemenata, dolazimo do situacije da u nizu ostaje samo jedan element ( slika 4).
Riža. 4. Demonstracija Huffmanovog algoritma
koristeći primjer riječi "avionska nesreća"
Istovremeno sa zamjenom elemenata i ponovnim razvrstavanjem niza, gradi se stablo binarnog koda. Algoritam izgradnje stabla je vrlo jednostavan: operacija kombiniranja (zamjene) dva elementa niza generira novi čvor u 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 sekvence dobivenom zamjenom (slika 5). U tom slučaju lijevom rubu kodnog stabla može se dodijeliti vrijednost "0", a desnom - "1". Ove vrijednosti će nadalje služiti kao elementi koda prefiksa.
Riža. 5. Izgradnja kodnog stabla
u Huffman algoritmu
(zamjena elemenata "o" i "f"
novi element S1)
Dovršite Huffmanovo stablo koda za jednu riječ "Avionska nesreća" , prikazano na sl. 6.
Riža. 6. Kompletno stablo koda za riječ "avionska nesreća"
izgrađen Huffmanovim algoritmom
Hodajući po rubovima kodnog stabla od vrha do dna, lako je dobiti prefiksne kodove za sve simbole naše informacijske abecede:
Ako sada pokušate napisati riječ "Avionska nesreća" u Huffmanovom kodiranju dobivamo 41-bitni slijed 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Zanimljivo je primijetiti da pri korištenju Shannon-Fano prefiksnog slijeda dobivamo i kodove prefiksa41 riječ "avionska nesreća". To jest, u konkretnom primjeru, učinkovitost kodiranja Huffmana i Shannon-Fana je ista. Ali ako uzmemo u obzir da je prava informacijska abeceda 256 znakova (a ne 14, kao u našem primjeru), a stvarni informacijski nizovi su datoteke bilo kojeg sadržaja i dužine, onda se postavlja pitanje o optimalnom kodu prefiksa, tj. kod koji vam omogućuje da dobijete minimalnu duljinu izlaznog niza.
Može se dokazati da je sustav kodova dobiven korištenjem Huffmanovog algoritma najbolji među svim mogućim sustavima prefiksnih kodova u smislu da je duljina rezultirajućeg kodiranog informacijskog niza minimalna. Odnosno, Huffmanov algoritam je optimalan.
Glavni nedostatak Huffmanovog algoritma je složenost procesa konstruiranja sustava kodova. Ipak, Huffmanov optimalni algoritam je najčešći algoritam za generiranje koda varijabilne duljine i utjelovljen je u većini alata za kompresiju i arhiviranje informacija.
Aritmetičko kodiranje
Kao što smo već napomenuli, prema Shanonovom kriteriju, optimalan kod je onaj u kojem je za svaki znak dodijeljen kod duljine – log 2 str malo. A ako je, na primjer, vjerojatnost određenog znaka 0,2, tada će optimalna duljina njegovog koda biti –log 2 0,2 = 2,3 bita. Jasno je da kodovi prefiksa ne mogu osigurati takvu duljinu koda, pa stoga nisu optimalni. Općenito, duljina koda određena Shannonovim kriterijem samo je teorijska granica. Pitanje je samo koja metoda kodiranja vam omogućuje da se što više približite ovoj teoretskoj granici. Prefiksni kodovi promjenjive duljine učinkoviti su i prilično jednostavni za implementaciju, ali postoje učinkovitije metode kodiranja, posebice algoritam aritmetičkog kodiranja.
Ideja iza aritmetičkog kodiranja je da umjesto kodiranja pojedinačnih znakova, kod se istovremeno dodjeljuje cijelom informacijskom nizu. Očito je da duljina koda po jednom pojedinačnom znaku ne smije biti cijeli broj. Zato je ova metoda kodiranja mnogo učinkovitija od prefiksnog kodiranja i konzistentnija je sa Shannonovim kriterijem.
Ideja iza algoritma aritmetičkog kodiranja je sljedeća. Kao iu svim prethodno razmatranim metodama kodiranja, svaki simbol izvornog informacijskog niza karakterizira njegova vjerojatnost. Izvornoj nekodiranoj sekvenci dodijeljen je poluinterval)
