Huffmanov algoritem se uporablja za stiskanje ali kodiranje podatkov. Običajno je vsak znak v besedilni datoteki shranjen kot osem bitov (števk, bodisi 0 ali 1), ki se preslikajo v ta znak z uporabo kodiranja, imenovanega ASCII. Huffmanova kodirana datoteka razbije togo 8-bitno strukturo, tako da so najpogosteje uporabljeni znaki shranjeni v le nekaj bitih ('a' je lahko "10" ali "1000" namesto ASCII, kar je "01100001"). Najmanj pogosti znaki bodo torej pogosto zavzeli veliko več kot 8 bitov ('z' je lahko "00100011010"), a ker se pojavljajo tako redko, Huffmanovo kodiranje na splošno ustvari veliko manjšo datoteko kot izvirnik.
Koraki
1. del 2: Kodiranje
Korak 1. Preštejte pogostost vsakega znaka v datoteki, ki jo želite kodirati
Za označitev konca datoteke vključite lažni znak - to bo pozneje pomembno. Zaenkrat ga poimenujte EOF (konec datoteke) in označite, da ima frekvenco 1.
Na primer, če želite kodirati besedilno datoteko z napisom "ab ab cab", bi imeli "a" s frekvenco 3, "b" s frekvenco 3, "(presledek) s frekvenco 2," c "s frekvenco 1 in EOF s frekvenco 1
Korak 2. Shranite znake kot drevesna vozlišča in jih postavite v prednostno čakalno vrsto
Zgradili boste veliko binarno drevo z vsakim znakom kot list, zato jih shranite v obliki, tako da lahko postanejo vozlišča drevesa. Postavite ta vozlišča v prioritetno čakalno vrsto s frekvenco vsakega znaka kot prednostjo njegovega vozlišča.
- Binarno drevo je podatkovni format, kjer je vsak kos vozlišče, ki ima lahko do enega starša in dva otroka. Pogosto je narisan kot razvejano drevo, od tod tudi ime.
- Čakalna vrsta je ustrezno poimenovano zbiranje podatkov, kjer prva stvar, ki gre v čakalno vrsto, tudi prva, ki pride ven (na primer čakanje v vrsti). V prioritetni čakalni vrsti so podatki shranjeni po vrstnem redu, tako da bo prva stvar, ki bo prišla ven, najnujnejša stvar, stvar z najmanjšo prioriteto, ne pa prva stvar v čakalni vrsti.
- V primeru "ab ab cab" bi bila vaša prednostna vrsta videti tako: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Korak 3. Začnite graditi svoje drevo
Odstranite (ali odstranite) dve najnujnejši stvari iz prioritetne čakalne vrste. Ustvarite novo drevesno vozlišče, ki bo starš teh dveh vozlišč, pri čemer bo prvo vozlišče shranjeno kot levi podrejeni, drugo pa kot njegov desni podrejeni. Prednost novega vozlišča mora biti vsota prednostnih nalog njegovega podrejenega. Nato to novo vozlišče postavite v čakalno vrsto prioritete.
Prednostna vrsta je zdaj videti tako: {'': 2, novo vozlišče: 2, 'a': 3, 'b': 3}
Korak 4. Dokončajte gradnjo svojega drevesa:
ponovite zgornji korak, dokler v čakalni vrsti ni samo eno vozlišče. Upoštevajte, da boste poleg vozlišč, ki ste jih ustvarili za znake in njihove frekvence, tudi umaknili, spremenili v drevesa in znova postavili v nadrejena vozlišča, vozlišča, ki so že sama drevesa.
- Ko končate, bo zadnje vozlišče v čakalni vrsti koren drevesa kodiranja, od njega pa se bodo odcepila vsa druga vozlišča.
- Najpogosteje uporabljeni znaki bodo listi, ki so najbližje vrhu drevesa, redko uporabljeni znaki pa bodo nameščeni na dnu drevesa, dlje od korena.
Korak 5. Ustvarite zemljevid kodiranja. Pojdite skozi drevo, da pridete do vsakega lika. Vsakič, ko obiščete levega otroka vozlišča, je to '0'. Vsakič, ko obiščete desnega otroka vozlišča, je to '1'. Ko pridete do znaka, ga shranite z zaporedjem 0 in 1, ki je bilo potrebno, da pridete do njega. To zaporedje je znak, ki bo kodiran kot v stisnjeni datoteki. Znake in njihove zaporedje shranite na zemljevid.
- Na primer, začnite pri korenu. Obiščite levega otroka korena in nato levega otroka tega vozlišča. Ker vozlišče, na katerem ste zdaj, nima otrok, ste dosegli lik. To je ''. Ker ste prišli dvakrat levo, da pridete sem, je kodiranje za '' '00'.
- Za to drevo bo zemljevid videti tako: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Korak 6. V izhodno datoteko vključite zemljevid kodiranja kot glavo
To bo omogočilo dekodiranje datoteke.
Korak 7. Kodirajte datoteko
Za vsak znak v datoteki, ki jo želite kodirati, napišite binarno zaporedje, ki ste ga shranili na zemljevid. Ko končate kodiranje datoteke, dodajte EOF na konec.
- Za datoteko "ab ab cab" bo kodirana datoteka videti tako: "1011001011000101011011".
- Datoteke so shranjene kot bajti (8 bitov ali 8 binarnih številk). Ker algoritem Huffman Encoding ne uporablja 8-bitnega formata, kodirane datoteke pogosto nimajo dolžin, večkratnih 8. Preostale številke bodo zapolnjene z 0. V tem primeru bi bili na koncu datoteke dodani dve 0, ki izgledata kot drug presledek. To bi lahko bil problem: kako bi dekoder vedel, kdaj prenehati z branjem? Ker pa smo vključili znak za konec datoteke, bo dekodirnik prišel do tega in se nato ustavil, pri čemer ne upošteva vsega, kar je bilo dodano po tem.
2. del 2: Dešifriranje
Korak 1. Preberite Huffmanovo kodirano datoteko
Najprej preberite glavo, ki naj bo zemljevid kodiranja. To uporabite za izdelavo drevesa za dekodiranje na enak način, kot ste ga zgradili za kodiranje datoteke. Dve drevesi morata biti enaki.
Korak 2. Preberite binarno eno številko naenkrat
Med branjem prečkajte drevo: če berete z '0', pojdite na levega podrejenega vozlišča, na katerem ste, in če berete z '1', pojdite na desnega otroka. Ko dosežete list (vozlišče brez otrok), pridete do lika. Zapišite znak v dekodirano datoteko.
Zaradi načina shranjevanja znakov v drevesu imajo kode za vsak znak lastnost predpone, tako da na začetku kodiranja drugega znaka ne more biti nobenega binarnega kodiranja znakov. Kodiranje za vsak znak je popolnoma edinstveno. Tako je dekodiranje veliko lažje
Korak 3. Ponavljajte, dokler ne dosežete EOF
Čestitamo! Dešifrirali ste datoteko.
