Հիմնական նյութ
Համակարգիչներ և համացանցը
Դասընթաց․ (Համակարգիչներ և համացանցը) > Բաժին 1
Դաս 5: Տվյալների սեղմումԲիթի Lossless (անկորուստ) սեղմում
Համակարգիչները ներկայացնում են բոլոր տվյալները երկուական տարբերակով, ուստի բոլոր տեսակի ֆայլերը՝ տեքստից մինչև պատկերներ, մինչև տեսանյութեր, ի վերջո բիթերի հաջորդականություն են: Անկախ նրանից բիթերը ներկայացնում են փաստաթուղթ, թե GIF, համակարգիչները կարող են օգտագործել բիթային սեղմման տեխնիկա, որը կոչվում է Հաֆմանի կոդավորում:
Հաֆմանի կոդավորման ալգորիթմ
Տեսնենք, թե ինչպես է այն աշխատում պարզ տեքստային օրինակով: Այս լեզուն օգտագործում է միայն 4 տարբեր նիշեր, և, որ մեզ համար աներևակայելի կարևոր է, դա այն լեզուն է, որն օգտագործվում է ԴՆԹ-ն ներկայացնելու համար և բաղկացած է չորս նիշերի A, C, G և T հաջորդականություններից:
Օրինակ, E.coli ԴՆԹ-ի հաջորդականությունը ներկայացնող 4,6 միլիոն նիշերը սկսվում են հետևյալով.
agcttttcattctՔանի որ մենք պետք է ներկայացնենք չորս նիշ, համակարգիչը սովորաբար ներկայացնում է յուրաքանչյուր նիշ՝ օգտագործելով 2 բիթ, օրինակ՝
| նիշ | երկուական համակարգի կոդ |
|---|---|
| a | 00 |
| c | 01 |
| g | 10 |
| t | 11 |
Վերևի 13 նիշերը գրվելու են 26 բիթով հետևյալ կերպ. ուշադրություն դարձրեք, որ յուրաքանչյուր բիթի կոդերի միջև բացատներ պետք չեն:
100111111111000000000000Բայց մենք կարող ենք սրանից ավելի լավ անել: Վերևում գտնվող կարճ նմուշի տեքստում «t» տառը ավելի տարածված է, քան մյուս տառերը («t» հանդիպում է 7 անգամ, «c» 3 անգամ, «a» երկու անգամ և «g» ընդամենը մեկ անգամ): Եթե մենք ավելի կարճ կոդ տանք «t»-ին, ապա մենք ավելի քիչ տեղ կօգտագործենք 54%-ի համար (13 նիշից 7-ը): Օրինակ, մենք կարող ենք օգտագործել կոդերը.
| նիշ | երկուական համակարգի կոդ |
|---|---|
| a | 010 |
| c | 00 |
| g | 011 |
| t | 1 |
Այնուհետև մեր 13 նիշերը կոդավորված կլինեն հետևյալ կերպ.
100110011110000000000Դա ընդամենը 22 բիթ է, չորս բիթ պակաս, քան մեր սկզբնական կոդավորումը: Դա կարող է շատ չթվալ, բայց պատկերացրեք, եթե մենք օգտագործեինք նման օպտիմալացում ԴՆԹ-ի ամբողջ 4,6 միլիոն նիշերի վրա:
Հաֆմանի վերծանում
Քեզ համար գուցե տարօրինակ է մեր օգտագործած տարբեր երկարություններով երկուական համակարգի կոդերը: Հնարավո՞ր է, արդյոք, այն հուսալիորեն վերծանել: Այո, կոդերի ճիշտ խմբով:
Դա Հաֆմանի կոդավորման գեղեցկությունն է. ալգորիթմը մեզ հնարավորություն է տալիս որոշակի հաջորդականության համար ստեղծել երկուական կոդեր, որոնք ապահովում են տվյալների միանշանակ և հուսալի վերակառուցում:
Հաֆմանի կոդավորման կիրառությունը
Շատ ֆայլերի ձևաչափեր ինչ-որ ձևով օգտագործում են Հաֆմանի կոդավորում՝ իրենց ֆայլի չափը նվազեցնելու համար: Ֆաքսի մեքենաներն օգտագործում են Հաֆմանի կոդավորումը RLE-ն օգտագործելուց հետո սև և սպիտակ վազքերում: PNG պատկերները սեղմվում են՝ օգտագործելով LZ77, ալգորիթմ, որը նման է մեր սովորած տեքստի սեղմման տեխնիկային՝ համակցված արդյունքների Հաֆմանի կոդավորման հետ:
🙋🏽🙋🏻♀️🙋🏿♂️Ունե՞ք հարցեր այս թեմայի վերաբերյալ: Մենք կցանկանայինք պատասխանել, պարզապես հարցրեք ստորև ներկայացված հարցերի տարածքում:
Ուզո՞ւմ ես միանալ խոսակցությանը։
Առայժմ հրապարակումներ չկան։