Huffmanin algoritmia käytetään tietojen pakkaamiseen tai koodaamiseen. Normaalisti jokainen tekstitiedoston merkki tallennetaan kahdeksan bittiä (numeroa, joko 0 tai 1), jotka yhdistetään kyseiseen merkkiin käyttämällä ASCII -koodausta. Huffman-koodattu tiedosto hajottaa jäykän 8-bittisen rakenteen niin, että yleisimmin käytetyt merkit tallennetaan vain muutamaan bittiin ("a" voi olla "10" tai "1000" ASCII: n sijasta, joka on "01100001"). Vähiten yleiset merkit vievät usein paljon enemmän kuin 8 bittiä ('z' voi olla "00100011010"), mutta koska niitä esiintyy niin harvoin, Huffman -koodaus luo kokonaisuudessaan paljon pienemmän tiedoston kuin alkuperäinen.
Askeleet
Osa 1/2: Koodaus
Vaihe 1. Laske koodattavan tiedoston kunkin merkin taajuus
Merkitse tiedoston loppuun nuken merkki - tämä on tärkeää myöhemmin. Kutsu sitä toistaiseksi EOF: ksi (tiedoston loppu) ja merkitse sen taajuudeksi 1.
Jos haluat esimerkiksi koodata tekstitiedoston lukemalla "ab ab cab", sinulla olisi "a" taajuudella 3, "b" taajuudella 3, '' (välilyönti) taajuudella 2, "c" taajuudella 1 ja EOF taajuudella 1
Vaihe 2. Tallenna merkit puusolmuiksi ja aseta ne ensisijaiseen jonoon
Rakennat suuren binaaripuun, jossa jokainen merkki on lehti, joten sinun tulee tallentaa merkit sellaisessa muodossa, että niistä voi tulla puun solmuja. Aseta nämä solmut prioriteettijonoon, jossa kunkin merkin taajuus on sen solmun prioriteetti.
- Binaaripuu on datamuoto, jossa jokainen tieto on solmu, jossa voi olla enintään yksi vanhempi ja kaksi lasta. Se on usein piirretty haarautuvaksi puuksi, joten nimi.
- Jono on osuvasti nimetty tiedonkokoelma, jossa ensimmäinen asia jonoon tulee myös ensimmäisenä ulos (kuten jonossa odottaminen). Prioriteettijonossa tiedot tallennetaan niiden tärkeysjärjestyksessä, joten ensimmäinen asia, joka tulee esiin, on kiireellisin asia, jolla on pienin prioriteetti, eikä ensimmäinen asetettu asia.
- Esimerkissä "ab ab cab" prioriteettijonosi näyttäisi tältä: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Vaihe 3. Aloita puun rakentaminen
Poista (tai dequeue) kaksi kiireellisintä asiaa prioriteettijonosta. Luo uusi puusolmu näiden kahden solmun vanhemmaksi ja tallenna ensimmäinen solmu vasemmaksi ja toinen oikeaksi. Uuden solmun prioriteetin tulisi olla sen lapsen prioriteettien summa. Määritä sitten tämä uusi solmu prioriteettijonoon.
Ensisijainen jono näyttää nyt tältä: {'': 2, new node: 2, 'a': 3, 'b': 3}
Vaihe 4. Viimeistele puun rakentaminen:
toista yllä olevaa vaihetta, kunnes jonossa on vain yksi solmu. Huomaa, että hahmoille ja niiden taajuuksille luomiesi solmujen lisäksi alennat myös, muutut puiksi ja uusit vanhempia solmuja, solmuja, jotka ovat jo itse puita.
- Kun olet valmis, jonon viimeinen solmu on koodauspuun juuri, ja kaikki muut solmut haarautuvat siitä.
- Yleisimmin käytetyt merkit ovat puun latvaa lähimmät lehdet, kun taas harvoin käytetyt merkit sijoitetaan puun alareunaan, kauemmas juurista.
Vaihe 5. Luo koodauskartta. Kävele puun läpi päästäksesi jokaiseen hahmoon. Joka kerta, kun käyt solmun vasemmassa lapsessa, se on 0. Joka kerta kun käyt solmun oikealla lapsella, se on 1. Kun pääset hahmoon, tallenna hahmo 0- ja 1 -sekvenssillä, joka kului sen saavuttamiseen. Tämä sarja on mitä merkki koodataan kuten pakatussa tiedostossa. Tallenna merkit ja niiden sekvenssit kartalle.
- Aloita esimerkiksi juurista. Käy juuren vasemman lapsen luona ja sitten kyseisen solmun vasemman lapsen luona. Koska solmulla, jossa olet nyt, ei ole lapsia, olet saavuttanut merkin. Tämä on ' '. Koska kävelit vasemmalle kahdesti päästäksesi tänne, koodaus '' on "00".
- Tämän puun osalta kartta näyttää tältä: {'': "00", "a": "10", "b": "11", "c": "010", EOF: "011"}.
Vaihe 6. Sisällytä tulostustiedostoon koodauskartta ylätunnisteena
Tämä mahdollistaa tiedoston purkamisen.
Vaihe 7. Koodaa tiedosto
Kirjoita jokaiselle koodattavan tiedoston merkille kartalle tallentamasi binäärisarja. Kun olet lopettanut tiedoston koodaamisen, muista lisätä EOF loppuun.
- Tiedostolle "ab ab cab" koodattu tiedosto näyttää tältä: "1011001011000101011011".
- Tiedostot tallennetaan tavuina (8 bittiä tai 8 binaarilukua). Koska Huffman-koodausalgoritmi ei käytä 8-bittistä muotoa, koodattujen tiedostojen pituudet eivät usein ole kahdeksankertaisia. Loput numerot täytetään 0: lla. Tässä tapauksessa kaksi 0: ta lisätään tiedoston loppuun, mikä näyttää toiselta välilyönniltä. Tämä voi olla ongelma: mistä dekooderi tietäisi milloin lopettaa lukeminen? Kuitenkin, koska sisällytimme tiedoston lopun merkin, dekooderi pääsee tähän ja pysähtyy, jättäen huomiotta kaiken muun, joka on lisätty sen jälkeen.
Osa 2/2: Dekoodaus
Vaihe 1. Lue Huffman-koodattu tiedosto
Lue ensin otsikko, jonka pitäisi olla koodauskartta. Käytä tätä rakentaaksesi dekoodauspuun samalla tavalla kuin puun, jota käytit tiedoston koodaamiseen. Kahden puun tulee olla identtisiä.
Vaihe 2. Lue binaariluku numero kerrallaan
Kulje puun läpi lukiessasi: jos luet 0: n, siirry sen solmun vasemman lapsen kohdalle, jossa olet, ja jos luet 1: n, siirry oikean lapsen kohdalle. Kun tulet lehteen (solmu ilman lapsia), olet saavuttanut hahmon. Kirjoita merkki dekoodattuun tiedostoon.
Koska merkit tallennetaan puuhun, kunkin merkin koodeilla on etuliiteominaisuus, joten yhden merkin binäärikoodausta ei voi koskaan esiintyä toisen merkin koodauksen alussa. Kunkin merkin koodaus on täysin ainutlaatuinen. Tämä helpottaa dekoodausta
Vaihe 3. Toista, kunnes saavutat EOF: n
Onnittelut! Olet purkanut tiedoston.
