Teoria informacji Shanonna

Teoria informacji

Entropia

Przyjmijmy, że mamy do czynienia ze źródłem danych wysyłającym \(n\) różnych komunikatów, \(k_1, k_2, \ldots, k_n\) . Komunikat \(k_i\) ma prawdopodobieństwo wystąpienia \(p_i\) .

Przykład. Źródłem danych jest na przykład kostka sześcienna do gry. Możliwe komunikaty to 1, 2, 3, 4, 5 i 6. Każdy z nich występuje z prawdopodobieństwem \(\frac 16\) .

Definicja Entropią źródła danych (o prametrach jak powyżej) nazywamy wartość:

\[ H = - \sum_{k=1}^n p_k \log_2 p_k \]

Jednostką tak zdefiniowanej entropii jest bit (w skrócie b).

Przykład. Entropia dla idealnej kostki sześciennej wynosi \(-6*\frac 16 \log_2 \frac 16 = \log_2 6 \approx 2{,}585 b\) .

Kodowanie

Informacje ze źródła danych będziemy zapisywali (kodowali) za pomocą alfabetu złożonego z dwóch symboli: 0 i 1. Dla przykładu, fakt wyrzucenia odpowiedniej ilości oczek na kostce moglibyśmy kodować następująco:

Liczba oczek Słowo kodowe
1 10
2 100
3 1000
4 10000
5 100000
6 1000000

Kolejne słowa kodowe z reguły przekazujemy bez przerw między nimi. Założmy, że przy powyższym kodowaniu dostaliśmy wiadomość:

\[ 101000100001001001000100010010001010100001010101000100 \]

Możemy ją bez większych problemów zdekodować jako ciąg rzutów: 1, 3, 4, 2, 2, 3, 3, 2, 3, 1, 1, 4, 1, 1, 1, 3, 2.

Przyjmijmy teraz, że kod wygląda następująco:

Liczba oczek Słowo kodowe
1 0
2 1
3 01
4 10
5 00
6 11

Przy tym kodowaniu wiadomość

\[ 0101 \]

nie jest jednoznaczna. Może oznaczać ciąg rzutów 1, 2, 1, 2 lub 1, 2, 3 lub 3, 1, 2 lub 3, 3 lub 1, 4, 2. Taki kod jest oczywiście niezbyt praktyczny, bo musielibyśmy dzielić wiadmość na poszczegolne słowa kodowe. Kodowania, przy których wiadmości dzielą się tylko w jeden sposób na słowa kodowe nazywamy jednoznacznymi.

Bardzo przydatną włąściwością kodu jest, abyśmy byli w stanie stwierdzić czy otrzymana wiadomość jest kompletna. Oczywiście najlepiej byłoby przesyłać jakiś znak końca wiadomości, ale nie zawsze jest to możliwe. Wróćmy do naszego pierwszego kodowania dla rzutów kostki. Jest ono co prawda jednoznaczne, to jednak nie ma tej pożądanej własności. Otrzymanie wiadomości

\[ 10 \]

może oznaczać wypadnięcie liczby 1, ale może też oznaczać, że pozostała częśc wiadomości jeszcze do nas nie dotarła. Nie możemy więc dekodować online, musimy poczekać na otrzymanie pełnej wiadomości. Zauważmy, że przyczyną problemu było to, że wszystkie nasze słowa kodowe zaczynają się od \(10\) , a samo \(10\) jest słowem kodowym. Kody dla których żadne słowo kodowe nie jest prefiksem (początkową częścia) innego słowa kodowego nazywamy prefiksowymi.

Nazwa kod prefiksowy może być nieco myląca, ponieważ te kody właśnie nie zawierają prefiksów.

Poniżej mamy przykład prefiksowego i jednoznacznego kodu dla rzutów kostką:

Liczba oczek Słowo kodowe
1 01
2 001
3 0001
4 00001
5 000001
6 0000001

Redundancja

Definicja. Przyjmijmy, że kod zawiera \(n\) słów kodowych o długościach \(N_1, N_2, \ldots, N_n\) i kolejne słowa kodowe występują w wiadomościach z prawdopodobieństwem odpowiednio \(p_1, p_2, \ldots, p_n\) . Średnią długością słowa kodowego dla tego kodu nazywamy liczbę

\[ L = \sum_{k=1}^n p_k N_k. \]

Przykład. Zakładając, że rozważane powyżej przykładowe kody dla kostek rzeczywiście kodują rzuty idealną kostką, a więc prawdopodobieństwo wystąpienia każdego słowa kodowego wynosi \(\frac 16\) , średnia długość słowa kodowego wynosi kolejno: \(4\frac12, 1\frac23, 4\frac12.\)

