Kodowanie Shannona-Fano

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[1].

Algorytm tworzenia słów kodowych[edytuj kod]

Algorytm przedstawia się następująco:

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

Przykład[edytuj kod]

Niech , .

Początkowo ciąg (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. , ; różnica prawdopodobieństw 0,1;
  2. , ; różnica prawdopodobieństw 0,5;
  3. , ; różnica prawdopodobieństw 0,9.

Wybierana jest pierwsza para, ponieważ różnica prawdopodobieństw jest najmniejsza. Do słów kodu liter z dopisywane są 0, do słów kodu liter z 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 liter z dopisywane są 0, do słów kodu liter z 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 () – 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 .

Przypisy

Bibliografia[edytuj kod]

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

Zobacz też[edytuj kod]