Ostatni wykład zakończylismy na metodzie Elliasa jako metodzie kompresji danych. Dziś zajmiemy się kodem Schannona. Kompresja Shannona jest bezstratną metodą kodowania znaków w wyniku której otrzymujemy kod, który jest jest kodem przedrostkowym. Tutaj znaki o większym prawdopodobieństwie kodowane są za pomocą mniejszej ilości bitów od znaków występujących z mniejszym prawdopodobieństwem. Kod ten prócz tego jest jednoznacznie dekodowalny. Aby zakodować dany strumień symboli postępujemy następująco:

• Zliczamy ilość wystąpień danego symbolu

• Obiczamy prawdopodobieństwo wystąpienia poszczególnych symboli (p_i)

• Obliczamy ilość bitów potrzebnych do zakodowania danego symbolu za pomocą wzoru l_i = sufit z wartości (log₂(1/p_i)

• Obliczamy prawdopodobieństwo kumulatywne k₀ = 0, k₁ = p₀, k₂ = k₁+p₁, ..., k_n = k_n-1+p_n-1

• Przekształcamy prawdopodobieństwa kumulatywne na postać binarną o długościach l_i za pomocą algorytmu :

t=p_i
słowo kodowe S
int licznik=0;
bin(t)
{
    if(l_i>licznik)
    {
       if (t>0)
            {
                S+="1"
                t-=1
            }
        else S+="0"
        t:=t*2
        licznik++
        bin(t)
    }
}

Rozpatrzmy nastepujący przykład:

Symbol	pi	ki	li	kody
a	0.35	0	2	0|00|00....
b	0.17	0.35	3	0|010|11...
c	0.17	0.52	3	0|100|001...
d	0.16	0.69	3	0|101|100...
e	0.15	0.85	3	0|110|110...

Otrzymane kody to:

a = 00
b = 010
c = 100
d = 101
e = 110.

Odnosząc się do tej metody istotne jest też zapamiętanie pierwszego twierdzenia Shannona o oszacowaniu minimalnej średniej długości słowa kodowego. Średnia długość kodu K dla źródła informacji określonego przez P wynosi:
. Dla kodu Shannona będzie określona wzorem:
. Twierdzenie Shannona mówi nam, że średnia długość słowa kodowego jest większa, bądź równa entropii (o pojęciu entropii będzie jeszcze mowa). Równość ta jest spełniona dla specjalnych wartości
, gdzie ki to dowolna liczba naturalna. Teraz nieco o entropii. Entropia w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypadająca na znak symbolizujący zajście zdarzenia z pewnego zbioru. Zdarzenia w tym zbiorze mają przypisane prawdopodobieństwa wystąpienia.

Oto wzór na entropię:

p(i) to prawdopodobieństwo zajścia zdarzenia i. W przypadku kodowania ciągu znaków jest to prawdopodobieństwo wystąpienia itego znaku. W teorii informacji najczęściej stosuje się logarytm o podstawie r = 2, wówczas jednostką entropii jest bit. Dla r = e jednostka ta nazywa się nat(nit), natomiast dla r = 10 - dit lub hartley. Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego w następnej chwili. Jeżeli następujące zdarzenie występuje z prawdopodobieństwem równym 1, to z prostego podstawienia wynika, że entropia wynosi 0, gdyż z góry wiadomo co się stanie - nie ma niepewności. Itnieje kilka własności entropii. Mianowicie jest nieujemna, jest maksymalna, gdy prawdopodobieństwa zajść zdarzeń są takie same, oraz jest równa 0, gdy stany systemu przyjmują wartości 0 albo 1. Zachodzi też własność superpozycji - gdy dwa systemy są niezależne to entropia sumy systemów równa się sumie entropii. Definicja informacyjna była pierwotnie próbą ujęcia tradycyjnego pojęcia entropii znanego z termodynamiki w kategoriach teorii informacji. Okazała się jednak, że definicja ta jest przydatna w ramach samej teorii informacji. Pojęcie entropii jest bardzo przydatne w dziedzinie kompresji informacji. Entropię zerowego rzędu można obliczyć znając histogram ciągu symboli. Jest to iloczyn entropii i ilości znaków w ciągu. Osiągi kodowania Huffmana są często zbliżone do tej granicy, ale istnieją lepsze sposoby np. kodowanie arytmetyczne. Przyjęcie modelu, w którym uwzględnia się kontekst znaku, pozwala zwykle na bardzo duże obniżenie entropii.

Zobaczmy na przykład entropii. Moneta, która wyrzuca z takim samym prawdopodobieństwem orły i reszki, ma 1 bit entropii na rzut:

Ogólniej każde źródło dające N równie prawdopodobnych wyników ma log2N bitów na symbol entropii:

Istnieje jeszcze takie poęcie, jak entropia Von Neumanna. Entropia von Neumanna to w mechanice kwantowej wielkość charakteryzująca nieuporządkowanie układu, zdefiniowana dla macierzy gęstości ρ jako:

Dla układu kwantowego który jest w stanie czystym entropia von Neumanna wynosi 0.

Ponieważ operator gęstości układu zawsze można przedstawić w postaci diagonalnej w bazie jego wektorów własnych, równoważną definicję entropii von Neumann daje wzór:

gdzie
to wartości własne operatora ρ.

W informatyce kwantowej entropia von Neumanna jest wykorzystywana jako podstawa kilku miar splątania. Jedną z nich jest zredukowana entropia von Neumanna, która jest zdefiniowana jako entropia von Neumanna dla zredukowanej macierzy gęstości układu. Kolejny temat, jakim się zajmiemy, to zasadnicze metody kodowania. Mamy trzy rodzaje takich metod. Jest to: kodowanie Huffmanna, arytmetyczne i słownikowe. Kodowanie Huffmana to jedna z najprostszych i łatwych w implementacji metod kompresji bezstratnej. Została opracowana w 1952 roku przez Amerykanina Davida Huffmana.Algorytm Huffmana nie należy do najefektywniejszych systemów bezstratnej kompresji danych, dlatego też praktycznie nie używa się go samodzielnie. Często wykorzystuje się go jako ostatni etap w różnych systemach kompresji, zarówno bezstratnej jak i stratnej jak MP3 lub JPEG. Pomimo, że nie jest doskonały, stosuje się go ze względu na prostotę oraz brak ograniczeń patentowych. Dany jest alfabet źródłowy (zbiór symboli)
oraz zbiór stowarzyszonych z nim prawdopodobieństw
. Symbolami są najczęściej bajty, choć nie ma żadnych przeszkód żeby było nimi coś innego (pary znaków). Prawdopodobieństwa mogą zostać z góry określone dla danego zestawu danych poprzez wyznaczenie częstotliwości występowania znaków w tekstach danego języka. Częściej jednak wyznacza się je indywidualnie dla każdego zestawu danych. Kodowanie Huffmana polega na utworzeniu słów kodowych (ciągów bitowych), których długość jest odwrotnie proporcjonalna do prawdopodobieństwa p_i. Im częściej dane słowo występuje (może wystąpić) w ciągu danych, tym mniej zajmie bitów. Własności kodu są następujące. Kod Huffmana jest kodem prefiksowym. Oznacza to, że żadne słowo kodowe nie jest początkiem innego słowa. Jeśli prawdopodobieństwa są różne, czyli p_j > p_i, to długość kodu dla symbolu x_j jest niewiększa od kodu dla symbolu x_i. Pamiętac należy, że słowa kodu dwóch najmniej prawdopodobnych symboli mają równą długość, a dwa najdłuższe symbole różnią się tylko jednym, ostatnim bitem. Kompresja polega na zastąpieniu symboli otrzymanymi kodami. Algorytm Huffmanna wygląda nastepująco:

1. Określ prawdopodobieństwo (lub częstość występowania) dla każdego symbolu ze zbioru S.

2. Utwórz listę drzew binarnych, które w węzłach przechowują pary: symbol, prawdopodobieństwo. Na początku drzewa składają się wyłącznie z korzenia.

3. Dopóki na liście jest więcej niż jedno drzewo powtarzaj:

• Usuń z listy dwa drzewa o najmniejszym prawdopodobieństwie zapisanym w korzeniu.

• Wstaw nowe drzewo, w którego korzeniu jest suma prawdopodobieństwusuniętych drzew, natomiast one same stają się jego lewym i prawym poddrzewem. Korzeń drzewa nie przechowuje symbolu.

Drzewo, które pozostanie na liście, jest nazywane drzewem Huffmana - prawdopodobieństwo zapisane w korzeniu jest równe 1, natomiast w liściach drzewa zapisane są symbole. Algorytm Huffmana jest algorytmem niedeterministycznym ponieważ nie określa w jakiej kolejności wybierać drzewa z listy, jeśli mają takie samo prawdopodobieństwo. Nie jest również określone, które z usuwanych drzew ma stać się lewym bądź prawym poddrzewem. Jednak bez względu na przyjęte rozwiązanie średnia długość kodu pozostaje taka sama.Na podstawie drzewa Huffmana tworzone są słowa kodowe. Algorytm jest następujący:

1. Każdej lewej krawędzi drzewa przypisz 0, prawej 1 (można oczywiście odwrotnie).

2. Przechodź w głąb drzewa od korzenia do każdego liścia (symbolu):

1. Jeśli skręcasz w prawo dopisz do kodu bit o wartości 1.

2. Jeśli skręcasz w lewo dopisz do kodu wartości 0.

Długość słowa kodowego jest równa głębokości symbolu w drzewie, wartość binarna zależy od jego położenia w drzewie.

Oto przykład. Mamy symbole A, B, C, D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].

