Epsilon

Wednesday, January 5, 2011

Wstęp do Teorii Informacji. Cz.5

Swoją metodę kompresji z Części 4' uzupełnię algorytmem pomocniczym, który ulepsza (dalej kompresuje) kodowanie z Części 4'. Cechą charakterystyczną kodowania z Części 4' jest równa długość otrzymanych kodów binarnych, powiedzmy [;n;]. Na ogół nie wykorzystuje się przy tym wszystkich [;2^n;] kodów binarnych długości, co z miejsca daje możliwość dalszej poprawy.

W niniejszej nocie algorytm poprawiający zilustruję jednak na prostszych przykładach, by szybciej pokazać jak działa. Zajmę się raz jeszcze (patrz Część 3) kodowaniem binarnym ternarnych strun losowych, w których każda wartość bitu trójkowego [;0\ 1\ 2;] występuje z tym samym prawdopodobienstwem [;1/3;], na każdej pozycji struny, statystycznie niezależnie od każdej innej pozycji.

Zacznijmy raz jeszcze, jak w Części 3, od najprostszego kodowania:

[;0 \rightarrow 00;]

[;1 \rightarrow 01;]

[;2 \rightarrow 10;]

Używamy aż całe 2 bity binarne dla zakodowania jednego ternarnego, gdy według teorii Shannona powinno w tym celu średnio wystarczyć

[;log_2(3) \approx 1.585;]

bitów binarnych (nawet ciut mniej). Możemy z łatwością ulepszyć powyższe kodowanie następująco:

[;0 \rightarrow 00;]

[;1 \rightarrow 01;]

[;2 \rightarrow 1;]

Ponieważ w oryginalnym kodowaniu nie wykorzystaliśmy binarnego kodu [;11;], to w kodzie [;10;] zero usunęliśmy, i nasze kodowanie dalej daje się wiernie odkodować (jako że żaden z trzech nowych kodów nie jest prefiksem żadnego pozostalego). Tym razem bitów binarnych na wszystkie trzy trójkowe zużyliśmy 2+2+1=5, zamiast 2+2+2=6, jak poprzednio. Zatem tym losowy bit trójkowy kodujemy średnio za pomocą 5/3 bitów binarnych. Z miejsca uzyskaliśmy przyzwoitą średnią liczbę bitów dwójkowych na jeden trójkowy, niewiele gorszą (czyli większą) od idealnego [;log_2(3);].

Korzystając z nierówności [;3^3 < 2^5;], możemy otrzymać następne proste kodowanie bloków ternarnych, tym razem długości 3, przez bloki binarne o długości 5: po prostu kolejnym 27 ternarnym kodom podporządkujemy odpowiednio 27 kolejnych kodów binarnych długości 5:

[;000 \rightarrow 00000;]

[;001 \rightarrow 00001;]

[;002 \rightarrow 00010;]

[;010 \rightarrow 00011;]

[;\dots\rightarrow\dots;]

[;\dots\rightarrow\dots;]

[;221 \rightarrow 11001;]

[;222 \rightarrow 11010;]

Kod ten operuje na większych blokach niż poprzedni - ulepszony - algorytm, a mimo to średnia liczba bitów dwójkowych na jeden trójkowy dla obu kodowań jest ta sama, 5/3. Możemy jednak nasz ostatni kod ulepszyć:

Tylko ostatnie trzy wyrazy binarnego kodu zaczynają się na 11. Możemy więc je skrócić, wciąż zachowując warunek: żaden wyraz binarnego kodu nie jest prefiksem żadnego innego. Pozostałe 24 binarne kody pozostawiamy be zmian:

[;000 \rightarrow 00000;]

[;\dots\rightarrow\dots;]

[;\dots\rightarrow\dots;]

[;212 \rightarrow 10111;]

[;220 \rightarrow 1100;]

[;221 \rightarrow 1101;]

[;222 \rightarrow 111;]

Zamiast 27 bloków binarnych o długości 5, mamy obecnie 24 o długości 5, 2 o długości 4, oraz 1 o długości 3. Zaoszczędziliśmy 4 bity, i jest ich teraz w sumie [;24\cdot 5+2\cdot 4+ 3 = 131;]. Obecnie liczba dwójkowych bitów na jeden trójkowy wynosi

[;131/81 \approx 1.6173;]

Zbliżyliśmy się do idealnego [;\log_2(3);]. Można w tych samych ramach bardziej, bo powyższe ulepszenie było leniwe, takie by jak najmniej pisać, by jak najlepiej wykorzystać trzykropek. Lepsze ulepszenie otrzymuje się, przez równowmierne rozłożenie oszczędności (w poniższej tabeli, w lewej kolumnie mamy kolejne liczby w układzie trójkowym, a koncentrować warto się na kodach po prawej):

[;000 \rightarrow 00000;]

[;001 \rightarrow 00001;]

[;002 \rightarrow 00010;]

[;010 \rightarrow 00011;]

[;011 \rightarrow 00100;]

[;012 \rightarrow 00101;]

[;020 \rightarrow 0011 \quad\quad *;]

[;021 \rightarrow 01000;]

[;022 \rightarrow 01001;]

[;100 \rightarrow 01010;]

[;101 \rightarrow 01011;]

[;102 \rightarrow 01100;]

[;110 \rightarrow 01101;]

[;111 \rightarrow 0111 \quad\quad *;]

[;112 \rightarrow 10000;]

[;120 \rightarrow 10001;]

[;121 \rightarrow 10010;]

[;122 \rightarrow 10011;]

[;200 \rightarrow 10100;]

[;201 \rightarrow 10101;]

[;202 \rightarrow 1011 \quad\quad *;]

[;210 \rightarrow 11000;]

[;211 \rightarrow 11001;]

