Ako skomprimovať údaje pomocou huffmanovho kódovania?
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.
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.
Časť 1 z 2: kódovanie
- 1Spočítajte frekvenciu každého znaku v súbore, ktorý sa má kódovať. Zahrňte fiktívny znak na označenie konca súboru - bude to dôležité neskôr. Pre túto chvíľu, volajte ho OSZ (koniec súboru) a označiť ju ako o frekvencii 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.
- 2Uložte znaky ako uzly stromu a vložte ich do frontu priorít. Budete stavať veľký binárny strom s každým znakom ako listom, takže znaky by ste mali ukladať vo formáte, aby sa z nich mohli stať uzly 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ípade „ab ab cab“ by váš prioritný front vyzeral takto: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Uložte znaky ako uzly stromu a vložte ich do frontu priorít. - 3Začnite stavať svoj strom. Odstráňte (alebo odstráňte z radu) dve najnaliehavejšie veci z prioritného frontu. 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}
- 4Dokončite stavbu svojho stromu: vyššie uvedený krok opakujte, kým sa vo fronte nenachádza 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 znova 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.
- 5Vytvorte kódovaciu mapu. 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"}.
Tieto uzly umiestnite do frontu priorít s frekvenciou každého znaku ako prioritou jeho uzla. - 6Do výstupného súboru zahrňte kódovaciu mapu ako hlavičku. To umožní dekódovanie súboru.
- 7Kódujte súbor. Pre každý znak v súbore, ktorý sa má kódovať, napíšte binárnu postupnosť, ktorú máte uloženú na mape. 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 tomto 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
- 1Prečítajte si v huffmanovom súbore. Najprv si prečítajte hlavičku, ktorá by mala byť kódovacou mapou. Toto použite na vytvorenie 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é.
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ú. - 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.
- 3Opakujte, kým nedosiahnete EOF. Gratulujem Dekódovali ste súbor.
Prečítajte si tiež: Ako pridať stopky k powerpointu?
Súvisiace články
