Algoritmi i Huffman përdoret për të ngjeshur ose koduar të dhënat. Normalisht, çdo karakter në një skedar teksti ruhet si tetë bit (shifra, ose 0 ose 1) që i bashkohen atij karakteri duke përdorur një kodim të quajtur ASCII. Një skedar i koduar me Huffman zbërthen strukturën e ngurtë 8-bit në mënyrë që karakteret më të përdorura të ruhen në vetëm disa bit ('a' mund të jetë "10" ose "1000" në vend të ASCII, që është "01100001") Karakteret më pak të zakonshme, atëherë, shpesh do të marrin shumë më tepër se 8 bit ('z' mund të jetë "00100011010"), por për shkak se ato ndodhin shumë rrallë, kodimi Huffman, në tërësi, krijon një skedar shumë më të vogël se origjinali.
Hapa
Pjesa 1 nga 2: Kodimi
Hapi 1. Numëroni frekuencën e secilit karakter në skedarin që do të kodohet
Përfshini një personazh fals për të shënuar fundin e skedarit - kjo do të jetë e rëndësishme më vonë. Tani për tani, quajeni EOF (fundi i skedarit) dhe shënojeni atë si një frekuencë prej 1.
Për shembull, nëse doni të kodoni një skedar teksti që lexon "ab ab cab", do të kishit 'a' me frekuencë 3, 'b' me frekuencë 3, '' (hapësirë) me frekuencë 2, 'c' me frekuencë 1, dhe EOF me frekuencën 1
Hapi 2. Ruani karakteret si nyje pemësh dhe vendosini në radhë prioritare
Ju do të ndërtoni një pemë të madhe binare me secilin karakter si një gjethe, kështu që ju duhet t'i ruani personazhet në një format të tillë që të mund të bëhen nyje të pemës. Vendosini këto nyje në një radhë përparësie me frekuencën e secilit karakter si përparësi të nyjës së saj.
- Një pemë binare është një format i të dhënave ku secila pjesë e të dhënave është një nyje që mund të ketë deri në një prind dhe dy fëmijë. Shpesh vizatohet si një pemë e degëzuar, prandaj edhe emri.
- Një radhë është një koleksion i të dhënave me emrin e duhur ku gjëja e parë që futet në radhë është gjithashtu gjëja e parë që del (si pritja në radhë). Në një radhë përparësie, të dhënat ruhen sipas përparësisë së tyre, kështu që gjëja e parë që del është gjëja më urgjente, ajo me përparësinë më të vogël, dhe jo gjëja e parë e enkuar.
- Në shembullin "ab ab cab", radha juaj e përparësisë do të duket kështu: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Hapi 3. Filloni të ndërtoni pemën tuaj
Hiqni (ose hiqni) dy gjërat më urgjente nga radha e përparësisë. Krijoni një nyje peme të re që të jetë prindi i këtyre dy nyjeve, duke ruajtur nyjen e parë si fëmijën e saj të majtë dhe të dytën si fëmijën e saj të djathtë. Prioriteti i nyjes së re duhet të jetë shuma e përparësive të fëmijës së saj. Pastaj vendosni këtë nyje të re në radhën e përparësive.
Radha e përparësisë tani duket kështu: {'': 2, nyja e re: 2, 'a': 3, 'b': 3}
Hapi 4. Përfundoni ndërtimin e pemës tuaj:
përsëritni hapin e mësipërm derisa të ketë vetëm një nyje në radhë. Vini re se përveç nyjeve që keni krijuar për personazhet dhe frekuencat e tyre, ju gjithashtu do të jeni duke hequr qafe, duke u shndërruar në pemë dhe duke ri-enekuuar nyjet mëmë, nyje që tashmë janë vetë pemë.
- Kur të keni mbaruar, nyja e fundit në radhë do të jetë rrënja e pemës koduese, me të gjitha nyjet e tjera që degëzohen prej saj.
- Karakteret më të përdorura do të jenë gjethet më afër majës së pemës, ndërsa personazhet e përdorur rrallë do të vendosen në fund të pemës, më larg nga rrënja.
Hapi 5. Krijoni një hartë kodimi. Ecni nëpër pemë për të arritur secilin personazh. Sa herë që vizitoni fëmijën e majtë të një nyje, është një '0'. Sa herë që vizitoni fëmijën e duhur të një nyje, është një '1'. Kur të arrini te një personazh, ruajeni karakterin me sekuencën e 0s dhe 1s që u deshën për të arritur atje. Kjo sekuencë është ajo që karakteri do të kodohet si në skedarin e ngjeshur. Ruani personazhet dhe sekuencat e tyre në një hartë.
- Për shembull, filloni në rrënjë. Vizitoni fëmijën e majtë të rrënjës, dhe më pas vizitoni fëmijën e majtë të asaj nyje. Meqenëse nyja në të cilën jeni tani nuk ka fëmijë, keni arritur një karakter. Kjo është ' '. Meqenëse keni ecur majtas dy herë për të arritur këtu, kodimi për '' është "00".
- Për këtë pemë, harta do të duket kështu: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Hapi 6. Në skedarin dalës, përfshini hartën e kodimit si kokë
Kjo do të lejojë deshifrimin e skedarit.
Hapi 7. Kodoni skedarin
Për secilin karakter në skedar që do të kodohet, shkruani sekuencën binare që keni ruajtur në hartë. Pasi të keni përfunduar kodimin e skedarit, sigurohuni që të shtoni EOF deri në fund.
- Për skedarin "ab ab cab", skedari i koduar do të duket kështu: "1011001011000101011011".
- Skedarët ruhen si byte (8 bit, ose 8 shifra binare). Për shkak se algoritmi i kodimit Huffman nuk përdor formatin 8-bit, skedarët e koduar shpesh nuk do të kenë gjatësi që janë shumëfish të 8. Shifrat e mbetura do të plotësohen me 0. Në këtë rast, dy 0 do të shtoheshin në fund të skedarit, i cili duket si një hapësirë tjetër. Ky mund të jetë një problem: si do ta dinte deshifruesi kur të ndalonte së lexuari? Sidoqoftë, për shkak se kemi përfshirë një karakter të skedarit, dekoduesi do të arrijë në këtë dhe pastaj do të ndalojë, duke injoruar çdo gjë tjetër që është shtuar më pas.
Pjesa 2 nga 2: Dekodimi
Hapi 1. Lexoni në një skedar të koduar nga Huffman
Së pari, lexoni titullin, i cili duhet të jetë harta e kodimit. Përdoreni këtë për të ndërtuar një pemë deshifrimi në të njëjtën mënyrë si keni ndërtuar pemën që keni përdorur për të koduar skedarin. Të dy pemët duhet të jenë identike.
Hapi 2. Lexoni në binar një shifër në të njëjtën kohë
Përshkoni pemën ndërsa lexoni: nëse lexoni në '0', shkoni te fëmija i majtë i nyjës ku jeni, dhe nëse lexoni në '1', shkoni te fëmija i duhur. Kur arrini një gjethe (një nyje pa fëmijë), keni arritur në një personazh. Shkruani personazhin në skedarin e deshifruar.
Për shkak të mënyrës së ruajtjes së karaktereve në pemë, kodet për secilin karakter kanë një pronë parashtese, kështu që kodimi binar i asnjë karakteri nuk mund të ndodhë në fillim të kodimit të një karakteri tjetër. Kodimi për secilin personazh është krejtësisht unik. Kjo e bën deshifrimin shumë më të lehtë
Hapi 3. Përsëriteni derisa të arrini në EOF
Urime! Ju e keni deshifruar skedarin.
