1. kod = sljedeći bit iz toka, dužina = 1
2. Ćao kod< base
   kod = kod<< 1
   kod = kod + sljedeći bit iz toka
   dužina = dužina + 1
3. simbol = simbol + kod - baza]

Drugim riječima, gurati ćemo bit po bit iz ulaznog toka u varijablu koda slijeva do koda< base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.

Pretpostavimo da se petlja u (2), nakon nekoliko iteracija, zaustavlja. U ovom slučaju, izraz (kod - baza) je serijski broj željenog čvora (simbola) na nivou dužine. Prvi čvor (simbol) koji se nalazi na nivou dužine u stablu nalazi se u nizu simbola na indeksnim isključenjima. Ali nas ne zanima prvi znak, već numerirani znak (kod - baza). Stoga je indeks traženog simbola u nizu simbola jednak (offs + (code - base)). Drugim riječima, željeni simbol simbol=symb + kod - baza].

Navedimo konkretan primjer. Koristeći opisani algoritam, dekodiramo poruku Z / .

Z / ="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 01 01 01 01 01 01 10 1 1"

1. kod = 0, dužina = 1
2. kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   dužina = 3 + 1 = 4
   kod = 1 = baza = 1
3. simbol = symb = 2 + kod = 1 - baza = 1] = symb = A

1. kod = 1, dužina = 1
2. kod = 1 = baza = 1
3. simbol = symb = 7 + kod = 1 - baza = 1] = symb = H

1. kod = 0, dužina = 1
2. kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 3 + 1 = 4
   kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   dužina = 4 + 1 = 5
   kod = 1 > baza = 0
3. simbol = symb = 0 + kod = 1 - baza = 0] = symb = F

Dakle, dekodirali smo prva 3 znaka: A, H, F. Jasno je da ćemo slijedeći ovaj algoritam dobiti upravo poruku S.

Proračun dužine koda

Da bismo kodirali poruku, moramo znati kodove znakova i njihove dužine. Kao što je navedeno u prethodnom odeljku, kanonski kodovi su u potpunosti određeni svojim dužinama. Dakle, naš glavni zadatak je izračunavanje dužine kodova.

Ispostavilo se da ovaj zadatak, u velikoj većini slučajeva, ne zahtijeva eksplicitnu konstrukciju Huffmanovog stabla. Štaviše, algoritmi koji koriste internu (ne eksplicitnu) reprezentaciju Hafmanovog stabla su mnogo efikasniji u smislu brzine i troškova memorije.

Danas postoji mnogo efikasnih algoritama za izračunavanje dužine koda (,). Ograničićemo se na razmatranje samo jednog od njih. Ovaj algoritam je prilično jednostavan, ali je unatoč tome vrlo popularan. Koristi se u programima kao što su zip, gzip, pkzip, bzip2 i mnogi drugi.

Vratimo se algoritmu za konstruisanje Hafmanovog stabla. Na svakoj iteraciji, izvršili smo linearnu pretragu za dva čvora s najmanjom težinom. Jasno je da je prioritetni red kao što je piramidalni (minimalni) pogodniji za ovu svrhu. Čvor sa najmanjom težinom imaće najveći prioritet i biće na vrhu piramide. Hajde da predstavimo ovaj algoritam.

Uključimo sve kodirane simbole u piramidu.

Iz piramide ćemo uzastopno izdvojiti 2 čvora (to će biti dva čvora s najmanjom težinom).

Hajde da se formiramo novi čvor i pričvrstite na njega, kao djeca, dva čvora uzeta iz piramide. U ovom slučaju postavljamo težinu formiranog čvora jednaku zbroju težina podređenih čvorova.

Uključimo formirani čvor u piramidu.

Ako postoji više od jednog čvora u piramidi, ponovite 2-5.

Pretpostavićemo da je za svaki čvor pohranjen pokazivač na njegov roditelj. U korijenu stabla postavljamo ovaj pokazivač jednak NULL. Odaberimo sada čvor (simbol) lista i, prateći sačuvane pokazivače, penjaćemo se po stablu sve dok sledeći pokazivač ne postane NULL. Poslednji uslov znači da smo stigli do korena drveta. Jasno je da je broj prelazaka sa nivoa na nivo jednak dubini lisnog čvora (simbola), a samim tim i dužini njegovog koda. Prolaskom kroz sve čvorove (simbole) na ovaj način dobijamo dužine njihovih kodova.

Maksimalna dužina koda

U pravilu se kod kodiranja koristi tzv šifrarnik (šifarnik), jednostavna struktura podataka, u suštini dva niza: jedan sa dužinama, drugi sa kodovima. Drugim riječima, kod (kao niz bitova) je pohranjen na memorijskoj lokaciji ili registru fiksne veličine (obično 16, 32 ili 64). Kako bismo spriječili prelijevanje, moramo biti sigurni da će kod stati u registar.

Ispostavilo se da na abecedi N znakova maksimalna veličina koda može biti dužine do (N-1) bita. Drugim riječima, sa N=256 (uobičajena opcija) možemo dobiti kod dug 255 bita (iako za ovo datoteka mora biti veoma velika: 2.292654130570773*10^53~=2^177.259)! Jasno je da se takav kod neće uklopiti u registar i sa njim treba nešto učiniti.

Prvo, hajde da saznamo pod kojim uslovima dolazi do prelivanja. Neka frekvencija i-tog simbola bude jednaka i-tom Fibonačijevom broju. Na primjer: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Konstruirajmo odgovarajuće Huffmanovo stablo.

ROOT /\ / \ / \ /\ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B

Takvo drvo se zove degenerisati. Da bi ga primili, frekvencije simbola moraju rasti barem onoliko koliko su Fibonačijevi brojevi ili čak i brže. Iako je u praksi, koristeći stvarne podatke, gotovo nemoguće dobiti takvo stablo, vrlo ga je lako generirati umjetno. U svakom slučaju, ova opasnost se mora uzeti u obzir.

Ovaj problem se može riješiti na dva prihvatljiva načina. Prvi od njih se oslanja na jedno od svojstava kanonskih kodova. Činjenica je da u kanonskom kodu (bit string) nijedan bitniji bit ne može biti različit od nule. Drugim riječima, svi ostali bitovi možda uopće neće biti sačuvani, jer uvijek su nula. U slučaju N=256, potrebno je samo pohraniti najmanje značajnih 8 bitova iz svakog koda, pod pretpostavkom da su svi ostali bitovi jednaki nuli. Ovo rješava problem, ali samo djelimično. Ovo će značajno zakomplicirati i usporiti i kodiranje i dekodiranje. Stoga se ova metoda rijetko koristi u praksi.

Drugi metod je da se veštački ograniči dužina kodova (bilo tokom izgradnje ili posle). Ova metoda je općenito prihvaćena, pa ćemo se na njoj detaljnije zadržati.

Postoje dvije vrste algoritama za ograničavanje dužine koda. Heuristički (približan) i optimalan. Algoritmi drugog tipa su prilično složeni za implementaciju i po pravilu zahtijevaju više vremena i memorije od prvog. Efikasnost heuristički ograničenog koda određena je njegovim odstupanjem od optimalno ograničenog koda. Što je ova razlika manja, to bolje. Vrijedi napomenuti da je za neke heurističke algoritme ova razlika vrlo mala ( , , ), i oni vrlo često generiraju optimalan kod (iako ne garantuju da će to uvijek biti slučaj). Štaviše, jer u praksi se prelivanje događa izuzetno rijetko (osim ako ne postoji vrlo striktno ograničenje na maksimalnu dužinu koda); s malom veličinom alfabeta preporučljivije je koristiti jednostavne i brze heurističke metode.

Pogledat ćemo jedan prilično jednostavan i vrlo popularan heuristički algoritam. Našao je svoju primjenu u programima kao što su zip, gzip, pkzip, bzip2 i mnogim drugim.

Problem ograničavanja maksimalne dužine koda je ekvivalentan problemu ograničavanja visine Hafmanovog stabla. Imajte na umu da po konstrukciji svaki nelisni čvor u Huffmanovu stablu ima tačno dva djeteta. Pri svakoj iteraciji našeg algoritma smanjit ćemo visinu stabla za 1. Dakle, neka je L maksimalna dužina koda (visina stabla) i želimo je ograničiti na L / < L. Neka je dalje RN i krajnji desni listni čvor na nivou i, a LN i je krajnji lijevi.

