Kodowanie Shannona

Z Wikipedii

(Przekierowano z Kodowanie Shannona-Fano)

Kodowanie Shannona, to metoda kodowania, którą Claude E. Shannon przedstawił jako jeden z dowodów swojego podstawowego twierdzenia o kodowaniu.

Kodowanie Shannona nie tworzy optymalnych kodów; nieco lepsze wyniki daje modyfikacja znana jako kodowanie Shannona-Fano. Kodowanie Shannona-Fano jest używane w kompresorze ZIP, przy wybranej kompresji metodzie implode^[1].

Znacznie lepszą efektywnością charakteryzują się kodowanie Huffmana oraz kodowanie arytmetyczne.

[edytuj] Kodowanie Shannona

Dane jest źródło $S = \{x_1, x_2, \ldots\}$ i stowarzyszone z nimi prawdopodobieństwa $p = \{p_1, p_2, \ldots\}$ .

Prawdopodobieństwa (a wraz z nimi symbole) są sortowane w porządku nierosnącym, tj. $p_i \ge p_{i+1}$ .
Następnie dla tak uporządkowanych danych oblicza się niepełne prawdopodobieństwo komulatywne: $P(x_i) = p_1 + p_2 + \ldots + p_{i-1}$ - jest to suma wszystkich prawdopodobieństw od 1. do i-1 elementu.
Kodowanie Shannona polega na wzięciu $\lceil -\log_{2}{P_i}\rceil$ (długość Shannona) pierwszych bitów binarnego rozwinięcia liczby $P i$ (brane są bity po przecinku).

Średnia długość kodów mieści się w przedziale $[H (S), H (S) + 1)$ , gdzie $H (S)$ to entropia źródła (średnia liczba bitów na symbol).

[edytuj] Przykład

Niech $S = {a, b, c, d}$ , $p = {0.45,0.3,0.2,0.05}$ (entropia $H (S) = 1.72$ ); prawdopodobieństwa są już podane nierosnąco.

Prawdopodobieństwa kumulatywne:

$P 1(a) = 0$
$P 2(b) = p 1 = 0.45$
$P 3(c) = p 1 + p 2 = 0.45 + 0.3 = 0.75$
$P 4(d) = p 1 + p 2 + p 3 = 0.45 + 0.3 + 0.2 = 0.95$

I ich rozwinięcia binarne (wzięte 5 pierwszych bitów po przecinku):

$P 1(a) = 0.00000 2$
$P 2(b) = 0.01110 2$
$P 3(c) = 0.11000 2$
$P 4(d) = 0.11110 2$

Długości Shannona (długości kodów w bitach):

$l_a = \lceil -\log_{2}{0.45}\rceil = 2$
$l_b = \lceil -\log_{2}{0.30}\rceil = 2$
$l_c = \lceil -\log_{2}{0.20}\rceil = 3$
$l_d = \lceil -\log_{2}{0.05}\rceil = 5$

Ostatecznie kody mają postać:

$k o d (a) = 00 2$
$k o d (b) = 01 2$
$k o d (c) = 110 2$
$k o d (d) = 11110 2$

Średnia długość kodu $L_k = 2 \cdot 0.45 + 2 \cdot 0.3 + 3 \cdot 0.2 + 5 \cdot 0.05 = 2.35$ ( $k = 1$ ). Po podstawieniu do nierówności podanej w twierdzeniu: $1.72 \le 2.35 < 1.72 + 1$ stwierdzamy, że otrzymany kod rzeczywiście ją spełnia.

Jednak, jak wspomniano, efektywność kodowania Shannona nie jest duża - dla danych z tego przykładu wynosi $\frac{H(S)}{L_k} \cdot 100\% = 73.2\%$ .

[edytuj] Kodowanie Shannona-Fano

Robert Fano zaproponował algorytm, który daje trochę lepsze wyniki kodowania - kody mogą być krótsze o 1 bit od kodów tworzonych metodą Shannona, także rozkład bitów może się różnić.