• Łączymy węzły odpowiadające symbolom (A) i (B). Teraz mamy (A + B) = 0.3, (C) = 0.3, (D) = 0.4

• Łączymy węzły odpowiadające drzewku (A + B) oraz (C). Teraz mamy ((A + B) + C)=0.6 i (D) = 0.4

• Łączymy węzły odpowiadające drzewku ((A + B) + C) oraz (D). Teraz mamy tylko jeden wolny węzeł - drzewko (((A + B) + C) + D) = 1.0

• Obliczamy kody znaków:

• A = lewo, lewo, lewo= 000

• B = lewo, lewo, prawo = 001

• C = lewo, prawo = 01

• D = prawo = 1

Jak łatwo sprawdzić średnia długość kodu wyniesie:
.

Jest to mniej niż 2 bity potrzebne w trywialnym kodowaniu o stałej długości znaku. Z kolei entropia źródła wynosi: E = − 0.1log₂0.1 − 0.2log₂0.2 − 0.3log₂0.3 − 0.4log₂0.4 = 1.8464 - optymalne kodowanie powinno charakteryzować się taką właśnie średnią długością kodu. Jednak widać, że jest ona większa - efektywność wynosi w tym przypadku:

.

Jednym z głównych problemów stosowania statycznego algorytmu Huffmana jest konieczność transmisji całego drzewa lub całej tablicy prawdopodobieństw (zwykle to drugie jako bardziej efektywne).Lepszą kompresję, kosztem jednak bardzo szybkiego wzrostu wymagań pamięciowych, uzyskuje się kodując kilka kolejnych znaków na raz, nawet jeżeli nie są one skorelowane. Oto przykład kodowania po 2 znaki naraz:

