Kodowanie Shannona-Fano

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

Nazwa „Shannon-Fano” może w zależności od publikacji (oraz kontekstu) obejmować obie metody, metodę FanoSzablon:Odn 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 ShannonaSzablon:Odn.

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

Algorytm tworzenia słów kodowych

Algorytm przedstawia się następującoSzablon:Odn:

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\mathrm{\%}=\frac{1,72}{1,80}\cdot 100\mathrm{\%}=95\mathrm{\%}.$ Dla tych samych danych efektywność kodowania Shannona wynosi zaledwie $73,2\mathrm{\%}.$

Zobacz też

• kodowanie arytmetyczne
• kodowanie Huffmana
• Szablon:Link-interwiki

Bibliografia

• Szablon:Cytuj książkę