Kodowanie Shannona-Fano

Kodowanie Shannona-Fano – nazwa obejmująca metody kompresji bezstratnej wynalezione równolegle przez Claude’a Shannona i Roberta Fano(inne języki) (opublikowane odpowiednio w 1948^[1][2] i 1949^[3]).

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

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^[4].

Kodowanie Shannona-Fano jest używane w kompresorze ZIP, przy wybranej metodzie kompresji implode^[7].

Algorytm tworzenia słów kodowych

Algorytm przedstawia się następująco^[8]:

1. s – ciąg symboli ze zbioru ${\displaystyle S}$ posortowanych według prawdopodobieństw ${\displaystyle 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 ${\displaystyle S=\{a,b,c,d\},}$ ${\displaystyle p=\{0{,}45;0{,}3;0{,}2;0{,}05\}.}$

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

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

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

Sytuacja jest podobna jak w poprzednim kroku, bo ${\displaystyle s_{12}=b}$ i ${\displaystyle s_{22}=cd.}$ Do słów kodu dla symboli z ${\displaystyle s_{12}=b}$ dopisywane są 0, do słów kodu dla symboli z ${\displaystyle s_{22}=cd}$ dopisywane są 1:

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

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

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

Średnia długość kodu ${\displaystyle 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 ${\displaystyle {\frac {H(S)}{L_{k}}}\cdot 100\%={\frac {1{,}72}{1{,}80}}\cdot 100\%=95\%.}$ Dla tych samych danych efektywność kodowania Shannona wynosi zaledwie ${\displaystyle 73{,}2\%.}$

Zobacz też

• kodowanie arytmetyczne
• kodowanie Huffmana
• A Mathematical Theory of Communication(inne języki)

Przypisy

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.