Zbigniew Doma ski
Instytut Matematyki i Informatyki, Politechnika Cz stochowska
Elementy teorii kodowania.
Wprowadzenie.
Przedyskutujemy niektóre aspekty kodowania informacji. Jednym ze znanych
kodów jest kod ASCII. W kodzie tym ka dy symbol jest kodowany za pomoc słowa
binarnego o długo ci 8. Istotn cech kodu ASCII, jak i wielu innych kodów, jest to, e ka dy symbol ma kod o tej samej długo ci (tzw. fixed length character code). Ma to swoje plusy i minusy.
• Plusem jest to, e nie potrzeba adnego specjalnego symbolu do oddzielania symboli w informacji. Dzi ki temu łatwo jest odkodowa informacj .
• Minus to fakt, e cz sto powtarzaj ce si symbole maj kod o takiej samej długo ci jak wyst puj ce rzadko. Jest to wi c strata czasu i przestrzeni w procesie kodowania i odkodowywania.
Powstała wi c idea u ywania kodów o zmiennej długo ci charakterów, tzn.
symbolom cz sto wyst puj cym przypisuje si krótkie charaktery, za tym o małej cz sto ci odpowiadaj dłu sze charaktery.
O ile nie ma problemu z wyborem mo liwie krótkich charakterów koduj cych to mo e wyst pi problem z odczytem kodu gdy przy zmiennej długo ci charakterów
trzeba wiedzie gdzie ko czy si kod jakiego symbolu a gdzie zaczyna nast pny.
Przykład.
Mamy zbiór symboli C={a,b,c,d,e,f}. Przypu my, e a oraz b maj
najwi ksz cz sto wyst powania. Mo emy wi c wybra nast puj cy kod:
a – 0, b – 1, c – 00, d – 01, e –10, f –11.
Kod ten jest bardzo „krótki” w tym sensie, e indywidualne symbole s kodowane przez najkrótsze mo liwe charaktery.
Jak jednak odczyta nast puj c zakodowan informacj : 010011?
Czy „010011” oznacza „abaabb” czy te „dcf”?
7
Mo na problem niejednoznaczno ci odczytu rozwi za wprowadzaj c extra charakter np. / do oddzielania indywidualnych charakterów. Jednak taki zabieg wydłu a kodowan informacj .
Istnieje elegancka metoda omini cia niejednoznaczno ci dekodowania. Metoda ta wykorzystuje tzw. kody prefiksowe.
Słowo w jest prefiksem słowa u je li u ma posta u = wx , gdzie x jest innym słowem.
Np. słowo 101 jest prefiksem słowa 1011100.
Widzimy wi c, e problem na tym, e kod dla jednego symbolu jest prefiksem dla innego. Np. kod dla symbolu a jest prefiksem kodu dla symbolu c. Je li informacja zaczyna si od 0 to nie wiemy jak j interpretowa .
Kod o tej własno ci, e kod indywidualnego symbolu nie jest prefiksem adnego innego symbolu nazywamy kodem prefiksowym.
Przykład.
Rozwa my nast puj cy kod dla zbioru symboli {c,e,o,r,t}:
c – 11, e – 0, o –100, r – 1010, t – 1011.
Jest to kod prefiksowy. Nie ma tu problemu z odczytem informacji. Np.
111001010101001111 (= 11 100 1010 100 11 11) oznacza corrocc.
Naszym celem jest wi c zbudowanie jak najkrótszego kodu prefiksowego.
Potrzebna jest nam znajomo cz sto ci wyst powania symboli w kodowanym
j zyku. Jest to charakterystyka, któr znamy z bada nad j zykiem. Przypisujemy wi c ka demu symbolowi cz sto f wzgl dem zbioru symboli.
Np. niech C = { a,b,c,d}. Przypisanie cz sto ci f( a)=2, f( b)=2, f( c)=8, f( d)=5 oznacza, e w danym j zyku zapisywanym przy pomocy tych 4 symboli na ka de dwa
wyst pienia symbolu a symbol b pojawia si te dwa razy, symbol c 8 razy a symbol d 5 razy. Tzn. c jest najcz ciej pojawiaj cym si symbolem.
W oparciu o cz sto ci symboli oblicza si wag kodu.
8
Definicja. Niech C = { a a
a jest zbiorem symboli za f ( a
f a
f a
1 ),
( 2 ), , ( k )
1 , 2 ,
, k }
s cz sto ciami tych symboli. Przyjmijmy, e mamy zbiór charakterów koduj cych poszczególne symbole oraz, e l( a l a
l a s długo ciami tych charakterów
1 ), ( 2 ),
, ( k )
koduj cych. Wtedy wag kodu jest
i= k f ( a l)( a ) .
i=
i
i
1
Przykład . Waga kodu: c – 11, e – 0, o –100, r – 1010, t – 1011 o cz sto ciach f ( c) = ,
4 f ( e) = ,
9 f ( o) = ,
3 f ( r) = f ( t) = 2 wynosi:
f ( c) ⋅ l( c) + f ( e) ⋅ l( e) + f ( o) ⋅ l( o) + f ( r) ⋅ l( r) + f ( t) ⋅ l( t) = 4 ⋅ 2 + 9 ⋅1+ 3⋅ 3 + 2 ⋅ 4 + 2 ⋅ 4 = 41.
Im mniejsza waga kodu tym kod jest efektywniejszy. Podamy teraz metod
konstruowania najefektywniejszego kodu prefiksowego. Kod ten został znaleziony przez D. A. Huffmana z Bell Labs.
D. A. Huffman, „A method for the construction of minimum redundancy codes”, Proc. IRE 40, 1098-1101 (1952).
9
Algorytm konstrukcji kodu Huffmana.
Algorytm kreuje drzewo, którego wierzchołki le na s siaduj cych poziomach.
Wierzchołki s etykietowane cz sto ciami wyst powania symboli w u ywanym
j zyku.
Krok 1.
Umie jeden wierzchołek dla ka dego symbolu na najwy szym
poziomie. Oznacz wierzchołki odpowiadaj cymi im symbolami i przypisz im
cz sto ci wyst powania symboli w j zyku. Uporz dkuj wierzchołki wzgl dem
wzrastaj cej cz sto ci.
Poziom
najwy szy
4 -
5 +
7 b
9 c
25 d
32 a
Krok 2.
Poł cz dwa wierzchołki o najmniejszej cz sto ci do nowego
wierzchołka na poziomie o jeden wy szym. Oznacz ten nowy wierzchołek sum cz sto ci. Podnie pozostałe wierzchołki o jeden poziom wy ej tak je przestawiaj c aby zachowane było uporz dkowanie wierzchołków wzgl dem wzrastaj cej cz sto ci.
7
9
9
25
32
Poziom
b
najwy szy
c
d
a
4 -
5 +
10
Powtarzaj Krok 2 tak długo a na najwy szym poziomie zostanie jeden
wierzchołek.
Poziom
9 c
16
25 d
32 a
najwy szy
9
7 b
Poziom
25
25 d
32 a
najwy szy
4 -
5 +
9 c
16
7 b
9
Poziom
32 a
najwy szy
50
4 -
5 +
25
25 d
Poziom
82
najwy szy
9 c
16
32 a
50
7 b
9
25
25 d
4 -
5 +
9 c
16
7 b
9
4 -
5 +
11
Usu wszystkie etykiety
cz sto ci oraz oznacz ka d lew
0
1
kraw d przez 0 a ka d praw kraw d
przez 1.
a
0
1
d
0
1
c
0
1
b
0
1
Tak otrzymany graf nazywa si drzewem Huffmana.
-
+
Krok 5.
Zbuduj tabel kodu. Kod wybranego symbolu otrzymuje si wypisuj c
wszystkie 0 i 1 jakie napotyka si na drodze o pocz tku w wierzchołku drzewa i ko cu w wierzchołku przypisanemu danemu symbolowi.
Symbol
Cz sto
Kod Huffmana
a
32
0
b
7
1010
c
9
100
d
25
11
+
5
10111
-
4
10110
Jest to kod prefiksowy, ponadto symbole o wysokiej cz sto ci wyst powania maj krótsze kody ni te o małej cz sto ci. Waga naszego przykładowego kodu wynosi
32 ⋅1+ 7 ⋅ 4 + 9 ⋅3 + 25 ⋅ 2 + 5⋅ 5 + 4 ⋅ 5 = 182.
Kod Huffmana jest kodem o najmniejszej mo liwej wadze po ród wszystkich kodów
prefiksowych.
12
Podane w powy szym algorytmie cz sto ci wyst powania symboli mo na zast pi prawdopodobie stwami pojawienia si poszczególnych symboli. Procedura przej cia
od cz stotliwo ci do prawdopodobie stw jest nast puj ca:
Prawdopodobie stwo
Cz sto
Symbol
fi
f
p
i =
i
fi
i= ,
1 5
a
32
32/82
b
7
7/82
c
9
9/82
d
25
25/82
+
5
5/82
-
4
4/82
f
p
i = 1
i = 82
i= ,
1 5
i= ,
1 5
Wyliczymy teraz entropi odpowiadaj c naszemu kodowi i porównamy j z entropi
Shanon’a.
Symbol
pi
Kod Huffmana
Długo [bits]
a
32/82
0
1
b
7/82
1010
4
c
9/82
100
3
d
25/82
11
2
+
5/82
10111
5
-
4/82
10110
5
SKOD = 1⋅32 /82 + 4 ⋅ 7 /82 + 3⋅9 /82 + 2 ⋅ 25/82 + 5⋅5/82 + 5⋅ 4 /82 = 182 /82 = 2 2
. 195
S
p
p
SHANON = −
i log
i =
2
1
,
2 818
i= ,
1 5
Kod Huffmana ma najmniejsz entropi spo ród kodów prefiksowych. Warto tej entropii jest bliska teoretycznej granicy danej warto ci entropii Shanon’a.
13