Z Wykład 02.03.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych


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:

t=pi
słowo kodowe S
int licznik=0;
bin(t)
{
    if(li>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: 0x01 graphic
. Dla kodu Shannona będzie określona wzorem: 0x01 graphic
. 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 0x01 graphic
, 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ę:

0x01 graphic

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:

0x01 graphic

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

0x01 graphic

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:

0x01 graphic

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:

0x01 graphic

gdzie 0x01 graphic
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) 0x01 graphic
oraz zbiór stowarzyszonych z nim prawdopodobieństw 0x01 graphic
. 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 pi. 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 pj > pi, to długość kodu dla symbolu xj jest niewiększa od kodu dla symbolu xi. 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:

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

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

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.1log20.1 − 0.2log20.2 − 0.3log20.3 − 0.4log20.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:

0x01 graphic
.

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:

Zatem odpowiednim parom znaków odpowiadają:

Ś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 0x01 graphic
oraz stowarzyszony z nim zbiór prawdopodobieństw 0x01 graphic
. 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 pi, czyli otrzymywany jest ciąg podprzedziałów

0x01 graphic

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

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 0x01 graphic
(0x01 graphic
- koniec komunikatu), prawdopodobieństwa p = {0.45,0.3,0.2,0.05}.Zakodowany zostanie ciąg 0x01 graphic
.

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



Wyszukiwarka

Podobne podstrony:
Z Wykład 17.05.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Z Wykład 20.04.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Z Ćwiczenia 19.04.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Z Labolatoria 31.05.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Prawo ochrony srodowiska wyklad 02.03.05, administracja, II ROK, III Semestr, rok II, sem IV, pr
Z Ćwiczenia 14.06.2008, Zajęcia, II semestr 2008, Algorytmy i struktury danych
Postepowanie administracyjne wyklad 02.03.05, administracja, II ROK, III Semestr, rok II, sem IV,
Wyklad 02.03.2011, PWR, Zarządzanie, SEMESTR IV, Zarządzanie produkcją i usługami
Z Wykład 15.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Wykład 23.02.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Z Wykład 01.03.2008, Zajęcia, II semestr 2008, Rachunek prawdopodobieństwa
Z Wykład 16.03.2008, Zajęcia, II semestr 2008, Techniki Internetowe
Z Wykład 29.03.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Z Wykład 24.02.2008, Zajęcia, II semestr 2008, Teoria informacji i kodowania
Z Wykład 30.03.2008, Zajęcia, II semestr 2008, Teoria informacji i kodowania
Z Wykład 15.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna
Wykład z dnia 10.05.2008, Zajęcia, II semestr 2008, Matematyka dyskretna i logika
Z Ćwiczenia 29.03.2008, Zajęcia, II semestr 2008, Wstęp do kryptologii
Z Ćwiczenia 15.03.2008, Zajęcia, II semestr 2008, Analiza matematyczna

więcej podobnych podstron