Huffmana algoritmu izmanto, lai saspiestu vai kodētu datus. Parasti katra teksta faila rakstzīme tiek saglabāta kā astoņi biti (cipari, 0 vai 1), kas atbilst šai rakstzīmei, izmantojot kodējumu ar nosaukumu ASCII. Huffmana kodēts fails nojauc stingro 8 bitu struktūru, lai visbiežāk izmantotās rakstzīmes tiktu saglabātas tikai dažos bitos ('a' varētu būt "10" vai "1000", nevis ASCII, kas ir "01100001"). Retāk sastopamās rakstzīmes bieži aizņem daudz vairāk par 8 bitiem ('z' var būt "00100011010"), taču, tā kā tās sastopamas tik reti, Hufmana kodējums kopumā rada daudz mazāku failu nekā oriģināls.
Soļi
1. daļa no 2: Kodēšana
1. solis. Saskaitiet katras kodējamā faila rakstzīmes
Iekļaujiet fiktīvu rakstzīmi, lai atzīmētu faila beigas - tas būs svarīgi vēlāk. Pagaidām sauciet to par EOF (faila beigas) un atzīmējiet to kā biežumu 1.
Piemēram, ja vēlaties kodēt teksta failu ar tekstu “ab ab cab”, jums būtu “a” ar frekvenci 3, “b” ar frekvenci 3,”” (atstarpe) ar frekvenci 2, “c” ar frekvenci 1 un EOF ar frekvenci 1
2. Saglabājiet rakstzīmes kā koku mezglus un ievietojiet tās prioritārajā rindā
Jūs veidosit lielu bināro koku ar katru rakstzīmi kā lapu, tāpēc rakstzīmes jāsaglabā tādā formātā, lai tās varētu kļūt par koka mezgliem. Ievietojiet šos mezglus prioritāšu rindā ar katras rakstzīmes frekvenci kā tās mezgla prioritāti.
- Binārais koks ir datu formāts, kurā katrs datu gabals ir mezgls, kurā var būt līdz vienam vecākam un diviem bērniem. To bieži zīmē kā zarojošu koku, līdz ar to arī nosaukumu.
- Rinda ir precīzi nosaukta datu kolekcija, kurā pirmā lieta, kas jāiet rindā, ir arī pirmā, kas iznāk (piemēram, gaidīšana rindā). Prioritāšu rindā dati tiek glabāti to prioritātes secībā, lai pirmā lieta, kas iznāktu, ir vissteidzamākā lieta, lieta ar mazāko prioritāti, nevis pirmā lieta.
- “Ab ab cab” piemērā prioritārā rinda izskatītos šādi: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
3. Sāciet veidot savu koku
Noņemiet (vai novietojiet) divas steidzamākās lietas no prioritārās rindas. Izveidojiet jaunu koka mezglu, lai kļūtu par šo divu mezglu vecākiem, pirmo mezglu saglabājot kā kreiso bērnu, bet otro - kā labo. Jaunā mezgla prioritātei jābūt tā bērna prioritāšu summai. Pēc tam iezīmējiet šo jauno mezglu prioritāro rindā.
Prioritātes rinda tagad izskatās šādi: {'': 2, jauns mezgls: 2, 'a': 3, 'b': 3}
4. solis. Pabeidziet koka veidošanu:
atkārtojiet iepriekš minēto darbību, līdz rindā ir tikai viens mezgls. Ņemiet vērā, ka papildus mezgliem, ko izveidojāt rakstzīmēm un to frekvencēm, jūs arī dequē, pārvēršaties par kokiem un atkārtoti uzņemat vecāku mezglus-mezglus, kas jau paši ir koki.
- Kad esat pabeidzis, pēdējais rindas mezgls būs kodēšanas koka sakne, un visi pārējie mezgli no tā atzarojas.
- Visbiežāk izmantotās rakstzīmes būs lapas, kas atrodas vistuvāk koka galotnei, savukārt reti lietotās rakstzīmes tiks novietotas koka apakšā, tālāk no saknes.
Solis 5. Izveidojiet kodēšanas karti. Ejiet pa koku, lai sasniegtu katru rakstzīmi. Katru reizi, kad apmeklējat mezgla kreiso bērnu, tas ir “0”. Katru reizi, kad apmeklējat mezgla pareizo bērnu, tas ir “1”. Kad tiekat līdz rakstzīmei, saglabājiet rakstzīmi ar 0s un 1s secību, kas bija nepieciešama, lai tur nokļūtu. Šī secība ir tāda, kāda rakstzīme tiks kodēta kā saspiestajā failā. Saglabājiet rakstzīmes un to secības kartē.
- Piemēram, sāciet no saknes. Apmeklējiet saknes kreiso bērnu un pēc tam apmeklējiet šī mezgla kreiso bērnu. Tā kā mezglā, kurā pašlaik atrodaties, nav bērnu, esat sasniedzis rakstzīmi. Tas ir ' '. Tā kā jūs divreiz gājāt pa kreisi, lai nokļūtu šeit, '' kodējums ir "00".
- Šim kokam karte izskatīsies šādi: {'': "00", 'a': "10", "b ':" 11 "," c': "010", EOF: "011"}.
6. solis. Izejas failā iekļaujiet kodēšanas karti kā galveni
Tas ļaus failu atšifrēt.
7. darbība. Šifrējiet failu
Lai katra kodētā faila rakstzīme tiktu ierakstīta kartē, ierakstiet bināro secību. Kad esat pabeidzis faila kodēšanu, noteikti pievienojiet EOF beigām.
- Failam "ab ab cab" kodētais fails izskatīsies šādi: "1011001011000101011011".
- Faili tiek saglabāti kā baiti (8 biti vai 8 bināri cipari). Tā kā Huffmana kodēšanas algoritms neizmanto 8 bitu formātu, kodēto failu garums bieži vien nav 8. Atlikušie cipari tiks aizpildīti ar 0. Šajā gadījumā faila beigās tiks pievienoti divi 0, kas izskatās kā cita vieta. Tā varētu būt problēma: kā dekodētājs zinātu, kad jāpārtrauc lasīšana? Tomēr, tā kā mēs iekļāvām faila beigu rakstzīmi, dekodētājs nokļūs pie šī un pēc tam apstāsies, ignorējot visu citu, kas tika pievienots pēc tam.
2. daļa no 2: Atšifrēšana
1. solis. Lasiet Huffmana kodētā failā
Vispirms izlasiet galveni, kurai vajadzētu būt kodēšanas kartei. Izmantojiet to, lai izveidotu dekodēšanas koku tādā pašā veidā, kā izveidojāt koku, ko izmantojāt faila kodēšanai. Abiem kokiem jābūt identiskiem.
2. solis. Vienā reizē izlasiet vienu ciparu
Šķērsojiet koku, lasot: ja lasāt ar “0”, dodieties uz mezgla kreiso bērnu, pie kura atrodaties, un, ja lasāt ar “1”, dodieties uz labo bērnu. Sasniedzot lapu (mezglu bez bērniem), jūs esat nonācis pie rakstura. Ierakstiet rakstzīmi dekodētajā failā.
Tā kā rakstzīmes tiek glabātas kokā, katras rakstzīmes kodiem ir prefiksa rekvizīts, tāpēc nevienas rakstzīmes binārais kodējums nekad nevar notikt citas rakstzīmes kodēšanas sākumā. Katras rakstzīmes kodējums ir pilnīgi unikāls. Tas ievērojami atvieglo dekodēšanu
Solis 3. Atkārtojiet, līdz sasniedzat EOF
Apsveicam! Jūs esat atšifrējis failu.
