Teoria informacji/TI Wykład 1

Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte.

(Napisałem ten list trochę dłuższy, gdyż nie miałem czasu napisać go krócej).

Blaise Pascal, Lettres provinciales, 1657

Notacja, co to takiego?

Na początek prosty eksperyment: Ktoś wymyśla słowo, a kto inny ma za zadanie je odgadnąć, zgadując literę po literze. Zwykle udaje się to znacznie szybciej niż by to wynikało z pesymistycznego oszacowania. Czy jednak będzie to równie łatwe w przypadku odgadywania liczby? Zauważmy że w przeciwieństwie do słów w języku naturalnym, liczby całkowite w systemie dziesiętnym (czy ogólnie k-arnym, dla k > 1) są „ciasno upakowane”. Mianowicie dowolny ciąg znaków ze zbioru {0, 1, …, 9} przedstawia jakąś liczbę (jeśli zignorujemy początkowe zera), podczas gdy bardzo niewiele ciągów utworzonych z liter {a, b, …, z} jest sensownymi słowami. Wynika to między innymi z tego, że nasze „algorytmy” do komunikacji za pomocą słów wymagają znacznie więcej redundancji niż te do operowania liczbami. Tę redundancję szczególnie widać, gdy jest ona wprowadzana celowo:

Przykład: Wypełniając czek wpisujemy kwotę zarówno przy pomocy liczb, jak i słownie. Zajmuje to oczywiście znacznie więcej miejsca, ale dzięki temu nie musimy obawiać się że jakaś literówka zmieni wartość wpisanej kwoty. Podobnie postępujemy przekazując przez telefon trudne słowo, na przykład, aby poinformować, jak nazywa się stolica Gruzji, mówimy: T jak Teresa, B jak Barbara, I jak Iwona, L jak Lucyna, I jak Iwona, S jak Stanisław, I jak Iwona (międzynarodowym standardem radiowców jest tzw. alfabet fonetyczny: Alpha Bravo Charlie Delta... Yankee Zulu).

Teoria informacji charakteryzuje w sposób matematyczny zapis, przesyłanie i odtwarzanie informacji. Dąży przy tym do pogodzenia dwóch przeciwstawnych celów:

• zapisywania wiadomości jak najzwięźlej
• chronienia wiadomości przed przekłamaniami podczas transmisji.

Zacznijmy od prostego pytania. Czy istnieją wiadomości, których nie da się zapisać zwięźlej? Wiadomość może być na przykład liczbą naturalną. Liczby naturalne można na wiele sposobów zapisać w języku polskim, na przykład dwadzieścia pięć, najmniejsza liczba doskonała, rok bitwy pod Grunwaldem itp. Jeśli jednak spróbujemy objąć wszystkie te sposoby „w ogólności”, natrafimy na słynny paradoks Berry'ego (podany przez B.Russela):

Niech n będzie najmniejszą liczbą naturalną której nie da się zdefiniować w języku polskim za pomocą mniej niż dwudziestu pięciu słów.

Ale przecież właśnie zdefiniowaliśmy tę liczbę - za pomocą powyższego zdania!

Istotne jest zatem prawidłowe zdefiniowanie notacji, która służy nam do definiowania liczb. Aby uniknąć paradoksów takich jak wyżej, notacja nie może być częścią badanego obiektu. Musi być czymś zewnętrznym, nadanym w celu rozróżniania pomiędzy obiektami.

Definicja [Notacja]

Notacją dla S nazywamy dowolną różnowartościową funkcję $\alpha :S\to {\mathrm{\Sigma }}^{*}$ gdzie $\mathrm{\Sigma }$ jest skończonym alfabetem.

Fakt

Jeśli $|S|=m\ge 1$ i $|\mathrm{\Sigma }|=r\ge 2$ to dla pewnego $s\in S$ zachodzi:

$|\alpha (s)|\ge \lfloor lo{g}_{r}m\rfloor$

Dowód: Ciągów znaków z $\mathrm{\Sigma }$ o długości mniejszej niż k jest:

$1+r+r^2+\dots +r^{k-1}=\frac{r^k-1}{r-1}<r^k$

Podstawiając $k=\lfloor lo{g}_{r}m\rfloor$, stwierdzamy że nie ma wystarczająco wiele ciągów krótszych niż k do oznaczenia wszystkich elementów S. QED.

Wniosek

Jeśli $\alpha :N\to {\mathrm{\Sigma }}^{*}$ jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n musi zajść: $\alpha (n)>\lfloor lo{g}_{r}n\rfloor$.

