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