Definicja. Redundancją (nadmiarowością) kodu nazywamy różnicę między średnią długością słowa kodowego a entropią źródła danych.

Twierdzenie Shanonna. Jeżeli kolejne komunikaty źródła są od siebie niezależne i kod jest bezstratny (tzn. z zakodowanej wiadomości można bezbłędnie odczytać ciąg komunikatów źródła danych), to redundancja tego kodu jest nieujemna.

Definicja. Kod binarny jednoznaczny o minimalnej możliwej redundancji nazywamy kodem zwartym lub kodem Huffmana.

Algorytm Huffmana

Algorytm Huffmana tworzy zwarty kod prefiksowy (kod Huffmana) dla źródła danych o zadanych prawdopodobieństwach komunikatów. Jest to kod o zmiennej długości słów kodowych. Częściej pojawiające się komunikaty są kodowane krótszymi słowami kodowymi, komunikaty rzadsze – dłuższymi słowami.

Algorytm Huffmana działa w następujący sposób:

  • Dla każdego komunikatu z ustalonym prawdopodobieństwem utwórz drzewo binarne o jednym wierzchołku – korzeniu przechowującym ten komunikat wraz z prawdopodobieństwem jego wystąpienia. Będzie to prawdopodobieństwo przypisane temu jednoelementowemu drzewu.
  • Dopóki mamy więcej niż jedno drzewo, wybierz dwa drzewa o najmniejszym prawdopodobieństwie, i połącz je w jedno większe drzewo, dodając nowy korzeń i krawędzie z tego nowego korzenia do korzeni wybranych uprzednio drzew. Krawędziom nadajemy etykiety 0 i 1, w dowolnym porządku. Prawdopodobieństwem tego nowego drzewa jest suma dwóch prawdopodobieństw drzew, które ono łączy.
  • Algorytm kończy się, gdy mamy tylko jedno drzewo. Liście tego drzewa to komunikaty źródła danych. Słowa kodowe przypisane im przez algorytm otrzymujemy odczytując etykiety krawędzi od korzenia do liścia.

Przykład. Dla źródła danych wysyłającego 6 komunikatów z prawdopodobieństwami odpowiednio 4/14, 3/14, 3/14, 2/14, 1/14, 1/14 otrzymujemy po wykonaniu algorytmu następujące drzewo:

Z drzewa odczytujemy (przykładowe) kodowanie Huffmana:

Prawdopodobieństwo komunikatu Słowo kodowe
4/14 11
3/14 01
3/14 00
2/14 101
1/14 1000
1/14 1001

Można sprawdzić, że entropia źródła danych o tych prawdopodobieństwach komunikatów wynosi około 2,4138, a średnia długość słowa kodowego dla otrzymanego kodowania Huffmana to około 2.85174.

Kompresja danych

Powyższy algorytm doskonale nadaje się do kompresowania danych. Popularne algorytmy kompresji używają wprost kodu Haffman lub metod mających z nim wiele wspólnego.

Teraz zobaczymy prosty przykład jak mógłby działać naiwny algorytm kompresji. Załóżmy dla uproszczenia, że mamy do skompresowania tekst:

ABAEBBBABABBABBCBBBABBABDCBBBBBABCBBBBCBBABBBBCBBBBABBCB

Aby użyć algorytmu Huffmana jako algorytmu kompresji, traktujemy tekst źródłowy jako źródło danych. Komunikatami będą poszczególne znaki, a jako prawdopodobieństwa weźmiemy częstość występowania znaków w tekście. Szybkie obliczenia pokazują, że mamy:

Litera Liczba wystąpień Kod Huffmana
A 10 10
B 38 0
C 6 110
D 1 1110
E 1 1111

Oryginalny tekst w kodzie ASCII to 56 bajtów, zakodowany kodem Huffmana ma 84 bity, więc nasz prosty algorytm był w stanie skompresować tekst do ok. 19% rozmiaru. Proszę zauważyć jednak, że wraz ze skompresowanym tekstem należy przesłać słownik (aby można było odkodować tekst). Oryginalne tekst moglibyśmy też przesyłać używając kodu o stałej długości słów kodowych, np:

Litera Słowo kodowe
A 000
B 001
C 010
D 011
E 100

Wtedy po zakodowaniu nasz tekst to 168 bitów, więc nadal dwa razy więcej niż przy kodowaniu Huffmana.

