КампутарыІнфармацыйныя тэхналогіі

Коды Хафман: прыклады, прымяненне

На дадзены момант мала хто задумваецца над тым, як жа працуе сціск файлаў. У параўнанні з мінулым карыстанне персанальным кампутарам стала нашмат прасцей. І практычна кожны чалавек, які працуе з файлавай сістэмай, карыстаецца архівамі. Але мала хто задумваецца над тым, як яны працуюць і па якім прынцыпе адбываецца сціск файлаў. Самым першым варыянтам гэтага працэсу сталі коды Хафман, і іх выкарыстоўваюць па гэты дзень у розных папулярных архіватар. Шматлікія карыстачы нават не задумваюцца, наколькі проста адбываецца сціск файла і па якой схеме гэта працуе. У дадзеным артыкуле мы разгледзім, як адбываецца сціск, якія нюансы дапамагаюць паскорыць і спрасціць працэс кадавання, а таксама разбярэмся, у чым прынцып пабудовы дрэва кадавання.

гісторыя алгарытму

Самым першым алгарытмам правядзення эфектыўнага кадавання электроннай інфармацыі стаў код, прапанаваны Хаффманом яшчэ ў сярэдзіне дваццатага стагоддзя, а менавіта ў 1952 годзе. Менавіта ён на дадзены момант з'яўляецца асноўным базавым элементам большасці праграм, створаных для сціску інфармацыі. На дадзены момант аднымі з самых папулярных крыніц, якія выкарыстоўваюць гэты код, з'яўляюцца архівы ZIP, ARJ, RAR і многія іншыя. Таксама дадзены алгарытм Хафман ўжываецца для сціску JPEG-малюнкаў і іншых графічных аб'ектаў. Ну і ўсе сучасныя факсы таксама выкарыстоўваюць кадаваньне, вынайдзенае ў 1952 годзе. Нягледзячы на тое што з часу стварэння кода прайшло так шмат часу, па гэты дзень яго выкарыстоўваюць у самых новых абалонках і на абсталяванні старога і сучаснага тыпаў.

Прынцып эфектыўнага кадавання

У аснову алгарытму па Хаффману ўваходзіць схема, якая дазваляе замяніць самыя верагодныя, часцей за ўсё сустракаемыя сімвалы кодамі двайковай сістэмы. А тыя, якія сустракаюцца радзей, замяняюцца больш доўгімі кодамі. Пераход на доўгія коды Хафман адбываецца толькі пасля таго, як сістэма выкарыстоўвае ўсе мінімальныя значэння. Такая методыка дазваляе мінімізаваць даўжыню кода на кожны знак зыходнага паведамленні ў цэлым. Важным момантам з'яўляецца тое, што ў пачатку кадавання верагоднасці з'яўлення літар павінны быць ужо вядомыя. Менавіта з іх і будзе складацца канчатковае паведамленне. Зыходзячы з гэтых дадзеных, ажыццяўляецца пабудова кодавага дрэва Хафман, на аснове якога і будзе праводзіцца працэс кадавання літар у архіве.

Код Хафман, прыклад

Каб праілюстраваць алгарытм, возьмем графічны варыянт пабудовы кодавага дрэва. Каб выкарыстанне гэтага спосабу было эфектыўным, варта ўдакладніць вызначэнне некаторых значэнняў, неабходных для паняцця дадзенага спосабу. Сукупнасць мноства дуг і вузлоў, якія накіраваны ад вузла да вузла, прынята называць графам. Само дрэва з'яўляецца графам з наборам пэўных уласцівасцяў:

  • у кожны вузел можа ўваходзіць не больш адной з дуг;
  • адзін з вузлоў павінен быць коранем дрэва, гэта значыць у яго не павінны ўваходзіць дугі наогул;
  • калі ад кораня пачаць перасоўванне па дугам, гэты працэс павінен дазваляць патрапіць зусім у любы з вузлоў.

