Хафманови кодови

Из Википедије, слободне енциклопедије

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

Историјат[уреди]

Хафманов алгоритам је настао 1953. Развио га је Дејвид Хафман док је био на докторским студијама на МИТ и објавио у раду "A Method for the Construction of Minimum-Redundancy Codes".

Хафманов алгоритам[уреди]

Huffman tree 2.svg

Циљ Хафмановог алгоритма је минимизација тежинске екстерне дужине пута што у ствари представља збир производа нивоа и тежина за све екстерне чворове стабла.

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

Ово је похлепни алгоритам и може се генерализовати и на стабла вишег реда. С обзиром да у реду може постојати више елемената са истом тежином онда може постојати и више стабала са истом минималном тежинском екстерном дужином пута. Међутим ако желимо да добијемо стабло које уједно има и најмању висину стабла онда елементе са истом тежином треба да уклањамо по FIFO редоследу.

Ово стабло служи као модел доношења бинарних одлука. Листови су коначне одлуке и не долази се до свих истом вероватноћом. Стабло реализује оптималну процедуру одлучивања.

Сложеност алгоритма је у најбољем случају О(хlog х). Сложеност зависи од имплементације реда и најефикасније је када се ред имплементира као бинарни heap.

Хафманови кодови[уреди]

Huffman coding-example.svg

Користе се за компресију података. Компресијом података приликом чувања или преноса се штеди на меморији. Један од примера су поруке које чине азбучна слова. Приликом кодовања поруке мора се водити рачуна да процеси кодовања и декодовања буду једноставни, а опет дужина поруке треба да буде минимална. Сваки симбол се представља неким бинарним кодом. Сада се за сваки симбол мора одредити вероватноћа Рх. У овом случају је најбоље да то буде вероватноћа појављивања датог симбола. Збир свих вероватноћа мора наравно да буде 100. Сваки знак може да има произвољан код. Због лаког декодовања користе се префиксни кодови. То значи да код ни једног симбола не сме да се користи као почетак кода неког другог симбола. Процес декодовања се сада своди на то да се креће од почетка бинарне секвенце и узима онолико знакова колико је потребно да се добије валидан код.

Префиксни кодови се добијају применом Хафмановог алгоритма па се такви кодови још називају и Хафмановим кодовима. Сада сваки симбол представља екстерни чвор који се ставља у ред и од којих се гради стабло. Тежине ових чворова су, у ствари, њихове вероватноће појављивања. У стаблу добијеном применом Хафмановог алгоритма листови су задати симболи. Бинарни код сваког симбола добија се као путања од корена до тог симбола тако што сваки пут када се иде у лево подстабло неког чвора у код се убацује 0, а када се иде у десно подстабло у бацује се 1. У бинарном стаблу пут до сваког екстерног чвора је јединствен па смо тиме обезбедили да добијени кодови буду префиксни

Особине Хафмановог кодирања[уреди]

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

Врсте Хафмановог кодирања[уреди]

На основу тога да ли су вероватноће појављивања симбола познате унапред или се динамички добијају током извршавања алгоритма, Хафманов алгоритам се дели на статички и динамички.

Статичко Хафманово кодирање[уреди]

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

Динамичко Хафманово кодирање[уреди]

Adaptive huffman.png

За разлику од статичког кодирања где се табела вероватноћа појављивања знакова одређује на почетку рада алгоритма код динамичког се вероватноће појављивања израчунавају и мењају динамички у току рада алгоритма.

Пример рада алгоритма[уреди]

Huffman huff demo

Литература[уреди]

  • D.A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the I.R.E., September 1952, pp 1098–1102. Huffman's original article.
  • Ken Huffman. Profile: David A. Huffman, Scientific American, September 1991, pp. 54–58
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 16.3, pp. 385–392.

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Хафманови кодови