Kodowanie Shannona-Fano

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Kodowanie Shannona-Fano – metoda kompresji bezstratnej autorstwa Roberta Fano. Kodowanie to dla dyskretnego źródła danych znajduje kod prefiksowy, który charakteryzuje się dość dobrą efektywnością – lepszą od kodowania Shannona (słowa kodowe krótsze o 1 bit), nie tworzy jednak optymalnych kodów. Kodowanie Shannona-Fano jest używane w kompresorze ZIP, przy wybranej metodzie kompresji implode[1].

Algorytm tworzenia słów kodowych[edytuj | edytuj kod]

Algorytm przedstawia się następująco:

  1. s – ciąg symboli ze zbioru S posortowanych wg prawdopodobieństw p_i
  2. Shannon-Fano(s):
    • Jeśli s zawiera dwa symbole, do słowa kodu pierwszej litery dodaj 0, do słowa kodu drugiej litery – 1.
    • W przeciwnym razie, jeśli s zawiera więcej niż dwa symbole, podziel go na dwa podciągi s1 i s2 tak, żeby różnica między sumą prawdopodobieństw liter z s1 i s2 była najmniejsza. Do słów kodu symboli z s1 dodaj 0, do kodów symboli z s21. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

Przykład[edytuj | edytuj kod]

Niech S = \{a, b, c, d\}, p = \{0{,}45; 0{,}3; 0{,}2; 0{,}05\}.

Początkowo ciąg s = abcd (porządek według malejącego prawdopodobieństwa).

Składa się z więcej niż 2 liter, zatem trzeba go podzielić. Możliwe są następujące sytuacje:

  1. s_1 = a, s_2 = bcd; różnica prawdopodobieństw 0,1;
  2. s_1 = ab, s_2 = cd; różnica prawdopodobieństw 0,5;
  3. s_1 = abc, s_2 = d; różnica prawdopodobieństw 0,9.

Wybierana jest pierwsza para, ponieważ różnica prawdopodobieństw jest najmniejsza. Do słów kodu liter z s_1 = a dopisywane są 0, do słów kodu liter z s_2 = bcd1:

a = 0
b = 1
c = 1
d = 1

Teraz wywoływana jest funkcja Shannon-Fano(s_1) – ten ciąg ma długość 1 i nie jest już dalej przetwarzany. Następnie wykonywane jest Shannon-Fano(s_2) – s_2 jest dłuższy niż 2 i musi zostać podzielony.

Sytuacja jest podobna jak w poprzednim kroku, bo s_{12} = b i s_{22} = cd. Do słów kodu liter z s_{12} = b dopisywane są 0, do słów kodu liter z s_{22} = cd1:

a = 0
b = 10
c = 11
d = 11

Wywoływana jest funkcja Shannon-Fano(s_{12}) – ten ciąg ma długość 1, nie jest już dalej przetwarzany. Następnie wykonywane jest Shannon-Fano(s_{22}) – s_{22} ma długość 2, więc tutaj kodowanie kończy się – do słowa kodu pierwszego symbolu (c) dopisywane jest 0, a do słowa kodu drugiego kodu (d) – 1:

a = 0
b = 10
c = 110
d = 111

Średnia długość kodu L_k = 1 \cdot 0{,}45 + 2 \cdot 0{,}3 + 3 \cdot 0{,}2 + 3 \cdot 0{,}05 = 1{,}8. W tym przypadku efektywność kodowania wynosi \frac{H(S)}{L_k} \cdot 100\% = \frac{1{,}72}{1{,}80} \cdot 100\% = 95\%. Dla tych samych danych efektywność kodowania Shannona wynosi zaledwie 73{,}2\%.

Bibliografia[edytuj | edytuj kod]

  • Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.

Zobacz też[edytuj | edytuj kod]

Przypisy