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.
No comments:
Post a Comment