Počnimo sa radom od nivoa L. Pomerimo čvor RN L na mesto njegovog roditelja. Jer čvorovi idu u parovima; moramo pronaći mjesto za čvor pored RN L. Da bismo to uradili, nalazimo nivo j najbliži L, koji sadrži čvorove lista, tako da je j < (L-1). Umjesto LN j, formiraćemo nelisni čvor i priložiti mu kao podređeni čvor LN j i preostali neupareni čvor sa nivoa L. Primijeniti istu operaciju na sve preostale parove čvorova na nivou L. Jasno je da smo preraspodjelom čvorova na ovaj način smanjili visinu našeg stabla za 1. Sada je jednako (L-1). Ako sada L / < (L-1), onda ćemo isto učiniti sa nivoom (L-1) itd. dok se ne dostigne traženi limit.

Vratimo se na naš primjer, gdje je L=5. Ograničimo maksimalnu dužinu koda na L / =4.

ROOT /\ / \ / \ /\ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F

Može se vidjeti da je u našem slučaju RN L = F, j=3, LN j = C. Prvo pomjerimo čvor RN L = F na mestu svog roditelja.

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(nespareni čvor)

Sada na mjestu LN j = C Formiramo čvor bez lista.

ROOT /\ / \ / \ /\ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(nespareni čvor) C(nespareni čvor)

Pričvrstimo dva neuparena na formirani čvor: B I C.

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C

Stoga smo maksimalnu dužinu koda ograničili na 4. Jasno je da smo promjenom dužine koda malo izgubili u efikasnosti. Dakle, poruka S, kodirana takvim kodom, imat će veličinu od 92 bita, tj. 3 bita više u poređenju sa minimalno redundantnim kodom.

Jasno je da što više ograničimo maksimalnu dužinu koda, to će kod biti manje efikasan. Hajde da saznamo koliko možemo ograničiti maksimalnu dužinu koda. Očigledno ne kraće.

Računanje kanonskih kodova

Kao što smo više puta napomenuli, dužine kodova su dovoljne za generisanje samih kodova. Hajde da pokažemo kako se to može uraditi. Pretpostavimo da smo već izračunali dužine kodova i izbrojali koliko kodova svake dužine imamo. Neka je L maksimalna dužina koda, a T i broj kodova dužine i.

Izračunajmo S i - početna vrijednost kod dužine i, za sve i od

S L = 0 (uvijek)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (uvijek)

Za naš primjer, L = 5, T 1 .. 5 = (1, 0, 2 , 3, 2).