[;212 \rightarrow 1101 \quad\quad *;]

[;220 \rightarrow 11100;]

[;221 \rightarrow 11101;]

[;222 \rightarrow 1111 \quad\quad *;]

Tym razem zaoszczędziliśmy 5 bitów (zamiast jak przedtem 4), używając do kodowania tylko 130 bitów. Obecna liczba dwójkowych bitów na jeden trójkowy wynosi

[;130/81 \approx 1.605;]

(a nawet ciut mniej). Przypominam, że [;\log_2(3)\approx 1.585;] .

REMARK Nie ważne dla kodowania było to, że przedstawialiśmy lewą stronę powyższej tabeli jako trójkowe struny długości 3. Ważne było tylko to, że było ich 27. Chodziło o podanie 27 binarnych kodów, za pomocą których można kodować wiernie. Był to bardzo, ale to bardzo specjalny przypadek problemu, który nieźle rozwiązali Shannon i Fano, a optymalnie - Huffman.

Przy równych prawdopodobieństwach elementów źródłowego alfabetu probabilistycznego, problem zamienia się w kombinatoryczny, o prawdopodobieństwach można nie mówić - po prostu w ostatnim przypadku chcieliśmy kodować 27 symboli tak by otrzymać wierne kodowanie ich strun. Ogólniej, zamiast alfabetu o 3 symbolach, lub 27, lub innej potędze 3, możemy rozpatrywać alfabety o dowolnej liczbie symboli. Ale to już temat dla oddzielnej noty.

Tuesday, January 4, 2011

Teoria Informacji. Luźne uwagi.

Co tam, Epsilon jest blogiem, więc mogę sobie pozwolić na uwagi od Sasa do lasa.

Algorytmy kompresujące dane dzielą się na lossy i lossless, co po polsku znaczy: stratne i bezstratne. Brzydkie nazwy, fuj! Wprowadziłem ładniejsze terminy: kompresja wierna i niewierna.

Po kompresji wiernej oryginalne dane można w pełni odtworzyć. Po niewiernej na ogół nie można. Niewierna ma zachowywać to co ważne z danego punktu widzenia. Różnym punktom widzenia powinny odpowiadać różne kompresje.

Im dłużej przyglądam się swojemu cyklowi "Wstęp do Teorii Informacji. Cz. nn" (tu, w tym blogu, w Epsilonie), tym silniej i ostrzej widzę, jak i czym się różni od podejścia klasycznego. Ale czy i jak nowe jest moje podejście, to nie wiem, powinienem odnowić kontakty i popytać specjalistów lub przynajmniej ludzi o lepszej ode mnie erudycji. Więcej o różnicach poniżej.

Chociaż Claude Shannon stworzył Teorię Informacji sam jeden (chyba w 1948 roku), to pierwszy algorytm, kompresujący teksty wiernie, stworzyli niemal jednocześnie i niezależnie Shannon i Fano. Komputery były jeszcze w powijakach, a oni już stworzyli algorytmy kodujące binarnie. Ciekawe.

Pierwszy etap kodowania, to kodowanie pojedynczych symboli alfabetu probabilistycznego za pomocą skończonych strun binarnych o zmiennej długości. Samo w sobie ma to ograniczony potencjał. Ale niżej zobaczymy, że przy lekkiej interpretacji uzyskuje się jednak bardzo dużo. Ciekawe. Jedna więcej nietrudna idea, a taki zysk!

Ogólna idea polega na krótkim kodowaniu symboli o wysokiej częstotliwości występowania w losowych strunach (o wysokim prawdopodobieństwie), a więc siłą rzeczy symbolom o niskim prawdopodobieństwie trzeba wtedy przypisywać dłuższe kody binarne, by cały kod dał się odkodować. Shannon i Fano postąpili naturalnie - podzielili symbole na dwie grupy tak, by różniły się te dwie totalnym prawdopodobienstwem możliwie mało, czyli sumy prawdopodobienstw w każdej grupie powinny w miarę możliwości przybliżyć 1/2. Wtedy symbolem jeednej grupy przypisujemy jako pierwszy bit 0, a drugiej grupie 1. Potem w ramach każdej grupy operację dzielenia na dwie zbliżone pod względem totalnego prawdopodobienstwa iterujemy, otrzymując dalsze bity. Powstanie drzewo kodujące, które pozwala kodować i jednoznacznie dekodować. Zakłada się, że drzewo kodu Shannona-Fano jest z góry znane dekodującemu.

Ta dziel (w miarę po równo) i panuj popularna metoda jest bardzo naturalna, zwykły rozsądek (zwykły po czasie).

Najlepszym algorytmem kodującym pojedyncze symbole alfabetu probabilistycznego jest praktyczny i bardzo elegancki algorytm Huffmana. Najlepszy w ścisłym sensie minimalizowania współczynnika oszczędności, co Huffman ślicznie udowodnił w wyjątkowo eleganckiej pracy. (Istnieje w matematyce ogromna liczba, zatrzęsienie, wyjątkowo eleganckich prac, wyników, pojęć, ... - już taka matematyka jest, piękna i elegancka). Być może, kto wie, poświęcę algorytmowi Huffmana post lub parę. Warto go stosować jako drugą połowę algorytmu dwuczęściowego, którego pierwszą połową jest mój algorytm, który opisałem w Części 4'. Co prawda Hufmana stosowałoby się do tak specjalnego przypadku, że na pewno prościej i może lepiej zastosować zamiast Huffmana pewien algorytm, specjalny dla powstałych sytuacji, jeszcze pomyślę.