• Symbole to tak jak wtedy - A,B,C,D o prawdopodobieństwach wystąpienia odpowiednio [0.1, 0.2, 0.3, 0.4].

• Jeśli liczba symboli jest nieparzysta, robimy coś z pierwszym lub ostatnim symbolem. Nie jest to w praktyce duży problem.

• Zastępujemy symbole parami symboli - AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD o prawdopodobieństwach odpowiednio - [0.01, 0.02, 0.03, 0.04, 0.02, 0.04, 0.06, 0.08, 0.03, 0.06, 0.09, 0.12, 0.04, 0.08, 0.12, 0.16].

• Drzewko rośnie po kolei:

• (AA + AB) = 0.03

• (BA + AC) = 0.05

• (CA + (AA + AB)) = 0.06

• (BB + AD) = 0.08

• (DA + (BA + AC)) = 0.09

• (BC + CB) = 0.12

• ((CA + (AA + AB)) + BD) = 0.14

• (DB + (BB + AD)) = 0.16

• ((DA + (BA + AC)) + CC) = 0.18

• (CD + DC) = 0.24

• ((BC + CB) + ((CA + (AA + AB)) + BD)) = 0.26

• (DD + (DB + (BB + AD))) = 0.32

• (((DA + (BA + AC)) + CC) + (CD + DC)) = 0.42

