Kody kompresji

Przedstawiając informację, np. obraz, cyfrowo, musimy ją podzielić na maleńkie fragmenty. To pozwala nam przesłać obraz jako ciąg barwnych symboli. A te kolory mogą być przedstawiane pod postacią liczb z jakiegoś kodu. Zastanówcie się nad zadaniem: Alicja i Bob binarnie przesyłają i odbierają wiadomości. Pobierają centa za bit od klientów - za korzystanie z systemu. Przychodzi klientka, która chce wysłać wiadomość. Ta wiadomość składa się z tysiąca symboli. A jej znaczenie jest nieznane. Wiadomości są zwykle wysyłane standardowym, dwubitowym kodem, trzeba by więc naliczyć opłatę za 2000 bitów. Jednak Alicja i Bob analizowali już wiadomości tej klientki. Obliczyli różne prawdopodobieństwa pojawiania się symboli. Czy, znając te wartości, mogą skompresować transmisję i zarobić więcej? Jaka jest optymalna strategia kodowania? David Huffman sformułował słynną strategię optymalną; opublikował ją w 1952 r. Podstawą było tworzenie drzewa binarnego od dołu. Wypiszmy więc wszystkie symbole. Nazwiemy je węzłami. Wyszukujemy dwa najmniej prawdopodobne węzły, w tym przypadku B i C, i łączymy je, dodając prawdopodobieństwo. Powtarzamy to z dwoma następnymi najmniej prawdopodobnymi węzłami. I łączymy dalej, aż zostanie jeden, na samej górze. Wreszcie oznaczamy krawędzie na tym drzewie zerami i jedynkami, w jakimś porządku. Kod każdej litery to ścieżka od szczytu drzewa do niej. Do A prowadzi tylko jedna krawędź, czyli 1. Metodę nazwano kodowaniem Huffmana. Do przykładów tego typu nie ma lepszej. Spróbujcie! Np. jeśli skrócicie kod dla D do samego zera, to wiadomość „011” może oznaczać DAA, ale też samo B. Trzeba by więc wprowadzić odstępy między literami, co niestety zniweluje wszelkie oszczędności w transmisji. Jak bardzo skompresowaliśmy wiadomość od pierwszych 2000 bitów? Musimy obliczyć przeciętną liczbę bitów na literę. Mnożymy długość każdego kodu przez prawdopodobieństwo wystąpienia i sumujemy. Uzyskujemy przeciętną długość 1,75 bita na symbol. To znaczy, że za pomocą kodowania Huffmana możemy kompresować wiadomości z 2000 bitów do 1750 bitów. Claude Shannon pierwszy stwierdził, że granica kompresji zawsze będzie równa entropii źródła wiadomości. W miarę, jak entropia lub niepewność naszego źródła maleje, wskutek czynników niestatystycznych, zdolność kompresji rośnie. Tymczasem gdy rośnie entropia, wskutek nieprzewidywalności, nasza zdolność kompresji spada. Chcąc coś skompresować powyżej entropii, koniecznie musimy odjąć część informacji z wiadomości.