Na ogół definiuje się wyrazy kodu, powiedzmy zero-jedynkowe, o zmiennej długości, dla odcinków (bloków) oryginału o równej długości. Ja natomiast podzielę (w Części 4') teksty oryginalne na odcinki o nierównej długości, ale koduję je za pomocą 0-1 wyrazów o równej długości. To nastepnie bez większego trudu pozwala skonstruować inne, bardziej klasyczne kodowanie A-bloków (to znaczy A-strun - patrz niżej) o równej długości za pomocą bloków zero-jedynkowych, o zmiennej długości.
Gdy matematyk zajmuje się pewnym zastosowaniem, to początkowo szuka odpowiedniej definicji (tj. systemu definicji czyli teorii) - odpowiedniej, czyli spełniającej dwa warunki:
- definicja nieźle przybliża ważną (lub pilną) część zastosowania;
- definicja jest na tyle trafna, prosta i elegancka, że prowadzi do harmonijnej, głębokiej teorii.
Jak tylko uzyska taką definicje, to krzyczy: niech się dzieje, co się ma dziać, ale odtąd liczy się moja definicja - po czym rozwija teorię. Definicja i rzeczywistość nie są tym samym. Nie istnieje "prawdziwa" definicja, tak jak nie istnieje prawdziwa mapa terenu. Istnieją co najwyżej lepsze i gorsze. Najlepsze są nieporównywalne pod względem matematycznej lepszości, choć mogą oddawać rzeczywistość z różną dokładnością lub w różnym zakresie (mogą zajmować się różnymi obszarami zastosowania) - podobnie nieporównywalne są dobre mapy: są fizyczne, administracyjne, geologiczne, nawigacyjne, ... Używają różnych układów współrzędnych (siatek), różnych skal pomniejszenia, przedstawiają różne tereny. Podobnie jest ze związkiem teorii matematycznych z rzeczywistością.
W niniejszej nocie, śladem Shannona, będzie podana matematyczna definicja informacji i entropii. Będzie zastosowana do teorii kompresji tekstów (strun nad zadanym alfabetem [;A;]). Struny, których wszystkie symbole należą do alfabetu [;A;] nazywamy A-strunami. Informację w niniejszej nocie mierzymy w bitach dwójkowych; stąd we wzorach logarytm o podstawie 2.
Niech [;(0;\infty);] oznacza przedział wszystkich wszystkich dodatnich liczb rzeczywistych. Przez alfabet probabilistyczny rozumiem parę uporządkowaną
[;(A\ \pi);]
gdzie alfabet [;A;] jest dowolnym zbiorem skończonym, oraz [;\pi : A \rightarrow (0;\infty);] spełnia warunek:
[;\sum_{a\in A} \pi(a)=1;]
Alfabet probabilistyczny w zasadzie jest po prostu skończoną przestrzenią probabilistyczną, jako że funkcja [;\pi;] naturalnie indukuje funkcję prawdopodobieństwa [;\pi';], zdefiniowaną dla dowolnego podzbioru [;B;] zbioru [;A;]:
[;\pi'(B) := \sum_{a\in B} \pi(a);]
Ponieważ jesteśmy zainteresowani w strunach, w których symbole występujące na dowolnych dwóch miejscach są niezależne (statystycznie), to definiujemy prawdopodobieństwo [;\pi(S);] dowolnej [;A;]-struny
[;S := (a_0 \dots a_{n-1});]
jako iloczyn prawdopodobieństw poszczególnych znaków:
[;\pi(S) := \prod_{k < n} \pi(a_k);]
Wtedy suma prawdopodobieństw wszystkich [;A;]-strun o ustalonej długości [;n;] jest równa 1, czyli struny o ustalonej długości tworzą przestrzeń probabilistyczną; takich strun o ustalonej długości [;n;] jest wszystkich razem [;|A|^n;].
Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Informacją zawartą w symbolu [;a\in A;] nazywamy
[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]
Im symbol ma niższe prawdopodobieństwo (wystąpienia w tekście), tym każde jego wystąpienie niesie więcej informacji. Gdy pewien symbol ma prawdopodobieństwo bliskie 1, to występuje w tekstach prawie na każdym miejscu, i jego występowanie jest spodziewane. Wtedy niesie on niewielką informację (logarytm jest bliski zeru).
Entropią [;\epsilon(A\ \pi);] alfabetu probabilistycznego [;(A\ \pi);] nazywamy wartość oczekiwaną, czyli średnią ważoną informacji zawartych w symbolach alfabetu:
[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot \log_2\left(\frac{1}{\pi(a)}\right);]
Informacją zawartą w strunie [;S := (a_0\dots a_{n-1});] nazywamy sumę informacji jej symboli:
[;\iota(S) := \sum_{k < n} \iota(a_k);]
Informacja per symbol, czyli informacja struny podzielona przez jej długość (przez liczbę jej symboli) jest dla długich, losowych strun na ogół równa w przybliżeniu entropii alfabetu.
Dla elegancji rozpatrzmy także struny nieskończone [;(a_0\ a_1\ \dots);]. Są one punktami czyli tworzą przestrzeń [;A^{\mathbb{Z}_+};], będacą iloczynem kartezjańskim nieskończenie wielu kopii [;A;]. W przestrzeni tej wprowadzamy miarę probabilistyczna, zaczynając od definicji [;\pi''(B_S);] miary S-kubów [;B(S);], gdzie [;S := (a_0\ \dots\ a_{n-1};] jest struną skończoną, oraz
[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n} x_k = a_k \right\} ;]
oraz S-kub jest zdefiniowany jako podzbiór przestrzeni:
[;\pi''\left(B_S\right) := \pi(S) = \prod_{k < n} \pi(a_k) ;]
Następnie miarę unii skończonej lub przeliczalnej rodziny parami rozłącznych S-kubów definiuje się jako sumę miar wchodzących w tę rodzinę S-kubów. Podstawowa własność S-kubów brzmi następująco:
TWIERDZENIE 0 Niech [;S\ T;] będą dwiema skończonymi A-strunami. Wtedy boksy [;B_S\ B_T;] są rozłączne [;\Leftrightarrow;] żadna ze strun [;S\ T;] nie jest prefiksem (początkowym odcinkiem) drugiej.
Wynika stąd, że dwa S-kuby są albo rozłączne albo jeden z nich jest zawarty w drugim.
Miara całej przestrzeni [;A^{\mathbb{Z}_+};] wynosi dokładnie 1.
cdn. (patrz Cz.4')
No comments:
Post a Comment