• (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD)))) = 0.58

• ((((DA + (BA + AC)) + CC) + (CD + DC)) + (((BC + CB) + ((CA + (AA + AB)) + BD)) + (DD + (DB + (BB + AD))))) = 1.0

Zatem odpowiednim parom znaków odpowiadają:

• AA - 101010

• AB - 101011

• AC - 00011

• AD - 11111

• BA - 00010

• BB - 11110

• BC - 1000

• BD - 1011

• CA - 10100

• CB - 1001

• CC - 001

• CD - 010

• DA - 0000

• DB - 1110

• DC - 011

• DD - 110

Średnia liczba bitów przypadająca na parę symboli to 3.73, a więc średnia liczba bitów na symbol to 1.865. Jest to znacznie lepsza kompresja (6.75% zamiast 5% przy maksymalnej możliwej 7.68%) niż poprzednio. Używając większej liczby znaków można dowolnie przybliżyć się do kompresji maksymalnej, jednak znacznie wcześniej wyczerpie się pamięć, ponieważ wymagania pamięciowe rosną wykładniczo do liczby kompresowanych jednocześnie symboli. Kolejny rodzaj kodowania, to kodowanie arytmetyczne. Kodowanie arytmetyczne to metoda kodowania źródłowego dyskretnych źródeł sygnałów, stosowana jako jeden z systemów w bezstratnej kompresji danych. Została wynaleziona przez Petera Eliasa około 1960 roku. Ideą tego kodu jest przedstawienie ciągu wiadomości jako podprzedziału przedziału jednostkowego [0,1) wyznaczonego rekursywnie na podstawie prawdopodobieństw wystąpienia tychże wiadomości generowanych przez źródło. Ciąg kodowy reprezentujący kodowane wiadomości jest binarnym zapisem wartości z wyznaczonego w ten sposób przedziału. Można udowodnić, że przy wyborze odpowiednio długiego ciągu wiadomości do zakodowania, średnia liczba symboli na wiadomość jest mniejsza od H(X) + 2, gdzie H(X) jest entropią źródła, lecz większa bądź co najwyżej równa samej entropii. Oto, jak przedtastawia się algorytm takiego kodowania. Dany jest zbiór symboli
oraz stowarzyszony z nim zbiór prawdopodobieństw
. Jeden z symboli jest wyróżniony - jego wystąpienie oznacza koniec komunikatu, zapobiegając wystąpieniu niejednoznaczności. Na początku dany jest przedział P = [0,1), który dzielony jest na podprzedziały o szerokościach równych kolejnym prawdopodobieństwom p_i, czyli otrzymywany jest ciąg podprzedziałów

Kolejnym podprzedziałom (ozn. R_i) odpowiadają symbole ze zbioru S. I teraz:

• Dla kolejnych symboli symbol c.

• Określ, który podprzedział bieżącego przedziału P odpowiada literze c - wynikiem jest R_i.

• Weź nowy przedział P: = R_i - następuje zawężenie przedziału

• Podziel ten przedział P na podprzedziały w sposób analogiczny jak to miało miejsce na samym początku (chodzi o zachowanie proporcji szerokości podprzedziałów).