Існуе таксама такое паняцце, якое ўваходзіць у коды Хафман, як ліст дрэва. Ён уяўляе сабой вузел, з якога не павінна выходзіць ні адной дугі. Калі два вузла злучаныя дугой, то адзін з іх з'яўляецца бацькам, іншы дзіцем, у залежнасці ад таго, з якога вузла дуга выходзіць, і ў якой уваходзіць. Калі два вузла маюць адзін і той жа бацькоўскі вузел, іх прынята называць брацкімі вузламі. Калі ж, акрамя лісця, у вузлоў выходзіць па некалькі дуг, то гэта дрэва называецца двайковым. Як раз такім і з'яўляецца дрэва Хафман. Асаблівасцю вузлоў дадзенага пабудовы з'яўляецца тое, што вага кожнага бацькі роўны суме вагі ўсіх яго вузлавых дзяцей.

Алгарытм пабудовы дрэва па Хаффману

Пабудова кода Хафман робіцца з літар уваходнага алфавіту. Утворыцца спіс тых вузлоў, якія вольныя ў будучыні кодавым дрэве. Вага кожнага вузла ў гэтым спісе павінен быць такім жа, як і верагоднасць узнікнення літары паведамленні, адпаведнай гэтаму вузлу. Пры гэтым сярод некалькіх свабодных вузлоў будучага дрэва выбіраецца той, які важыць менш за ўсё. Пры гэтым калі мінімальныя паказчыкі назіраюцца ў некалькіх вузлах, то можна свабодна выбіраць любую з пар. Пасля чаго адбываецца стварэнне бацькоўскага вузла, які павінен важыць столькі ж, колькі важыць сума гэтай пары вузлоў. Пасля гэтага з бацькоў адпраўляюць у спіс са свабоднымі вузламі, а дзеці выдаляюцца. Пры гэтым дугі атрымліваюць адпаведныя паказчыкі, адзінкі і нулі. Гэты працэс паўтараецца роўна столькі, колькі трэба, каб пакінуць толькі адзін вузел. Пасля чаго выпісваюцца двайковых лічбаў па кірунку зверху ўніз.

Павышэнне эфектыўнасці сціску

Каб павысіць эфектыўнасць сціску, трэба падчас пабудовы дрэва кода выкарыстоўваць усе дадзеныя адносна верагоднасці з'яўлення літар у канкрэтным файле, прымацаваным да дрэва, і не дапускаць таго, каб яны былі раскіданыя па вялікай колькасці тэкставых дакументаў. Калі папярэдне прайсціся па гэтым файлу, можна адразу пралічыць статыстыку таго, наколькі часта сустракаюцца літары з аб'екта, якая падлягае сцісканні.

Паскарэнне працэсу сціску

Каб паскорыць працу алгарытму, вызначэнне літар трэба праводзіць не па паказчыках верагоднасці з'яўлення той ці іншай літары, а па частаце яе встречаемості. Дзякуючы гэтаму алгарытм становіцца прасцей, і праца з ім значна паскараецца. Таксама гэта дазваляе пазбегнуць аперацый, звязаных з якія плаваюць коскамі і дзяленнем. Акрамя таго, працуючы ў такім рэжыме, дынамічны код Хафман, а дакладней сам алгарытм, не падлягае ніякім зменам. У асноўным гэта звязана з тым, што верагоднасці маюць прамую прапарцыянальнасць частотах. Варта звярнуць асаблівую ўвагу на тое, што канчатковы вага файла ці так званага каранёвага вузла будзе роўны суме колькасці літар у аб'екце, які падлягае апрацоўцы.

заключэнне

Коды Хафман - просты і даўно створаны алгарытм, які да гэтага часу выкарыстоўваецца многімі вядомымі праграмамі і кампаніямі. Яго прастата і зразумеласць дазваляюць дамагчыся эфектыўных вынікаў сціску файлаў любых аб'ёмаў і значна паменшыць займанае імі месца на дыску захоўвання. Іншымі словамі, алгарытм Хафман - даўно вывучаная і прапрацаваная схема, актуальнасць якой не памяншаецца па гэты дзень. А дзякуючы магчымасці паменшыць памер файлаў, іх перадача праз сетку або іншымі спосабамі становіцца больш просты, хуткай і зручнай. Працуючы з алгарытмам, можна сціснуць цалкам любую інфармацыю без шкоды для яе структуры і якасці, але з максімальным эфектам памяншэння вагі файла. Іншымі словамі, кадаванне па кодзе Хафман было і застаецца самым папулярным і актуальным метадам сціску памеру файла.

Similar articles

 

 

 

 

Trending Now

 

 

 

 

Newest

Copyright © 2018 be.unansea.com. Theme powered by WordPress.