Kodowanie Shannona-Fano – nazwa obejmująca metody kompresji bezstratnej wynalezione równolegle przez Claude’a Shannona i (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 implodehttp://www.pkware.com/documents/casestudies/APPNOTE.TXT (dostęp 2008-09-20)..

Algorytm tworzenia słów kodowych Algorytm przedstawia się następująco: s – ciąg symboli ze zbioru posortowanych według prawdopodobieństw 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 (entropia ).

Początkowo ciąg (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: różnica prawdopodobieństw 0,1; różnica prawdopodobieństw 0,5; 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 dopisz 0, do słów kodu dla symboli z dopisz 1:

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

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

Sytuacja jest podobna jak w poprzednim kroku, bo i Do słów kodu dla symboli z dopisywane są 0, do słów kodu dla symboli z dopisywane są 1:

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

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

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

Średnia długość kodu W tym przypadku efektywność kodowania wynosi Dla tych samych danych efektywność kodowania Shannona wynosi zaledwie

Zobacz też kodowanie arytmetyczne kodowanie Huffmana

Przypisy

Bibliografia

Shannona-Fano