Տվյալների սեղմում (կոմպրեսիա)

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search

Տվյալների սեղմում (անգլ.՝ data compression), տվյալների ալգորիթմային փոխակերպում, նրանց ծավալը նվազեցնելու նպատակով։ Կիրառվում է սարքերի ավելի ռացիոնալ օգտագործման համար (մասնավորապես ինֆորմացիայի պահեստավորման եւ փոխանցման սարքերում)։ Հոմանիշներտվյալների փաթեթավորում , կոմպրեսիա,  սեղման կոդավորում, աղբյուրի կոդավորման ։ Հետադարձ գործընթացը կոչվում է տվյալների վերականգնում (unpacking)։


Սեղմումը հիմնված է սկզբնական տվյալներում ավելորդությունների վերացման վրա. Ամենապարզ ավելորդության օրինակ  է հանդիսանում տեքստում կրկնվող բառերը, նախադասությունները։ Նման ավելորդությունը սովորաբար չեզոքացվում է, փոխարինելով կրկնվող հաջորդականությունն արդեն գոյություն ունեցող տեքստի հատվածի հասցեով (link)։ Այլ տեսակ ավելորդության օրինակ է այն, որ որոշ տվյալներ (սկզբնական տվյալներում) հանդիպում են առավել հաճախ։ Տվյալների ծավալի նվազեցումը իրականացվում է հաճախ հանդիպող տվյալների փոխարինումով ավելի կարճ կողային բառերով, իսկ հազվագյուտ հանդիպող տվյալները՝ երկար (Էնտրոպիական կոդավորում)։ Տվյալների սեղմումը, որոնք չունեն ավելորդության հատկություն (օր․ պատահական տվյալներ, սպիտակ աղմուկ), սկզբունքորեն անհնար է առանց կորուստների։

Առանց կորուստների սեղմումը թույլ է տալիս լիովին վերականգնել բնօրինակ հաղորդագրությունը, քանի որ չի նվազեցնում տեղեկության (ինֆորմացիա) քանակը , չնայած նվազեցնում է նրա ծավալը.

Տվյալների սեղման սկզբունքները[խմբագրել | խմբագրել կոդը]

Ցանկացած սեղման ալգորիթմի հիմքում սկզբնական տվյալների մոդելն է, կամ ավելի ճիշտ ավելորդության մոդելը։ Այլ կերպ ասած, տվյալների սեղման համար օգտագործվում է որոշ հավաստի տեղեկությունները, թե ի՞նչ բնույթի է տվյալներ են ենթարկվում սեղման (նկարներ, ձայնային հոլովակ և այլն)։ Չունենալով նման տեղեկություններ սկզբանական տվյալների մասին, հնարավոր չէ որեւէ ենթադրություններ անել վերակազմավորման (ձևափոխման) մասին, որը թույլ կտար նվազեցնել հաղորդագրության ծավալը։ Ավելորդության մոդելը կարող է լինել ստատիկ, անփոփոխ ողջ սեղման ենթարկվող հաղորդագրության համար, կամ կառուցված սեղման փուլում (կամ վերականգնման)։ Մեթոդները, որոնք թույլ են տալիս մուտքային տվյալների հիման վրա փոխել տեղեկատվության (ինֆորմացիայի) ավելորդության մոդելը, կոչվում են հարմարվողական մեթոդներ. Չհարմարվողական են սովորաբար բարձր մասնագիտական ալգորիթմները, որոնք կիրառվում են հայտնի և անփոփոխ հատկանիշներով տվյալների հետ աշխատելու համար։ Ալգորիթմերի գերակշիռ մասը բավական ունիվերսալ են եւ այս կամ այն չափով հարմարվողական։

Տվյալների սեղման բոլոր մեթոդները բաժանվում են երկու հիմնական դասի․

