Kodowanie Shannona-Fano

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.

Algorytm tworzenia słów kodowych

Algorytm przedstawia się następująco:

1. s – ciąg symboli ze zbioru $S$$S$ posortowanych według prawdopodobieństw $p_{i}$$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 s2 – 1. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

Przykład

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

Początkowo ciąg $s=abcd$$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_{1}=a$, $s_{2}=bcd$$s_{2}=bcd$; różnica prawdopodobieństw 0,1;
2. $s_{1}=ab$$s_{1}=ab$, $s_{2}=cd$$s_{2}=cd$; różnica prawdopodobieństw 0,5;
3. $s_{1}=abc$$s_{1}=abc$, $s_{2}=d$$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$$s_{1}=a$ dopisywane są 0, do słów kodu liter z $s_{2}=bcd$$s_{2}=bcd$ – 1:

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

Teraz wywoływana jest funkcja Shannon-Fano($s_{1}$$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}$) – $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$$s_{12}=b$ i $s_{22}=cd$$s_{22}=cd$. Do słów kodu liter z $s_{12}=b$$s_{12}=b$ dopisywane są 0, do słów kodu liter z $s_{22}=cd$$s_{22}=cd$ – 1:

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

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

Bibliografia

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

Zobacz też

• kodowanie Huffmana
• kodowanie arytmetyczne