Huffmanov algoritam se koristi za komprimiranje ili kodiranje podataka. Obično je svaki znak u tekstualnoj datoteci pohranjen kao osam bita (znamenke, 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" umjesto ASCII, što je "01100001"). Najmanje uobičajeni znakovi će često zauzimati mnogo više od 8 bita ('z' bi moglo biti "00100011010"), ali budući da se pojavljuju tako rijetko, Huffmanovo kodiranje, u cjelini, stvara mnogo manju datoteku od originala.
Koraci
1. dio 2: Kodiranje
Korak 1. Izbrojite učestalost svakog znaka u datoteci koja se kodira
Uključite lažni znak za označavanje kraja datoteke - to će kasnije biti važno. Za sada 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 sa frekvencijom 1
Korak 2. Pohranite znakove kao čvorove stabla i stavite ih u red prioriteta
Izgradit ćete veliko binarno stablo sa svakim znakom u obliku lista, pa biste likove trebali pohraniti u formatu tako da mogu postati čvorovi stabla. Postavite ove čvorove u red prioriteta sa frekvencijom svakog karaktera kao prioritetom njegovog č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 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 taxi", vaš prioritetni red bi izgledao ovako: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Korak 3. Počnite graditi svoje drvo
Uklonite (ili uklonite) dvije najhitnije stvari iz reda prioriteta. Kreirajte 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 zbir 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 iz redova, pretvoriti se u stabla i ponovo postaviti u red roditeljske čvorove, čvorove koji su već sami po sebi stabla.
- Kada završite, posljednji čvor u redu bit će korijen stabla kodiranja, sa svim ostalim čvorovima koji se od njega granaju.
- Najčešće korišteni znakovi bit će listovi najbliži vrhu stabla, dok će se rijetko korišteni znakovi postaviti na dnu stabla, dalje od korijena.
Korak 5. Kreirajte mapu kodiranja. Prođite kroz drvo da dođete 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 karaktera, pohranite ga s nizom 0 i 1 koji su potrebni da biste do njega došli. Ova sekvenca 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 na kojem se sada nalazite nema djece, došli ste do lika. Ovo je ' '. Pošto ste dvaput hodali lijevo da biste došli ovdje, kodiranje za '' je "00".
- Za ovo stablo, mapa će izgledati ovako: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Korak 6. U izlaznu datoteku uključite mapu kodiranja kao zaglavlje
Ovo će omogućiti dekodiranje datoteke.
Korak 7. Kodirajte datoteku
Da biste svaki znak u datoteci kodirali, napišite binarni niz koji ste pohranili na karti. Kada završite s kodiranjem datoteke, svakako dodajte EOF do kraja.
- Za datoteku "ab ab cab", kodirana datoteka će izgledati 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šestruke dužine 8. Preostale znamenke će se popuniti s 0. U ovom slučaju, dvije 0 bi se dodale na kraj 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 sve drugo što je dodano nakon toga.
2. dio 2: Dekodiranje
Korak 1. Pročitajte datoteku kodiranu od Huffmana
Prvo pročitajte zaglavlje koje bi trebalo biti mapa kodiranja. Koristite ovo za izgradnju stabla dekodiranja na isti način na koji ste izgradili stablo koje ste koristili za kodiranje datoteke. Dva stabla bi trebala biti identična.
Korak 2. Binarno čitajte jednu po jednu cifru
Prelazite stablom dok čitate: ako čitate u '0', idite na lijevo dijete čvora na kojem se nalazite, a ako čitate u '1', idite u 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 je potpuno jedinstveno. To znatno olakšava dekodiranje
Korak 3. Ponavljajte dok ne dođete do EOF -a
Čestitamo! Dekodirali ste datoteku.
