Huffmano algoritmas naudojamas duomenims suspausti arba užkoduoti. Paprastai kiekvienas tekstinio failo simbolis yra saugomas kaip aštuoni bitai (skaitmenys, 0 arba 1), susiejantys tą simbolį naudojant kodavimą, vadinamą ASCII. „Huffman“užkoduotas failas suskaido standžią 8 bitų struktūrą, todėl dažniausiai naudojami simboliai yra išsaugomi vos keliais bitais („a“gali būti „10“arba „1000“, o ne ASCII, kuris yra „01100001“). Mažiausiai paplitę simboliai dažnai užims daug daugiau nei 8 bitus („z“gali būti „00100011010“), tačiau kadangi jie pasitaiko taip retai, Huffmano kodavimas apskritai sukuria daug mažesnį failą nei originalas.
Žingsniai
1 dalis iš 2: Kodavimas
1 žingsnis. Apskaičiuokite kiekvieno koduojamo failo simbolio dažnį
Įtraukite netikrą simbolį, kad pažymėtumėte failo pabaigą - tai bus svarbu vėliau. Kol kas pavadinkite jį EOF (failo pabaiga) ir pažymėkite kaip 1 dažnį.
Pvz., Jei norite užkoduoti teksto failą „ab ab cab“, turėsite „a“su 3 dažniu, „b“su 3 dažniu, „“(tarpas) su 2 dažniu, „c“su 1 dažniu ir EOF 1 dažniu
Žingsnis 2. Išsaugokite simbolius kaip medžio mazgus ir sudėkite juos į prioritetinę eilę
Jūs sukursite didelį dvejetainį medį su kiekvienu simboliu kaip lapu, todėl turėtumėte saugoti simbolius tokiu formatu, kad jie galėtų tapti medžio mazgais. Įdėkite šiuos mazgus į prioritetų eilę, o kiekvieno simbolio dažnis - jo mazgo prioritetas.
- Dvejetainis medis yra duomenų formatas, kuriame kiekvienas duomenų elementas yra mazgas, kuriame gali būti iki vieno iš tėvų ir du vaikai. Jis dažnai piešiamas kaip šakojantis medis, taigi ir pavadinimas.
- Eilė yra taikliai pavadintas duomenų rinkinys, kuriame pirmas dalykas, kuris patenka į eilę, yra pirmas dalykas (pvz., Laukimas eilėje). Prioritetų eilėje duomenys saugomi pagal jų prioritetą, todėl pirmas dalykas, kurį reikia išgirsti, yra pats skubiausias, mažiausio prioriteto dalykas, o ne pirmas dalykas.
- Pavyzdyje „ab ab cab“jūsų prioritetų eilė atrodytų taip: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Žingsnis 3. Pradėkite kurti savo medį
Pašalinkite (arba pašalinkite) du skubiausius dalykus iš prioritetų eilės. Sukurkite naują medžio mazgą, kuris bus šių dviejų mazgų tėvas, pirmąjį mazgą išsaugodami kaip kairįjį, o antrąjį - kaip dešinįjį. Naujo mazgo prioritetas turėtų būti jo vaiko prioritetų suma. Tada įtraukite šį naują mazgą į prioritetų eilę.
Prioritetų eilė dabar atrodo taip: {'': 2, naujas mazgas: 2, 'a': 3, 'b': 3}
Žingsnis 4. Baikite statyti savo medį:
kartokite aukščiau aprašytą veiksmą, kol eilėje bus tik vienas mazgas. Atminkite, kad be mazgų, kuriuos sukūrėte simboliams ir jų dažniui, jūs taip pat būsite nuvertę, paversite medžiais ir pakartotinai įveiksite tėvų mazgus, mazgus, kurie jau yra medžiai.
- Kai baigsite, paskutinis eilės mazgas bus kodavimo medžio šaknis, o visi kiti mazgai nuo jo išsišakos.
- Dažniausiai naudojami simboliai bus lapai, esantys arčiausiai medžio viršūnės, o retai naudojami simboliai bus išdėstyti medžio apačioje, toliau nuo šaknies.
Žingsnis 5. Sukurkite kodavimo žemėlapį. Eikite per medį, kad pasiektumėte kiekvieną personažą. Kiekvieną kartą, kai aplankote kairįjį mazgo vaiką, tai yra „0“. Kiekvieną kartą, kai aplankote tinkamą mazgo vaiką, tai yra „1“. Kai susipažinsite su simboliu, išsaugokite simbolį su 0 ir 1 sekomis, kurių prireikė ten patekti. Ši seka simbolis bus užkoduotas kaip suspaustame faile. Išsaugokite simbolius ir jų sekas žemėlapyje.
- Pavyzdžiui, pradėkite nuo šaknies. Aplankykite šaknies kairįjį vaiką, o tada - kairįjį mazgo vaiką. Kadangi mazgas, kuriame esate dabar, neturi vaikų, jūs pasiekėte charakterį. Tai yra ' '. Kadangi du kartus vaikščiojote kairėn, kad atvyktumėte čia, „“kodavimas yra „00“.
- Šio medžio žemėlapis atrodys taip: {'': "00", 'a': "10", "b": "11", "c": "010", EOF: "011"}.
Žingsnis 6. Išvesties faile įtraukite kodavimo žemėlapį kaip antraštę
Tai leis failą iššifruoti.
Žingsnis 7. Užšifruokite failą
Kad kiekvienas failo simbolis būtų užkoduotas, parašykite dvejetainę seką, kurią išsaugojote žemėlapyje. Baigę koduoti failą, būtinai pridėkite EOF prie pabaigos.
- Failui „ab ab cab“užkoduotas failas atrodys taip: „1011001011000101011011“.
- Failai saugomi kaip baitai (8 bitai arba 8 dvejetainiai skaitmenys). Kadangi „Huffman“kodavimo algoritmas nenaudoja 8 bitų formato, užkoduotų failų ilgis dažnai nėra 8 kartų. Likę skaitmenys užpildomi 0. Tokiu atveju failo pabaigoje bus pridėti du 0, o tai atrodo kaip kita erdvė. Tai gali būti problema: kaip dekoderis žinotų, kada nustoti skaityti? Tačiau, kadangi įtraukėme failo pabaigos simbolį, dekoderis prie to pripras ir sustos, nekreipdamas dėmesio į viską, kas buvo pridėta vėliau.
2 dalis iš 2: Dekodavimas
Žingsnis 1. Perskaitykite Huffmano koduotą failą
Pirmiausia perskaitykite antraštę, kuri turėtų būti kodavimo žemėlapis. Naudokite tai dekodavimo medžiui sukurti taip, kaip sukūrėte medį, kurį naudojote koduodami failą. Abu medžiai turi būti vienodi.
Žingsnis 2. Vienu metu skaitykite dvejetainį skaitmenį
Skaitydami pereikite medį: jei skaitote „0“, eikite į kairįjį mazgo, kuriame esate, o jei skaitote „1“, eikite į dešinįjį vaiką. Pasiekę lapą (mazgą be vaikų), priėjote prie veikėjo. Įrašykite simbolį į iššifruotą failą.
Kadangi simboliai saugomi medyje, kiekvieno simbolio kodai turi priešdėlio ypatybę, todėl bet kurio simbolio dvejetainė koduotė negali atsirasti kito simbolio kodavimo pradžioje. Kiekvieno simbolio kodavimas yra visiškai unikalus. Tai labai palengvina dekodavimą
Žingsnis 3. Kartokite, kol pasieksite EOF
Sveikinu! Jūs iššifravote failą.
