Хуффман цодес: екамплес апплицатион

У овом тренутку, мало људи размишља о томе, како компресију датотеке. У поређењу са претходном употребом персоналног рачунара је постало много лакше. И скоро свака особа која ради са системом датотека користи фајлове. Али мало људи размишља о томе како они раде и на основу чега је сажимање датотеке. Сама прва верзија овог процеса су Хуффман кодови, а они се данас користи у разним популарним архивера. Многи корисници не помишљај како је лако сажимање датотеке се одвија и да ради на шеми. У овом чланку ћемо погледати како је компресија је оно што нијанси помоћи да се убрза и поједностави процес кодирања, као и видети шта је принцип дрвета кодирања.

алгоритам историја

Већ у првом алгоритам ефикасно кодирање електронских информација је постала број Хаффман предложени већ средином двадесетог века, тачније 1952. године. То је био ко у овом тренутку је основа елемент већине програма креираних за компресију података. У овом тренутку, један од најпопуларнијих извора који користе овај код су архиви поштенски, АРЈ, РАР и многи други. Такође, Хаффман алгоритам се користи за компримирати ЈПЕГ слике и друге графичке објекте. Па, сви факсови се такође користи модерну кодирање, изумео је 1952. године. Упркос чињеници да је од стварање кода је толико времена до данас се користи у разним нових мембрана и опреме старих и модерних типова.

Принцип ефикасне кодирања

Основа Хуффман алгоритам обухвата шему која омогућава да замени највише кредибилан, најчешће се јављају симболи кодирани бинарни систем. А они који су мање уобичајена, замењен са дужим кодовима. Ће дуго Хуффманове кодове јавља тек након што систем користи све минималне вредности. Ова техника омогућава да смањите дужину кода за сваки симбол оригиналне поруке у целини. Важно је да на почетку кодирајуће вероватноће појављивања слова треба већ позната. То је од њих ће бити припремљен и последња порука. На основу ових података, врши изградња Хуффман код дрвета, на основу којих ће се одржати писма процес који кодирају у архиви.

Хаффман код, пример

Да би илустровао алгоритам, размислите графички варијанту изградње код дрвета. Да бисте користили овај метод био ефикасан, неопходно је да се разјасни дефиницију одређених вредности неопходних за концепт процеса. Скуп мноштва чворова и лукова, које су усмерене од чвора до чвора, назван граф. Сама дрво је графикон са низом специфичних својстава:

• у сваком чвору може укључивати не више од једног од лукова;
• један од чворова мора бити корен дрвета, то јест, не би требало да буде део лука на све;
• ако је стабло почне креће дуж лука, процес би требало да омогући да се у потпуности ни у једном од чворова.

Такође постоји таква ствар, део Хуффман кодова као лист на дрвету. То је чвор од којих не би требало да иде никакав лук. Ако су два чвора повезана лука, једна од њих је и родитељ другом детету, у зависности од тога из које чвор лук излази, и шта је укључено. Ако два чвора има исту родитељски чвор, они се називају сајтове-рођаке. Ако је, у листовима, оставља од чворова неколико лукова, онда се зове бинарно стабло. Само да је Хаффман дрво. Специфичност изградње јединица је да маса сваког родитеља је једнак збиру пондера свих његових потомака чворовима.

Алгоритам за изградњу стабла Хуффман

Изградња Хуффман код је улаз из словима абецеде. Генератед листу сајтова који су слободни у будућем код дрвета. Тежина сваког чвора у листи мора бити исти као и вероватноћа појаве стубове слова која одговарају овом чвору. У овом случају, онај ко тежи најмање је изабран из реда неколико слободних места будућег дрвета. У том случају, ако су минималне стопе су примећени у неколико локација, можете слободно одабрати било који од парова. Затим долази стварање матичног чвора, који мора одмерити колико збир пондера пара чворова. Након тога, родитељи шаљу листу са слободним тоалета, а деца су уклоњени. У овом луку су одговарајуће показатеље, јединице и нуле. Овај процес се понавља онолико колико је потребно да би само један чвор. Затим написати бинарне цифре од врха до дна.

Унапређење ефикасности компресије

У циљу повећања ефикасности компресије, неопходно је током дрво зграде код да користите све податке о вероватноћи појаве слова у одређеној датотеци, везан за дрво, а не дозволити чињеницу да су расуте по великом броју текстуалних докумената. Ако је пре шетња кроз ову датотеку, можете одмах израчунати статистику колико често постоје писма предмета објекта на компресију.

Убрзање процеса компресије

Да би се убрзао алгоритам, дефиниција слова треба да уради у смислу вероватноће појаве одређеног писма, и учесталости његовог настанка. Уз овај алгоритам постаје лакше, и радити са њима много брже. такође избегава операције у вези са поделом флоатинг-поинт. Поред тога, рад у овом режиму, динамички Хаффман код, односно сама алгоритам не подлеже било каквим променама. То је углавном због чињенице да су вероватноће су директно пропорционалан фреквенцији. Вреди обратити пажњу на чињеницу да је коначна маса датотеке, или тзв роот чвор је једнак збиру броја знакова у објекту који се третира.

закључак

Хуффман кодови - једноставна и дуго успостављена алгоритам, који се и данас користе многе познате програме и компанија. Његова једноставност и јасноћа може постићи ефективни резултати компримујете датотеке било које запремине и значајно смањити простор на диску складиштења. У другим речима, Хаффман алгоритам - је дуго истраживао и дијаграм рад који хитност није смањен за овај дан. И са могућношћу да се смањи величину датотеке, пребаците их преко мреже или на други начин да је једноставније, брзо и повољно. Рад са алгоритма, можете у потпуности компримујете било какву информацију, без штете за њене структуре и квалитета, али са максималним ефектом да се смањи фајл тежине. Другим речима, кодирање на Хуффман кода је био и остао најпопуларнији и релевантан начин компресије величину.