Kodowanie Shannona-Fano przedstawia się następująco:

s - ciąg symboli ze zbioru $S$ posortowanych wg prawdopodobieństw $p i$
Shanon-Fano(s):
- Jeśli s zawiera dwa symbole do słowa kodu pierwszej litery dodaj 1, do słowa kodu drugiej litery - 0.
- 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 1, do kodów symboli z s2 - 0. Wywołaj rekurencyjnie funkcje: Shannon-Fano(s1) oraz Shannon-Fano(s2).

[edytuj] Przykład

Niech $S = {a, b, c, d}$ , $p = {0.45,0.3,0.2,0.05}$ .

Początkowo ciąg $s = a b c d$ (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:

$s 1 = a$ , $s 2 = b c d$ ; różnica prawdopodobieństw 0.1;
$s 1 = a b$ , $s 2 = c d$ ; różnica prawdopodobieństw 0.5;
$s 1 = a b c$ , $s 2 = d$ ; różnica prawdopodobieństw 0.9.

Wybierana jest pierwsza para, ponieważ różnica prawdopodobieństw jest najmniejsza. Do słów kodu liter z $s 1 = a$ dopisywane są 0, do słów kodu liter z $s 2 = b c d$ - 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 = c d$ . Do słów kodu liter z $s 12 = b$ dopisywane są 0, do słów kodu liter z $s 22 = c d$ - 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$ ) - 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\% = \frac{1.72}{1.80} \cdot 100\% = 95\%$ , jest więc znacznie lepsza niż kodowania Shannona.

[edytuj] Bibliografia

Claude. E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, str. 379-423, 623-656, lipiec, październik, 1948
Adam Drozdek, Wprowadzenie do kompresji danych, WNT 1999

[edytuj] Zobacz też

Przypisy

↑ http://www.pkware.com/documents/casestudies/APPNOTE.TXT (dostęp 20.09.2008)

Pompy insulinowe potrzebne przy planowaniu ciąży

Kobiety z cukrzycą powinny mieć możliwość korzystania z pomp insulinowych już w okresie planowania ciąży. Zmniejsza to bowiem znacznie ryzyko wad wrodzonych i zgonów ich dzieci, mówili lekarze na konferencji w Warszawie.

Alternatywa dla aukcji uprawnień do emisji CO2

Polska proponuje, aby także po 2013 roku unijne elektrownie otrzymywały za darmo część uprawnień do emisji CO2. Dopiero powyżej pewnego poziomu emisji będą musiały kupować je na aukcji - poinformowało Ministerstwo Gospodarki (MG).

Co czwarty człowiek ma zaburzenia psychiczne

Co czwarty mieszkaniec Ziemi może cierpieć na zaburzenia psychiczne. Takie alarmujące statystyki przedstawiła w najnowszym raporcie Światowa Organizacja Zdrowia.

Po "melaminowej" aferze zwiększą się kontrole

W związku ze skandalem z melaminą w chińskim sproszkowanym mleku Chiny zaostrzyły kontrolę procesu produkcji wyrobów mleczarskich i zagroziły umieszczeniem nieuczciwych producentów na czarnej liście - podały tamtejsze media.

Szklarnie są odpowiedzialne za ochłodzenie klimatu?

Białe dachy szklarni w hiszpańskiej prowincji Almeria odbijają tyle światła słonecznego, że w okolicy obniżyła się temperatura. - informuje "New Scientist".

Linki: Strona g��wna

[0] ttp://www.pkware.com/documents/casestudies/APPNOTE.TXT (dostęp 20.09.2008)

[1]

Encyklopedia

Kodowanie Shannona

Z Wikipedii

Spis treści

[edytuj] Kodowanie Shannona

[edytuj] Przykład

[edytuj] Kodowanie Shannona-Fano

[edytuj] Przykład

[edytuj] Bibliografia

[edytuj] Zobacz też

Przypisy