Huffmanov algoritmus sa používa na kompresiu alebo kódovanie údajov. Každý znak v textovom súbore je obvykle uložený ako osem bitov (číslic, buď 0 alebo 1), ktoré sú k tomuto znaku mapované pomocou kódovania nazývaného ASCII. Huffmanov kódovaný súbor rozkladá rigidnú 8-bitovú štruktúru, takže najčastejšie používané znaky sú uložené iba v niekoľkých bitoch („a“môže byť „10“alebo „1000“namiesto ASCII, čo je „01100001“). Najmenšie bežné znaky potom často zaberú oveľa viac ako 8 bitov („z“môže byť „00100011010“), ale pretože sa vyskytujú len zriedka, Huffmanovo kódovanie celkovo vytvorí oveľa menší súbor ako originál.
Kroky
Časť 1 z 2: Kódovanie
Krok 1. Spočítajte frekvenciu každého znaku v súbore, ktorý chcete kódovať
Zahrňte fiktívny znak na označenie konca súboru - bude to dôležité neskôr. Hovorte tomu zatiaľ EOF (koniec súboru) a označte to ako frekvenciu 1.
Napríklad, ak chcete kódovať textový súbor s textom „ab ab cab“, mali by ste mať „a“s frekvenciou 3, „b“s frekvenciou 3, „(medzera) s frekvenciou 2,„ c “s frekvenciou 1 a EOF s frekvenciou 1
Krok 2. Uložte znaky ako uzly stromu a vložte ich do prioritného frontu
Budete stavať veľký binárny strom s každým znakom ako listom, takže znaky by ste mali uložiť vo formáte, v ktorom sa môžu stať uzlami stromu. Umiestnite tieto uzly do frontu priorít s frekvenciou každého znaku ako prioritou jeho uzla.
- Binárny strom je dátový formát, kde každý údaj je uzlom, ktorý môže mať až jedného rodiča a dve deti. Často je nakreslený ako vetviaci strom, odtiaľ pochádza názov.
- Fronta je vhodne pomenovaný zber údajov, kde prvá vec, ktorá ide do frontu, je aj prvá vec, ktorá vyjde (ako čakanie v rade). V poradí priorít sú údaje uložené v poradí podľa ich priority, takže prvá vec, ktorá vyjde, je najnaliehavejšia vec, vec s najmenšou prioritou, a nie prvá vec zaradená do poradia.
- V príklade „ab ab cab“bude váš prioritný front vyzerať takto: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Krok 3. Začnite stavať svoj strom
Odstráňte (alebo odstráňte z radu) dve najnaliehavejšie veci z frontu priorít. Vytvorte nový stromový uzol, ktorý bude rodičom týchto dvoch uzlov, pričom prvý uzol budete ukladať ako ľavé dieťa a druhý ako pravý podradený. Prioritou nového uzla by mal byť súčet priorít jeho dieťaťa. Potom zaradte tento nový uzol do frontu priorít.
Poradie priorít teraz vyzerá takto: {'': 2, nový uzol: 2, 'a': 3, 'b': 3}
Krok 4. Dokončite stavbu stromu:
opakujte vyššie uvedený krok, kým nie je vo fronte iba jeden uzol. Všimnite si toho, že okrem uzlov, ktoré ste vytvorili pre znaky a ich frekvencií, budete tiež odstraňovať jadrá z jadra, meniť sa na stromy a opätovne zaradiť do poradia rodičovské uzly, uzly, ktoré už sú samy stromami.
- Keď skončíte, posledným uzlom vo fronte bude koreň stromu kódovania so všetkými ostatnými uzlami, ktoré z neho odbočujú.
- Najčastejšie používanými znakmi budú listy najbližšie k vrcholu stromu, zatiaľ čo zriedka používané znaky budú umiestnené v spodnej časti stromu, ďalej od koreňa.
Krok 5. Vytvorte mapu kódovania. Prejdite stromom, aby ste dosiahli každú postavu. Pri každej návšteve ľavého dieťaťa uzla je to „0“. Pri každej návšteve správneho dieťaťa uzla je to „1“. Keď sa dostanete k znaku, uložte ho so sekvenciou 0 s a 1 s, ktorá bola potrebná na jeho získanie. V tejto sekvencii bude znak kódovaný ako v komprimovanom súbore. Uložte postavy a ich sekvencie na mapu.
- Začnite napríklad od koreňa. Navštívte ľavé dieťa koreňa a potom navštívte ľavé dieťa tohto uzla. Keďže uzol, v ktorom sa teraz nachádzate, nemá žiadne deti, dosiahli ste postavu. Toto je ' '. Keďže ste sa dostali dvakrát doľava, kódovanie '' je '00'.
- Mapa pre tento strom bude vyzerať takto: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Krok 6. Do výstupného súboru zahrňte kódovaciu mapu ako hlavičku
To umožní dekódovanie súboru.
Krok 7. Kódujte súbor
Pre každý znak v súbore, ktorý sa má kódovať, napíšte binárnu postupnosť, ktorú ste uložili na mapu. Akonáhle dokončíte kódovanie súboru, nezabudnite pridať EOF na koniec.
- Pre súbor „ab ab cab“bude kódovaný súbor vyzerať takto: „1011001011000101011011“.
- Súbory sú uložené ako bajty (8 bitov alebo 8 binárnych číslic). Pretože algoritmus Huffmanovho kódovania nepoužíva 8-bitový formát, kódované súbory často nebudú mať dĺžky, ktoré sú násobky 8. Zostávajúce číslice budú vyplnené 0 s. V takom prípade by na konci súboru boli pridané dve 0, ktoré vyzerá ako ďalšie miesto. To môže byť problém: ako by dekodér vedel, kedy prestať čítať? Pretože sme však zahrnuli znak konca súboru, dekodér sa k tomu dostane a potom zastaví, pričom ignoruje všetko ostatné, čo bolo pridané neskôr.
Časť 2 z 2: Dekódovanie
Krok 1. Prečítajte si v súbore kódovanom Huffman
Najprv si prečítajte hlavičku, ktorá by mala byť kódovacou mapou. Toto použite na zostavenie stromu dekódovania rovnakým spôsobom, akým ste vytvorili strom, ktorý ste použili na kódovanie súboru. Oba stromy by mali byť identické.
Krok 2. Čítajte binárne jednu číslicu naraz
Pri čítaní prechádzajte stromom: ak čítate „0“, choďte k ľavému dieťaťu uzla, v ktorom sa nachádzate, a ak čítate „1“, choďte k správnemu dieťaťu. Keď dosiahnete list (uzol bez akýchkoľvek detí), dorazili ste k postave. Napíšte znak do dekódovaného súboru.
Vzhľadom na spôsob uloženia znakov v strome majú kódy pre každý znak vlastnosť predpony, takže na začiatku kódovania iného znaku nemôže nikdy dôjsť k binárnemu kódovaniu znakov. Kódovanie pre každý znak je úplne jedinečné. Vďaka tomu je dekódovanie oveľa jednoduchšie
Krok 3. Opakujte, kým nedosiahnete EOF
Gratulujem Dekódovali ste súbor.
