Հաֆֆմանի ալգորիթմը օգտագործվում է տվյալների սեղմման կամ կոդավորման համար: Սովորաբար, տեքստային ֆայլի յուրաքանչյուր նիշ պահվում է որպես ութ բիթ (թվանշան ՝ 0 կամ 1), որը քարտեզագրվում է այդ բնույթին ՝ օգտագործելով ASCII կոչվող կոդավորումը: Huffman- ի կողմից կոդավորված ֆայլը քայքայում է կոշտ 8-բիթանոց կառուցվածքը, այնպես որ ամենից հաճախ օգտագործվող նիշերը պահվում են ընդամենը մի քանի բիթում («a»-ն կարող է լինել «10» կամ «1000», այլ ոչ թե ASCII, որը «01100001» է)): Այսպիսով, ամենաքիչ տարածված կերպարները հաճախ կգրավեն շատ ավելի քան 8 բիթ («z» - ն կարող է լինել «00100011010»), բայց քանի որ դրանք շատ հազվադեպ են հանդիպում, Huffman- ի կոդավորումը, ընդհանուր առմամբ, ստեղծում է շատ ավելի փոքր ֆայլ, քան բնօրինակը:
Քայլեր
2 -րդ մաս 1 -ից ՝ կոդավորում
Քայլ 1. Հաշվեք կոդավորվող ֆայլի յուրաքանչյուր նիշի հաճախականությունը:
Ֆայլի վերջը նշելու համար ներառեք կեղծ կերպար, սա հետագայում կարևոր կլինի: Առայժմ այն անվանեք EOF (ֆայլի վերջ) և նշեք որպես 1 հաճախականությամբ:
Օրինակ, եթե ցանկանում եք ծածկագրել «ab ab cab» գրությամբ տեքստային ֆայլ, ապա կունենաք «a» 3 հաճախականությամբ, «b» ՝ 3 հաճախականությամբ, «» (տարածություն) 2 հաճախականությամբ, «c» ՝ 1 հաճախականությամբ:, և EOF 1 հաճախականությամբ:
Քայլ 2. Նիշերը պահեք որպես ծառի հանգույց և տեղադրեք դրանք առաջնահերթ հերթում:
Դուք կկառուցեք մեծ երկուական ծառ ՝ յուրաքանչյուր բնույթով որպես տերև, այնպես որ դուք պետք է կերպարները պահեք այնպիսի ձևաչափով, որ դրանք կարող են դառնալ ծառի հանգույցներ: Տեղադրեք այս հանգույցները առաջնահերթ հերթում `յուրաքանչյուր բնույթի հաճախականությունը որպես իր հանգույցի առաջնահերթություն:
- Երկուական ծառը տվյալների ձևաչափ է, որտեղ յուրաքանչյուր տվյալների մի հանգույց է, որը կարող է ունենալ մինչև մեկ ծնող և երկու երեխա: Այն հաճախ նկարվում է որպես ճյուղավորված ծառ, ուստի և անունը:
- Հերթը տվյալների ճիշտ հավաքածու է, որտեղ հերթը մտնելը նաև առաջինը դուրս գալն է (ինչպես հերթում սպասելը): Առաջնահերթ հերթում տվյալները պահվում են ըստ իրենց առաջնահերթության, այնպես որ առաջին բանը, որ դուրս է գալիս, ամենահրատապ բանն է, ամենափոքր առաջնահերթությունը, և ոչ թե առաջին բանը, որ պարունակվում է:
- «Ab ab cab» - ի օրինակում ձեր առաջնահերթ հերթն այսպիսի տեսք կունենա ՝ {'c': 1, EOF: 1, '': 2, 'a': 3, 'b': 3}
Քայլ 3. Սկսեք կառուցել ձեր ծառը:
Հեռացրեք (կամ հեռացրեք) երկու առավել հրատապ իրերը առաջնահերթ հերթից: Ստեղծեք նոր ծառի հանգույց, որը կլինի այս երկու հանգույցների ծնողը ՝ առաջին հանգույցը պահելով որպես ձախ, իսկ երկրորդը ՝ որպես աջ երեխա: Նոր հանգույցի առաջնահերթությունը պետք է լինի իր երեխայի առաջնահերթությունների գումարը: Հետո այս նոր հանգույցը շարեք առաջնահերթության հերթում:
Առաջնահերթ հերթն այժմ այս տեսքն ունի ՝ {'': 2, նոր հանգույց `2, 'a': 3, 'b': 3}
Քայլ 4. Ավարտեք ձեր ծառի կառուցումը
կրկնել վերը նշված քայլը, մինչև հերթում մնա միայն մեկ հանգույց: Նկատի ունեցեք, որ կերպարների համար ձեր ստեղծած հանգույցներից և դրանց հաճախականություններից բացի, դուք նաև կշրջանցեք, կվերածվեք ծառերի և կվերականգնեք ծնողական հանգույցները, այն հանգույցները, որոնք արդեն իսկ ծառեր են:
- Ավարտելուց հետո հերթի վերջին հանգույցը կլինի կոդավորող ծառի արմատը, իսկ մնացած բոլոր հանգույցները կճյուղվեն դրանից:
- Առավել հաճախ օգտագործվող կերպարները կլինեն ծառի գագաթին ամենամոտ գտնվող տերևները, իսկ հազվադեպ օգտագործվող կերպարները ՝ ծառի ներքևում, արմատից ավելի հեռու:
Քայլ 5. Ստեղծեք կոդավորման քարտեզ: Քայլեք ծառի միջով ՝ հասնելու յուրաքանչյուր կերպարի: Ամեն անգամ, երբ այցելում եք հանգույցի ձախ երեխային, դա «0» է: Ամեն անգամ, երբ այցելում եք հանգույցի ճիշտ երեխային, դա «1» է: Երբ հասնում եք կերպարի, պահեք բնույթը 0 -երի և 1 -երի հաջորդականությամբ, որն անհրաժեշտ էր այնտեղ հասնելու համար: Այս հաջորդականությունն այն է, ինչ բնույթը կոդավորված կլինի, ինչպես սեղմված ֆայլում: Պահպանեք կերպարները և դրանց հաջորդականությունները քարտեզի վրա:
- Օրինակ, սկսեք արմատից: Այցելեք արմատի ձախ երեխան, այնուհետև այցելեք այդ հանգույցի ձախ երեխային: Քանի որ այն հանգույցը, որտեղ այժմ գտնվում եք, երեխաներ չունի, դուք հասել եք բնույթի: Սա ' '. Քանի որ այստեղ հասնելու համար երկու անգամ քայլել եք ձախ, '' - ի կոդավորումը «00» է:
- Այս ծառի համար քարտեզը կունենա այս տեսքը ՝ {'': "00", "a": "10", "b": "11", "c": "010", EOF: "011"}:
Քայլ 6. Ելքային ֆայլում ներառեք ծածկագրման քարտեզը որպես վերնագիր:
Սա թույլ կտա ֆայլը վերծանել:
Քայլ 7. Կոդավորեք ֆայլը:
Կոդավորվող ֆայլի յուրաքանչյուր բնույթի համար գրեք քարտեզում պահած երկուական հաջորդականությունը: Ֆայլի կոդավորումն ավարտելուց հետո համոզվեք, որ EOF- ն ավելացրեք մինչև վերջ:
- «Ab ab cab» ֆայլի համար կոդավորված ֆայլը կունենա այս տեսքը ՝ «1011001011000101011011»:
- Ֆայլերը պահվում են որպես բայթ (8 բիթ կամ 8 երկուական թվանշան): Քանի որ Huffman կոդավորման ալգորիթմը չի օգտագործում 8-բիթանոց ձևաչափը, կոդավորված ֆայլերը հաճախ չեն ունենա 8-ի բազմապատիկ երկարություններ: Մնացած թվանշանները կլրացվեն 0-ով: Այս դեպքում ֆայլի վերջում կավելացվեր երկու 0, ինչը նման է մեկ այլ տարածության: Սա կարող է խնդիր լինել. Ինչպե՞ս ապակոդավորողը կիմանա, թե երբ դադարեցնել կարդալը: Այնուամենայնիվ, քանի որ մենք ներառել ենք ֆայլի վերջնական նիշ, ապակոդավորիչը կհասնի դրան և այնուհետև կդադարի ՝ անտեսելով այն ամենն, ինչ ավելացվել է դրանից հետո:
2 -րդ մաս 2 -ից ՝ վերծանում
Քայլ 1. Կարդացեք Huffman- ի կոդավորված ֆայլում:
Նախ, կարդացեք վերնագիրը, որը պետք է լինի կոդավորման քարտեզը: Օգտագործեք սա ՝ ապակոդավորման ծառ կառուցելու համար, ինչպես և այն ծառը, որն օգտագործել եք ֆայլը կոդավորելու համար: Երկու ծառերը պետք է նույնական լինեն:
Քայլ 2. Կրկնակի երկու թվանշանով կարդացեք միանգամից:
Ընթերցելիս հատեք ծառը. Եթե կարդում եք «0» թվով, գնացեք այն հանգույցի ձախ երեխան, որտեղ գտնվում եք, և եթե կարդում եք «1» -ով, գնացեք աջ երեխայի մոտ: Երբ հասնում ես տերևի (առանց որևէ երեխայի հանգույցի), հասել ես կերպարի: Գրեք կերպարը վերծանված ֆայլում:
Քանի որ կերպարները պահվում են ծառի մեջ, յուրաքանչյուր բնույթի կոդերն ունեն նախածանցի հատկություն, այնպես որ որևէ կերպարի երկուական կոդավորումը երբեք չի կարող առաջանալ մեկ այլ կերպարի կոդավորման սկզբում: Յուրաքանչյուր կերպարի կոդավորումը բոլորովին եզակի է: Սա շատ ավելի հեշտ է դարձնում վերծանումը:
Քայլ 3. Կրկնեք մինչև հասնեք EOF- ին:
Շնորհավորում եմ: Դուք վերծանել եք ֆայլը:
