26: Huffmanovo kodiranje

Dokazali bomo, da Huffmanov agloritem deluje pravilno. Zato bomo pokazali,

 

Lema 1.

Naj bo C nabor znakov, tako da ima vsak znak c 0 C frekvenco f(c). Naj bosta x in y dva znaka v C, ki imata najmanjši frekvenci. Potem obstaja optimalno kodiranje s predpono za C, kjer sta kodni besedi za x in y enko dolgi, razlikujeta pa se le v zadnjem bitu.

Dokaz:

Vzemimo drevo T, ki predstavlja poljubno optimalno kodiranje s predpono. Če to drevo lahko spremenimo tako, da v optimalno kodrianje s predpono dodajmo povsem na dnu znaka x in y kot sorodna lista (torej z istim očetom). Če to lahko storimo, bosta kodni besedi za x in y enako dolgi, razlikovali pa se bosta le v zadnjem bitu.

Naj bosta a in b dva znaka, ki imata istega očeta in se nahajata najgloblje v drevesu T. Brez škode za splošnost lahko predpostavimo, da velja f(a) # f(b) in f(x) # f(y). Ker sta f(x) in f(y) najmanjši frekvenci potem velja f(x) # f(a) in f(y) # f(b). Kot kaže slika 3, v drevesu  T zamenjamo poziciji a in x ter tako dobimo drevo T'. V tem drevesu zamenjajmo še b in y ter tako dobimo drevo T''. S spodnjim računom vidimo, da je razlika v ceni med T in T' nenegativna:

B(T) - B(T') = 3_c0C  f(c) d_T(c)  - 3_c0C  f(c) d_T'(c) =

= f(x) d_T(x) + f(a) d_T(a) - f(x) d_T'(x) - f(a) d_T'(a) =

= f(x) d_T(x) + f(a) d_T(a) - f(x) d_T(a) - f(a) d_T(x) =

= (f(a) - f(x))(d_T(a) - d_T(x)) $0

saj sta obe razliki f(a) - f(x) in d_T(a) - d_T(x) nenegativni. Natančneje, razlika f(a) - f(x) je nenegativna saj je frekvenca znaka x najmanjša, razlika d_T(a) - d_T(x) pa je nenegativna, saj ima list z znakom a največjo globino. Podobno pokažemo, da z zamenjavo znakov b in y ne poveča cene, torej B(T') - B(T'') $ 0. Od tod sledi, da je B(T'') # B(T). Ker je B(T) po predpostavki optimalno drevo, velja tudi B(T'') $ B(T), torej je B(T'') = B(T). Zato je tudi T'' optimalno drevo kjer sta x in y sinova istega očeta z največjo globino. QED

Slika 3. Prikaz ključnega koraka pri dokazu Leme 1. V optimalnem drevesu T sta lista a in b najglobja potomca istega očeta. Lista x in y sta dva lista (na poljubnih mestih v drevesu T), ki ju po Huffmanovem algoritmu najprej združimo. Najprej zamenjamo lista a in x, da dobimo drevo T', nato pa še lista b in y, da dobimo drevo T''. Ker nobena zamenjava ne poveča cene, je drevo T'' tudi optimalno.

Lema 1 potrdi, da lahko začnemo graditi drevo z združevanjem dveh znakov z najmanjšima frekvencama. Zdaj pa pokažimo še, da ima gradnja optimalnega drevesa kodiranja s predpono optimalno podstrukturo - da na vsakem koraku res zgradimo optimalno drevo.

Lema 2.

Naj bo C nabor znakov, tako da ima vsak znak c 0 C frekvenco f(c). Naj bosta x in y dva znaka v C, ki imata najmanjši frekvenci. C' je nabor znakov C, iz katerega smo odrstranili znaka x in y, namesto njiju pa je dodan znak z, torej

C' = C - {x,y} c {z}

Frekvenca je za C' definirana enako kot za C, le da je f(z) = f(x) + f(y).
Naj bo T' drevo, ki predstavlja optimalno kodo s predpono za nabor znakov C'. Potem drevo T, ki ga iz T' zgradimo tako, da namesto lista z znakom z vstavimo vozlišče s sinovoma x in y, predstavlja optimalno kodo s predpono za nabor znakov C.

Dokaz:

Najprej pokažimo, da lahko ceno B(T) drevesa T izrazimo kot ceno B(T') drevesa T' s pomočjo enačbe (1). Za vsak c 0 C - {x,y} velja d_T(c) = d_T'(c) in od tod f(c)d_T(c) = f(c)d_T'(c). Ker je d_T(x) = d_T(y) = d_T'(z) + 1, dobimo

f(x)d_T(x) + f(y)d_T(y) = (f(x) + f(y))(d_T'(z) + 1) =
= f(z)d_T'(z) + (f(x) + f(y))

in od tod

B(T) = B(T') + f(x) + f(y) oziroma B(T') = B(T) - f(x) - f(y)

Zdaj lemo dokažimo s protislovjem. Naj dervo T ne predstavlja optimalne kode s predpono za C. Potem obstaja drevo T'', tako da velja B(T'') < B(T). Brez škode za splošnost (Lema 1), naj imata lista x in y v drevesu T'' istega očeta. Naj bo T''' drevo, ki ga dobimo iz drevesa T'' tako, da zamenjamo očeta x in y z listom z s frekvenco f(z) = f(x) + f(y). Potem velja

B(T''') = B(T'') - f(x) - f(y) < B(T) - f(x) - f(y) = B(T')

kar pa je v protislovju s predpostavko, da je T' predstavlja optimalno kodo s predpono za nabor C'. QED

Izrek.

S Huffmanovim algoritmom zgradimo optimalno kodo s predpono.

Dokaz:

Sledi neposredno iz Leme 1 in Leme 2. QED