Մասնակից:Sargsyan Albert/Շենոն-Ֆանոյի կոդավորում
Շենոն-Ֆանոյի ալգորիթմը — սեղմման առաջին ալգորիթմներից էր, որն առաջին անգամ ձևակերպեցին ամերիկացի գիտնականներ Շենոնը և Կաղապար:Translation2: Սեղմման այս մեթոդը շատ ընդհանրություններ ունի Հոֆմանի ալգորիթմի հետ, որը մի քանի տարի հետո հայտնվեց: Ալգորիթմն օգտագործում է փոփոխական երկարությամբ կոդեր. առավել հաճախ հանդիպող սիմվոլները առավել կարճ կոդեր են ստանում, իսկ ավելի քիչ հանդիպողները ավելի երկար են կոդավորվում:
Հիմնական տեղեկություններ խմբագրել
Շենոն-Ֆանոյի կոդավորումը (անգլ.՝ 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.
Категория:Теория кодирования Категория:Сжатие данных Категория:Алгоритмы сжатия без потерь