Շենոն-Ֆանոյի կոդավորում
| Շենոն-Ֆանոյի կոդավորում | |
|---|---|
| Տեսակ | entropy coding? |
| Անվանված է | Կլոդ Էլվուդ Շենոն և Robert Fano? |
Շենոն-Ֆանոյի ալգորիթմը, սեղմման առաջին ալգորիթմներից էր, որն առաջին անգամ ձևակերպեցին ամերիկացի գիտնականներ Կլոդ Շենոնը և Ռոբերտ Ֆանոն։ Սեղմման այս մեթոդը շատ ընդհանրություններ ունի Հոֆմանի ալգորիթմի հետ, որը հայտնվեց մի քանի տարի անց։ Ալգորիթմն օգտագործում է փոփոխական երկարությամբ կոդեր. առավել հաճախ հանդիպող սիմվոլները առավել կարճ կոդեր են ստանում, իսկ ավելի քիչ հանդիպողները ավելի երկար են կոդավորվում։
Հիմնական տեղեկություններ
[խմբագրել | խմբագրել կոդը]Շենոն-Ֆանոյի կոդավորումը (անգլ.՝ Shannon-Fano coding) ոչ միատարր կոդավորման ալգորիթմ է։ Այն վերաբերում է սեղմման հավանականային մեթոդներին։ Հաֆմանի ալգորիթմի նման Շենոն-Ֆանոյի ալգորիթմը օգտագործում է հաղորդագրության ավելորդությունը, որը պայմանավորված է դրա հիմնական այբուբենի սիմվոլների ոչ միասեռ բաշխմամբ, այսինքն այն ավելի հաճախ հանդիպող սիմվոլներին փոխարինում է ավելի կարճ երկհիմնային հաջորդականություններով, իսկ ավելի քիչ հանդիպող սիմվոլներին՝ ավելի երկար։
Այս ալգորիթմը մեկը մյուսից անկախ մշակվել են Շենոնի (Կապի մաթեմատիկական տեսություն հրապարակություն, 1984 թ.) և, հետագայում, Ֆանոյի (հրապարակել է որպես տեխնիկական զեկույց)։
Հիմնական փուլերը
[խմբագրել | խմբագրել կոդը]- Սկզբնական այբուբենի սիմվոլները գրվում են հավանականությունների նվազման կարգով.
- Ստացված այբուբենի սիմվոլները բաժանվում են երկու մասի, այնպես որ այդ երկու մասերի հավանականությունների գումարը մեկը մյուսին մաքսիմալ մոտիկ լինի.
- Սյբուբենի առաջին խմբին կցվում է <0> թիվը, իսկ երկրորդ մասին՝ <1> թիվը.
- Ստացված մասերը ռեկուռսիվ կերպով բաժանվում են և դրանց մասերին նշանակվում են համապատասխան երկհիմնային թվերը.
Երբ հերթական ենթաայբուբենի չափսը հավասարվում է մեկի կամ զրոյի, ապա հետագա զրոյի կամ մեկի կցումը ել տեղի չի ունենեում։ Այսպիսով ալգորիթմը տարբեր սիմվոլներ փոխակերպում է տարբեր երկարությամբ երկհիմնային կոդեր։ Այբուբենի բաժանման փուլում գոյություն ունի որոշակի անորոշություն, քանի որ գումարայանի հավանականությունների տարբերությունը կարող է միևնույնը լինել բաժանման երկու տարբեր տարբերակների դեպքում(հաշվի առնելով, որ հիմնական այբուբենի բոլոր սիմվոլները ունեն զրոյից տարբեր հավանականություն)։
Շենոն-Ֆանոյի կոդերի հաշվարկման ալգորիթմը
[խմբագրել | խմբագրել կոդը]Շենոն-Ֆանոյի կոդը կառուցվում է ծառի միջոցով։ Այդ ծառի կառուցումը սկսվում է արմատից։ Կոդավորվող էլեմենտների ամբողջ բազմությունը համապատասխանում է ծառի արմատին (առաջին մակարդակի գագաթին)։ Այն բաժանվում է երկու ենթաբազմության մոտավորապես միևնույն գումարային հավանականություններով։ Այդ ենթաբազմությունները համապատասխանում են երկրորդ մակարդակի երկու գագաթներին, որոնք միանում են արմատի միջոցով։ Այնուհետև այդ ենթաբազմություններից յուրաքանչյուրը բաժանվում են երկու ենթաբազմությունների մոտավորապես իրար հավասար գումարային հավանականություններով։ Դրանց համապատասխանում են երրորդ մակարդակի գագաթները։ Եթե ենթաբազմությունը պարունակում է միայն մեկ էլեմենտ, ապա նրան համապատասխանում է կոդային ծառը վերջացնող գագաթը։ Այդպիսի ենթաբազմությունը բաժանման ենթակա չէ։ Նման ձևով ենք վարվում այնքան ժամանակ մինչև որ չենք ստանում բոլոր վերջնական գագաթները։ Կոդային ծառի ճյուղերը նշանակում ենք <0> և <1> սիմվոլներով։
Շենոն-Ֆանոյի կոդի կառուցման ժամանակ բազմությունների տրոհումը ընդհանուր առմամբ կարող է իրականացվել մի քանի եղանակներով։N մակարդակում բազմության տրոհոման ընտրությունը կարող է վատացնել տրոհման տարբերակները (N+1) մակարդակում և հետևաբար հանգեցնի ամբողջական կոդի ոչ օպտիմալությանը։ Այլ խոսքերով ամեն քայլում օպտիմալ վարքագիծը դեռ չի երաշխավորում ամբողջ գործողության օպտիմալությունը։ Այդ պատճառով Շենոն-Ֆանոյի կոդավորումը ընդհանուր իմաստով չի հանդիսանում օպտիմալ, չնայած այն տալիս է օպտիմալ արդյունքներ հավանականությունների որոշ բաշխումների դեպքում։ Հավանականությունների նույն բաշխումով ընդհանուր առմամբ կարելի է կառուցել մի քանի Շենոն-Ֆանոյի կոդ, և դրանք բոլորը կարող են տալ տարբեր տարբեր արդյունքներ։ Եթե կառուցենք բոլոր հնարավոր Շենոն-Ֆանոյի կոդերը տրված հավանականությունների բաշխումով, ապա դրանց մեջ կլինեն նաև Հաֆմանի բոլոր կոդերը, այսինքն օպտիմալ կոդերը։
Կոդային ծառի օրինակ
[խմբագրել | խմբագրել կոդը]Ընթացիկ սիմվոլներ։
- A (հանդիպման հաճախականությունը 50)
- B (հանդիպման հաճախականությունը 39)
- C (հանդիպման հաճախականությունը 18)
- D (հանդիպման հաճախականությունը 49)
- E (հանդիպման հաճախականությունը 35)
- F (հանդիպման հաճախականությունը 24)
Ստացված կոդը։ A - 11, B - 101, C - 100, D - 00, E - 011, F - 010.
Շենոն-Ֆանոյի կոդավորումը սեղմման բավականին հնացած մեթոդ է հանդիսանում, և այսօր այն չունի գործնական նշանակություն։ Հիմանկանում այս մեթոդով սեղմված հաջորդականությունների երկարությունները հավասար են Հոֆմանի կոդավորմամբ ստացված հաջորդականությունների երկարություններին, բայց որոշ հերթականությունների դեպքում կարող են կառուցվել ոչ օպտիմալ կոդեր, այդ իսկ պատճառով ավելի եֆեկտիվ է համարվում Հոֆմանի կոդավորումը։
Գրականություն
[խմբագրել | խմբագրել կոդը]- (ռուսերեն) А. М. Яглом, И. М. Яглом. Вероятность и информация. - М.։ Наука, 1973.