Առանց կորուստների սեղմման դեպքում հնարավոր է սկզբնական տվյալների ամբողջական վերականգնումը , կորուստներով սեղմումը թույլ է տալիս վերականգնել տվյալները խեղաթյուրումներով, վերականգնված տվյալների հետագա օգտագործման տեսանկյունից դրանք աննշան են։ Առանց կորուստների սեղմումը սովորաբար օգտագործում են տեքստային տվյալների փոխանցման և պահպանման , համակարգչային ծրագրերի, հազվադեպ նաև աուդիո- և վիդեոտվյալների, թվային լուսանկարների ծավալի կրճատման համար, այն դեպքերում, երբ խեղաթյուրումները անթույլատրելի, կամ ցանկալի չեն ։ Կորուստներով սեղմումը, որը զգալիորեն ավելի արդյունավետ է, քան սեղմումն առանց կորուստների, այն սովորաբար կիրառվում է աուդիո - և վիդեոտվյալների և թվային լուսանկարներ ծավալի կրճատման համար, այն դեպքերում, երբ նման կրճատումը առաջնային է, իսկ ամբողջական համապատասխանությունը սկզբնական և վերականգնված տվյալների միջև չի պահանջվում։

Սեղման ալգորիթմների նկարագրությունը և դրանց կիրառելիությունը[խմբագրել | խմբագրել կոդը]

Սեղմման հարաբերակցությունը[խմբագրել | խմբագրել կոդը]

Սեղման գործակիցը սեղման ալգորիթմի հիմնական բնութագիրն է։ Այն բնորոշվում է որպես սեղմված տվյալների և սկզբնական տվյալների ծավալների հարաբերություն, այսինքն  k = Sc/Sօ, որտեղ k — սեղման գործակիցն է, So— սկզբնական տվյալների ծավալը, իսկ Sc — սեղմված տվյալների ծավալը. Այսպիսով, որքան ցածր է սեղման գործակիցը, այնքան արդյունավետ է ալգորիթմը. Հարկ է նշել՝

  • եթե k = 1, ապա ալգորիթմը չի սեղմում տվյալները, այսինքն ելքային հաղորդագրության պարզվում է, ծավալով հավասար սկզբնականին,
  • եթե k > 1, ապա ալգորիթմը է ստղծում է հաղորդագրություն ավելի մեծ չափի, քան սկզբնականը, այսինքն, իրականացնում է "վնասակար" աշխատանք։

Կորուստների թույլատրելիությունը[խմբագրել | խմբագրել կոդը]

Ալգորիթմների համակարգի պահանջները (System requirements)[խմբագրել | խմբագրել կոդը]

Անհայտ ձեւաչափի տվյալների սեղմման ալգորիթմներ[խմբագրել | խմբագրել կոդը]

Անհայտ ձևաչափի տվյալների սեղման համար առկա է երկու հիմնական մոտեցում՝

  • Սեղման ալգորիթմի ամեն քայլին հերթակակն սեղմվող նիշը կամ տեղադրվում է ելքային բուֆեր ինչպես կա (հատուկ դրոշակով, որ նա չի սեղմվել), կամ մի խումբ սեղմվող նիշեր փոխարինվում են նրանց հետ համընկնող այլ խմբի հասցեով։ Քանի որ այսպիսով սեղմված տվյալների վերականգնումը կատարվում է շատ արագ, նման մոտեցումը հաճախ օգտագործվում է ինքնակառավարվող ծրագրերի ստեղծման համար։
  • Սեղման ենթարկվող հաջորդականության յուրաքանչյուր նիշի համար մեկ անգամ կամ ժամանակի ամեն պահին հավաքվում է առաջացման հաճախականության վիճակագրությունը. Այդ վիճակագրության հիման վրա հաշվարկվում է հերթական կոդավորվող նիշի (կամ հաջորդականության) հավանականության նշանակությունը։ Դրանից հետո կիրառվում է այս կամ այն տեսակի Էնտրոպիական կոդավորում, օրինակ, թվաբանական կոդավորում կամ Հաֆֆմանի կոդավորում, հաճախ հանդիպող հաջորդականությունները կոդավորվում են կարճ բառերով(կոդերով), իսկ հազվադեպ հանդիպողները՝ ավելի երկար։

Տես նաև[խմբագրել | խմբագրել կոդը]

Գրականություն[խմբագրել | խմբագրել կոդը]

  • Д. Ватолин, А. Ратушняк, М. Смирнов, В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — Диалог-МИФИ, 2002. — С. 384. — ISBN 5-86404-170-X 3000 экз.
  • Д. Сэломон. Сжатие данных, изображения и звука. — М.: Техносфера, 2004. — С. 368. — ISBN 5-94836-027-X 3000 экз.

Հղումներ[խմբագրել | խմբագրել կոդը]