Andmete tihendamiseks või kodeerimiseks kasutatakse Huffmani algoritmi. Tavaliselt salvestatakse tekstifaili iga märk kaheksa bitina (numbrid, kas 0 või 1), mis vastavad sellele märgile, kasutades kodeeringut nimega ASCII. Huffmani kodeeritud fail lagundab jäiga 8-bitise struktuuri, nii et kõige sagedamini kasutatavad märgid salvestatakse vaid mõne bitini ('a' võib olla "10" või "1000", mitte ASCII, mis on "01100001"). Kõige vähem levinud märgid võtavad sageli palju rohkem kui 8 bitti ('z' võib olla "00100011010"), kuid kuna neid esineb nii harva, loob Huffmani kodeering tervikuna palju väiksema faili kui originaal.
Sammud
Osa 1: Kodeerimine
Samm 1. Loendage kodeeritavas failis iga märgi sagedus
Faili lõpu märkimiseks lisage näiv märk - see on hiljem oluline. Praegu nimetage seda EOF -iks (faili lõpp) ja märkige see sageduseks 1.
Näiteks kui soovite kodeerida tekstifaili tekstiga „ab ab cab”, oleks teil „a” sagedusega 3, „b” sagedusega 3, „” (tühik) sagedusega 2, „c” sagedusega 1 ja EOF sagedusega 1
Samm 2. Salvestage märgid puusõlmedena ja asetage need prioriteetsesse järjekorda
Ehitate suure kahendpuu, kus iga märk on leht, nii et peaksite salvestama märgid sellises vormingus, et neist saaksid puu sõlmed. Asetage need sõlmed prioriteetsesse järjekorda, kus iga märgi sagedus on sõlme prioriteet.
- Binaarpuu on andmevorming, kus iga andmestik on sõlm, millel võib olla kuni üks vanem ja kaks last. Seda joonistatakse sageli hargneva puuna, sellest ka nimi.
- Järjekord on tabava nimega andmekogu, kus esimene asi, mis järjekorda läheb, on ka esimene asi, mis tuleb välja (nagu järjekorras ootamine). Prioriteedijärjekorras salvestatakse andmed nende prioriteetsuse järjekorras, nii et esimene asi, mis tuleb välja, on kõige pakilisem asi, kõige väiksema prioriteediga asi, mitte esimene loodetud.
- Näites "ab ab cab" näeks teie eelisjärjekord välja selline: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Samm 3. Alustage oma puu ehitamist
Eemaldage (või tühistage) kaks kõige pakilisemat asja prioriteedijärjekorrast. Looge uus puusõlm nende kahe sõlme vanemaks, salvestades esimese sõlme vasaku ja teise parema lapsena. Uue sõlme prioriteet peaks olema selle lapse prioriteetide summa. Seejärel lisage see uus sõlm prioriteetsesse järjekorda.
Prioriteedijärjekord näeb nüüd välja selline: {'': 2, new node: 2, 'a': 3, 'b': 3}
Samm 4. Lõpetage oma puu ehitamine:
korrake ülaltoodud sammu, kuni järjekorras on ainult üks sõlm. Pange tähele, et lisaks tähemärkidele ja nende sagedustele loodud sõlmedele teete ka deikki, muutute puudeks ja loote uuesti vanemasõlmed, sõlmed, mis on juba ise puud.
- Kui olete lõpetanud, on järjekorra viimane sõlm kodeerimispuu juur, millest kõik teised sõlmed hargnevad.
- Kõige sagedamini kasutatavad märgid on puu ülaosale lähimad lehed, harva kasutatavad märgid aga puu allosas, juurest kaugemal.
Samm 5. Looge kodeerimiskaart. Kõigi tegelaste juurde jõudmiseks kõndige läbi puu. Iga kord, kui külastate sõlme vasakpoolset last, on see "0". Iga kord, kui külastate sõlme õiget last, on see 1. Kui jõuate tegelase juurde, salvestage märk koos 0 -de ja 1 -de jadaga, mis kulus sinna jõudmiseks. See jada on see, mida märk kodeeritakse nagu tihendatud failis. Salvestage märgid ja nende järjestused kaardile.
- Alustage näiteks juurest. Külastage juure vasakut last ja seejärel selle sõlme vasakpoolset last. Kuna sõlmel, kus praegu viibite, pole lapsi, olete jõudnud tegelaseni. See on ' '. Kuna kõndisite siia jõudmiseks kaks korda vasakule, on '' kodeering "00".
- Selle puu puhul näeb kaart välja selline: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Samm 6. Väljundfailis lisage päisesse kodeerimiskaart
See võimaldab faili dekodeerida.
Samm 7. Kodeerige fail
Kirjutage iga kodeeritava faili märgi jaoks kaardile salvestatud binaarjärjestus. Kui olete faili kodeerimise lõpetanud, lisage kindlasti EOF lõppu.
- Faili "ab ab cab" puhul näeb kodeeritud fail välja selline: "1011001011000101011011".
- Failid salvestatakse baitidena (8 bitti või 8 binaarset numbrit). Kuna Huffmani kodeerimisalgoritm ei kasuta 8-bitist vormingut, ei ole kodeeritud failide pikkused sageli kaheksakordsed. Ülejäänud numbrid täidetakse 0-ga. Sel juhul lisatakse faili lõppu kaks 0 -d, mis näeb välja nagu teine tühik. See võib olla probleem: kuidas dekooder teaks, millal lugemine lõpetada? Kuid kuna lisasime faili lõppmärgi, jõuab dekooder selleni ja peatub, ignoreerides kõike muud, mis on pärast seda lisatud.
Osa 2: Dekodeerimine
Samm 1. Lugege Huffmani kodeeritud faili
Kõigepealt lugege päist, mis peaks olema kodeerimiskaart. Kasutage seda dekodeerimispuu ehitamiseks samamoodi, nagu ehitasite puu, mida kasutasite faili kodeerimiseks. Need kaks puud peaksid olema identsed.
Samm 2. Lugege binaarset numbrit korraga
Pöörake lugedes puust läbi: kui loete „0”, minge selle sõlme vasakule alamle, kus olete, ja kui loete „1”, siis minge parema lapse juurde. Kui jõuate lehele (sõlme ilma lasteta), olete jõudnud tegelase juurde. Kirjutage märk dekodeeritud faili.
Märkide puusse salvestamise viisi tõttu on iga tähemärgi koodidel eesliite omadus, nii et ühegi märgi binaarne kodeering ei saa kunagi tekkida teise märgi kodeerimise alguses. Iga märgi kodeering on täiesti ainulaadne. See muudab dekodeerimise palju lihtsamaks
Samm 3. Korrake, kuni jõuate EOF -i
Palju õnne! Olete faili dekodeerinud.