S 5 = 00000 bin = 0 dec
S 4 = (S 5 =0 + T 5 =2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dec
S 3 = (S 4 =1 + T 4 =3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dec
S 2 = (S 3 =2 + T 3 =2) >> 1 = (100 bin >> 1) = 10 bin = 2 dec
S 1 = (S 2 =2 + T 2 =0) >> 1 = (10 bin >> 1) = 1 bin = 1 dec

Može se vidjeti da su S 5, S 4, S 3, S 1 upravo znakovni kodovi B, A, C, H. Zajedničko ovim simbolima je da su svi prvi, svaki na svom nivou. Drugim riječima, pronašli smo početnu vrijednost koda za svaku dužinu (ili nivo).

Sada dodijelimo kodove preostalim simbolima. Šifra prvog znaka na nivou i je S i , drugog je S i + 1, trećeg je S i + 2, itd.

Zapišimo preostale kodove za naš primjer:

Može se vidjeti da smo dobili potpuno iste kodove kao da smo eksplicitno izgradili kanonsko Huffmanovo stablo.

Transfer stabla koda

Da bi kodirana poruka bila dekodirana, dekoder mora imati isto stablo koda (u ovom ili onom obliku) koje je korišteno tokom kodiranja. Stoga smo, zajedno sa kodiranim podacima, primorani da sačuvamo odgovarajuće stablo koda. Jasno je da što je kompaktniji, to bolje.

Postoji nekoliko načina za rješavanje ovog problema. Najviše očigledno rešenje- sačuvati stablo u eksplicitnom obliku (tj. kao uređeni skup čvorova i pokazivača jednog ili drugog tipa). Ovo je možda najrasipniji i najneefikasniji način. U praksi se ne koristi.

Možete pohraniti listu frekvencija simbola (tj. frekvencijski rečnik). Uz njegovu pomoć, dekoder može lako rekonstruirati kodno stablo. Iako je ova metoda manje rasipnička od prethodne, nije najbolja.

Konačno, možete koristiti jedno od svojstava kanonskih kodova. Kao što je ranije navedeno, kanonski kodovi su u potpunosti određeni svojim dužinama. Drugim riječima, sve što je dekoderu potrebno je lista dužina znakovnog koda. Uzimajući u obzir da se u prosjeku dužina jednog koda za N-znakovnu abecedu može kodirati u [(log 2 (log 2 N))] bitovima, dobijamo vrlo efikasan algoritam. Zadržat ćemo se na tome detaljnije.

Pretpostavimo da je veličina abecede N=256 i da komprimujemo običan tekstualnu datoteku(ASCII). Najvjerovatnije nećemo pronaći svih N znakova naše abecede u takvoj datoteci. Postavimo zatim dužinu koda znakova koji nedostaju jednaka nuli. U ovom slučaju, sačuvana lista dužina kodova će sadržavati dovoljno veliki broj nule (dužine koda znakova koji nedostaju) grupisane zajedno. Svaka takva grupa može se komprimirati korištenjem takozvanog grupnog kodiranja - RLE (Run - Length - Encoding). Ovaj algoritam je izuzetno jednostavan. Umjesto niza od M identičnih elemenata u nizu, pohranit ćemo prvi element ovog niza i broj njegovih ponavljanja, tj. (M-1). Primjer: RLE("AAABBBBCDDDDDD")=A3 B2 C0 D6.

Štaviše, ova metoda se može donekle proširiti. Možemo se prijaviti RLE algoritam ne samo na grupe nulte dužine, već i na sve ostale. Ova metoda prenošenja kodnog stabla je općenito prihvaćena i koristi se u većini modernih implementacija.

Implementacija: SHCODEC

Dodatak: biografija D. Huffmana

David Huffman rođen je 1925. godine u Ohaju, SAD. Huffman je diplomirao elektrotehniku ​​od državni univerzitet Ohajo (Ohio State University) sa 18 godina. Potom je služio u vojsci kao časnik radarske podrške na razaraču koji je pomagao u čišćenju mina u japanskim i kineskim vodama nakon Drugog svjetskog rata. Nakon toga je magistrirao na Univerzitetu Ohajo i doktorirao na Massachusetts Institute of Technology (MIT). Iako je Hafman najpoznatiji po razvoju metode za konstruisanje minimalno redundantnih kodova, dao je važan doprinos i mnogim drugim poljima (uglavnom elektronici). On dugo vremenaŠef Odsjeka za kompjuterske nauke na MIT-u. 1974. godine, već kao profesor emeritus, dao je ostavku. Huffman je dobio niz vrijednih nagrada. 1999 - Medalja Richarda W. Hamminga sa Instituta inženjera elektrotehnike i elektronike (IEEE) za izuzetan doprinos teoriji informacija, Louis E. Levy medalja sa Franklin instituta za njegovu doktorsku disertaciju o sekvencijalnim sklopnim krugovima, nagrada W. Wallacea McDowella, IEEE Computer Society Award i IEEE Golden Anniversary Technology Innovation Award 1998. U oktobru 1999., u 74. godini, David Huffman je umro od raka. R.L. Milidiu, A.A. Pessoa, E.S. Laber, "Efikasna implementacija algoritma zagrijavanja za konstrukciju prefiksnih kodova s ​​ograničenom dužinom", Proc. ALENEX-a (Međunarodna radionica o algoritamskom inženjerstvu i eksperimentiranju), str. 1-17, Springer, januar. 1999.

Danas je malo korisnika zainteresovano za pitanje u vezi sa mehanizmom kompresije datoteka. Proces rada sa PC U poređenju sa prošlošću, postalo je mnogo lakše za implementaciju.

Huffmanovi kodovi su postali prva opcija. Još uvijek se koriste u raznim arhivima. Većina korisnika čak i ne razmišlja o tome koliko je lako komprimirati datoteku pomoću ove sheme. IN ovu recenziju pogledat ćemo kako se vrši kompresija, koje karakteristike pomažu da se ubrza i pojednostavi proces kodiranja. Također ćemo pokušati razumjeti osnovne principe konstruiranja stabla kodiranja.

Algoritam: istorija

Prvi algoritam dizajniran za izvođenje efikasnog kodiranja elektronske informacije, postao je kod koji je predložio Huffman 1952. godine. To je taj kod koji se danas može smatrati osnovni element većina programa dizajniranih za kompresiju informacija. Neki od najpopularnijih izvora koji se koriste ovaj kod, danas su RAR arhive, ARJ, ZIP. Ovaj algoritam se također koristi za kompresiju JPEG slike I grafičkih objekata. Također, svi moderni faksovi koriste algoritam za kodiranje koji je izmišljen davne 1952. godine. Unatoč činjenici da je prošlo dosta vremena od stvaranja ovog koda, on se učinkovito koristi u opremi starog tipa, kao iu novoj opremi i školjkama.

Princip efikasnog kodiranja

Huffmanov algoritam baziran je na shemi koja vam omogućava zamjenu najvjerovatnijih i najčešćih znakova kodovima binarni sistem. Oni znakovi koji se pojavljuju rjeđe zamjenjuju se dugim kodovima. Prijelaz na duge kodove Huffman se izvodi tek nakon što je sistem iskoristio sve minimalne vrijednosti. Ova tehnika omogućava da se minimizira dužina koda po karakteru originalne poruke. IN u ovom slučaju Posebnost je u tome što već moraju biti poznate vjerovatnoće pojave slova na početku kodiranja. Konačna poruka će biti sastavljena od njih. Na osnovu ovih informacija, konstruiše se Huffmanovo kodno stablo. Na osnovu toga će se izvršiti proces kodiranja slova u arhivi.

Huffman kod: primjer

Da biste ilustrirali Huffmanov algoritam, razmotrite grafičku verziju konstrukcije kodnog stabla. Koristiti ovu metodu bio efikasniji, potrebno je razjasniti definiciju nekih vrijednosti koje su neophodne za koncept ove metode. Čitav skup čvorova i lukova koji su usmjereni od čvora do čvora naziva se graf. Samo drvo je graf sa skupom određenih svojstava. Svaki čvor ne smije sadržavati više od jednog od svih lukova. Jedan od čvorova mora biti korijen stabla. To znači da u njemu uopće ne bi trebalo biti uključenih lukova. Ako krenete od korijena kretanja duž lukova, tada bi vam ovaj proces trebao omogućiti da dođete do bilo kojeg čvora.

Huffmanovi kodovi također uključuju koncept lista drveta. Predstavlja čvor iz kojeg ne bi trebao nastati luk. Ako su dva čvora povezana lukom, onda je jedan od njih roditelj, a drugi dijete. Ako dva čvora imaju zajednički roditeljski čvor, oni se nazivaju bratski i sestrinski čvorovi. Ako, osim listova, čvorovi imaju nekoliko lukova, onda se takvo stablo naziva binarnim. To je upravo ono što je Hafmanovo drvo. Posebnost čvorova ove strukture je da je težina svakog roditelja jednaka zbroju težina djece čvora.

Huffmanovo drvo: konstrukcijski algoritam

Konstrukcija Huffmanovog koda se izvodi od slova ulazne abecede. Formira se lista čvorova koji su slobodni u budućem kodnom stablu. Na ovoj listi, težina svakog čvora mora biti ista kao vjerovatnoća pojavljivanja slova poruke koje odgovara ovaj čvor. Među nekoliko slobodnih čvorova odabire se onaj koji ima najmanju težinu. Ako se istovremeno promatraju minimalni pokazatelji u nekoliko čvorova, tada možete slobodno odabrati bilo koji par. Nakon toga, kreira se roditeljski čvor. Trebalo bi da teži isto kao i zbir datog para čvorova. Roditelj se zatim šalje na listu sa slobodnim čvorovima. Djeca se uklanjaju. Lukovi dobijaju odgovarajuće indikatore, nule i jedinice. Ovaj proces se ponavlja onoliko puta koliko je potrebno dok ne ostane samo jedan čvor. Nakon toga, binarne cifre se pišu od vrha do dna.

Kako poboljšati efikasnost kompresije

Da bi se poboljšala efikasnost kompresije, prilikom izgradnje kodnog stabla potrebno je koristiti sve podatke o vjerovatnoći pojavljivanja slova u određenom fajlu koji je priložen stablu. Ne bi trebalo dozvoliti da budu razbacani po velikom broju tekstualnih dokumenata. Ako prvo prođete ovaj fajl, tada možete dobiti statistiku o tome koliko često se slova pojavljuju iz objekta koji se kompresuje.

Kako ubrzati proces kompresije

Da bi se ubrzao rad algoritma, identifikaciju slova treba vršiti ne prema indikatorima pojavljivanja određenih slova, već po učestalosti njihovog pojavljivanja. Zahvaljujući tome, algoritam postaje jednostavniji, a rad s njim značajno se ubrzava. Ovo također omogućava izbjegavanje operacija dijeljenja i plutajućeg zareza. Takođe, kada radite u ovom režimu, algoritam se ne može menjati. Ovo je uglavnom zbog činjenice da su vjerovatnoće direktno proporcionalne frekvencijama. Također je vrijedno obratiti pažnju na činjenicu da će konačna težina korijenskog čvora biti jednaka zbroju broja slova u objektu koji se obrađuje.

Zaključak

Huffmanovi kodovi su jednostavan i dugo razvijen algoritam koji se još uvijek koristi u mnogima popularni programi. Jednostavnost i jasnoća ovog koda vam omogućavaju da to postignete efektivna kompresija datoteke bilo koje veličine.

Relativno jednostavan način kompresije podataka može se postići stvaranjem takozvanih Huffmanovih stabala na datoteci i korištenjem za kompresiju i dekomprimiranje podataka unutar nje. Za većinu aplikacija koriste se binarna Huffmanova stabla (na primjer, svaki čvor je ili list ili ima tačno dva podčvora). Moguće je, međutim, konstruisati Huffmanovo stablo bilo koji broj podstabla (na primjer, ternarna ili, in opšti slučaj, N-arno drveće).

Huffmanovo stablo za datoteku koja sadrži Z različiti likovi Ima Z listovi. Put od korijena do lista koji predstavlja određeni znak određuje kodiranje, a svaki korak duž puta do lista određuje kodiranje (koje može biti 0 , 1 , ..., (N-1)). Postavljanjem znakova koji se često pojavljuju bliže korijenu, a znakova koji se rjeđe pojavljuju dalje od korijena, postiže se željena kompresija. Strogo govoreći, takvo stablo će biti Huffmanovo stablo samo ako kodiranje rezultira korištenjem minimalnog broja N-ari znakovi za kodiranje date datoteke.

U ovom problemu ćemo razmotriti samo stabla gdje je svaki čvor ili interni čvor ili list za kodiranje znakova, i nema izoliranih listova koji ne kodiraju znak.

Slika ispod prikazuje primjer Huffmanovog ternarnog stabla, simboli " a" i " e" su kodirani pomoću jednog ternarnog znaka; znakovi koji se rjeđe pojavljuju " s" i " str" su kodirani pomoću dva ternarna znaka i znakova koji se najčešće pojavljuju " x", "q" i " y" su kodirani korištenjem po tri ternarna znaka.

Naravno, ako želimo možemo proširiti listu N-arnih simbola pa nazad, važno je znati koje stablo se koristi za kompresiju podataka. To se može učiniti na nekoliko načina. U ovom zadatku ćemo koristiti sledeća metoda: Ulaznom toku podataka će prethoditi zaglavlje koje se sastoji od vrijednosti kodiranih znakova Z nalazi se u izvorni fajl po leksikografskom redu.

Poznavanje broja ulaznih znakova Z, značenje N, što znači " N-arity" Huffmanovog stabla i samog zaglavlja, potrebno je pronaći primarno značenje kodiranih znakova.

Ulazni podaci

Ulazni podaci počinju cijelim brojem T, koji se nalazi u posebnom redu i označava broj narednih test slučajeva. Svako od sljedećeg je specificirano T test slučajevima, od kojih se svaki nalazi u 3 -x linije kako slijedi:

• Broj različitih znakova u testnom slučaju Z (2 ≤ Z ≤ 20 );
• Broj N, što znači " N-arnost" Hafmanovog drveta ( 2 ≤ N ≤ 10 );
• Niz koji predstavlja naslov primljene poruke, svaki znak će biti cifra u opsegu . Ovaj red će sadržavati manje 200 karaktera.

Bilješka: Iako rijetko, moguće je da naslov ima višestruka tumačenja kada se dešifruje (na primjer, za naslov " 010011101100 “, i vrijednosti Z=5 I N=2). Garantovano je da u svim test slučajevima predloženim u ulaznim podacima postoji jedinstveno rešenje.

Izlaz

Za svaku od T prikaz test slučajeva Z linije koje daju dekodiranu verziju svakog od njih Z znakova u rastućem redoslijedu. Koristite format original->kodiranje, Gdje original- Ovo decimalni broj u rasponu i odgovarajući kodirani niz kodiranih cifara za te znakove (svaka cifra ≥ 0 I< N).

1. kod = sljedeći bit iz toka, dužina = 1
2. Ćao kod< base
   kod = kod<< 1
   kod = kod + sljedeći bit iz toka
   dužina = dužina + 1
3. simbol = simbol + kod - baza]

Drugim riječima, gurati ćemo bit po bit iz ulaznog toka u varijablu koda slijeva do koda< base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.

Pretpostavimo da se petlja u (2), nakon nekoliko iteracija, zaustavlja. U ovom slučaju, izraz (kod - baza) je serijski broj željenog čvora (simbola) na nivou dužine. Prvi čvor (simbol) koji se nalazi na nivou dužine u stablu nalazi se u nizu simbola na indeksnim isključenjima. Ali nas ne zanima prvi znak, već numerirani znak (kod - baza). Stoga je indeks traženog simbola u nizu simbola jednak (offs + (code - base)). Drugim riječima, željeni simbol simbol=symb + kod - baza].

Navedimo konkretan primjer. Koristeći opisani algoritam, dekodiramo poruku Z / .

Z / ="0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 0010 01 01 01 01 01 01 10 1 1"

1. kod = 0, dužina = 1
2. kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   dužina = 3 + 1 = 4
   kod = 1 = baza = 1
3. simbol = symb = 2 + kod = 1 - baza = 1] = symb = A

