Algorithm ya Huffman hutumiwa kubana au kusimba data. Kawaida, kila mhusika katika faili ya maandishi huhifadhiwa kama bits nane (nambari, ama 0 au 1) ramani hiyo kwa mhusika huyo kwa kutumia usimbuaji uitwao ASCII. Faili iliyosimbwa na Huffman inavunja muundo mgumu wa biti 8 ili herufi zinazotumiwa sana zihifadhiwe kwa vipande vichache tu ('a' inaweza kuwa "10" au "1000" badala ya ASCII, ambayo ni "01100001"). Wahusika wasio wa kawaida, basi, mara nyingi huchukua zaidi ya bits 8 ('z' inaweza kuwa "00100011010"), lakini kwa sababu hujitokeza mara chache sana, usimbuaji wa Huffman, kwa ujumla, huunda faili ndogo sana kuliko ile ya asili.
Hatua
Sehemu ya 1 ya 2: Usimbaji
Hatua ya 1. Hesabu masafa ya kila herufi kwenye faili itakayosimbwa
Jumuisha tabia ya dummy kuashiria mwisho wa faili - hii itakuwa muhimu baadaye. Kwa sasa, iite EOF (mwisho wa faili) na uweke alama kama kuwa na masafa ya 1.
Kwa mfano, ikiwa unataka kusimba faili ya maandishi kusoma "ab ab cab," ungekuwa na 'a' na masafa 3, 'b' na masafa 3, '' (nafasi) na masafa 2, 'c' na masafa 1, na EOF na masafa ya 1
Hatua ya 2. Hifadhi herufi kama nodi za miti na uziweke kwenye foleni ya kipaumbele
Utakuwa ukijenga mti mkubwa wa kibinadamu na kila mhusika kama jani, kwa hivyo unapaswa kuhifadhi wahusika kwa muundo ambao wanaweza kuwa node za mti. Weka nodi hizi kwenye foleni ya kipaumbele na masafa ya kila mhusika kama kipaumbele cha node yake.
- Mti wa binary ni muundo wa data ambapo kila kipande cha data ni node ambayo inaweza kuwa na mzazi mmoja na watoto wawili. Mara nyingi hutolewa kama mti wa matawi, kwa hivyo jina.
- Foleni ni mkusanyiko wa data uliopewa jina ambalo kitu cha kwanza kuingia kwenye foleni pia ni jambo la kwanza kutoka (kama kusubiri kwenye foleni). Katika foleni ya kipaumbele, data zinahifadhiwa kwa utaratibu wa vipaumbele vyao, ili jambo la kwanza kutoka ni jambo la haraka zaidi, jambo lenye kipaumbele kidogo, badala ya jambo la kwanza lililowekwa.
- Katika mfano wa "ab ab cab", foleni yako ya kipaumbele ingeonekana kama hii: {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Hatua ya 3. Anza kujenga mti wako
Ondoa (au usue) vitu viwili vya haraka zaidi kutoka kwenye foleni ya kipaumbele. Unda node mpya ya mti kuwa mzazi wa nodi hizi mbili, ukihifadhi nodi ya kwanza kama mtoto wake wa kushoto na wa pili kama mtoto wake wa kulia. Kipaumbele cha node mpya inapaswa kuwa jumla ya vipaumbele vya mtoto wake. Kisha weka nodi hii mpya kwenye foleni ya kipaumbele.
Foleni ya kipaumbele sasa inaonekana kama hii: {'': 2, node mpya: 2, 'a': 3, 'b': 3}
Hatua ya 4. Maliza kujenga mti wako:
kurudia hatua hiyo hapo juu mpaka iwe na node moja tu kwenye foleni. Kumbuka kuwa kwa kuongezea nambari ulizoziunda kwa wahusika na masafa yao, utakuwa pia unachagua, ukibadilika kuwa miti, na ukirudisha nodi za wazazi, nodi ambazo tayari ni miti.
- Unapomaliza, node ya mwisho kwenye foleni itakuwa mzizi wa mti wa usimbuaji, na nodi zingine zote zikitawi kutoka kwake.
- Herufi zinazotumiwa mara nyingi zitakuwa majani yaliyo karibu zaidi na juu ya mti, wakati herufi ambazo hazitumiwi sana zitawekwa chini ya mti, mbali zaidi na mzizi.
Hatua ya 5. Unda ramani ya usimbuaji. Tembea kupitia mti kufikia kila mhusika. Kila wakati unapotembelea mtoto wa kushoto wa nodi, hiyo ni '0'. Kila wakati unapotembelea mtoto wa kulia wa nodi, hiyo ni '1'. Unapofika kwa mhusika, weka mhusika na mlolongo wa 0 na 1 ambazo ilichukua kufika hapo. Mlolongo huu ndio mhusika atasimbwa kama kwenye faili iliyoshinikizwa. Hifadhi wahusika na mfuatano wao kwenye ramani.
- Kwa mfano, anza kwenye mzizi. Tembelea mtoto wa kushoto wa mzizi, na kisha utembelee mtoto huyo wa kushoto wa nodi. Kwa kuwa node unayo sasa haina watoto wowote, umefikia tabia. Hii ni ' '. Kwa kuwa ulitembea kushoto mara mbili kufika hapa, encoding ya '' ni "00".
- Kwa mti huu, ramani itaonekana kama hii: {'': "00", 'a': "10", 'b': "11", 'c': "010", EOF: "011"}.
Hatua ya 6. Katika faili ya pato, jumuisha ramani ya usimbuaji kama kichwa
Hii itaruhusu faili kutolewa.
Hatua ya 7. Encode faili
Kwa kila herufi kwenye faili hiyo itasimbwa, andika mlolongo wa binary ambao umehifadhi kwenye ramani. Mara tu ukimaliza kusimba faili, hakikisha uongeze EOF hadi mwisho.
- Kwa faili "ab ab cab", faili iliyosimbwa itaonekana kama hii: "1011001011000101011011".
- Faili zimehifadhiwa kama ka (bits 8, au tarakimu 8 za binary). Kwa sababu hesabu ya Usimbuaji ya Huffman haitumii fomati ya 8-bit, faili zilizosimbwa mara nyingi hazitakuwa na urefu ambao ni kuzidisha kwa 8. Nambari zilizobaki zitajazwa na 0s. Katika kesi hii, 0s mbili zingeongezwa mwishoni mwa faili, ambayo inaonekana kama nafasi nyingine. Hii inaweza kuwa shida: ni vipi dekoda angejua wakati wa kuacha kusoma? Walakini, kwa sababu tulijumuisha herufi ya mwisho wa faili, kisimbuzi kitafika kwa hii na kisha kuacha, kupuuza kitu kingine chochote kilichoongezwa baadaye.
Sehemu ya 2 ya 2: Kusimba
Hatua ya 1. Soma katika faili iliyosimbwa na Huffman
Kwanza, soma kichwa, ambayo inapaswa kuwa ramani ya usimbuaji. Tumia hii kujenga mti wa kusimba kwa njia ile ile uliyoijenga mti uliotumia kusimba faili. Miti miwili inapaswa kufanana.
Hatua ya 2. Soma kwa tarakimu moja kwa wakati mmoja
Tembeza mti unavyosoma: ikiwa unasoma kwa '0', nenda kwa mtoto wa kushoto wa nodi uliyopo, na ukisoma katika '1', nenda kwa mtoto wa kulia. Unapofikia jani (node bila watoto wowote), umefika kwa mhusika. Andika herufi kwenye faili iliyotengwa.
Kwa sababu ya wahusika waliohifadhiwa kwenye mti, nambari za kila mhusika zina mali ya kiambishi awali, ili usimbuaji wa kibinadamu wa wahusika usiweze kutokea mwanzoni mwa usimbuaji wa mhusika mwingine. Usimbuaji wa kila mhusika ni wa kipekee kabisa. Hii inafanya usuluhishi kuwa rahisi zaidi
Hatua ya 3. Rudia hadi ufikie EOF
Hongera! Umesimbua faili.
