1) Zaproponuj algorytm definiujący D-arny kod Huffmana C, który nie tylko minimalizuje średnią długość kodu, L C =∑ p⋅ l i
i
i
ale także i długość całkowitą, rozumianą jako:
C =∑ li
i
Weźmy przykład (dla kodu binarnego): Słowo
S1
S2
S3
Bitów
w1
p1=0,4
p1=0,4
p2+p3+p4=0,6
1
w2
p2=0,2
p3+p4=0,4
p1=0,4
2
w3
p3=0,2
p2=0,2
3
w4
p4=0,2
3
C =∑ l =9
i
i
L C =∑ p⋅ l =2
i
i
i
Teraz poskładajmy to korzystając z innego algorytmu: Słowo
S1
S2
S3
Bitów
w1
p1=0,4
p3+p4=0,4
p1+p2=0,6
2
w2
p2=0,2
p1=0,4
p3+p4=0,4
2
w3
p3=0,2
p2=0,2
2
w4
p4=0,2
2
C =∑ l =8
i
i
L C =∑ p⋅ l =2
i
i
i
Widać, że drugi kod jest lepszy.
Metoda jest prosta, wystarczy umieszczać 'sklejenia' najwyżej jak się da.
Ponadto C będzie najmniejsza dla źródła, które każdą wiadomość generuje z takim samym prawdopodobieństwem (rozkład równomierny) 2) Na podstawie analizy kodowania Huffmana (lub korzystając z wyników zadania 1) pokaż, że dla bezpamięciowego źródła generującego N wiadomości, słowa kodowe binarnego kodu zwięzłego o długościach li spełniają podaną nierówność: N
∑ l ≥ N lg N
i
i=1
Wiemy, że:
N
N
∑ l ≥∑ lrówn (1) i
i
i=1
i =1
Czyli łączna długość ciągu kodowego zawsze jest większa bądź równa łącznej długości dla kodu, w którym rozkład jest równomierny.
Dla kodu optymalnego zachodzi: Krzychoo, TIiK
L= log D
2
Dla kodu o rozkładzie równomiernym można zapisać: log N
N⋅log N
N
N⋅log N
L=
2
⇔ N⋅ L=
2
⇔∑ lrówn=
2
log D
log D
i
log D
2
2
i =1
2
Dla kodu binarnego mamy:
N
∑ lrówn= N⋅log N
i
2
i=1
Korzystając z (1) mamy:
N
N
N
∑ l ≥∑ lrówn= N⋅log N ⇔∑ l ≥ N⋅log N
i
i
2
i
2
i=1
i =1
i=1
cbdu
3) Zakoduj w binarnym kodzie Shannona-Fano 10 wiadomości o jednakowych prawdopodobieństwach i wykaż, że kod jest zwięzły.
0
1
m1,m2,m3,m4,m5
m6,m7,m8,m9,m10
1
0
1
0
m1,m2
m3,m4,m5
m6,m7
m8,m9,m10
1
0
0
0
1
0
1
1
m1
m2
m3 m4,m5
m6
m7
m8
m9,m10
1
0
0
1
m9
m10
m4
m5
m1
000
m6
100
m2
001
m7
101
m3
010
m8
110
m4
0110
m9 1110
m5
0111 m10 1111
L= 3,4
Można się zastanowić, czy da się uzyskać kod o krótszej średniej długości wiadomości.
N
N
L C =∑ p⋅ l = 1 ∑ l i
i
i
i =1
N i=1
Krzychoo, TIiK
Patrząc na powyższą formułę widać, że należałoby skrócić długość co najmniej jednego słowa, pozostawiając niezmienione długości pozostałych.
Oczywiście taka sytuacja jest niemożliwa, jeśli kod ma być jednoznaczny (można lekko poeksperymentować, pamiętając o tym, że musi być spełniona nierówność Krafta).
4) Skompresuj za pomocą kodu arytmetycznego sekwencję "SWIS_MISS".
Znaki, jakie wystąpią w sekwencji to: S,W,I,M,_,@ -> znak końca.
Symbol Prawdopodobieństwo Przedział
S
p =0,4
<0 ; 0,4)
S
W
p =0,1
<0,4 ; 0,5)
W
I
p =0,2
<0,5 ; 0,7)
I
M
p =0,1
<0,7 ; 0,8)
M
_
p =0,1
<0,8 ; 0,9)
_
@
p =0,1
<0,9 ; 1)
@
Przystąpmy do kodowania:
Sekwencja
Przedział
S
<0 ; 0,4)
SW
<0,16 ; 0,2)
SWI
<0,18 ; 0,188)
SWIS
<0,18 ; 0,1832)
...
...
SWIS_MISS@ <0,1828009216 ; 0,18280010240) Teraz należy znaleźć jakąś liczbę z tego przedziału i przesłać ją binarnie. Zapiszmy więc krańce przedziału:
0,1828009216 = 0,001011101100110000001010...
0,18280010240 = 0,001011101100110000001111...
Pogrubiony jest ciąg wspólny dla obu przedziałów, to musimy przesłać obowiązkowo! Ponadto liczba przesłana musi się zawierać w przedziale, zatem może nią być na przykład: K = 0,00101110110011000000110
5) Skompresuj za pomocą adaptacyjnego (dynamicznego) kodowania Huffmana sekwencję "Ala_ma_kota".
Wesołowski s. 43 - 47
A
1
0
e0
A1
Krzychoo, TIiK
1
0
1
0
1
A1
e0
l1
a
0
1
1
0
2
2
0
1
A1
A1
1
0
1
1
1
0
l1
0
1
l1
e0
a1
e0
a1
_
1
0
0
1
2
1
2
0
3
1
0
A1
1
0
1
0
1
a1
A1
l1
2
0
1
l1
_1
1
e0
1
0
a1
e0
_1
Krzychoo, TIiK
1
1
0
0
3
2
2
3
0
1
0
1
1
0
1
0
2
0
2
1
a1
l1
a1
0
A1
A1
1
l1
1
1
_1
1
0
0
1
_1
e0
m1
e0
m1
a
1
0
0
1
0
1
2
4
0
1
1
3
0
3
0
1
0
1
l1
2
A1
a2
0
1
l1
2
A1
0
a2
1
1
1
_1
0
1
0
1
_1
e0
m1
e0
m1
itd
Ostatecznie przesłana sekwencja będzie postaci (znaki różne od zera i jedynki to znaki zakodowane w kodzie ASCII): A 0 l 00 a 100 _ 000 m 01 111 1100 k 0000 o 11100 t 10
A
l
a
_
m
a
_
k
o
t
a
Sekwencja sporządzona na podstawie Wesołowskiego of korz...
Krzychoo, TIiK