1. kod = 1, dužina = 1
2. kod = 1 = baza = 1
3. simbol = symb = 7 + kod = 1 - baza = 1] = symb = H

1. kod = 0, dužina = 1
2. kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 1 + 1 = 2
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 2 + 1 = 3
   kod = 0< base = 2
   kod = 0<< 1 = 0
   kod = 0 + 0 = 0
   dužina = 3 + 1 = 4
   kod = 0< base = 1
   kod = 0<< 1 = 0
   kod = 0 + 1 = 1
   dužina = 4 + 1 = 5
   kod = 1 > baza = 0
3. simbol = symb = 0 + kod = 1 - baza = 0] = symb = F

Dakle, dekodirali smo prva 3 znaka: A, H, F. Jasno je da ćemo slijedeći ovaj algoritam dobiti upravo poruku S.

Proračun dužine koda

Da bismo kodirali poruku, moramo znati kodove znakova i njihove dužine. Kao što je navedeno u prethodnom odeljku, kanonski kodovi su u potpunosti određeni svojim dužinama. Dakle, naš glavni zadatak je izračunavanje dužine kodova.

Ispostavilo se da ovaj zadatak, u velikoj većini slučajeva, ne zahtijeva eksplicitnu konstrukciju Huffmanovog stabla. Štaviše, algoritmi koji koriste internu (ne eksplicitnu) reprezentaciju Hafmanovog stabla su mnogo efikasniji u smislu brzine i troškova memorije.

Danas postoji mnogo efikasnih algoritama za izračunavanje dužine koda (,). Ograničićemo se na razmatranje samo jednog od njih. Ovaj algoritam je prilično jednostavan, ali je unatoč tome vrlo popularan. Koristi se u programima kao što su zip, gzip, pkzip, bzip2 i mnogi drugi.

Vratimo se algoritmu za konstruisanje Hafmanovog stabla. Na svakoj iteraciji, izvršili smo linearnu pretragu za dva čvora s najmanjom težinom. Jasno je da je prioritetni red kao što je piramidalni (minimalni) pogodniji za ovu svrhu. Čvor sa najmanjom težinom imaće najveći prioritet i biće na vrhu piramide. Hajde da predstavimo ovaj algoritam.

Uključimo sve kodirane simbole u piramidu.

Iz piramide ćemo uzastopno izdvojiti 2 čvora (to će biti dva čvora s najmanjom težinom).

Formirajmo novi čvor i priložimo mu, kao djeca, dva čvora uzeta iz piramide. U ovom slučaju postavljamo težinu formiranog čvora jednaku zbroju težina podređenih čvorova.

Uključimo formirani čvor u piramidu.

Ako postoji više od jednog čvora u piramidi, ponovite 2-5.

Pretpostavićemo da je za svaki čvor pohranjen pokazivač na njegov roditelj. U korijenu stabla postavljamo ovaj pokazivač jednak NULL. Odaberimo sada čvor (simbol) lista i, prateći sačuvane pokazivače, penjaćemo se po stablu sve dok sledeći pokazivač ne postane NULL. Poslednji uslov znači da smo stigli do korena drveta. Jasno je da je broj prelazaka sa nivoa na nivo jednak dubini lisnog čvora (simbola), a samim tim i dužini njegovog koda. Prolaskom kroz sve čvorove (simbole) na ovaj način dobijamo dužine njihovih kodova.

Maksimalna dužina koda

U pravilu se kod kodiranja koristi tzv šifrarnik (šifarnik), jednostavna struktura podataka, u suštini dva niza: jedan sa dužinama, drugi sa kodovima. Drugim riječima, kod (kao niz bitova) je pohranjen na memorijskoj lokaciji ili registru fiksne veličine (obično 16, 32 ili 64). Kako bismo spriječili prelijevanje, moramo biti sigurni da će kod stati u registar.

Ispostavilo se da na abecedi N znakova maksimalna veličina koda može biti dužine do (N-1) bita. Drugim riječima, sa N=256 (uobičajena opcija) možemo dobiti kod dug 255 bita (iako za ovo datoteka mora biti veoma velika: 2.292654130570773*10^53~=2^177.259)! Jasno je da se takav kod neće uklopiti u registar i sa njim treba nešto učiniti.

Prvo, hajde da saznamo pod kojim uslovima dolazi do prelivanja. Neka frekvencija i-tog simbola bude jednaka i-tom Fibonačijevom broju. Na primjer: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Konstruirajmo odgovarajuće Huffmanovo stablo.

ROOT /\ / \ / \ /\ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B

Takvo drvo se zove degenerisati. Da bi ga primili, frekvencije simbola moraju rasti barem onoliko koliko su Fibonačijevi brojevi ili čak i brže. Iako je u praksi, koristeći stvarne podatke, gotovo nemoguće dobiti takvo stablo, vrlo ga je lako generirati umjetno. U svakom slučaju, ova opasnost se mora uzeti u obzir.

Ovaj problem se može riješiti na dva prihvatljiva načina. Prvi od njih se oslanja na jedno od svojstava kanonskih kodova. Činjenica je da u kanonskom kodu (bit string) nijedan bitniji bit ne može biti različit od nule. Drugim riječima, svi ostali bitovi možda uopće neće biti sačuvani, jer uvijek su nula. U slučaju N=256, potrebno je samo pohraniti najmanje značajnih 8 bitova iz svakog koda, pod pretpostavkom da su svi ostali bitovi jednaki nuli. Ovo rješava problem, ali samo djelimično. Ovo će značajno zakomplicirati i usporiti i kodiranje i dekodiranje. Stoga se ova metoda rijetko koristi u praksi.

Drugi metod je da se veštački ograniči dužina kodova (bilo tokom izgradnje ili posle). Ova metoda je općenito prihvaćena, pa ćemo se na njoj detaljnije zadržati.

Postoje dvije vrste algoritama za ograničavanje dužine koda. Heuristički (približan) i optimalan. Algoritmi drugog tipa su prilično složeni za implementaciju i po pravilu zahtijevaju više vremena i memorije od prvog. Efikasnost heuristički ograničenog koda određena je njegovim odstupanjem od optimalno ograničenog koda. Što je ova razlika manja, to bolje. Vrijedi napomenuti da je za neke heurističke algoritme ova razlika vrlo mala ( , , ), i oni vrlo često generiraju optimalan kod (iako ne garantuju da će to uvijek biti slučaj). Štaviše, jer u praksi se prelivanje događa izuzetno rijetko (osim ako ne postoji vrlo striktno ograničenje na maksimalnu dužinu koda); s malom veličinom alfabeta preporučljivije je koristiti jednostavne i brze heurističke metode.

Pogledat ćemo jedan prilično jednostavan i vrlo popularan heuristički algoritam. Našao je svoju primjenu u programima kao što su zip, gzip, pkzip, bzip2 i mnogim drugim.

Problem ograničavanja maksimalne dužine koda je ekvivalentan problemu ograničavanja visine Hafmanovog stabla. Imajte na umu da po konstrukciji svaki nelisni čvor u Huffmanovu stablu ima tačno dva djeteta. Pri svakoj iteraciji našeg algoritma smanjit ćemo visinu stabla za 1. Dakle, neka je L maksimalna dužina koda (visina stabla) i želimo je ograničiti na L / < L. Neka je dalje RN i krajnji desni listni čvor na nivou i, a LN i je krajnji lijevi.

