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

Канонски Хафманов код је посебна врста Хафмановог кода са јединственим својствима који омогућавају да буде описан на врло компактан начин.

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

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

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

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

Алгоритам

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

A = 11 
B = 0 
C = 101 
D = 100

Овде су слову А додељена два бита, B има један бит, а C и D имају по три бита. Да би се направио канонски Хафманов код, кодови су пренумерисани. Дужине у битовима остају исте с тим што су кодови сортирани прво по дужини кодне речи, а затим по абецедном реду:

B = 0 
A = 11 
C = 101 
D = 100

Сваки од постојећих кодова је замењен новим исте дужине, користећи следећи алгоритам:

• Првом симболу у листи додељује се кодна реч која је исте дужине као првобитна кодна реч симбола, али замењена свим нулама. То ће бити једна нула ('0').
• Сваком наредном симболу је секвенцијално додељен следећи бинарни број, обезбеђујући да су следећи кодови увек веће вредности.
• Када достигне дужу кодну реч, након увећања, додајемо нуле док дужина нове кодне речи не буде иста као дужина старе. Ово се може посматрати као померање улево.

Пратећи ова три правила, канонска верзија ће бити:

B = 0
A = 10 
C = 110 
D = 111

Као разломљени бинарни број

Други изглед канонског шифрарника је да су оне цифре иза бинарне тачке (бинарни децимални зарез) бинарна репрезентација одређеног низа. Специјално претпоставимо да су дужине l₁,...,l_n. Онда је канонска кодна реч за симбол i прва l_i бинарна цифра иза бинарне тачке у бинарној репрезентацији.

$\sum _{j=1}^{i-1}2^{-l_{j}}$

Оваква перспектива је посебно корисна имајући у виду Крафтову неједнакост која каже да ће износ изнад увек бити мањи од 1 (јер дужине долазе из слободног префиксног кода). Ово показује да додавањем јединице у алгоритму изнад никад не ствара кодну реч која је дужа него што је предвиђено.

Кодирање

Сва предност канонског Хафмановог стабла је да се може кодирати опис (кодна схема) у мање бита него комплетно описано стабло.

Узмимо првобитну Хафманов шифрарник:

A = 11 
B = 0 
C = 101 
D = 100

Постоји неколико начина на које можемо кодирати ово Хафманово стабло. На пример, можемо написати сваки симбол, а затим број битова и код.

('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)

Пошто смо набројали симболе у секвенцијалном абецедном реду, можемо изоставити симболе, наводећи само број битова и код:

(2,11), (1,0), (3,101), (3,100)

Са нашом канонском верзијом знамо да су симболи у секвенцијалном абецедном реду и да ће вредност наредног кода увек бити већа од вредности претходног. Једини део који је остао за слање је број битова за сваки симбол. Имајте на уму да канонско Хафманово стабло увек има веће вредности за симболе који имају већи број битова и да сваки симбол са истим бројем битова (C и D) има веће вредности кодова за веће симболе:

A = 10    (вредност кода: 2 децимално, битова: 2) 
B = 0     (вредност кода: 0 децимално, битова: 1) 
C = 110   (вредност кода: 6 децимално, битова: 3) 
D = 111   (вредност кода: 7 децимално, битова: 3)

Пошто су познате две трећине ограничења, само број битова за сваки симбол треба да се пренесе:

2, 1, 3, 3

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

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

(1,1,2), ('B','A','C','D')

То значи да је први симбол B дужине 1, затим А дужине 2, а остатак 3. Будући да су симболи сортирани по броју битова можемо ефикасно да реконструишемо шифрарник. Псеудо код који представља реконструкцију је представљен у следећем одељку.

Овај тип кодирања има велике предности када је компресовано само неколико симбола у писму. На пример, ако шифрарник садржи само четири слова C, O, D и E, сваки дужине два. Да би представили слово O користећи претходни метод требало би да или додамо много нула:

0, 0, 2, 2, 2, 0, ... , 2, ...

или евидентирати која четири слова смо користили. Сваки начин чини опис дужи од:

(0,4), ('C','O','D','E')

JPEG формат је усвојио, заправо, овај начин кодирања, јер, углавном, само 162 симбола 8-битне азбуке, која има величину 256, биће у шифрарнику.

Псеудо код

С обзиром да је листа симбола разврстана по броју битова, следећи псеудо код приказати канонски Хафманов код:

code = 0
while more symbols:    
print symbol, code    
code = (code + 1) << ((broj bitova sledeceg simbola) - (trenutni broj bitova))

Алгоритам

Алгоритам описан у  "A Method for the Construction of Minimum-Redundancy Codes", Дејвид А. Хафман, издавач  I.R.E је:

израчунати Хафманов код: 
улаз: порука (комплет од (порука, вероватноћа)).
      основа D 
излаз: код (комплет од (порука, код)). 
алгоритам: 
1- сортирати поруке према опадајућој могућности. 
2- N је кардинал порука (број различитих порука)).
3- израчунати цео број n_0 као 2<=n_0<=D и (N-n_0)/(D-1) је цео број. 
4- изабрати n_0 поруке најмање вероватноће и доделити им свима цифре.
5- заменити одабране поруке поруком која је композиција њихових вероватноћа, и поновити га. 
6- док има више од једне поруке, извршавати до 8.
7- изабрати поруке са најмањом вероватноћом и доделити им свима цифре.
8- заменити одабране поруке поруком која је композиција њихових вероватноћа, и поновити га. 
9- код сваке поруке дат је спајањем кода цифара скупа који је уметнут.

Литература

• 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 978-0-262-03293-3. Section 16.3, pp. 385–392.