Dowód: Wybierzmy m takie że $\lfloor lo{g}_{r}m\rfloor >|\alpha (0)|$. Z powyższego Faktu, dla pewnego $i_0\in \{0,1,\dots ,m-1\}$ mamy $|\alpha (i_0)|\ge \lfloor lo{g}_{r}m\rfloor >\lfloor lo{g}_r{i}_0\rfloor$. Z tego wynika również że $i_0>0$.

Wybierzmy teraz m’ takie że $\lfloor lo{g}_r{m}^{\prime }\rfloor >|a(i_0)|$. Znów musi istnieć $i_1\in \{0,1,\dots ,m^{\prime }-1\}$ takie że $|a(i_1)|\ge \lfloor lo{g}_r{m}^{\prime }\rfloor >\lfloor lo{g}_r{i}_1\rfloor$. Analogicznie $i_1>i_0$. I tak dalej. QED.

Jako zastosowanie, możemy podać teorioinformacyjny dowód znanego faktu:

Fakt (Euklides)

Istnieje nieskończenie wiele liczb pierwszych.

Dowód: Załóżmy przeciwnie, że istnieje tylko M liczb pierwszych: $p_1,p_2,\dots ,p_M$. Wprowadzamy notację $\alpha :\mathbb{\mathbb{N}}\to \{0,1,\mathrm{\#}{\}}^{*}$ w następujący sposób: Dla $n=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_M^{{\beta }_M}$ niech

$\alpha (n)=bin({\beta }_1)\mathrm{\#}bin({\beta }_2)\mathrm{\#}\dots \mathrm{\#}bin({\beta }_M)$

gdzie $bin(\beta )$ jest zwykłym zapisem binarnym liczby $\beta$ (a więc $|bin(\beta )|\le 1+{\log }_2\beta$).

Ponieważ $2^{{\beta }_i}\le p_i^{{\beta }_i}\le n$, mamy ${\beta }_i\le lo{g}_{2}n$, dla wszystkich i. A zatem

$|\alpha (n)|\le M(1+{\log }_2{\log }_{2}n)$

dla wszystkich n, co oczywiście przeczy twierdzeniu że dla nieskończenie wielu n $|a(n)|\ge {\log }_{3}n$. QED.

Kody

Niektóre własności notacji mają szczególne znaczenie dla ich praktycznego zastosowania. Przyjrzyjmy się na przykład co się dzieje jeśli w naturalny sposób rozszerzymy notację $\phi :S\to {\mathrm{\Sigma }}^{*}$ do morfizmu $\hat{\phi }:S^{*}\to {\mathrm{\Sigma }}^{*}$:

$\hat{\phi }(s_1\dots s_i)=\phi (s_1)\phi (s_2)\dots \phi (s_i)$

Mając dany wynikowy ciąg znaków, kluczowe znaczenie ma czy potrafimy odtworzyć jednoznacznie ciąg argumentów.

Definicja [Kod]

Odwzorowanie $\phi :S\to {\mathrm{\Sigma }}^{*}$ dla skończonego niepustego zbioru S jest kodem, jeśli jego naturalne rozszerzenie do morfizmu $\hat{\phi }$ jest różnowartościowe. Mówimy że kod jest bezprefiksowy jeśli dodatkowo $\hat{\phi }(s)\le ̸\hat{\phi }(s^{\prime })$ dla $s\ne s^{\prime }$.

Jak widać własność bezprefiksowości zależy wyłącznie od postaci zbioru $\phi (S)$. Ponadto dla każdego kodu $\epsilon \in ̸\phi (S)$.

Łatwo zauważyć że każdy zbiór bezprefiksowy jest kodem. Istnieją oczywiście kody które nie są bezprefiksowe (np. dla $\phi (S)=\{aa,baa,ba\}$), a nie każda notacja jest kodem (np. dla $\phi (S)=\{a,ab,ba\}$).

W dalszej części będziemy omijać daszek i utożsamiać $\hat{\phi }$ z $\phi$.

Aby kodować zbiór S o m elementach za pomocą alfabetu $\mathrm{\Sigma }$ o r elementach (dla $m,r\ge 2$), wystarczy oczywiście używać ciągów długości $\lceil {\log }_{r}m\rceil$. Wtedy $|\phi (w)|\le |w|\cdot \lceil {\log }_{r}m\rceil$, dla dowolnego $w\in S^{*}$.

Czasem możemy jednak wymyśleć bardziej efektywne kodowanie. Jeśli wiemy że jakieś obiekty z S pojawiają się częściej, możemy im przyporządkować krótsze ciągi znaków. W ten sposób średnio możemy uzyskać mniejsze $|\phi (w)|$.

Bliską analogią jest tu Gra w 20 pytań. W tej grze jedna osoba wymyśla obiekt o (w domyśle z jakiegoś dużego zbioru możliwości S), a druga osoba stara się zgadnąć jaki to obiekt przez zadawanie pytań (co najwyżej 20), na które odpowiedzą może być tylko tak lub nie. Tym samym pytania są tak naprawdę postaci $o\in S^{\prime }$?, gdzie $S^{\prime }\subseteq S$.

Łatwo zauważyć że $\lceil {\log }_2|S|\rceil$ pytań wystarczy do zidentyfikowania dowolnego obiektu w S. Czy da się to zrobić lepiej? W ogólności oczywiście nie. Dowolną strategię zadawania pytań możemy sobie wyobrazić jako drzewo binarne, z pytaniem w każdym wierzchołku i rozwiązaniami w liściach. Jeśli liści jest $2^k$, to drzewo musi oczywiście mieć głębokość co najmniej k. Jednak jeśli niektóre rozwiązania są bardziej prawdopodobne niż inne, możemy zmniejszyć oczekiwaną liczbę pytań. (Faktycznie dopiero taka wersja tej gry jest interesująca.)

Zapiszmy to formalnie. Drzewem nad zbiorem X (albo krócej 'X-drzewem'), będziemy nazywać dowolny niepusty zbiór $T\subseteq X^{*}$ zamknięty na operację brania prefiksu. Relację bycia prefiksem będziemy oznaczać przez $\le$. W X-drzewie dowolny element w jest węzłem rzędu |w|, $\epsilon$ jest korzeniem, $\le$-maksymalne węzły są liśćmi.

Dodatkowo będziemy posługiwać się następującymi pojęciami: dla dowolnego $w\in T$, $x\in X$ i $v\in X^{*}$:

• wx jest bezpośrednim następnikiem (lub dzieckiem) w
• wv jest poniżej w
• zbiór $T_w=\{v:wv\in T\}$ nazywamy poddrzewem indukowanym przez w

Korzystając z tych definicji, możemy powiedzieć że dowolny bezprefiksowy kod $\phi :S\to {\mathrm{\Sigma }}^{*}$ indukuje drzewo nad $\mathrm{\Sigma }$: :$T_{\phi }=\{w:\mathrm{\exists }s:w\le \phi (s)\}$. W drugą stronę, dowolne drzewo $T\subset {\mathrm{\Sigma }}^{*}$ z |S| liśćmi indukuje bezprefiksowy kod nad S (z dokładnością do permutacji elementów zbioru S).

Jak wspominaliśmy wcześniej, naszym zadaniem jest optymalizacja długości kodu, jednocześnie zabezpieczając się na przekłamania w czasie transmisji. Pierwszym krokiem będzie sprawdzenie jak krótkie mogą być długości słów kodowych.

Dla danego kodu $\phi :S\to {\mathrm{\Sigma }}^{*}$, niech $|\phi |:S\to \mathbb{\mathbb{N}}$ określa funkcję długości, zdefiniowaną jako $|\phi |(s)=|\phi (s)|$.

Twierdzenie [Nierówność Krafta]

Niech $2\le |S|<\mathrm{\infty }$ i niech $|\mathrm{\Sigma }|=r$. Funkcja $\ell :S\to \mathbb{\mathbb{N}}$ jest funkcją długości ($\ell =|\phi |$) dla pewnego bezprefiksowego kodu $\phi :S\to {\mathrm{\Sigma }}^{*}$ wtedy i tylko wtedy gdy:

$\sum _{s\in S}\frac{1}{r^{\ell (s)}}\le 1.$

Dowód:

$\Rightarrow$ Jeśli wszystkie słowa $\phi (S)$ mają tą samą długość k, to uwzględniając różnowartościowość $\phi$ dostajemy $\sum _{s\in S}\frac{1}{r^{|\phi (s)|}}\le \frac{r^k}{r^k}=1.$

Jeśli teraz mamy słowa różnej długości, to oznaczmy przez k maksymalną długość $\phi (s)$. Następnie dla każdego s mierzymy długość jego kodu $|\phi (s)|=i$ i definiujemy

$P_s=\{\phi (s)v:v\in {\mathrm{\Sigma }}^{k-i}\}$

(czyli zbiór wszystkich liści na poziomie k poniżej $\phi (s)$ w pełnym $\mathrm{\Sigma }$-drzewie). Łatwo teraz zauważyć że podmienienie $\phi (s)$ na cały zbiór $P_s$ nie zmieni sumy:

$\sum _{w\in P_s}\frac{1}{r^{|w|}}=\frac{r^{k-i}}{r^k}=\frac{1}{r^i}$,

a zbiory $P_s$,$P_{s^{\prime }}$ są parami rozłączne. Tym samym

$\sum _{s\in S}\frac{1}{r^{|\phi (s)|}}=\sum _{s\in S}\sum _{w\in P_s}\frac{1}{r^{|w|}}\le \frac{r^k}{r^k}=1$

$\Leftarrow$ Posortujmy elementy zbioru S względem rosnącej długości ich kodów $\ell (s)$, tak że $\ell (s_1)\le \dots \le \ell (s_m)$. Indukcyjnie dla $i=0,1,\dots ,m-1$ będziemy definiować $\phi (s_{i+1})$ jako leksykograficznie pierwsze słowo długości $\ell (s_{i+1})$ które nie jest porównywalne z żadnym ze słów $\phi (s_1),\dots ,\phi (s_i)$ (względem porządku prefiksowego). Jedyne co musimy pokazać to że takie słowo zawsze istnieje. Tak jak w poprzednim przypadku, oznaczmy przez $P_{s_j}$ zbiór wszystkich węzłów rzędu $\ell (s_{i+1})$ poniżej $\phi (s_j)$. Łatwo sprawdzić że $|P_{s_j}|=r^{\ell (i+1)-\ell (j)}$. Warunkiem koniecznym i wystarczającym do istnienia szukanego wierzchołka jest

$r^{\ell (i+1)-\ell (1)}+r^{\ell (i+1)-\ell (2)}+\dots +r^{\ell (i+1)-\ell (i)}<r^{\ell (i+1)}$

co można zapisać jako

$\frac{1}{r^{\ell (1)}}+\frac{1}{r^{\ell (2)}}+\dots +\frac{1}{r^{\ell (i)}}<1$

To z kolej jest spełnione na mocy założenia dla każdego $i<m$. QED

Jeśli kod nie jest bezprefiksowy, nierówność Krafta wciąż jest spełniona, co można pokazać za pomocą sprytnej techniki.

Twierdzenie (Mcmillan)

Dla dowolnego kodu $\phi :S\to {\mathrm{\Sigma }}^{*}$ istnieje bezprefiksowy kod ${\phi }^{\prime }$ dla którego $|\phi |=|{\phi }^{\prime }|$

Dowód: Przypadek $|S|=1$ jest trywialny. Dla $|S|\ge 2$ musi zachodzić również $r=|\mathrm{\Sigma }|\ge 2$. Wystarczy wtedy pokazać że $\phi$ spełnia nierówność Krafta. Wprowadźmy oznaczenie $K=\sum _{s\in S}\frac{1}{r^{|\phi (s)|}}$ i załóżmy że ta nierówność nie jest spełniona, czyli $K>1$. Niech ${M}{i}{n}=\min \{|\phi (s)|:s\in S\}$, ${M}{a}{x}=\max \{|\phi (s)|:s\in S\}$. Rozważmy teraz

$K^n={\left(\sum _{s\in S}\frac{1}{r^{|\phi (s)|}}\right)}^n=\sum _{i={M}{i}{n}\cdot n}^{{M}{a}{x}\cdot n}\frac{N_{n,i}}{r^i}$

Gdzie $N_{n,i}$ jest liczbą sekwencji $q_1,\dots ,q_n\in S^n$ takich że $i=|\phi (q_1)|+\dots +|\phi (q_n)|=|\phi (q_1\dots q_n)|$. Z warunku że $\phi$ jest kodem, wynika że każda sekwencja odpowiada innemu słowu długości i, a więc takich sekwencji jest nie więcej niż słów.

$\frac{N_{n,i}}{r^i}\le 1$

Stąd otrzymujemy

$K^n\le ({M}{a}{x}-{M}{i}{n})\cdot n+1$

co dla wystarczająco dużego n musi być fałszem, ponieważ funkcja wykładnicza rośnie szybciej niż liniowa. W konsekwencji mamy $K\le 1$. QED.