Počnimo sa radom od nivoa L. Pomerimo čvor RN L na mesto njegovog roditelja. Jer čvorovi idu u parovima; moramo pronaći mjesto za čvor pored RN L. Da bismo to uradili, nalazimo nivo j najbliži L, koji sadrži čvorove lista, tako da je j < (L-1). Umjesto LN j, formiraćemo nelisni čvor i priložiti mu kao podređeni čvor LN j i preostali neupareni čvor sa nivoa L. Primijeniti istu operaciju na sve preostale parove čvorova na nivou L. Jasno je da smo preraspodjelom čvorova na ovaj način smanjili visinu našeg stabla za 1. Sada je jednako (L-1). Ako sada L / < (L-1), onda ćemo isto učiniti sa nivoom (L-1) itd. dok se ne dostigne traženi limit.

Vratimo se na naš primjer, gdje je L=5. Ograničimo maksimalnu dužinu koda na L / =4.

ROOT /\ / \ / \ /\ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F

Može se vidjeti da je u našem slučaju RN L = F, j=3, LN j = C. Prvo pomjerimo čvor RN L = F na mestu svog roditelja.

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(nespareni čvor)

Sada na mjestu LN j = C Formiramo čvor bez lista.

ROOT /\ / \ / \ /\ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(nespareni čvor) C(nespareni čvor)

Pričvrstimo dva neuparena na formirani čvor: B I C.

ROOT /\ / \ / \ /\ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C

Stoga smo maksimalnu dužinu koda ograničili na 4. Jasno je da smo promjenom dužine koda malo izgubili u efikasnosti. Dakle, poruka S, kodirana takvim kodom, imat će veličinu od 92 bita, tj. 3 bita više u poređenju sa minimalno redundantnim kodom.

Jasno je da što više ograničimo maksimalnu dužinu koda, to će kod biti manje efikasan. Hajde da saznamo koliko možemo ograničiti maksimalnu dužinu koda. Očigledno ne kraće.

Računanje kanonskih kodova

Kao što smo više puta napomenuli, dužine kodova su dovoljne za generisanje samih kodova. Hajde da pokažemo kako se to može uraditi. Pretpostavimo da smo već izračunali dužine kodova i izbrojali koliko kodova svake dužine imamo. Neka je L maksimalna dužina koda, a T i broj kodova dužine i.

Izračunajmo S i - početnu vrijednost koda dužine i, za sve i iz

S L = 0 (uvijek)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (uvijek)

Za naš primjer, L = 5, T 1 .. 5 = (1, 0, 2 , 3, 2).

