Teoria informacji/TI Wykład 3

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Minimalna długość kodu

Jak widzieliśmy w analizie przykładu gry w zgadywanie, jeśli wszystkie prawdopodobieństwa są potęgami , to entropia jest równa średniej długości optymalnego kodu. Udowodnimy, że zawsze stanowi ona dolne ograniczenie:


Definicja [długość kodu]

Dla danego kodu , średnią długość kodu definiujemy jako

Dla danego S i parametru niech będzie minimum ze wszystkich dla dowolnego kodu , gdzie . Zauważmy, że na mocy Twierdzenia McMillana wystarczy, że znajdziemy minimum dla wszystkich kodów bezprefiksowych.


Twierdzenie

Dla dowolnej skończonej przestrzeni probabilistycznej S
i równość zachodzi wtedy i tylko wtedy, gdy wszystkie prawdopodobieństwa p(s) są potęgami

Dowód

Rozważmy dowolny kod gdzie . Pokażmy, że

Wystarczy w tym celu użyć Złotego Lematu dla i .

Pozostało jedynie pokazać drugą część twierdzenia. Jeśli , to znaczy, że dla pewnego kodu . Znów na podstawie Złotego Lematu dostajemy dla wszystkich .

Z drugiej strony, jeśli wszystkie prawdopodobieństwa są postaci , to na mocy nierówności Krafta istnieje kod z , i dla tego kodu . A zatem , czyli musi zachodzić równość. End of proof.gif


Znalezienie optymalnego kodu bezprefiksowego dla danego rozkładu prawdopodobieństwa nie jest wcale trudnym zadaniem. Algorytm rozwiązujący ten problem podał amerykański inżynier David A. Huffman (1925-1999).

Algorytm Huffmana
(dla zbioru kodowanego S i alfabetu )
Jeśli , przypisz po prostu jakieś symbole obiektom z S. W przeciwnym wypadku:
1. Jeśli , w razie konieczności uzupełnij S symbolami o prawdopodobieństwie 0, 
   tak aby .
2. Wybierz  symboli  o minimalnych prawdopodobieństwach.
3. Uruchom rekurencyjnie ten algorytm dla zbioru  z prawdopodobieństwami 
    dla  i .
4. Mając dane drzewo  z poprzedniego punktu skonstruuj drzewo  w następujący sposób: 
   Dodaj k synów do słowa  i oznacz ich jako .


Dla przedstawionej powyżej definicji kodu problem mamy zatem rozwiązany. Niestety, w większości wypadków długość takiego optymalnego kodu będzie się różniła od dolnej granicy . Na szczęście możemy ten problem obejść. Okazuje się, że dla dowolnego zadanego S i p można uzyskiwać mniejszą średnią długość kodu, dowolnie zbliżając się do . Uzyskuje się to przez lekkie poszerzenie samego pojęcia kodu.


Przykład [Kodowanie par]

Niech z . Oczywiście . (Jednocześnie łatwo oszacować, że ). Oznacza to, że nie możemy zakodować wiadomości w postaci krótszej niż sama . Wyobraźmy sobie jednak następujące kodowanie par:

Nie jest to w dosłownym sensie kod dla S, ale wygląda na to, że możemy go użyć do zakodowania dowolnych wiadomości o parzystej długości. Faktycznie, zgodnie z definicją to jest kod dla . Rozważmy jako produkt (probabilistyczny) przestrzeni, w którym

Średnia długość naszego kodowania dwuznakowych bloków będzie wynosić

Jak można się spodziewać, podążając tym tropem dla kodów złożonych z trzech, czterech i więcej znaków, będziemy mogli otrzymać coraz efektywniejsze kodowania. Czy jednak możemy zejść poniżej granicy entropii, czyli uzyskać

dla pewnego n?

Udowodnimy później, że to jest niemożliwe, ale Pierwsze Twierdzenie Shannona pokaże, że możemy zbliżyć się do niej dowolnie blisko dla .

Najpierw jednak policzmy entropię przestrzeni interpretowanej jako przestrzeń produktowa.

Entropia przestrzeni produktowej

Entropię możemy znaleźć przez nieco żmudne elementarne wyliczenia, ale wygodniej będzie skorzystać z ogólnych własności zmiennych losowych opisanych w wykładzie 7 z Rachunku prawdopodobieństwa i statystyki.

Przypomnijmy, że wartość oczekiwaną (zwaną też nadzieją matematyczną) zmiennej losowej można przedstawić na dwa równoważne sposoby:

Drugi sposób często zapisuje się prościej jako

przyjmując, że suma dowolnie wielu zer daje 0.

Używana tutaj notacja jest szczególnym przypadkiem notacji , określającej prawdopodobieństwo że zachodzi zdarzenie , czyli sumę p(s) po wszystkich , dla których zdanie jest spełnione.

Przypominamy z Rachunku Prawdopodobieństwa (por. wspomniany wykład 7):

Fakt [Liniowość wartości oczekiwanej]

Jeśli X i Y są dowolnymi zmiennymi losowymi (określonymi na tej samej przestrzeni probabilistycznej), to dla dowolnych :


Rozważmy teraz przypadek, gdy mamy dwie przestrzenie probabilistyczne S i Q. (Zwyczajowo, jeśli nie powoduje to niejasności, będziemy używać tej samej litery p na określenie prawdopodobieństwa we wszystkich przestrzeniach).

Niech będzie przestrzenią produktową z prawdopodobieństwem określonym następująco

.

Dla zmiennych losowych i , definiujemy zmienne , na jako

Oczywiście mamy:

i analogicznie . Zatem i . Z liniowości wartości oczekiwanej

Niech teraz i . Zgodnie z definicją entropii, mamy więc , . Z przyjętych definicji i własności funkcji otrzymujemy

A zatem jest dokładnie tą zmienną losową na , której wartość oczekiwana jest entropią . Czyli

.

W konsekwencji:

Fakt

Niech będzie n-tą potęgą przestrzeni S z prawdopodobieństwem . Wtedy
.