Кампутары, Інфармацыйныя тэхналогіі
Коды Хафман: прыклады, прымяненне
На дадзены момант мала хто задумваецца над тым, як жа працуе сціск файлаў. У параўнанні з мінулым карыстанне персанальным кампутарам стала нашмат прасцей. І практычна кожны чалавек, які працуе з файлавай сістэмай, карыстаецца архівамі. Але мала хто задумваецца над тым, як яны працуюць і па якім прынцыпе адбываецца сціск файлаў. Самым першым варыянтам гэтага працэсу сталі коды Хафман, і іх выкарыстоўваюць па гэты дзень у розных папулярных архіватар. Шматлікія карыстачы нават не задумваюцца, наколькі проста адбываецца сціск файла і па якой схеме гэта працуе. У дадзеным артыкуле мы разгледзім, як адбываецца сціск, якія нюансы дапамагаюць паскорыць і спрасціць працэс кадавання, а таксама разбярэмся, у чым прынцып пабудовы дрэва кадавання.
гісторыя алгарытму
Самым першым алгарытмам правядзення эфектыўнага кадавання электроннай інфармацыі стаў код, прапанаваны Хаффманом яшчэ ў сярэдзіне дваццатага стагоддзя, а менавіта ў 1952 годзе. Менавіта ён на дадзены момант з'яўляецца асноўным базавым элементам большасці праграм, створаных для сціску інфармацыі. На дадзены момант аднымі з самых папулярных крыніц, якія выкарыстоўваюць гэты код, з'яўляюцца архівы ZIP, ARJ, RAR і многія іншыя.
Прынцып эфектыўнага кадавання
У аснову алгарытму па Хаффману ўваходзіць схема, якая дазваляе замяніць самыя верагодныя, часцей за ўсё сустракаемыя сімвалы кодамі двайковай сістэмы. А тыя, якія сустракаюцца радзей, замяняюцца больш доўгімі кодамі. Пераход на доўгія коды Хафман адбываецца толькі пасля таго, як сістэма выкарыстоўвае ўсе мінімальныя значэння. Такая методыка дазваляе мінімізаваць даўжыню кода на кожны знак зыходнага паведамленні ў цэлым.
Код Хафман, прыклад
Каб праілюстраваць алгарытм, возьмем графічны варыянт пабудовы кодавага дрэва. Каб выкарыстанне гэтага спосабу было эфектыўным, варта ўдакладніць вызначэнне некаторых значэнняў, неабходных для паняцця дадзенага спосабу. Сукупнасць мноства дуг і вузлоў, якія накіраваны ад вузла да вузла, прынята называць графам. Само дрэва з'яўляецца графам з наборам пэўных уласцівасцяў:
- у кожны вузел можа ўваходзіць не больш адной з дуг;
- адзін з вузлоў павінен быць коранем дрэва, гэта значыць у яго не павінны ўваходзіць дугі наогул;
- калі ад кораня пачаць перасоўванне па дугам, гэты працэс павінен дазваляць патрапіць зусім у любы з вузлоў.
Алгарытм пабудовы дрэва па Хаффману
Пабудова кода Хафман робіцца з літар уваходнага алфавіту. Утворыцца спіс тых вузлоў, якія вольныя ў будучыні кодавым дрэве. Вага кожнага вузла ў гэтым спісе павінен быць такім жа, як і верагоднасць узнікнення літары паведамленні, адпаведнай гэтаму вузлу. Пры гэтым сярод некалькіх свабодных вузлоў будучага дрэва выбіраецца той, які важыць менш за ўсё. Пры гэтым калі мінімальныя паказчыкі назіраюцца ў некалькіх вузлах, то можна свабодна выбіраць любую з пар.
Павышэнне эфектыўнасці сціску
Каб павысіць эфектыўнасць сціску, трэба падчас пабудовы дрэва кода выкарыстоўваць усе дадзеныя адносна верагоднасці з'яўлення літар у канкрэтным файле, прымацаваным да дрэва, і не дапускаць таго, каб яны былі раскіданыя па вялікай колькасці тэкставых дакументаў. Калі папярэдне прайсціся па гэтым файлу, можна адразу пралічыць статыстыку таго, наколькі часта сустракаюцца літары з аб'екта, якая падлягае сцісканні.
Паскарэнне працэсу сціску
Каб паскорыць працу алгарытму, вызначэнне літар трэба праводзіць не па паказчыках верагоднасці з'яўлення той ці іншай літары, а па частаце яе встречаемості. Дзякуючы гэтаму алгарытм становіцца прасцей, і праца з ім значна паскараецца. Таксама гэта дазваляе пазбегнуць аперацый, звязаных з якія плаваюць коскамі і дзяленнем.
заключэнне
Коды Хафман - просты і даўно створаны алгарытм, які да гэтага часу выкарыстоўваецца многімі вядомымі праграмамі і кампаніямі. Яго прастата і зразумеласць дазваляюць дамагчыся эфектыўных вынікаў сціску файлаў любых аб'ёмаў і значна паменшыць займанае імі месца на дыску захоўвання. Іншымі словамі, алгарытм Хафман - даўно вывучаная і прапрацаваная схема, актуальнасць якой не памяншаецца па гэты дзень.
Similar articles
Trending Now