S 5 = 00000 bin = 0 dec
S 4 = (S 5 =0 + T 5 =2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dec
S 3 = (S 4 =1 + T 4 =3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dec
S 2 = (S 3 =2 + T 3 =2) >> 1 = (100 bin >> 1) = 10 bin = 2 dec
S 1 = (S 2 =2 + T 2 =0) >> 1 = (10 bin >> 1) = 1 bin = 1 dec

Može se vidjeti da su S 5, S 4, S 3, S 1 upravo znakovni kodovi B, A, C, H. Zajedničko ovim simbolima je da su svi prvi, svaki na svom nivou. Drugim riječima, pronašli smo početnu vrijednost koda za svaku dužinu (ili nivo).

Sada dodijelimo kodove preostalim simbolima. Šifra prvog znaka na nivou i je S i , drugog je S i + 1, trećeg je S i + 2, itd.

Zapišimo preostale kodove za naš primjer:

Može se vidjeti da smo dobili potpuno iste kodove kao da smo eksplicitno izgradili kanonsko Huffmanovo stablo.

Transfer stabla koda

Da bi kodirana poruka bila dekodirana, dekoder mora imati isto stablo koda (u ovom ili onom obliku) koje je korišteno tokom kodiranja. Stoga smo, zajedno sa kodiranim podacima, primorani da sačuvamo odgovarajuće stablo koda. Jasno je da što je kompaktniji, to bolje.

Postoji nekoliko načina za rješavanje ovog problema. Najočiglednije rješenje je eksplicitno pohraniti stablo (tj. kao uređeni skup čvorova i pokazivača ove ili one vrste). Ovo je možda najrasipniji i najneefikasniji način. U praksi se ne koristi.

Možete pohraniti listu frekvencija simbola (tj. frekvencijski rečnik). Uz njegovu pomoć, dekoder može lako rekonstruirati kodno stablo. Iako je ova metoda manje rasipnička od prethodne, nije najbolja.

Konačno, možete koristiti jedno od svojstava kanonskih kodova. Kao što je ranije navedeno, kanonski kodovi su u potpunosti određeni svojim dužinama. Drugim riječima, sve što je dekoderu potrebno je lista dužina znakovnog koda. Uzimajući u obzir da se u prosjeku dužina jednog koda za N-znakovnu abecedu može kodirati u [(log 2 (log 2 N))] bitovima, dobijamo vrlo efikasan algoritam. Zadržat ćemo se na tome detaljnije.

Pretpostavimo da je veličina abecede N=256 i da komprimujemo običan tekstualni fajl (ASCII). Najvjerovatnije nećemo pronaći svih N znakova naše abecede u takvoj datoteci. Postavimo zatim dužinu koda znakova koji nedostaju jednaku nuli. U ovom slučaju, pohranjena lista dužina kodova će sadržavati prilično veliki broj nula (dužine kodova znakova koji nedostaju) grupisanih zajedno. Svaka takva grupa može se komprimirati korištenjem takozvanog grupnog kodiranja - RLE (Run - Length - Encoding). Ovaj algoritam je izuzetno jednostavan. Umjesto niza od M identičnih elemenata u nizu, pohranit ćemo prvi element ovog niza i broj njegovih ponavljanja, tj. (M-1). Primjer: RLE("AAABBBBCDDDDDD")=A3 B2 C0 D6.

Štaviše, ova metoda se može donekle proširiti. RLE algoritam možemo primijeniti ne samo na grupe nulte dužine, već i na sve ostale. Ova metoda prenošenja kodnog stabla je općenito prihvaćena i koristi se u većini modernih implementacija.

Implementacija: SHCODEC

Dodatak: biografija D. Huffmana

David Huffman rođen je 1925. godine u Ohaju, SAD. Huffman je sa 18 godina diplomirao elektrotehniku ​​na Državnom univerzitetu u Ohaju. Potom je služio u vojsci kao časnik radarske podrške na razaraču koji je pomagao u čišćenju mina u japanskim i kineskim vodama nakon Drugog svjetskog rata. Nakon toga je magistrirao na Univerzitetu Ohajo i doktorirao na Massachusetts Institute of Technology (MIT). Iako je Hafman najpoznatiji po razvoju metode za konstruisanje minimalno redundantnih kodova, dao je važan doprinos i mnogim drugim poljima (uglavnom elektronici). Bio je dugogodišnji predsjedavajući Odsjeka za kompjuterske nauke na MIT-u. 1974. godine, već kao profesor emeritus, dao je ostavku. Huffman je dobio niz vrijednih nagrada. 1999 - Medalja Richarda W. Hamminga sa Instituta inženjera elektrotehnike i elektronike (IEEE) za izuzetan doprinos teoriji informacija, Louis E. Levy medalja sa Franklin instituta za njegovu doktorsku disertaciju o sekvencijalnim sklopnim krugovima, nagrada W. Wallacea McDowella, IEEE Computer Society Award i IEEE Golden Anniversary Technology Innovation Award 1998. U oktobru 1999., u 74. godini, David Huffman je umro od raka.

Huffman kodiranje. Dio 1.
Uvod
Zdravo, dragi čitaoče! Ovaj članak će raspravljati o jednoj od metoda kompresije podataka. Ova metoda je prilično rasprostranjena i zaslužuje pažnju. Ovaj materijal dizajniran je za tri članka, od kojih će prvi biti posvećen algoritmu kompresije, a drugi - implementacija softvera algoritam, a treći je dekompresija. Algoritam kompresije će biti napisan u C++, a dekompresijski algoritam u Assembleru.
Međutim, prije nego što pređemo na sam algoritam, u članak treba uključiti malo teorije.
Malo teorije
Kompresija (kompresija) je metoda smanjenja količine podataka u svrhu daljeg prijenosa i skladištenja.
Dekompresija je metoda vraćanja komprimiranih podataka u njihov izvorni oblik.
Kompresija i dekompresija mogu biti ili bez gubitka kvalitete (kada su prenesene/pohranjene informacije u komprimiranom obliku nakon dekompresije potpuno identične originalu), ili sa gubitkom kvalitete (kada se podaci nakon dekompresije razlikuju od originala). Na primjer, tekstualni dokumenti, baze podataka, programi se mogu komprimirati samo metodom bez gubitka kvalitete, dok se slike, video i audio fajlovi komprimiraju upravo zbog gubitka kvalitete originalnih podataka (tipičan primjer algoritama je JPEG, MPEG, ADPCM), sa ponekad neprimetnim gubitkom kvaliteta čak i sa kompresijom 1:4 ili 1:10.
Razlikuju se glavne vrste ambalaže:

• Decimalno pakovanje namijenjen je pakiranju znakovnih podataka koji se sastoje samo od brojeva. Umjesto korištenja 8 bita po karakteru, sasvim je racionalno koristiti samo 4 bita za decimalne i heksadecimalne cifre, 3 bita za oktalne cifre i tako dalje. Ovim pristupom već se osjeća kompresija od najmanje 1:2.
• Relativno kodiranje je kodiranje sa gubicima. Zasnovan je na činjenici da se sljedeći element podataka razlikuje od prethodnog po količini koja zauzima manje prostora u memoriji od samog elementa. Tipičan primjer je ADPCM (Adaptive Differential Pulse Code Modulation) audio kompresija, koja se široko koristi u digitalna telefonija i omogućava vam komprimiranje audio podataka u omjeru 1:2 uz gotovo neprimjetan gubitak kvaliteta.
• Simboličko potiskivanje- metoda kompresije informacija u kojoj se dugi nizovi identičnih podataka zamjenjuju kraćim.
• Statističko kodiranje na osnovu činjenice da se ne susreću svi elementi podataka istu frekvenciju(ili vjerovatnoća). Ovim pristupom kodovi se biraju tako da element koji se najčešće pojavljuje odgovara kodu najkraće dužine, a najrjeđi element odgovara najdužem.

Osim toga, kodovi su odabrani na takav način da je tokom dekodiranja moguće nedvosmisleno odrediti element izvornih podataka. Ovim pristupom moguće je samo bitsko orijentirano kodiranje, u kojem se razlikuju dozvoljeni i zabranjeni kodovi. Ako se kod dekodiranja bitne sekvence pokaže da je kod zabranjen, tada mu je potrebno dodati još jedan bit originalne sekvence i ponoviti operaciju dekodiranja. Primjeri takvog kodiranja su Shannon i Huffman algoritmi, od kojih ćemo potonje razmotriti.
Tačnije o algoritmu
Kao što je već poznato iz prethodnog pododjeljka, Hafmanov algoritam je zasnovan na statističko kodiranje. Pogledajmo bliže njegovu implementaciju.
Neka postoji izvor podataka koji prenosi simbole (a_1, a_2, ..., a_n) s različitim stupnjevima vjerovatnoće, to jest, svaki a_i ima svoju vjerovatnoću (ili frekvenciju) P_i(a_i), i postoji barem jedan par a_i i a_j ,i\ne j tako da P_i(a_i) i P_j(a_j) nisu jednaki. Ovo stvara skup frekvencija (P_1(a_1), P_2(a_2),...,P_n(a_n)), kakve to veze ima \displaystyle \sum_(i=1)^(n) P_i(a_i)=1, budući da predajnik ne prenosi više simbola osim (a_1,a_2,...,a_n).
Naš zadatak je odabrati takve kodni znakovi (b_1, b_2,...,b_n) sa dužinama (L_1(b_1),L_2(b_2),...,L_n(b_n)) tako da prosječna dužina kodnog simbola ne prelazi prosječnu dužinu originalnog simbola. U ovom slučaju potrebno je uzeti u obzir uslov da ako P_i(a_i)>P_j(a_j) i i\ne j , tada L_i(b_i)\le L_j(b_j).
Huffman je predložio izgradnju stabla u kojem su čvorovi s najvećom vjerovatnoćom najmanje udaljeni od korijena. Odatle dolazi metoda izgradnje stabla:
1. Odaberite dva simbola a_i i a_j , i\ne j , tako da P_i(a_i) i P_j(a_j) sa cijele liste (P_1(a_1),P_2,...,P_n(a_n)) su minimalne.
2. Dovedite grane stabla iz ova dva elementa u jednu tačku sa vjerovatnoćom P=P_i(a_i)+P_j(a_j), označavajući jednu granu nulom, a drugu jedinicom (po vlastitom nahođenju).
3. Ponovite korak 1, uzimajući u obzir nova tačka umjesto a_i i a_j ako je broj rezultirajućih tačaka veći od jedan. Inače smo stigli do korijena drveta.
Pokušajmo sada upotrijebiti rezultirajuću teoriju i kodirati informacije koje prenosi izvor, koristeći primjer od sedam simbola.
Pogledajmo detaljnije prvi ciklus. Slika prikazuje tabelu u kojoj svaki simbol a_i ima svoju vlastitu vjerovatnoću (frekvenciju) P_i(a_i) . Prema tački 1, iz tabele biramo dva simbola sa najmanjom vjerovatnoćom. U našem slučaju, to su a_1 i a_4. Prema tački 2, grane stabla sa a_1 i a_4 svedemo na jednu tačku i granu koja vodi do a_1 označavamo sa jedan, a granu koja vodi do a_4 sa nulom. Iznad nove tačke dodjeljujemo njenu vjerovatnoću (u ovom slučaju - 0,03) V dalja akcija se ponavljaju uzimajući u obzir novu tačku i bez uzimanja u obzir a_1 i a_4.

Nakon višestrukog ponavljanja gornjih koraka, gradi se sljedeće stablo:

Na osnovu izgrađenog stabla možete odrediti značenje kodova (b_1,b_2,...,b_n), spuštajući se od korijena do odgovarajućeg elementa a_i , dok dodaje nulu ili jedan rezultujućoj sekvenci kako se svaka grana prenosi (ovisno o tome kako je određena grana imenovana). Dakle, tabela kodova izgleda ovako:

ib iL i (b i) 1 011111 62 1 13 0110 44 011110 65 010 36 00 27 01110 5

Pokušajmo sada kodirati niz znakova.
Neka simbol a_i odgovara (kao primjer) broju i. Neka postoji niz 12672262. Moramo dobiti rezultujući binarni kod.
Za kodiranje možete koristiti već postojeću tablicu kodnih simbola b_i, uzimajući u obzir da b_i odgovara simbolu a_i. U ovom slučaju, kod za broj 1 će biti niz 011111, za broj 2 - 1, a za broj 6 - 00. Tako dobijamo sljedeći rezultat:

Podaci12672262Dužina kodaOriginal001010110111010010110 01024 bita Kodirano011111100011101100119 bita

Kao rezultat kodiranja, dobili smo 5 bita i snimili sekvencu sa 19 bita umjesto 24.
Međutim, ovo ne daje potpunu procjenu kompresije podataka. Vratimo se matematici i procijenimo stepen kompresije koda. Ovo će zahtijevati procjenu entropije.
Entropija— mjera neizvjesnosti situacije (slučajna varijabla) sa konačnim ili parnim brojem ishoda. Matematički, entropija je formulisana kao zbir proizvoda verovatnoća različitih stanja sistema logaritmima ovih verovatnoća, uzetih sa suprotnim predznakom:

H(X)=-\displaystyle \sum_(i=1)^(n)P_i\cdot log_d (P_i).​

Gdje je X diskretno slučajna vrijednost(u našem slučaju, kodni simbol), a d je proizvoljna baza veća od jedan. Izbor baze je ekvivalentan izboru specifične jedinice mjerenja entropije. Pošto imamo posla sa binarne cifre, onda je racionalno izabrati d=2 kao osnovu.
Dakle, entropija za naš slučaj se može predstaviti kao:

H(b)=-\displaystyle \sum_(i=1)^(n)P_i(a_i)\cdot log_2 (P_i(a_i)).​

Entropija ima izvanredno svojstvo: jednaka je minimalnoj dozvoljenoj prosječnoj dužini kodnog simbola \overline(L_(min)) u bitovima. Prosječna dužina samog kodnog simbola se izračunava po formuli

\overline(L(b))=\displaystyle \sum_(i=1)^(n)P_i(a_i)\cdot L_i(b_i).​

Zamjenom vrijednosti u formule H(b) i \overline(L(b)), dobijamo sljedeći rezultat: H(b)=2,048, \overline(L(b))=2100.
Vrijednosti H(b) i \overline(L(b)) su vrlo bliske, što ukazuje na stvarnu dobit u izboru algoritma. Sada uporedite prosječnu dužinu originalnog simbola i prosječnu dužinu simbola koda kroz relaciju:

\frac(\overline(L_(src)))(L(b))=\frac(3)(2,1)=1.429.​

Tako smo dobili omjer kompresije od 1:1,429, što je vrlo dobro.
I na kraju, riješimo posljednji problem: dešifriranje niza bitova.
Neka postoji niz bitova za našu situaciju:

001101100001110001000111111​

Treba utvrditi izvor, odnosno dekodirajte ovu sekvencu.
Naravno, u takvoj situaciji možete koristiti tablicu kodova, ali to je prilično nezgodno, jer dužina kodnih simbola nije konstantna. Mnogo je zgodnije spustiti stablo (počevši od korijena) prema sljedećem pravilu:
1. Polazna tačka je korijen stabla.
2. Pročitajte novi bit. Ako je nula, idite duž grane označene nulom, u suprotnom - jednom.
3. Ako je tačka koju smo pogodili konačna, tada smo odredili kodni simbol koji treba zapisati i vratiti se na korak 1. U suprotnom, korak 2 treba ponoviti.
Pogledajmo primjer dekodiranja prvog znaka. Nalazimo se u tački sa verovatnoćom 1.00 (koren stabla), čitamo prvi bit niza i idemo duž grane označene nulom do tačke sa verovatnoćom 0.60. Pošto ova tačka nije krajnja tačka u stablu, čitamo sledeći bit, koji je takođe nula, i idemo duž grane označene nulom do tačke a_6, koja je krajnja tačka. Simbol smo dešifrovali - ovo je broj 6. Zapisujemo ga i vraćamo se početno stanje(premjesti u korijen).
Tako dekodirani niz poprima oblik.

Podaci

001101100001110001000111111 Dužina kodaKodirbita Original6223676261233 bita

U ovom slučaju, dobitak je bio 6 bita sa prilično kratkom dužinom sekvence.
Zaključak se nameće sam od sebe: algoritam je jednostavan. Međutim, treba napomenuti: ovaj algoritam dobar za kompresiju tekstualne informacije(zaista, u stvarnosti koristimo oko 60 karaktera od dostupnih 256 kada kucamo tekst, odnosno vjerovatnoća da ćemo naići na druge znakove je blizu nuli), ali je dovoljno loša za komprimiranje programa (pošto su svi znakovi u programu skoro podjednako vjerovatno). Dakle, efikasnost algoritma u velikoj meri zavisi od vrste podataka koji se kompresuju.
P.S
U ovom članku smo se osvrnuli na Huffmanov algoritam kodiranja, koji je zasnovan na neravnomerno kodiranje. Omogućava vam da smanjite veličinu prenesenih ili pohranjenih podataka. Algoritam je lak za razumijevanje i može donijeti prave dobitke. Osim toga, ima još jedno izvanredno svojstvo: sposobnost kodiranja i dekodiranja informacija u hodu, pod uslovom da su vjerovatnoće kodnih riječi ispravno određene. Iako postoji modifikacija algoritma koja vam omogućava da promijenite strukturu stabla u realnom vremenu.
U sljedećem dijelu članka ćemo pogledati bajt-orijentiranu kompresiju datoteka koristeći Huffman algoritam, implementiran u C++.
Huffman kodiranje. Dio 2
Uvod
U zadnjem dijelu smo pogledali algoritam kodiranja i opisali ga matematički model, izvršeno kodiranje i dekodiranje na konkretan primjer, izračunao je prosječnu dužinu kodna riječ, a također je odredio omjer kompresije. Osim toga, izvedeni su zaključci o prednostima i nedostacima ovog algoritma.
Međutim, pored ovoga, ostala su neriješena još dva pitanja: implementacija programa koji komprimira datoteku s podacima i programa koji raspakira komprimovani fajl. Ovaj članak je posvećen prvom pitanju. Stoga, trebali biste početi dizajnirati.
Dizajn
Prvo što trebate učiniti je izračunati učestalost pojavljivanja znakova u datoteci. Da bismo to učinili, opisujemo sljedeću strukturu:

// Struktura za izračunavanje frekvencije simbola

typedef struct TFreq

int ch;

TTable * tablica;

DWORD freq;

) TFreq;

Ova struktura će opisati svaki znak od 256. ch- sam ASCII znak, freq― broj pojavljivanja simbola u datoteci. Polje sto— pokazivač na strukturu:

// Deskriptor čvora

typedef struct TTable

int ch;

TTtable * lijevo;

TTtable * desno;

) TTable;

