-
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.
