powrót
kopciuszek powróciła
pod miotłę do macocha
użera się z jego ogłuszającymi
od siedmiu boleści muzykantami
pod kiecką rozsypują się
niebieskie majtki
i nucą
jestem pół naukowa
i w pełni kulturalna
buzuje mi w zadku
panuję nad słowami
nikt nie wie że przed laty
tańczyłam z królewiczem na balu
on źle użył swe szelki
a ja zgubiłam pantofelki
wh
2011-02-05
Saturday, February 5, 2011
Thursday, January 27, 2011
Węzły i linki. Cz. 0 (Wstęp)
Wyobraźmy sobie zawieszony w powietrzu (lub pod wodą) elastyczny sznurek, którego końce są szczepione. Sznurek może być niemiłosiernie zaplątany. Gdy wodzimy po nim okiem, to widzimy jeden po drugim zakrzywiony odcinek sznurka, który na moment chowa się pod innym, itd. I te łuki składają się na cały sznurek. Czy da się sznurek tak rozplątać, żeby utworzył na koniec okrąg? Przy rozplątywaniu nie wolno rwać go, można tylko przemieszczać, można rozciągać i kurczyć. Tych łuków w każdym momencie ma być tylko skończona liczba, ale problem i tak jest trudny (ba, jest TRUDNY!!!).
Ogólniej, można wyobrazić sobie dwa takie poplątane kłębki. Czy da się jeden z nich tak przemieścić i zdeformować (znowu nie wolno rozrywać), by na koniec oba wyglądały tak samo, by się różniły tylko o przesunięcie równoległe (gdy jeden ze sznurków usuniemy, a drugim będziemy będziemy manipulować, to na koniec ma zająć miejsce tego usuniętego, ale dokładnie tak jakbyśmy widzieli ten poprzedni).
Sznurek, ze szczepionymi końcami, zafiksowany w przetrzeni, nazywamy węzłem.
Otrzymaliśmy pewną relację równoważności pomiędzy węzłami. Ogólniej, kłębek może zawierać nie jeden sznurek (czyli węzeł), lecz szereg rozłącznych sznurków. Zbiór w przestrzeni euklidesowej, który rozpada się na unię rozłącznych węzłów nazywa się linkiem. Dla linków stawia się pytania podobne jak dla węzłów. I właśnie takimi pytaniami, związanymi z rozplątywaniem linków, zajmuje się Teoria Węzłów i Linków. Na przykład znany jest klasyczny link, złożony z trzech "okręgów", z których żadne dwa nie są zahaczone, ale jednak tych trzech "okręgów" nie da się rozsunąć w przestrzeni tak, by znalazły się wewnątrz trzech, parami rozłącznych kul, każdy w swojej własnej kuli (lub żeby, co na jedno wychodzi, wylądowały na jednej, wspólnej płaszczyźnie, ale dalej te "okręgi" mają być parami rozłączne).
Dla pełniejszego i głębszego zrozumienia węzłów i linków wprowadźmy orientację czyli na każdym sznurku narysujmy strzałkę wzdłuż sznurka - można w jednym z dwóch istniejących kierunków. Narysowanie strzałki w dowolnym miejscu sznurka indukuje zgodną strzałkę w dowolnym jego miejscu (strzałka może wędrować wzdłuż sznurka). To jest właśnie orientacja sznurka. Odtąd możemy klasyfikować węzły i linki subtelniej, żądając zachowania kierunku strzałek.
Z miejsca otrzymujemy dwa rodzaje węzłów. Jedne można tak przekształcać, żeby otrzymać je z powrotem, ale ze strzałką zwróconą w przeciwnym kierunku. Na przykład taki jest okrąg. Możemy go obrócić w przestrzeni wokół jednej z jego średnic o 180 stopni. Wtedy okrąg najdzie na siebie, ale strzałka będzie wskazywać kierunek przeciwny (wzdłuż "sznurka"), a nie oryginalny. W przypadku pewnych innych węzłów jest to niemożliwe.
Pokrewnym pytaniem jest równaważność węzła i jego odbicia lustrzanego (nawet gdy nie obchodzi nas orientacja w sensie strzałki namalowanej na sznurku). Pewne węzły nie dają się przekształcić na swoje odicie lustrzane.
TERMINOLOGIA
Przypominam, że bijekcja jest tym samym, co odwzorowanie wzajemnie jednoznaczne. Bijekcja zbioru skończonego na siebie nazywana jest permutacją.
Bijekcja (na przykład permutacja), która każdemu argumentowi przypisuje jego samego, nazywa się odwzorowaniem tożsamościowym lub po prostu tożsamością. Oznaczamy je [;I_E : E \rightarrow E;], więc [;I_E(x):=x;] dla każdego [;x\in E;].
CYKLE
Parę uporządkowaną [;(E\ \nu);], złożoną z niepustego zbioru skończonego [;E;] i permutacji [;\nu;] będziemy nazywać cyklem. Elementy zbioru [;E;] będziemy nazywać odcinkami. Gdy [;\nu(a)=b;] to odcinek [;b;] nazywamy następnym po [;a;], a odcinek [;a;] poprzednikiem odcinka [;b;].
Najprostszy cykl otrzymujemy, gdy zbiór odcinków [;E;] jest 1-elementowy (wtedy ten jedyny odcinek jest swoim własnym poprzednikiem i następnikiem).
Cykl [;(F\ \mu);] nazywamy podcyklem cyklu [;(E\ \nu);], gdy spełnione są dwa warunki
Cykl [;(E\ \nu);] nazywamy prostym, gdy nie zawiera żadnego podcyklu właściwego (t.j. różnego od siebie samego).
Dwa cykle (lub podcykle) nazywamy rozłącznymi, gdy nie mają wspólnego odcinka. Jest jasnym, że każdy cykl rozpada się jednoznacznie na parami rozłączne podcykle proste - jest to jedna z najwcześniejszych obserwacji (twierdzeń :-) teorii grup permutacji. To, że podstawą linków są permutacje, wskazuje na moźliwy silny związek teorii linków z teorią grup. Teoria linków jest wzbogaconą teorią grup permutacji. Jednak klasyczny, silnie rozwinięty główny głęboki związek teorii węzłów z teorią grup jest zupełnie inny, via grupę fundamentalną dopełnienia węzła w przestrzeni euklidesowej (są też inne).
PRZYKŁAD 0 Cykl [;(E\ I_E);] rozpada się na jednoodcinkowe cykle proste.
Cykl, którego wszystkie podcykle proste składają się z pojedynczego odcinka, nazywa się cyklem zredukowanym.
Izomorfizmem dwóch cykli [;(E\ \nu);] [;(F\ \mu);] nazywamy bijeckcję [;f : E \rightarrow F;] taką, że
[;f(\nu(x)) = \mu(f(x);]
dla każdego odcinka [;x\in E;]. Gdy dla dwóch cykli istnieje izomorfizm, to nazywamy je izomorficznymi. Przy izomorfiźmie podcykl prosty przechodzi na podcykl prosty, o tej samej liczbie odcinków; mówimy, że izomorfizm zachowuje rozkład na podcykle proste. Cykle izomorficzne rozpadają się na tę samą liczbę podcykli prostych (przy czym liczba odcinków w odpowiednich podcyklach jest ta sama).
Niech cykle [;(E\ \nu);] [;(F\ \mu);] oraz odcinek [;a\in E;], taki że [;\nu(a)\ne a;], będą następująco powiązane:
Wtedy mówimy, że cykl [;(F\ \mu);] jest prostą redukcją cyklu [;(E\ \nu);], a ten ostatni prostym rozszerzeniem poprzedniego (o odcinek [;\nu(a);].
Gdy cykl [;(F\ \mu);] można przedstawić jako wynik szeregu prostych redukcji, poczynając od cyklu [;(E\ \nu);], to cykl [;(F\ \mu);] nazywamy redukcją cyklu [;(E\ \nu);], a ten ostatni rozszerzeniem poprzedniego.
Niech podzbiór [;F;] zbioru [;E;] zawiera dokładnie po jednym odcinku z każdego cyklu prostego cyklu [;(E\ \nu;]. Wtedy cykl [;(E\ \nu);] redukuje się do cyklu [;(F\ I_E);] czyli każdy cykl redukuje się do cyklu zredukowanego. Tak więc dwa cykle są izomorficzne [;\Leftrightarrow;] redukują się do cykli zredukowanych, o tej samej liczbie odcinków.
Ogólniej, można wyobrazić sobie dwa takie poplątane kłębki. Czy da się jeden z nich tak przemieścić i zdeformować (znowu nie wolno rozrywać), by na koniec oba wyglądały tak samo, by się różniły tylko o przesunięcie równoległe (gdy jeden ze sznurków usuniemy, a drugim będziemy będziemy manipulować, to na koniec ma zająć miejsce tego usuniętego, ale dokładnie tak jakbyśmy widzieli ten poprzedni).
Sznurek, ze szczepionymi końcami, zafiksowany w przetrzeni, nazywamy węzłem.
Otrzymaliśmy pewną relację równoważności pomiędzy węzłami. Ogólniej, kłębek może zawierać nie jeden sznurek (czyli węzeł), lecz szereg rozłącznych sznurków. Zbiór w przestrzeni euklidesowej, który rozpada się na unię rozłącznych węzłów nazywa się linkiem. Dla linków stawia się pytania podobne jak dla węzłów. I właśnie takimi pytaniami, związanymi z rozplątywaniem linków, zajmuje się Teoria Węzłów i Linków. Na przykład znany jest klasyczny link, złożony z trzech "okręgów", z których żadne dwa nie są zahaczone, ale jednak tych trzech "okręgów" nie da się rozsunąć w przestrzeni tak, by znalazły się wewnątrz trzech, parami rozłącznych kul, każdy w swojej własnej kuli (lub żeby, co na jedno wychodzi, wylądowały na jednej, wspólnej płaszczyźnie, ale dalej te "okręgi" mają być parami rozłączne).
Dla pełniejszego i głębszego zrozumienia węzłów i linków wprowadźmy orientację czyli na każdym sznurku narysujmy strzałkę wzdłuż sznurka - można w jednym z dwóch istniejących kierunków. Narysowanie strzałki w dowolnym miejscu sznurka indukuje zgodną strzałkę w dowolnym jego miejscu (strzałka może wędrować wzdłuż sznurka). To jest właśnie orientacja sznurka. Odtąd możemy klasyfikować węzły i linki subtelniej, żądając zachowania kierunku strzałek.
Z miejsca otrzymujemy dwa rodzaje węzłów. Jedne można tak przekształcać, żeby otrzymać je z powrotem, ale ze strzałką zwróconą w przeciwnym kierunku. Na przykład taki jest okrąg. Możemy go obrócić w przestrzeni wokół jednej z jego średnic o 180 stopni. Wtedy okrąg najdzie na siebie, ale strzałka będzie wskazywać kierunek przeciwny (wzdłuż "sznurka"), a nie oryginalny. W przypadku pewnych innych węzłów jest to niemożliwe.
Pokrewnym pytaniem jest równaważność węzła i jego odbicia lustrzanego (nawet gdy nie obchodzi nas orientacja w sensie strzałki namalowanej na sznurku). Pewne węzły nie dają się przekształcić na swoje odicie lustrzane.
TERMINOLOGIA
Przypominam, że bijekcja jest tym samym, co odwzorowanie wzajemnie jednoznaczne. Bijekcja zbioru skończonego na siebie nazywana jest permutacją.
Bijekcja (na przykład permutacja), która każdemu argumentowi przypisuje jego samego, nazywa się odwzorowaniem tożsamościowym lub po prostu tożsamością. Oznaczamy je [;I_E : E \rightarrow E;], więc [;I_E(x):=x;] dla każdego [;x\in E;].
CYKLE
Parę uporządkowaną [;(E\ \nu);], złożoną z niepustego zbioru skończonego [;E;] i permutacji [;\nu;] będziemy nazywać cyklem. Elementy zbioru [;E;] będziemy nazywać odcinkami. Gdy [;\nu(a)=b;] to odcinek [;b;] nazywamy następnym po [;a;], a odcinek [;a;] poprzednikiem odcinka [;b;].
Najprostszy cykl otrzymujemy, gdy zbiór odcinków [;E;] jest 1-elementowy (wtedy ten jedyny odcinek jest swoim własnym poprzednikiem i następnikiem).
Cykl [;(F\ \mu);] nazywamy podcyklem cyklu [;(E\ \nu);], gdy spełnione są dwa warunki
- [;F\subseteq E;]
- [;\mu = \nu\,|\,F;]
Cykl [;(E\ \nu);] nazywamy prostym, gdy nie zawiera żadnego podcyklu właściwego (t.j. różnego od siebie samego).
Dwa cykle (lub podcykle) nazywamy rozłącznymi, gdy nie mają wspólnego odcinka. Jest jasnym, że każdy cykl rozpada się jednoznacznie na parami rozłączne podcykle proste - jest to jedna z najwcześniejszych obserwacji (twierdzeń :-) teorii grup permutacji. To, że podstawą linków są permutacje, wskazuje na moźliwy silny związek teorii linków z teorią grup. Teoria linków jest wzbogaconą teorią grup permutacji. Jednak klasyczny, silnie rozwinięty główny głęboki związek teorii węzłów z teorią grup jest zupełnie inny, via grupę fundamentalną dopełnienia węzła w przestrzeni euklidesowej (są też inne).
PRZYKŁAD 0 Cykl [;(E\ I_E);] rozpada się na jednoodcinkowe cykle proste.
Cykl, którego wszystkie podcykle proste składają się z pojedynczego odcinka, nazywa się cyklem zredukowanym.
Izomorfizmem dwóch cykli [;(E\ \nu);] [;(F\ \mu);] nazywamy bijeckcję [;f : E \rightarrow F;] taką, że
[;f(\nu(x)) = \mu(f(x);]
dla każdego odcinka [;x\in E;]. Gdy dla dwóch cykli istnieje izomorfizm, to nazywamy je izomorficznymi. Przy izomorfiźmie podcykl prosty przechodzi na podcykl prosty, o tej samej liczbie odcinków; mówimy, że izomorfizm zachowuje rozkład na podcykle proste. Cykle izomorficzne rozpadają się na tę samą liczbę podcykli prostych (przy czym liczba odcinków w odpowiednich podcyklach jest ta sama).
Niech cykle [;(E\ \nu);] [;(F\ \mu);] oraz odcinek [;a\in E;], taki że [;\nu(a)\ne a;], będą następująco powiązane:
- [;F = E\backslash\{\nu(a)\};]
- [;\mu\,|\,G\backslash\{a\} = \nu\,|\,E\backslash\{a\ \nu(a)\} ;]
- [;\mu(a) = \nu(\nu(a));]
Wtedy mówimy, że cykl [;(F\ \mu);] jest prostą redukcją cyklu [;(E\ \nu);], a ten ostatni prostym rozszerzeniem poprzedniego (o odcinek [;\nu(a);].
Gdy cykl [;(F\ \mu);] można przedstawić jako wynik szeregu prostych redukcji, poczynając od cyklu [;(E\ \nu);], to cykl [;(F\ \mu);] nazywamy redukcją cyklu [;(E\ \nu);], a ten ostatni rozszerzeniem poprzedniego.
Niech podzbiór [;F;] zbioru [;E;] zawiera dokładnie po jednym odcinku z każdego cyklu prostego cyklu [;(E\ \nu;]. Wtedy cykl [;(E\ \nu);] redukuje się do cyklu [;(F\ I_E);] czyli każdy cykl redukuje się do cyklu zredukowanego. Tak więc dwa cykle są izomorficzne [;\Leftrightarrow;] redukują się do cykli zredukowanych, o tej samej liczbie odcinków.
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:
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:
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:
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:
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):
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.
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
itd. :-)
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
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:
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
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ę:
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;]:
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:
(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 :-)
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 :-)
Subscribe to:
Posts (Atom)