kao što se vidi, TTable je deskriptor čvora sa grananjem na nulu i jedan. Uz pomoć ovih struktura u budućnosti će se konstruirati kompresijsko stablo. Sada deklarisimo za svaki simbol svoju frekvenciju i vlastiti čvor:

TFreq Freq[ 256 ] ;

Pokušajmo shvatiti kako će drvo biti izgrađeno. U početnoj fazi, program mora preći cijelu datoteku i izbrojati broj pojavljivanja znakova u njoj. Osim toga, za svaki pronađeni simbol, program mora kreirati ručku čvora. Nakon toga program od kreiranih čvorova gradi stablo, uzimajući u obzir učestalost simbola, postavlja čvorove određenim redoslijedom i uspostavlja veze između njih.
Konstruirano stablo je dobro za dekodiranje datoteka. Ali za kodiranje datoteka to je nezgodno jer se ne zna u kom smjeru ići od korijena da bi se došlo do traženog znaka. Da biste to učinili, prikladnije je napraviti tablicu konverzije simbola u kod. Stoga definiramo drugu strukturu:

// Deskriptor karaktera koda

typedef struct TOPcode

DWORD opcode;

DWORD len;

) TOPcode;

Evo opcode je kodna kombinacija simbola i len- njegovu dužinu (u bitovima). I hajde da proglasimo tabelu od 256 takvih struktura:

Topcode Opcodes[ 256 ] ;

Poznavajući kodirani simbol, možete odrediti njegovu kodnu riječ iz tabele. Pređimo sada direktno na brojanje frekvencija simbola (i ne samo).
Brojanje frekvencija simbola
U principu, ova akcija nije teška. Dovoljno je otvoriti datoteku i prebrojati broj znakova u njoj, popunjavajući odgovarajuće strukture. Pogledajmo implementaciju ove akcije.
Da bismo to učinili, deklariramo globalne deskriptore datoteka:

FILE *ulaz, *izlaz, *sastavljanje;

in― datoteka iz koje se čitaju nekomprimirani podaci.
van― datoteka u koju se upisuju kompresovani podaci.
montaža― datoteka u kojoj će stablo biti sačuvano u obliku pogodnom za raspakivanje. Budući da će raspakivač biti napisan na asembleru, sasvim je racionalno stablo učiniti dijelom raspakivača, odnosno predstaviti ga u obliku instrukcija u asembleru.
Prvi korak je inicijalizacija svih struktura nulte vrijednosti:

// Brojanje frekvencija simbola

int CountFrequency(void)

int i; // varijabla petlje

int count= 0 ; // varijabla druge petlje

DWORD TotalCount= 0 ; // veličina fajla.

// Inicijalizacija struktura

za (i= 0; i< 256 ; i++ )

Frekv[i].frekv = 0;

Frekv[i].tabela = 0;

Frekv[i].ch = i;

Nakon toga, brojimo broj pojavljivanja simbola u datoteci i veličinu datoteke (naravno, ne na najidealniji način, ali primjer treba pojasniti):

// Brojanje frekvencije znakova (znak po znak)

dok (! feof (in) ) // dok se ne dostigne kraj datoteke

i= fgetc (in) ;

ako (i!=EOF) // ako nije kraj datoteke

Freq[i].freq++; // frekvencija ++

TotalCount++ ; // veličina ++

Budući da je kod neujednačen, raspakivaču će biti teško otkriti broj znakova koji se čitaju. Stoga je potrebno zabilježiti njegovu veličinu u tablici za raspakivanje:

// “Recite” raspakivaču veličinu datoteke

fprintf(assembl, "coded_file_size: \n dd %8lxh\n \n ", TotalCount);

Nakon toga, svi korišteni znakovi se pomjeraju na početak niza, a neiskorišteni se prepisuju (preuređivanjem).

// premjestiti sve neiskorištene znakove na kraj

i= 0 ;

broj= 256 ;

dok (i< count) // još nismo stigli do kraja

if (Freq[ i].freq == 0 ) // ako je frekvencija 0

Frekv[ i] = Frekv[ -- broj] ; // zatim kopirajte unos s kraja

ostalo

i++ ; // sve je OK - idemo dalje.

