Kodowanie Shannona-Fano

Kodowanie Shannona-Fano – nazwa obejmująca metody kompresji bezstratnej wynalezione równolegle przez Claude’a Shannona i Roberta Fano (opublikowane odpowiednio w 1948 i 1949).

Nazwa „Shannon-Fano” może w zależności od publikacji (oraz kontekstu) obejmować obie metody, metodę Fano lub metodę Shannona.

Kodowanie te dla dyskretnego źródła danych znajduje kod prefiksowy o zbliżonych do optymalnych kodach. Metoda Fano osiąga zazwyczaj słowa kodowe krótsze o 1 bit od metody kodowania Shannona.

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$ posortowanych według prawdopodobieństw $p_{i}$
2. funkcja Shannon-Fano(s) (metoda Fano):
   • Jeśli s zawiera dwa symbole, do słowa kodu dla pierwszego symbolu dopisz 0, do słowa kodu dla drugiego symbolu dopisz 1.
   • W przeciwnym razie, jeśli s zawiera więcej niż dwa symbole, podziel je na dwa podciągi s1 i s2 tak, żeby różnica między sumą prawdopodobieństw symboli w s1 i s2 była jak najmniejsza. Do słów kodu dla symboli z s1 dopisz 0, do kodów dla symboli z s2 dopisz 1. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

Przykład

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 nierosnącego prawdopodobieństwa).

Składa się z więcej niż 2 symboli, 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 podciągów s1 i s2 jest wtedy najmniejsza. Do słów kodu dla symboli z $s_{1}=a$ dopisz 0, do słów kodu dla symboli z $s_{2}=bcd$ dopisz 1:

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 dla symboli z $s_{12}=b$ dopisywane są 0, do słów kodu dla symboli z $s_{22}=cd$ dopisywane są 1:

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)$ dopisywana jest 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\%.$

Zobacz też

• kodowanie arytmetyczne
• kodowanie Huffmana
• A Mathematical Theory of Communication

Bibliografia

• Rozdział 1 - Informacja i kodowanie, Rozdział 2 - Kodowanie Shannona-Fano. W: Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.