Huffmanov algoritam koristi se za sažimanje ili kodiranje podataka. Obično je svaki znak u tekstualnoj datoteci pohranjen kao osam bitova (znamenki, bilo 0 ili 1) koji se preslikavaju na taj znak pomoću kodiranja zvanog ASCII. Datoteka kodirana Huffmanom razbija krutu 8-bitnu strukturu tako da se najčešće korišteni znakovi pohranjuju u samo nekoliko bitova ('a' bi moglo biti "10" ili "1000", a ne ASCII, što je "01100001"). Najmanje uobičajeni znakovi često će zauzeti mnogo više od 8 bitova ('z' bi moglo biti "00100011010"), ali budući da se pojavljuju tako rijetko, Huffmanovo kodiranje u cjelini stvara mnogo manju datoteku od izvornika.
Koraci
1. dio 2: Kodiranje
Korak 1. Izbrojite učestalost svakog znaka u datoteci koju želite kodirati
Uključite lažni znak za označavanje kraja datoteke - to će kasnije biti važno. Zasad ga nazovite EOF (kraj datoteke) i označite kao da ima frekvenciju 1.
Na primjer, ako želite kodirati tekstualnu datoteku koja čita "ab ab cab", imali biste "a" s frekvencijom 3, "b" s frekvencijom 3, "" (razmak) s frekvencijom 2, "c" s frekvencijom 1, i EOF s frekvencijom 1
Korak 2. Spremite likove kao čvorove stabla i stavite ih u red prioriteta
Izgradit ćete veliko binarno stablo sa svakim likom u obliku lista, pa biste likove trebali pohraniti u formatu tako da mogu postati čvorovi stabla. Postavite ove čvorove u red prioriteta s učestalošću svakog znaka kao prioritetom čvora.
- Binarno stablo je format podataka u kojem je svaki dio čvor koji može imati do jednog roditelja i dvoje djece. Često je nacrtano kao granasto drvo, pa otuda i naziv.
- Red je zbirka podataka prikladno nazvana gdje prva stvar koja uđe u red ujedno je i prva stvar koja izlazi (poput čekanja u redu). U redu s prioritetom, podaci se pohranjuju prema njihovom prioritetu, tako da prva stvar koja će izaći je najhitnija stvar, stvar s najmanjim prioritetom, a ne prva stavljena u red.
- U primjeru "ab ab cab" vaš red prioriteta izgledao bi ovako: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Korak 3. Počnite graditi svoje stablo
Uklonite (ili stavite u red) dvije najhitnije stvari iz reda prioriteta. Izradite novi čvor stabla koji će biti roditelj ova dva čvora, spremajući prvi čvor kao njegovo lijevo dijete, a drugi kao njegovo desno dijete. Prioritet novog čvora trebao bi biti zbroj prioriteta njegovog djeteta. Zatim stavite novi čvor u red prioriteta.
Red prioriteta sada izgleda ovako: {'': 2, novi čvor: 2, 'a': 3, 'b': 3}
Korak 4. Završite sa izgradnjom stabla:
ponavljajte gornji korak dok u redu ne bude samo jedan čvor. Imajte na umu da ćete osim čvorova koje ste stvorili za likove i njihove frekvencije, također ukloniti u red, pretvoriti u stabla i ponovno postaviti u red roditeljske čvorove, čvorove koji su već sami po sebi stabla.
- Kad završite, posljednji čvor u redu bit će korijen stabla kodiranja, a svi ostali čvorovi granaju se od njega.
- Najčešće korišteni znakovi bit će listovi najbliži vrhu stabla, dok će rijetko korišteni znakovi biti smješteni pri dnu stabla, dalje od korijena.
Korak 5. Napravite kartu kodiranja. Prođite kroz drvo kako biste došli do svakog lika. Svaki put kada posjetite lijevo dijete čvora, to je '0'. Svaki put kada posjetite pravo dijete čvora, to je '1'. Kad dođete do lika, pohranite ga s nizom 0 i 1 koji su potrebni da biste došli do njega. Ovaj slijed je ono što će znak biti kodiran kao u komprimiranoj datoteci. Pohranite likove i njihove sekvence na kartu.
- Na primjer, počnite od korijena. Posjetite lijevo dijete korijena, a zatim lijevo dijete tog čvora. Budući da čvor u kojem se sada nalazite nema djece, dosegli ste lik. Ovo je ' '. Budući da ste dvaput hodali lijevo da biste došli ovamo, kodiranje za '' je "00".
- Za ovo stablo karta će izgledati ovako: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Korak 6. U izlaznu datoteku uključite mapu kodiranja kao zaglavlje
To će omogućiti dekodiranje datoteke.
Korak 7. Kodirajte datoteku
Za svaki kodirani znak u datoteci napišite binarni niz koji ste pohranili na karti. Nakon što završite s kodiranjem datoteke, svakako dodajte EOF do kraja.
- Za datoteku "ab ab cab" kodirana datoteka izgledat će ovako: "1011001011000101011011".
- Datoteke se pohranjuju kao bajtovi (8 bita ili 8 binarnih znamenki). Budući da algoritam Huffman kodiranja ne koristi 8-bitni format, kodirane datoteke često neće imati višekratnike 8. Preostale znamenke bit će ispunjene 0-ima. U ovom slučaju, dvije bi se 0 dodale na kraju datoteke, što izgleda kao drugi razmak. To bi mogao biti problem: kako bi dekoder znao kada treba prestati čitati? Međutim, budući da smo uključili znak kraja datoteke, dekoder će doći do ovoga, a zatim prestati, zanemarujući ništa drugo što je dodano nakon.
2. dio 2: Dekodiranje
Korak 1. Pročitajte datoteku kodiranu od Huffmana
Prvo pročitajte zaglavlje koje bi trebalo biti karta kodiranja. Koristite ovo za izgradnju stabla dekodiranja na isti način na koji ste izgradili stablo koje ste koristili za kodiranje datoteke. Dva stabla trebaju biti identična.
Korak 2. Binarno čitajte jednu po jednu znamenku
Prelazite stablom dok čitate: ako čitate u '0', idite na lijevo dijete čvora na kojem se nalazite, a ako čitate u '1', idite na desno dijete. Kad dođete do lista (čvor bez djece), došli ste do lika. Upišite znak u dekodiranu datoteku.
Zbog načina na koji su znakovi pohranjeni u stablu, kodovi za svaki znak imaju svojstvo prefiksa, tako da se binarno kodiranje nijednog znaka ne može pojaviti na početku kodiranja drugog znaka. Kodiranje za svaki znak potpuno je jedinstveno. To uvelike olakšava dekodiranje
Korak 3. Ponavljajte dok ne dosegnete EOF
Čestitamo! Dekodirali ste datoteku.