I tek nakon takvog "sortiranja" memorija se dodjeljuje čvorovima (za neke uštede).

// Dodijeli memoriju za čvorove

za (i= 0; i< count; i++ )

Freq[ i].table = nova TTtable; // kreiranje čvora

Freq[ i].tabela - > lijevo= 0 ; // nema veze

Freq[ i].tabela - > desno= 0 ; // nema veze

Freq[ i].tabela - > ch= Freq.ch ; // kopiraj simbol

Freq[ i].freq = Frekv.frekv; // i frekvencija

povratni broj;

Dakle, napisali smo funkciju za početnu inicijalizaciju sistema, ili, ako pogledate algoritam u prvom dijelu članka, „zapisali smo simbole koji se koriste u koloni i dodijelili im vjerovatnoće“, kao i za svaki simbol kreirali smo “početnu tačku” - čvor - i inicijalizirali ga. U polja lijevo I u pravu zapisao nule. Dakle, ako je čvor posljednji u stablu, lako će ga vidjeti lijevo I u pravu, jednako nuli.
Kreiranje drveta
Dakle, u prethodnom odjeljku smo “snimili simbole korištene u koloni i dodijelili im vjerovatnoće.” U stvari, nismo im dodijelili vjerovatnoće, već brojioce razlomka (to jest, broj pojavljivanja znakova u datoteci). Sada treba da napravimo drvo. Ali da biste to učinili, morate pronaći minimalni element na listi. Da bismo to učinili, uvodimo funkciju kojoj prosljeđujemo dva parametra - broj elemenata na listi i element koji treba isključiti (jer ćemo pretraživati ​​u parovima, a bit će vrlo neugodno ako dobijemo isti element od funkcija dvaput):

// tražimo čvor sa najmanjom vjerovatnoćom.

int FindLeast(int count, int index)

int i;

DWORD min= (indeks== 0 ) ? 10 ; // element koji brojimo

// minimalno

za (i= 1; i< count; i++ ) // petlja kroz niz

ako (i!=indeks) // ako element nije isključen

if (Freq[ i].freq< Freq[ min] .freq ) // сравниваем

min= i; // manje od minimuma - zapamtite

povratak min; // vraća minimalni indeks

Pretraživanje se implementira jednostavno: prvo odabiremo "minimalni" element niza. Ako je isključeni element 0, tada uzimamo prvi element kao minimum, u suprotnom smatramo nulu kao minimum. Dok se krećemo kroz niz, upoređujemo trenutni element sa "minimalnim" elementom, a ako se pokaže da je manji, onda ga označavamo kao minimalan.
Sada, zapravo, sama funkcija izgradnje stabla:

// Funkcija izgradnje stabla

void PreInit(int count)

int ind1, ind2; // indeksi elemenata

TTable * tablica; // pokazivač na "novi čvor"

dok (broj> 1) // petlja dok ne dođemo do korijena

ind1= FindLeast(broj,- 1) ; // prvi čvor

ind2= FindLeast(count,ind1) ; // drugi čvor

tablica= novi TTable; // kreiramo novi čvor

tablica->ch= - 1 ; // nije konačan

table->left= Freq[ ind1].table ; // 0 - čvor 1

tablica->desno= Frekv[ ind2].tabela ; // 1 - čvor 2

Frekv[ ind1].ch = - 1 ; // modificirati unos o

Frekv[ ind1].freq + = Frekv[ ind2].freq ; // frekvencija za simbol

Frekv[ ind1].tabela = tabela; // i napišemo novi čvor

if (ind2! = (-- broji) ) // ako ind2 nije posljednji

Frekv[ ind2] = Frekv[ broj] ; // onda na svoje mjesto

// postavi posljednju u niz

Tabela simbola kodova
Dakle, napravili smo stablo u memoriji: uzeli smo dva čvora u paru, kreirali novi čvor, u koji smo upisali pokazivače na njih, nakon čega je drugi čvor uklonjen sa liste, a umjesto prvog čvora, novi je napisano sa granom.
Sada se javlja još jedan problem: kodiranje stabla je nezgodno, jer morate tačno znati na kojoj se putanji nalazi određeni simbol. Međutim, problem se rješava prilično jednostavno: u nju se kreira još jedna tablica - tablica kodnih simbola i upisuje se kombinacije bitova svih korištenih simbola. Da biste to učinili, dovoljno je jednom rekurzivno preći stablo. Istovremeno, kako ga ne biste ponovno zaobišli, možete dodati generiranje datoteke sklopa u funkciju zaobilaženja za dalje dekodiranje komprimiranih podataka (pogledajte odjeljak " Dizajn").
Zapravo, sama funkcija nije komplicirana. Trebalo bi dodijeliti 0 ili 1 kombinaciji koda ako čvor nije krajnji čvor, u suprotnom dodajte simbol koda u tablicu. Uz sve ovo, generirajte asemblerski fajl. Razmotrite ovu funkciju:

void RecurseMake(TTable * tbl, DWORD opcode, int len)

fprintf (assembl,"opcode%08lx_%04x: \n",opcode,len) ; // oznaka u datoteku

if (tbl- > ch! = - 1 ) // krajnji čvor

BYTE mod= 32 - len;

Opcodes[ tbl->ch].opcode = (opcode>> mod) ; // sačuvati kod

Opkodovi[ tbl- > ch].len = len; // i njegova dužina (u bitovima)

// i kreiramo odgovarajuću oznaku

fprintf(sastavljanje, " db %03xh,0ffh,0ffh,0ffh\n \n ",tbl->ch) ;

ostalo // čvor nije konačan

opcode>>= 1 ; // napravimo mjesta za novi bit

len++ ; // povećava dužinu kodne riječi

\n",opcode,len) ;

fprintf (assembl," dw opcode%08lx_%04x \n\n",opcode| 0x80000000 ,len) ;

RecurseMake(tbl- > lijevo,opcode,len) ;

RecurseMake(tbl- > desno,opcode| 0x80000000 ,len) ;

// izbrišite čvor (više nije potreban)

delete tbl;

Između ostalog, nakon prolaska čvora, funkcija ga briše (oslobađa pokazivač). Sada hajde da shvatimo koje vrste parametara se prosleđuju funkciji.

• tbl- čvor koji treba zaobići.
• opcode— trenutna kodna riječ. Najznačajniji bit uvijek mora biti slobodan.
• len— dužina kodne riječi.

U principu, funkcija nije ništa komplikovanija od „klasičnog faktorijala“ i ne bi trebalo da izaziva poteškoće.
Bitni izlaz
Sada smo došli do ne baš ugodnog dijela našeg arhivatora, odnosno do izlaza kodnih znakova u datoteku. Problem je u tome što su kodni simboli neujednačene dužine i izlaz se mora obaviti po bitovima. Funkcija će vam pomoći u tome PutCode. Ali prvo, deklarirajmo dvije varijable - brojač bitova u bajtu i bajt za izlaz:

// Brojač bitova

int OutBits;

// Izlazni znak

BYTE OutChar;

OutBits se povećava za jedan svaki put kada se bit izlazi, OutBits==8 signalizira da OutChar treba biti spremljen u datoteku.

void PutCode(int ch)

int len;

int outcode;

// dobijemo dužinu kodne riječi i samu kodnu riječ

outcode= Opkodovi[ ch].opcode ; // kodna riječ

len= Opkodovi[ ch].len ; // dužina (u bitovima)

dok (len> 0 ) // izlaz bit po bit

// Petlja dok varijabla OutBits ne bude u potpunosti zauzeta

dok ((OutBits< 8 ) && (len> 0 ) )

OutChar>>= 1 ; // osloboditi prostor

OutChar| = ((outcode& 1 )<< 7 ) ; // i stavite malo u njega

outcode>>= 1 ; // sljedeći bit koda

len -- ; // smanjiti dužinu

1. OutBits ++ ; // broj bitova se povećao

2. }

3. // ako se koristi svih 8 bitova, onda ih spremite u datoteku

4. ako ( OutBits == 8 )

5. {

6. fputc( OutChar, out ) ; // sačuvaj u datoteku

7. OutBits = 0 ; // resetovati

8. OutChar = 0 ; // opcije

9. }

10. }

11. }

Osim toga, trebate organizirati nešto poput "flush", odnosno nakon izlaza posljednje kodne riječi OutChar neće stati u izlaznu datoteku, jer OutBits!=8. Ovo dovodi do još jedne male funkcije:

1. // "Čišćenje" bafera bitova

2. void EndPut (void)

3. {

4. // Ako postoje bitovi u međuspremniku

5. ako ( OutBits ! = 0 )