Gdy zastosujemy algorytm Shannona-Fano lub Huffmana na przykład do alfabetu probabilistycznego [;(A\ \pi);], gdzie [;A:={F\ S};] oraz [;\pi(F) := 5/6,\quad \pi(S):=1/6;], to nic ciekawego się nie otrzyma. Dla małych alfabetów algorytmy kodujące pojedyncze symbole wiele nie zdziałają. Nawet ogólniej, kłopot naprawdę polega nie na tym, że alfabet jest mały, lecz na tym, że co najmniej jeden symbol ma spore prawdopodobieństwo, co przy małej liczbie symboli jest koniecznością.

Tak naprawdę, to chodzi o kodowanie bloków (strun) o równej długości [;n;], powiedzmy strun o 8 symbolach. Każdy blok traktujemy wtedy jako jeden symbol nowego rodzaju. Wtedy każdy blok ma relatywnie małe prawdopodobieństwo. Im większa wspólna długość [;n;] tym mniejsze maksymalne prawdopodobieństwo bloku; a przy [;n;] dążącym do zera maksymalne prawdopodobieństwo bloku dąży do zera. W przypadku symboli [;F\ S;], wszystkie bloki długości 8 mają prawdopodobieństwa nie większe niż [;5/6)^8 < 1/4].

Przy długich blokach otrzymuje się lepszą kompresję, ale jest to dogodne tylko do czasu. Powstają wszelakie niewygody, fizyczność świata rzeczywistego wtrąca się do świata matematyki (z czego matematyka korzysta, rozwija się :-).

Dotąd pisałem tylko o kompresji koncepcyjnie najprostszych strun losowych, w których prawdopodobieństwo występowania symboli na różnych pozycjach zależało wyłącznie od rozkładu prawdopodobieństw w alfabecie, i od niczego więcej. W przypadku strun będących polskimi tekstami, prawdopodobieństwo wystąpienia litery lub innego znaku silnie zależy także od tego, co pojawiło się na miejscu poprzednim. Na przykład po kropce lub po przecinku prawie na pewno wystąpi odstęp lub (jeżeli w ogóle przekazujemy znak nowej linii). Dlatego w przypadku tekstów z danego języka warto brać pod uwagę prawdopodobieństwa realtywne, nie po prostu występowania znaku, lecz prawdopodobieństwa wystąpienie po innym. Czyli zamiast jednej listy prawdopodobienstw, mamy listę list, jakby listę do kwadratu, o wiele większą. Z jednej strony korzystanie z relatywnych prawdopodobieństw pozwala teksty istotnie lepiej kompresować, a z drugiej - jest to komplikacja.

itd. :-)

Monday, January 3, 2011

Wstęp do Teorii Informacji. Cz.4"

W Części 4' podałem połowę podstawowego twierdzenia Shannona o kodowaniu strun losowych, pokazując, że istnieją kodowania, których stopień oszczędności dowolnie blisko przybliża entropię używanego alfabetu losowego. W niniejszej nocie pokaże, że kodowania, średnio, lepszej oszczędności niż danej przez entropię, mieć już nie mogą.

Oprócz Części 4', warto przejrzeć przed czytaniem poniższego tekstu, lub w trakcie, także Część 4. Będę zakładał ich znajomość. Zresztą warto porównać Część 4' i 4", widzieć jak są pokrewne.

Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n>2;] będzie liczbą naturalną (według intencji raczej sporą, choć formalnie tego nie wymagam). [;A;]-strunę [;S := (a_0\ \dots\ a_{n-1});] nazywam [;(\mathbf{A}\ n^+);]-struną lub minimalnie przesyconą lub dla krótkości po prostu przesyconą [;\Leftarrow:\Rightarrow;] spełnione są dwie nierówności:

[;\iota(S) \ge n;]

[;\iota(S') < n;] dla [;S' := (a_0\ \dots\ a_{n-2});]

Zbiór wszystkich takich strun przesyconych oznaczamy symbolicznie [;\Delta(\mathbf{A}\ n);].

UWAGA 0 Zbiory [;\Delta(\mathbf{A}\ n);] oraz [;\nabla(\mathbf{A}\ n);] można słowo w słowo tak samo zdefiniować dla dowolnej liczby dodatniej [;n;] (zamiast wyłącznie dla naturalnych). Zachodzi wtedy równość:

[;\Delta(\mathbf{A}\ n) = \nabla\left(\mathbf{A}\ \,n\!+\!\mu\left(\mathbf{A}\right)\right);]

TWIERDZENIE 0 Żadna z dowolnych dwóch różnych [;(\mathbf{A}\ n^+);]-strun nie jest prefiksem drugiej.

DOWÓD Gdy prefiks właściwy pewnej struny ma informację [;n;] lub większą, to sama struna nie może być minimalnie przesycona. KONIEC DOWODU

TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun przesyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są przesycone.

DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU

TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, przesyconych A-strun są rozłączne.

DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU

TWIERDZENIE 3 Dla dowolnej struny nieskończonej [;(a_0\ a_1\ \cdots)\in A^{\mathbb{Z}_+};] istnieje dokładnie jedno [;m;] takie, że [;(a_0\ \cdots\ a_{m-1})\in\Delta(\mathbf{A}\ n);]. Innymi słowy:

[;\bigcup_{S\in\Delta(\mathbf{A}\ n)}B_S = A^{\mathbb{Z}_+};]

DOWÓD Ponieważ [;A;] jest skończone, to

[;\min_{a\in A}\iota(a) > 0;]

więc

[;\lim_{m\rightarrow \infty} \iota\left((a_0\ \dots\ a_{m-1})\right) = \infty;]
przy czym ciąg informacji prefiksów [;\iota\left((a_0\ \dots\ a_{m-1})\right));] jest rosnący. Zatem istnieje dokładnie jedno naturalne [;m;] takie, że prefiks jest przesycony. KONIEC DOWODU