Widać oczywiście, że nasz algorytm można by jeszcze poprawić. Na przykład mógłby próbować wykrywać powtarzające się całe ciągi znaków i je w jakiś sposób kodować. podobne pomysły prowadzą do współcześnie powszechnie używanych algorytmów kompresji danych.

Kodowanie znaków

Poniższa część dotyczy zaszłości historycznych, które powodują problemy przy kodowaniu i dekodowaniu znaków alfanumerycznych i plików tekstowych. Co prawda nie łączy się to ściśle z teorią informacji, jest to pewnie dobre miejsce, żeby o tym wspomnieć.

ASCII

Standard ASCII nie był bynajmniej pierwszym standardem kodowania znaków, ale zdecydowana większość sytemów nie ma problemów z interpretowaniem znaków w tym kodowaniu i dzięki UTF-8 (o którym poniżej) może być uznawany za „wspólny mianownik”. ASCII definiuje 7-bitowe kodowanie dla małych i wielkich liter alfabetu łacińskiego, podstawowych znaków interpunkcyjnych i pewnych znaków sterujących. Pełna tabela tutaj.

Kodowania 8-bitowe

Ponieważ od końca lat 70-tych powszechne w użyciu stały się komputery 8-bitowe, tekst w kodowaniu ASCII był z reguły przesyłany w postaci 1 znak = 1 bajt. 1 bajt może przyjmować jedną z 256 wartości, jednak ASCII dawało znaczenie tylko pierwszym 128 wartościom. To znaczy, że zostawalo kolejne 128 znaków do wykorzystania. Naturalnym było przyporządkowanie tych wartości znakom narodowym spoza alfabetu łacińskiego. Niestety, 128 wartości to za mało by zakodować znaki wszystkich używanych języków, więc naturalnym było powstanie wielu uzupełniających się standardóœ kodowania. Niestety powstało też wiele standardów konkurencyjnych, co dodatkowo utrudnia dekodowanie plików. Znaki języka polskiego zawierają następujące kodowania 8-bitowe:

Nie jest to co prawda ściśle prawdą, ale plik zapisany z użyciem kodowania Windows-1250 jest również poprawnym plikiem w pozostałych kodowaniach, chociaż symbole reprezentowane przez te same wartości będą się oczywiście różnić. To prowadzi do wyśwetlania czasem tzw. krzaczków.

Unicode

Zamieszanie spowodowane różnymi kodowaniami 8-bitowymi wymusiło przejście (czy też bardziej przechodzenie) na system Unicode. Obecnie Unicode zawiera ponad 250000 znaków. Unicode jest zorganizowany w 17 „płaszczyzn” (ang. planes), z których każda zawiera potencjalnie miejsce na 65536 symboli. W istocie używane są właściwie 3 pierwsze płaszczyzny:

  • płaszczyzna 0: większość powszechnie używanych liter: m.in,.: alfabety łacińskie, arabskie, część ideogramów pisma chińskiego, trochę popularnych symboli.
  • płaszczyzna 1: głównie alfabety o znaczeniu historycznym, sporo symboli.
  • płaszczyzna 2: dodatkowe ideogramy pisma chińskiego.

Dodatkowe dwie (ostanie) płaszczyzny są zarezerwowane do prywatnego użytku.

Każdy znak ma przypisany w standardzie Unicode tzw. punkt kodowy, czyli odpowiadający mu numer, oznaczany w systemie szesnastkowym jako U+XXXXX. Pierwsza cyfra w tym zapisie oznacza płaszczyznę i jest ona pomijana, jeżeli jest równa 0. Dla przykładu U+0118 to „LATIN CAPITAL LETTER E WITH OGONEK”, czyli Ę, a U+3041 to „HIRAGANA LETTER SMALL A” czyli ぁ (znak wyświetli się tylko, jeśli przeglądarka ma odpowiednie czcionki).

Znak o punkcie kodowym U+XXXXX można zapisać w HTML-u jako encję w postaci 〹 (punkt kodowy w postaci dziesiętnej) lub &#xXXXXX; (punkt kodowy w postaci szesnastkowej).

Kodowanie binarne Unicode

Unicode pozwala przyporządkować każdemu znakowi w tekście odpowiednie punkty kodowe Unicode, ale nie mówi o tym jak należy je przesyłać. Najprostszym systemem jest użycie kodowania o stałej szerokości słowa kodowego. Kodowania te to:

  • UCS-4 (kodowanie 4-bajtowe – każdy punkt kodowy jest zapisywany w postaci liczby 32-bitowej i przesyłana jest ta liczba)
  • UCS-2 (kodowanie 2-bajtowe – punkt kodowy zapisywany w postaci liczby 16-bitowej, pozwala na przesyłanie jedynie znaków z zerowej płaszczyzny Unikodu)