• Zwróć liczbę jednoznacznie wskazującą przedział P (najczęściej dolne ograniczenie, albo średnia dolnego i górnego ograniczenia).

Oto przykład. Na rysunku pokazano, jak zmienia się aktualny przedział P w trzech pierwszych krokach kodowania. Kodowane są cztery symbole o prawdopodobieństwach p = {0.6,0.2,0.1,0.1} w kolejności: pierwszy, trzeci, czwarty.

Zobaczmy na jeszcze inny przykład. Niech
(
- koniec komunikatu), prawdopodobieństwa p = {0.45,0.3,0.2,0.05}.Zakodowany zostanie ciąg
.

• Początkowo przedział P = [0,1), jest on dzielony na podprzedziały [0,0.45),[0.45,0.75),[0.75,0.95),[0.95,1).

• Pierwszym kodowany symbolem jest c, któremu odpowiada 3. podprzedział, zatem P: = R₃ = [0.75,0.95). Nowy przedział znów jest dzielony: [0.75,0.84),[0.84,0.9),[0.9,0.94),[0.94,0.95).

• Kolejnym kodowanym symbolem jest a, któremu odpowiada 1. podprzedział, zatem P: = R₁ = [0.75,0.84). Nowy przedział znów jest dzielony: [0.75,0.7905),[0.7905,0.8175),[0.8175,0.8355),[0.8355,0.84).

• Kolejnym kodowanym symbolem jest b, któremu odpowiada 2. podprzedział, zatem P: = R₂ = [0.7905,0.8175). Nowy przedział znów jest dzielony: [0.7905,0.80265),[0.80265,0.81075),[0.81075,0.81615),[0.81615,0.8175).

• Kolejnym kodowanym symbolem jest (ponownie) a, któremu odpowiada 1. podprzedział, zatem P: = R₁ = [0.7905,0.80265). Nowy przedział znów jest dzielony: [0.7905,0.795968),[0.795968,0.799612),[0.799612,0.802042),[0.802042,0.80265).

• Kolejnym kodowanym symbolem jest
  , kończący kodowanie, któremu odpowiada 4. podprzedział, zatem P: = R₄ = [0.802042,0.80265).

• Na wyjście zostaje zapisana liczba identyfikująca ten przedział - może to być, jak wspomniano, jego dolne ograniczenie, czyli 0.802042.

I na zakończenie tematu powiemy nieco o kodowaniu słoqnikowym. Jest to kodowanie danych, w którym podciągi komunikatu koduje się za pomocą słów ze słownika (zbioru słów), zapisując ich pozycję (indeks) w słowniku. Takie metody dobrze kompresują dane, w których podciągi powtarzają się, np. w przypadku tekstów naturalnych (teksty książek, czasopism itp.) wiele słów a nawet całych fraz występuje wielokrotnie. Powszechnie stosuje się metody kodowania słownikowego, w których słownik jest dynamiczny, budowany na podstawie kodowanych danych. Słownik dynamiczny ma zwykle ograniczony rozmiar. Metody ze słownikiem dynamicznym to LZ77, LZ78, LZSS, LZW i pochodne. Słownik może być również statyczny, zadany z góry. Jednak słownik może nie obejmować wszystkich możliwych słów - podciągi nie występujące w słowniku muszą zostać w jakiś sposób zapisane (zapamiętane wprost). Rozpatrzmy przykład. Niech naszym alfabetem wyjściowym będzie alfabet złożony z liter A, B, C i D. Nasz słownik nich przyjmie postać:

1 2 3 4 5 6 7 8 9 10 11 12

A B C D AA BB CC DD AAA BBB CCC DDD

Niech nasz tekst wygląda nastepująco: AABABACBAACBAADAAA. Po zakodowaniu tego słowa ta metodą, będzie ono miało nastepującą postać:

AA B A B A C B AA C B AA D AAA

5 2 1 2 1 3 2 5 3 2 5 4 9

---