Tekst źródłowy strony Kodowanie Shannona-Fano

'''Kodowanie Shannona-Fano''' – nazwa obejmująca metody [[kompresja bezstratna|kompresji bezstratnej]] wynalezione równolegle przez [[Claude E. Shannon|Claude’a Shannona]] i {{link-interwiki|Robert Fano|Q=Q93052|tekst=Roberta Fano}} (opublikowane odpowiednio w 1948<ref>{{Cytuj |autor = Claude Shannon |tytuł = A Mathematical Theory of Communication |czasopismo = The Bell System Technical Journal |data = 1948-07 |data dostępu = 2023-07-07 |wolumin = 27 |numer = 3 |wydawca = AT & T Bell Laboratories |s = 379–423 |url = https://archive.org/details/sim_att-technical-journal_1948-07_27_3/page/n2/ |język = en |kropka = na s. 403 Shannon odnosi się do metody Fano.}}</ref><ref>{{Cytuj |autor = C. E. Shannon |tytuł = A Mathematical Theory of Communication |data = |data dostępu = 2023-07-08 |opis = reprint z poprawkami |opublikowany = Internet Archive |url = https://archive.org/details/ost-engineering-shannon1948/page/n16/ |język = en}}</ref> i 1949<ref>{{Cytuj |autor = Robert M. Fano |tytuł = The Transmission of Information |czasopismo = Technical Report No. 65 |data = 1949-03-17 |data dostępu = 2023-07-07 |url = http://archive.org/details/fano-tr65.7z |język = en}}</ref>).

Nazwa „Shannon-Fano” może w zależności od publikacji (oraz kontekstu) obejmować obie metody, metodę Fano{{odn|Drozdek|1999|s=32, 34}} lub metodę Shannona<ref>{{Cytuj |autor = Te Sun Han, Kingo Kobayashi |rozdział = 3.7.1 Shannon-Fano Code |tytuł = Mathematics of Information and Coding |data = 2002 |data dostępu = 2023-07-07 |isbn = 978-0-8218-4256-0 |wydawca = American Mathematical Soc. |s = 95–96 |url = https://books.google.pl/books?id=VpRESN24Zj0C&lpg=PA10&dq=mathematics%20as%20universal%20code&pg=PA95#v=onepage&q=shannon-fano&f=false |język = en}}</ref><ref>{{Cytuj |autor = Stanislav Krajci, Chin-Fu Liu, Ladislav Mikes, Stefan M. Moser |rozdział = I. Introduction |tytuł = Performance analysis of Fano coding |data = 2015-06 |data dostępu = 2023-07-07 |isbn = 978-1-4673-7704-1 |wydawca = IEEE |s = 1746–1750 |doi = 10.1109/ISIT.2015.7282755 |url = https://moser-isi.ethz.ch/publications.html#conferencepapers |język = en}}</ref>.

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 [[kodowanie Shannona|kodowania Shannona]]{{odn|Drozdek|1999|s=32, 34}}.

Kodowanie Shannona-Fano jest używane w kompresorze [[ZIP]], przy wybranej metodzie kompresji ''implode''<ref>http://www.pkware.com/documents/casestudies/APPNOTE.TXT (dostęp 2008-09-20).</ref>.

== Algorytm tworzenia słów kodowych ==
Algorytm przedstawia się następująco{{odn|Drozdek|1999|s=34–35}}:
# '''s''' – ciąg symboli ze zbioru <math>S</math> posortowanych według prawdopodobieństw <math>p_i</math>
# 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 <math>S = \{a, b, c, d\},</math> <math>p = \{0{,}45; 0{,}3; 0{,}2; 0{,}05\}.</math>

Początkowo ciąg <math>s = abcd</math> (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:
# <math>s_1 = a,</math> <math>s_2 = bcd;</math> różnica prawdopodobieństw 0,1;
# <math>s_1 = ab,</math> <math>s_2 = cd;</math> różnica prawdopodobieństw 0,5;
# <math>s_1 = abc,</math> <math>s_2 = d;</math> 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 <math>s_1 = a</math> dopisz '''0''', do słów kodu dla symboli z <math>s_2 = bcd</math> dopisz '''1''':

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

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

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

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

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

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

Średnia długość kodu <math>L_k = 1 \cdot 0{,}45 + 2 \cdot 0{,}3 + 3 \cdot 0{,}2 + 3 \cdot 0{,}05 = 1{,}8.</math> W tym przypadku efektywność kodowania wynosi <math>\frac{H(S)}{L_k} \cdot 100\% = \frac{1{,}72}{1{,}80} \cdot 100\% = 95\%.</math> Dla tych samych danych efektywność [[Kodowanie Shannona|kodowania Shannona]] wynosi zaledwie <math>73{,}2\%.</math>

== Zobacz też ==
* [[kodowanie arytmetyczne]]
* [[kodowanie Huffmana]]
* {{link-interwiki|A Mathematical Theory of Communication|Q=Q724029}}

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj książkę |nazwisko = Drozdek |imię = Adam |tytuł = Wprowadzenie do kompresji danych |data = 1999 |wydawca = Wydawnictwa Naukowo-Techniczne |miejsce = Warszawa |isbn = 83-204-2303-1 |rozdział = Rozdział 1 - Informacja i kodowanie, Rozdział 2 - Kodowanie Shannona-Fano |odn = tak}}

[[Kategoria:Algorytmy kompresji bezstratnej|Shannona-Fano]]