Najczęściej używane kodowanie UTF-8 jest kodowaniem o zmiennej szerokości słowa kodowego. Znaki ASCII (punkty kodowe od U+0000 od U+007F) są przesyłane w postaci jednego bajtu. Pozostałe punkty kodowe są przesyłane w kilku kolejnych bajtach, z których pierwszy mówi ile bajtów zawiera taka kombinacja. Dokładny mechanizm wraz ze szczegółami technicznymi jest opisany na Wikipedii. Tutaj tylko jeden przykład, aby wyrobić sobie wyobrażenie jak to działa.

Przeanalizyjemy kodowanie znaku „EN DASH” (półpauza) o punkcie kodowym U+2013. Szesnastkowe 2013 w zapisie binarnym to 0010 0000 0001 0011. Ostatnie 14 bitów jest niezerowych, będziemy więc potrzebowali w UTF-8 3 bajtów do przesłania tego znaku (2 bajty pozwalają przesłać w UTF-8 punkty kodowe najwyżej 11-bitowe). Zapis będzie wyglądał następująco (na czerwono oznaczono kodowany punkt kodowy, na niebiesko dodatkowe dane sterujące):

11100010 10000000 10010011

Dzięki takiemu systemowi teskt zakodowany w ASCII jest poprawnie zakodowany w UTF-8, poza tym częściej pojawiające się znaki są kodowane przy użyciu jednego lub dwóch bajtów. Niestety dekodowanie jest bardziej skomplikowane, w szczególności znalezienie dajmy na to 66 znaku w napisie wymaga zdekodowania całego tekstu od początku. Dlatego większość języków programowania przechowuje napisy w pamięci w kodowaniu o stałej szerokości słowa kodowego (UCS-2 lub UCS-4), a UTF-8 używany jest do przesyłania tekstu na zewnątrz (chociaż, patrz notatkę poniżej).

Nowsze języki programowania (Java, Python) pozwalają na używanie Unikodu w plikach źródłowych, także w nazwach zmiennych, chociaż w praktyce nie jest polecane korzystanie z tego mechanizmu.

Poprawne działanie programów z tekstem, który to tekst może zawierać przeróżne znaki narodowe nie jest sprawą prostą. Zalecam każdemu przeczytanie, dlaczego UTF-8 jest dobrym wyborem na przechowywanie napisów w pamięci oraz najważniejsze rzeczy, które programista powinien wiedzieć o Unikodzie. W XXI wieku nie ma powodu by program nie używał znaków narodowych w wyświetlanym tekście czy w interfejsie użytkownika lub miał problem z przyjęciem tekstu napisanego z użyciem znaków narodowych. Do obsługi Unikodu wraz z jego wszystkimi technicznymi meandrami w C/C++ służy np. biblioteka ICU.

Przykład na zajęcia. Źródło emituje komunikaty z prawdopodobieństwami kolejno: \[ \frac{3}{11},\frac{2}{11},\frac{2}{11},\frac{1}{11},\frac{1}{11},\frac{1}{11},\frac{1}{11}.\]

  • Oblicz entropię danych emitowanych przez źródło.
  • Oblicz średnią długość słowa kodowego dla kodu, w którym słowa kodowe mają długość 3. Jaką redundancję ma ten kod?
  • Znajdź kod zwarty (Huffmana) dla tego źródła. Jaką redundancję ma ten kod?

Zadania do wykonania

Zadanie 1. Wykonaj poniższe polecenia starując od swojego numeru indeksu. Poniższe przykładowe obliczenia wykonywane są dla numeru 286934.

Zadanie 2. Weź swoje imię i nazwisko, zamień wszystkie litery na wielkie, wszystkie polskie litery na ich odpowiedniki łacińskie i zdubluj wszystkie samogłoski, pomiń spacje. Skompresuj tak otrzymany tekst algorytmem Huffmana tak jak to opisano w powyższych materiałach (np. Michał Goliński kompresowałby tekst MIICHAALGOOLIINSKII). Znajdź średnią długośc słowa kodowego dla znalezionego kodowania.

Rozwiązania proszę przesyłać w postaci jasno formatowanych plików tekstowych, plików PDF lub zdjęć/skanów ręcznie spisanych rozwiązań w sensownej jakości i wielkości (np. wysoka rozdzielczość, tryb 1-bitowy i kompresja CCITT). Proszę unikać formatu MS Word czy Open/LibreOffice. Lepiej konwertować je na końcu do PDF-a.