Przypominam (patrz Część 4', Tw.3), że dla dowolnej A-struny skończonej [;S;] zachodzi nierówność

[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]

Wynika z niej, że

[;\pi''(B_S) \le \frac{1}{2^n};]

Stąd

TWIERDZENIE 4

[;|\Delta(\mathbf{A}\ n)| \ge 2^n;]

KONIEC DOWODU

Przypominam (patrz Część 4'), że marginesem [;\mu(\mathbf{A});] alfabetu probabilistycznego [;\mathbf{A};] nazywam maksimum informacji jego symboli. Natychmiast otrzymujemy wynik główny

TWIERDZENIE 5 Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Rozpatrzmy dowolne wierne kodowanie binarne skończonych [;A;]-strun. Wtedy dla dowolnej liczby naturalnej [;n;] istnieje przesycona A-struna [;S;] (więc spełnia warunek [;\iota(S) < n+\mu(\mathbf{A});] ), której kod ma conajmniej [;n;] bitów dwójkowych.

DOWÓD Wszystkich niepustych ciągów zer i jedynek, o długości mniejszej od [;n;], jest tylko [;2^{n}-2;]. Natomiast strun przesyconych jest co najmniej [;2^n;]. KONIEC DOWODU

Friday, December 31, 2010

Wstęp do Teorii Informacji. Cz.4'

Poniżej podam dowód pewnego podstawowego wyniku Shannona, o kompresji tekstów (strun). W wersji wyniku, którą podaję, dowód jest krótki i łatwy (i chyba elegancki) - miejsce zajmie tylko przypomnienie wstępnych definicji podstawowych. Przejście do wersji klasycznej jest intuicyjnie oczywiste, a i formalnie jest rutynowe, ale wymaga solidnej znajomości elementarnych podstaw teorii prawdopodobieństwa.

Niniejszy post jest kontynuacją Części 4, w której wprowadziłem klasyczną terminologię:

alfabet probabilistyczny [;(A\ \pi);] - zawsze zakładamy, że [;|A| > 1;], czyli że istnieją co najmniej 2 różne symbole;

[;A;]-struna (i [;A;]-blok) ;

informacja

[;\iota(a) := \log_2\left(\frac{1}{\pi(a)}\right);]

symbolu [;a;] alfabetu [;A;] ;

entropia

[;\epsilon(A\ \pi) := \sum_{a\in A} \pi(a)\cdot\log_2\left(\frac{1}{\pi(a)}\right);]

alfabetu probabilistycznego [;(A\ \pi);] ;

informacja

[;\iota(S) := \sum_{k < n} \log_2\left(\frac{1}{\pi(a_k)}\right);]

[;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ;

przestrzenie skończenie i nieskończenie wymiarowe [;A;]-strun:

[;A^n;] oraz [;A^{\mathbb{Z_+}};]

wraz z funkcją prawdopodobieństwa [;\pi'';] (patrz następne trzy punkty tej listy);

prawdopodobieństwo [;\pi''(B);] dowolnego zbioru [;B\subseteq A^n;], jako suma prawdopodobieństw [;\pi(S);] jego [;A;]-strun:

[;\pi''(B) := \sum_{S\in B} \pi(S);]

dla dowolnego [;n = 1\ 2\ \dots;]

S-kub [;B_S;]:

[;B_S := \left\{(x_0\ x_1\ \dots) : \displaystyle\forall_{k < n}\ x_k = a_k \right\} ;]

dla dowolnej skończonej [;A;]-struny [;S := (a_0 \dots\ a_{n-1});] ;

Prawdopodobieństwo [;\pi'';] w przestrzeni [;A^{\mathbb{Z_+}};]:

[;\pi''(B_S) := \pi(S);]

oraz prawdopodobieństwo [;\pi'';] dowolnego zbioru, będącego unią skóńczonej lub przeliczalnej rodziny parami rozłącznych S-kubów jest sumą prawdopodobieństw [;pi'';] S-kubów, będących składnikami unii.

Prawdopodobieństwo [;\pi''(B);], zbioru [;B;] w przestrzeni [;A^n;] lub [;A^{\mathbb{Z_+}};], można traktować jako objętość tego zbioru; przy czym objętość całej przestrzeni jest równa 1. Myślenie w terminach objętości powinno ułatwić zrozumienie i zapamiętanie wielu rozważań (chyba, że jesteś strasznym oryginałem :-).

Alfabety probabilistyczne rozważamy w kontekście strun losowych, w których symbole na każdym miejscu występują z prawdopodobieństwem danym przez alfabet probabilistyczny, przy czym symbole w różnych miejscach struny występują niezależnie od pozostałych (jak wyniki rzutów kostką lub monetą).

Powszechnym w algebrze nieprzemiennej i w logice matematycznej, a potem podstawowym dla całej informatyki, jest pojęcie złożenia dwóch strun (skończonych):

[;W := S.T;]

Dla strun [;S := (a_0\ \dots\ a_{m-1});] oraz [;T := (b_0\ \dots\ b_{n-1});], ich złożenie [;W;] definiujemy jako strunę o długości [;m+n;]:

[;W(i) := S(i);] dla [;i=0\ \dots\ m-1;]. oraz

[;W(i) := T(i-m);] dla [;i=m\ \dots\ n-1;].

Złożenie strun jest działaniem łącznym, dzięki czemu w wyrażeniach [;S.T.U;] [;Q.S.T.U;] itp. nie musimy stosować nawiasów.

Złożenie strun skończonych i skończonej z nieskończoną (w tej kolejności) rozpatruje się także w przestrzeni [;A^{\mathbb{Z}_+};]. W szczególności, dla A-struny skończonej [;S;], S-kub [;B_S;] może być równoważnie i elegancko określony jak następuje:

[;B_S := \left\{ S.T : T\in A^{\mathbb{Z}_+}\right\};]

Dla ustalonego alfabetu [;A;], skończone struny niepuste (o skończonej, dodatniej długości - innych strun dotąd w tej serii not nie rozpatrywałem, z wyjątkiem elementów przestrzeni [;A^{\mathbb{Z}_+};]) tworzą półgrupę (i to półgrupę wolną). Gdy dołączymy strunę pustą [;\emptyset;], to uzyskamy monoid (a nawet monoid wolny), w którym rolę jedności gra właśnie struna pusta.

Niech [;(A\ \pi);] będzie alfabetem probabilistycznym. Jego marginesem [;\mu(A\ \pi);] nazywam maksymalną informację jego symbolu:

[;\mu(A\ \pi) := \max_a\ \iota(a);]

Margines jest więc informacja symbolu o najmniejszym prawdopodobieństwie, więc zawsze jest równy nie mniej niż 1 (nawet jest większy niż 1, poza jedynym wyjątkiem, gdy mamy dokładnie 2 symbole, i każdy ma prawdopodobieństwo równe 1/2).

Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;n > \mu(\mathbf{A});] będzie dowolną liczbą naturalną (tak naprawdę, to obchodzą nas przede wszystkim liczby [;n;] sporo większe od marginesu). [;A;]-strunę [;S := (a_0 \dots\ a_{m-1});] nazywam [;(\mathbf{A}\ n);]-struną lub struną nasyconą (względem [;\mathbf{A};] oraz [;n;]) [;\Leftarrow:\Rightarrow;] [;S;] spełnia dwa warunki:

[;n - \mu(\mathbf{A}) < \iota(S) \le n;]

[;\iota(S') \le n-\mu(\mathbf{A});], gdzie [;S' := (a_0\ \dots\ a_{m-2});]

(Prawa nierówność w pierwszym warunku wynika z pozostałych dwóch nierówności). W kontekście jednego twierdzenia, gdy mówimy o strunach nasyconych, to cały czas mamy na myśli ustaloną liczbę naturalną [;n;], oraz ustalony alfabet propbabilistyczny. Udowodnię teraz ciąg łatwych własności strun nasyconych, prowadzący do wyniku głównego.

TWIERDZENIE 0 Żadna [;(\mathbf{A}\ n);]-struna nie jest prefiksem żadnej innej, różnej od niej [;(\mathbf{A}\ n);]-struny.

DOWÓD Prefiks właściwy struny nasyconej nie jest nasycony, gdyż ma informację nieprzekraczającą [;n-\mu(\mathbf{A});]. KONIEC DOWODU

TWIERDZENIE 1 Każda A-struna nieskończona jest jednoznacznym, nieskończonym złożeniem strun nasyconych. Każda A-struna skończona jest jednoznaczynym skończonym złożeniem strun, z których wszystkie, poza ewentualnie ostatnią (tę występująca na ostatnim miejscu po prawej), są nasycone.

DOWÓD Zbyt nudny by go prezentować. W każdym razie, jednoznaczność rozkładu wynika z Twierdzenia 0. KONIEC DOWODU

TWIERDZENIE 2 S-kuby dowolnych dwóch różnych, nasyconych A-strun są rozłączne.

DOWÓD Na mocy Twierdzenia 0, żadna z tych dwóch strun nie jest prefiksem pozostałej. Zatem rzeczywiście ich S-kuby są rozłączne. KONIEC DOWODU

TWIERDZENIE 3 Dla dowolnej A-struny skończonej [;S;] zachodzi równość

[;\pi''(B_S) = \pi(S) = \frac{1}{2^{\iota(S)}};]

DOWÓD Niech [;S := (a_0\ \dots\ a_{n-1});] Należy skorzystać z definicji informacji, i z własności logarytmu:

[;\frac{1}{2^{\iota(S)}} =
\frac{1}{2^{\sum_{k < n}\iota(a_k)}} =
\frac{1}{2^{\sum_{k < n}\log_2\left(\frac{1}{\pi(a_k)}\right)}} ;]
[;= \frac{1}{2^{\log_2\left(
\prod_{k < n}\frac{1}{\pi(a_k)}
\right)}} = \frac{1}{\prod_{k < n}\frac{1}{\pi(a_k)}} = \pi(S);]

KONIEC DOWODU

Niech [;\mathbf{A} := (A\ \pi);] będzie alfabetem probabilistycznym. Niech [;\nabla(\mathbf{A}\ n);] będzie zbiorem wszystkich [;(\mathbf{A}\ n);]-strun (czyli strun nasyconych). Jest ich nie więcej niż [;2^n;], co - w połączeniu z Twierdzeniem 1 jest głównym wynikiem tej noty:

TWIERDZENIE 4

[;|\nabla(\mathbf{A}\ n)| \le 2^n;]

dla każdego naturalnego [;n \ge \mu(\mathbf{A});].

DOWÓD Wiemy z poprzedniego twierdzenia (Tw. 3), że [;\pi''(B_S) \ge 2^{-n};] dla dowolnej struny nasyconej [;S;]. Ponieważ S-kuby są rozłączne, oraz [;\pi''(A^{\mathbb{Z}_+}) = 1;], to takich S-kubów jest nie więcej niż [;2^n;]. KONIEC DOWODU

Widzimy, że struny nasycone [;S;] możemy kodować za pomocą bloków zero-jedynkowych, długości [;n;], czyli - przy [;n;] sporo większym od marginesu [;\mu(\mathbf{A});] - co najwyżej nieznacznie dłuższych od informacji [;\iota(S);]. Niech [;\delta > 0;] będzie dowolną, dodatnią liczbą rzeczywistą (chodzi o dowolnie małe). Gdy ustalimy

[;n > \delta + \mu\cdot(1+\delta);]

to liczba bitów dwójkowych kodu będzie tylko nieznacznie przekraczać liczbę bitów informacji zawartej w źródłowej strunie nasyconej:

[;\frac{n}{\iota(S)} < 1 +\delta;]

Niech [;\delta\ n;] będą jak powyżej. Gdy ustalimy dostatecznie wielką liczbę naturalną [;M;], to A-struny [;T;] długości co najmniej [;M;] będą złożeniem długiego ciągu strun nasyconych, zakończonych ewentualnie struną nienasyconą (a te są relatywnie krótkie, bo marginesowe). Struny nasycone zakodują się za pomocą nie więcej niż [;(1+\delta');] dwójkowego bitu per bit informacji, gdzie [\delta';] jest stałą spełniającą:

[;0 < \delta' < \delta;]

Gdyby nie było nienasyconej końcówki, to cała struna [;T;] zakodowałaby się za pomocą średnio [;1+\delta';] dwójkowego bitu per bit informacji. Ewentualna nienasycona końcówka może to nieco zepsuć, ale dla dostatecznie dużego [;M;] wciąż będzie prawdziwe nieco gorsze oszacowanie [;1+\delta;] dwójkowego bitu per bit informacji.

UWAGA Istnienie [;\delta';] wynika ze skończoności zbioru \nabla(\mathbf{A}\ n) wszystkich strun nasyconych [;S;]. Możemy przyjąć

[;\delta' =
\max_{S\in\nabla(\mathbf{A}\ n)}\ \left(\frac{n}{\iota(S)}\ -\ 1\right);]

Nieco już praktyczniejszą kwestią jest takie dobranie [;\delta';] by [;M;] mogło być jak najmniejsze.

W tym odcinku nie chciałem Was nużyć zbyt pedantycznymi, rutynowymi, epsilon-delta ścisłymi dowodami.

W całej nocie moglibyśmy zastąpić [;2;], w roli podstawy logarytmu i potęgowania, przez dowolną liczbę naturalną [;b > 1;] - Hugo Steinhaus powiedziałby, że 2 jest zmienna :-). Chociaż takie uogólnienie jest automatyczne, to i tak jest bardzo wartościowe. Wynika z niego na przykład to, że przy ustalonej liczbie [;\alpha := |A|;] symboli alfabetu, maksuymalną entropię alfabetu probabilistycznego otrzymuje się przy jednorodnym rozkładzie prawdopodobieństw symboli, gdy

[;\pi(a) = \frac{1}{\alpha};]

dla każdego [;a\in A;]. Pomyślcie o tym :-)

Thursday, December 30, 2010

Wstęp do Teorii Informacji. Cz.4

Przedstawię w niniejszej nocie jeden z wyników Clauda Shannona, o tym że można długie teksty kompresować, przybliżając się dowolnie blisko do ograniczenia podanego przez Shannona. Moje podejście będzie niestandardowe, a może nawet oryginalne - mała na to ostatnie szansa, bo literatura jest ogromna, a jej nie znam.

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')

Monday, December 27, 2010

Wstęp do Teorii Informacji. Cz.3

Część 1 sugerowała, z pewnym uzasadnieniem, że losowe struny (teksty), złożone z symboli 0 1, każdy występujący na dowolnym miejscu z prawdopodobieństwem 1/2, niezależnie od pozostałych (jak Orzeł i Reszka przy rzutach monetą), nie dają się kompresować; oznacza to, że nie istnieje algorytm, który by wiernie kodował takie struny, zastępując je przez inne struny 0-1, o mniejszej długości oczekiwanej.

Część 2 poświęcona była strunom losowym, złożonych z symboli F S, w których każde wystąpienie symbolu było niezależne od pozostałych, ale tym razem prawdopodobieńtwa wynosiły 1/6 i 5/6. Takie struny (gdy nie są zbyt krótkie) dają się skompresować średnio lepiej niż 2/3 razy niż w przypadku prawdopodobieństw 1/2:1/2. Czyli jeden symbol takiej informacji jest wart mniej niż 2/3 symbolu 0-1 struny losowej o równych prawdopodobieństwach dla 0 i 1.

Poniżej zajmiemy się łatwiejszym zadaniem. Porównamy kanał ternarny, przesyłający bezbłędnie symbole 0 1 2, z bezbłędnym binarnym, przesyłającym symbole 0 1. Takie porównanie może być ważne dla biznesu. Kanał trójkowy jest droższy, ale efektywniejszy. Co opłaca się lepiej, mieć dwa kanały trójkowe, czy trzy dwójkowe? Odpowiedź może zależeć od wielu czynników, ale między innymi od porównania poniżej.

Powiedzmy, że z ternarnego kanału otrzymujemy ciąg niezależnych symboli 0 1 2, z równymi prawdopodobieństwami 1/3. Mamy go przesłać w świat, a raczej informację, używając kanał binarny. Każdy trójkowy bit możemy zastąpić przez dwa bity dwójkowe jak następuje:

0 ➔ 00

1 ➔ 01

2 ➔ 10

(Gdy wyrazy kodu są jednakowej długości, to oczywiście kod się dekoduje, i to łatwo). Widzimy, że trójkowy bit jest wart nie więcej niż dwa dwójkowe (z pewnością mniej, bo nie wykorzystaliśmy 11, ale o tym później).

I na odwrót, gdy otrzymujemy informację w postaci bitów dwójkowych 0 1, a mamy ją dalej przekazać kanałem trójkowym, to każdy symbol binarny 0 1 zastępujemy tym samym 0 lub 1, ale traktowanym jako bit trójkowy. Zatem bit dwójkowy jest nie więcej wart niż jeden bit trójkowy (zobaczymy, że wyraźnie mniej).

Nie chcę urazić Meksykańczyków, ale mnie goła takila nie smakuje. Drugi i dalsze kieliszki piję już jednak z lodem i czym tak jeszcze - wódce nigdy bym tak nie ubliżył (chyba, że w gościach, to trudno, gdakam w Rzymie jak starożytni). Wszystko jedno takila pomaga mi nie przejmować się zbytnio edytorem, pije się chropowato, ale pisze się gładziej. (Dzieci, nie czytać tego. Banach powiedział, że matematyka nie jest dla dzieci.) Co do jakości mojej noty? Cóż, to się nazywa po angielsku trade-off (coś za coś). W moim subiektywnym odczuciu, moja (c)nota tylko zyskuje.

Wykorzystajmy nierówności typu

[;3^k < 2^n;]

oraz

[;3^k > 2^n;]

dla porównania kanału trójkowego z dwójkowym. Na przykład:

[;3 < 2^2;]

[;3^3 < 2^5;]

[;3^5 < 2^8;]

Pierwszą nierówność już wykorzystaliśmy. Powiedziała nam, że trójkowy bit jest wart co najwyżej dwa bity dwójkowe. Następna nierówność mówi nam że co najwyżej 5/3, a ostatnia, że 8/5 lub mniej. Ogólnie nierówność [;3^k < 2^n;] mówi nam, że bit trójkowy jest wart co najwyżej [;n/k;] bitu dwójkowego. Rzeczywiście, każdą z [;3^k;] strun trójkowych, długości [;k;] możemy zastąpić przez dwójkową, o długości [;n;], przy czym różne przez różne.

Podobnie nierówności:

[;3 > 2;]

[;3^2 > 2^3;]

[;3^{12} > 2^{19};]

mówią nam kolejno, że bit trójkowy jest wart co najmniej jednego dwójkowego; następna nierówność - że co najmniej półtora czyli 3/2 dwójkowego; a ostatnia, że nawet 19/12 lub więcej. Otrzymaliśmy łącznie nierówność:

(19/12)*info(bit₂) < info(bit₃) < (8/5)*info(bit₂)

Można też porównanie prowadzić w drugą stronę, gdy bity dwójkowe tłumaczymy na trójkowe:

(5/8)*info(bit₃) < info(bit₂) < (12/19)*info(bit₃)

Prosta teoria liczb mówi nam, że istnieją coraz większe wykładniki [;k'\ k''\ n'\ n'';] takie, że:

[;2^{k'} < 3^{n'};]

[;2^{k''} > 3^{n''};]

oraz oba ułamki po bokach następujących (oczywiście prawdziwych) nierówności:

[;\frac{k'}{n'} < \log_2(3) < \frac{k''}{n''};]

przybliżają [;\log_2(3);] z dowolną dokładnością. Ta obserwacja daje dobry powód, żeby uważać trójkowy bit informacji wart [;\log_2(3);] dwójkowego bitu informacji. Dalsze twierdzenia pokażą, że to jest głęboko uzasadniona opinia. (Podobnie można uważać, że jeden bit dwójkowy jest wart [;\log_3(2);] bitu trójkowego; ze szkoły wiecie, że

[;\log_3(2) = \frac{1}{\log_2(3)};]

Wszystko dzieje się harmonijnie.)

Chociaż polskie wychowanie burzy się przed tym co jako naukowiec muszę obiektywnie przyznać, wartość kolejnych kieliszków takili (czy jak tam to się spelluje), po pięciu maleje eksponencjalnie (za to smak się po trochu poprawia). Jednak kończę tę notę, jakże niechętnie, z innego powodu. Muszę wkrótce lecieć (takila itp zmiękcza "muszę", ale obowiązek, to obowiązek). Nie chcę się spieszyć z pisaniem przesadnie, przerwać coś w połowie, lub pisać na siłę, i wszystko zapaprać. Zresztą butelka wyschła. Z lodem i itp, jak wiecie, to nic nie jest. 3/4L. Przysięgam, że nie była pełna. Szkoda, że nie była pełna. Żal. Koniec takilowych zwierzeń.

Friday, December 24, 2010

Wstęp do Teorii Informacji. Cz.2

Metauwaga: końcowe uwagi są istotną częścią niniejszej noty. Kto temat poznaje z tej noty, powinien przeczytać także uwagi końcowe.

Jak w poprzedniej Części 1, rozpatruję kanał binarny, czyli przyjmujący i przekazujący na zewnątrz sygnały 0 1. Zakładam, że bezbłędnie co kanał otrzyma to przekaże.

Tym razem chcemy przekazać ciąg wyników rzutów kostką, przy czym obchodzi nas tylko, czy wypadło 6. Oznaczając wynik 6 przez "S" (sukces), a pozostałą możliwość (od 1 do 5) przez F, z każdym ciągiem rzutów kostką możemy związać ciąg liter S i F. Jak przekazać te informację, jak ją kodować?

Mógłby ktoś machnąć ręką na litery, by po prostu przekazywać wyniki rzutów, na przykład

2 6 1 1 4 3 4 3 5 6 3 3 ...

By tak dosłownie postąpić, to potrzebny byłby kanał przekazujący bity szóstkowe 1 2 3 4 5 6. Taki kanał jest bardziej złożony od binarnego. Byłaby w takim postępowaniu marnacja, gdyż interesują nas tylko wygrane:

F S F F F F F F F S F F ...

Więc możemy użyć kanału binarnego, wysyłając tyle samo sygnałów, ale prostszych (0 1), gdzie 0 kodowałoby F, oraz 1 kodowałoby S. Wtedy powyższy ciąg rzutów kostki byłby zakodowany w sposób zredukowany, ale adekwatny dla naszego zadania:

0 1 0 0 0 0 0 0 0 1 0 0 ...

Powiedzmy, że za każdym razem wysyłamy 12 milionów wyników rzutów kostki (może chodzi o zachowanie jakiejś siatki krystalicznej, a nie dosłownie o kostkę do Chińczyka). Czy rzeczywiście musimy wysyłać aż tyle sygnałów? W przypadku rzutów monetą podobna procedura była optymalna. Zachodzi jednak istotna różnica. W przypadku monety, szansa zarówno Orła jak i Reszki była równa 1/2. Tym razem szansa wygranej S jest 1/6, a przegranej F aż 5/6. Nie widać jak z tego skorzystać bezpośrednio, gdy mamy przecież za każdym razem możliwe dwa różne wyniki (F lub S) oraz dwa różne sygnały do dyspozycji (0 oraz 1). Postęp uzyskamy kodując nie pojedyncze znaki F i S, lecz na przykład ich trójki, choćby tak:

FFF → 0

FFS → 100

FSF → 101

SFF → 110

FSS → 11100

SFS → 11101

SSF → 11110

SSS → 11111

Dla ilustracji zapiszmy wcześniejszy ciąg FSFFFFFFFSFF..., grupując symbole po trzy:

FSF FFF FFF SFF ...

Ciąg ten nowa metoda zakoduje tak (dodaję odstępy by było lepiej widać kodowanie):

101 0 0 110 ...

czyli zamiast 12 sygnałów przesyłanych wcześniejszą metodą, obecna przesyła tylko 8. Popatrzmy teraz jak jest ogólnie, to znaczy policzmy oczekiwaną długość przesyłki. Uczyńmy to najpierw dla przesyłki XYZ ciągu trzech symboli F S. Prawdopodobieństwo ciągu XYZ (gdzie każde X Y Z oznacza albo S albo F) dane jest wzorem:

[;p(XY\!Z) := \left(\frac{1}{6}\right)^{3-f}\cdot \left(\frac{5}{6}\right)^f = \frac{5^f}{6^3};]

gdzie [;f;] jest liczbą wystąpień F w ciągu XYZ. Grupując ciągi według [;f;] równego 0 1 2 lub 3, otrzymujemy następujące wyrażenie dla długości oczekiwanej kodu ciągu długości 3:

[;1\cdot 5\cdot\frac{1}{6^3} + 3\cdot 5\cdot\frac{5}{6^3} + 3\cdot 3\cdot\frac{5^2}{6^3} + 1\cdot 1\cdot\frac{5^3}{6^3} = \frac{215}{108};]

Każdy ciąg XYZ trzech liter F S możemy zakodować przez średnio niecałe dwie cyfry 0 1. Zatem ciąg 12 milionów liter F S możemy zakodować przez średnio mniej niż 8 milionów znaków 0 1. Jest tak dlatego, że S występuje średnio 5 razy rzadziej niż F. Możemy odtąd uważać, że informacja zawarta w strunie 12 milionów znaków F S jest średnio warta mniej niż zapis ciągu 8 milionów znaków 0 1.

Lepiej oszczędność kodowania liczyć nie w przeliczeniu na 3 lub 12 milionów znaków tekstu źródłowego, lecz dla jednego znaku. Czyli współczynnik oszczędności (kompresji) naszego kodowania (dla tekstów [;A;], których długość [;|A|;] jest podzielna przez 3) wynosi:

[;\frac{\frac{215}{108}}{3} = \frac{215}{324} < 2/3;]

Współczynnik oszczędności pozwala porównywać wydajność kodowania tekstów o różnej długości - im niższy współczynnik, tym wydajniejsze kodowanie. Zrobiliśmy kolejny krok w kierunku zrozumienia informacji w sensie Shannona.

UWAGA 0 Żaden z powyższych 8 wyrazów kodu:

0 100 101 110 11100 11101 11110 11111

nie jest prefiksem (czyli odcinkiem początkowym) żadnego innego wyrazu.

UWAGA 1 Dzięki własności z Uwagi 0, nasze kodowanie jest wierne, czyli daje się jednoznacznie odkodować - gdy teksty źródłowe [;A\ B;] są różne, to ich zakodowane wersje [;K(A)\ K(B);] też są różne:

[;A\ne B \Rightarrow K(A)\ne K(B);]

W przeciwnym razie, gdy [;K(A) = K(B);], nie moglibyśmy zdecydować, czy tekstem źródłowym było [;A;] czy [;B;], lub może jeszcze co innego.

W praktyce wierność to za mało. Potrzebny jest algorytm (i to wydajny), który potrafi obliczyć [;A;], gdy dane jest [;K(A);]. Właśnie taką pożądaną, wygodną sytuację mamy, gdy żaden wyraz kodu nie jest prefiksem innego wyrazu kodu.

UWAGA 2 Występuje pewna drobna nieregularność przy naszym kodowaniu odcinkami złóżonych z trzech znaków F S. Co będzie, gdy długość tekstu żródłowego (czyli liczba występujących w nim znaków F S) nie jest podzielna przez 3? Powiedzmy, że tekst żródłowy miał 12 milionów i jeden znak. Rozwiązanie jest proste: przedłużamy tekst o znak lub dwa znaki F, tak by jego długość stała się podzielna przez 3. W przypadku 12 milionów i jednego znaku, tekst przedłużymy o strunę FF. Współczynnik oszczędności kodowania

[;\frac{|K(A)|}{|A|};]

dalej w mianowniku ma 12000001, a nie 12000003. Więc przeciętna oszczędność kodowania w przypadku przedłużonych tekstów jest nieco gorsza niż dla tekstów, których długość jest okrągłą wielokrotnością 3. Przy długich tekstach nie ma to większego znaczenia (nadwyżka współczynnika oszczędności dąży do zera, gdy długość źródłowego tekstu dąży do nieskończoności). Tak działa oddech nieskończoności. Pozwala zaniedbywać drobne komplikacje.