Kodowanie Shannona-Fano
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 | edytuj kod]
Algorytm przedstawia się następująco:
- s – ciąg symboli ze zbioru posortowanych według prawdopodobieństw
- 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 s2 – 1. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).
Przykład[edytuj | 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:
- , ; 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 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[edytuj | edytuj kod]
- ↑ http://www.pkware.com/documents/casestudies/APPNOTE.TXT (dostęp 20.09.2008)
Bibliografia[edytuj | edytuj kod]
- Adam Drozdek: Wprowadzenie do kompresji danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 1999. ISBN 83-204-2303-1.