Podręcznik

6. Kompresja informacji

6.1. Wstęp

Kompresja informacji to inaczej kompresja danych. Dokładniej, konkretna metoda kompresji danych to zawsze 2 algorytmy:

algorytm kompresji danych
algorytm rekonstrukcji danych

Kompresję dzielimy na 2 kategorie: kompresję stratną i kompresję bezstratną. Jeśli dane poddawane kompresji potrafimy odtworzyć, zrekonstruować w dokładnie takiej samej postaci jak dane poddawane kompresji to kompresję nazywamy bezstratną. W przeciwnym razie kompresja jest kompresją stratną.

Rodzaj kompresji zależy również od danych poddawanych kompresji. Tak więc mamy:

kompresję plików tekstowych
kompresję plików dźwiękowych (kompresja audio)
kompresję obrazów statycznych
kompresję sekwencji video czyli obrazów dynamicznych (obrazów ruchomych)

Model probabilistyczny generacji danych przez źródło danych: W zagadnieniach związanych z kompresją danych bardzo ważny jest model matematyczny generacji danych. Załóżmy, że obiektami kodowanymi są litery (symbole) z pewnego alfabetu V₁ {a1 , a2 ,..., an } i znamy prawdopodobieństwo pojawienia się każdej litery tzn. podane są prawdopodobieństwa P(a_i)  p_i dla i  1, 2,..., n . Jeśli przyjmiemy, że słowo nad alfabetem V₁ {a1 , a2 ,..., an } generowane jest przez źródło danych jako ciąg niezależnych k losowań liter (podobnie jak w ciągu k doświadczeń Bernoulliego) to otrzymujemy w naturalny rozkład prawdopodobieństwa na zbiorze V₁ ^kwszystkich słów o długości k .

Ważnym parametrem charakteryzującym źródło danych jest entropia źródła. Jest to liczba definiowana wzorem:

H   $\displaystyle\sum^{n}_{i=1}$ p_ilog₂p_i i1

Shannon udowodnił, że najlepszym rezultatem (przy kodowaniu binarnym) jaki można uzyskać za pomocą algorytmu kompresji bezstratnej jest taki algorytm kodowania (taki kod binarny k : V₁  {0,1}^) by średnia bitów wykorzystanych do kodowania liter z alfabetu była równa entropii źródła.

Podstawowy pomysł na kompresję jest następujący. Obiekty kodowane występujące częściej (czyli o większym prawdopodobieństwie wystąpienia) powinny być kodowane krótszym słowem a obiekty występujące rzadziej (o mniejszym prawdopodobieństwie) dłuższym słowem. Takie rozwiązanie wykorzystywane jest w znanym każdemu harcerzowi kodzie zwanym „alfabetem Morse’a”. Na przykład litera „e” często pojawiająca się w tekstach angielskich jest kodowana za pomocą jednej kropki (słowo o długości 1 nad alfabetem V₂ {□, } ).

Jednoznaczna dekodowalność: Dosyć ważną użyteczną własnością kodu jest jego jednoznaczna dekodowalność. Oto definicja tej własności. Niech V₁ {a1 , a2 ,..., an } . Kod k : V₁  V ^ nazywamy jednoznacznie dekodowalnym jeżeli każdy ciąg słów kodowych daje 2 się odkodować w dokładnie jeden sposób tzn. nie ma dwóch różnych słów   ₁₂..._m,   ₁₂..._m nad alfabetem V₁dających (po zakodowaniu każdej litery z V₁i konkatenacji uzyskanych słów kodowych) to samo słowo tzn. nie może być

k(₁)k(₂)...k (_m)  k(₁)k(₂)...k(_m)

Prefiks i sufiks. Niech V będzie dowolnym ustalonym alfabetem oraz   a₁a₂...a_nsłowem nad alfabetem V, wówczas każde słowo a₁a₂...a_k, gdzie 1  k  n nazywamy prefiksem słowa   a₁a₂...a_n a każde słowo a_ka₂...a_n, gdzie 1  k  n nazywamy sufiksem słowa   a₁a₂...a_n. Jednocześnie słowo puste jest sufiksem i prefiksem każdego słowa.

Kod prefiksowy. Kod prefiksowy to kod w którym żadne słowo kodowe nie jest prefiksem innego słowa kodowego.

Istota rzeczy jest tu taka. Załóżmy, ze odbieramy słowo kodowe litera po literze. W kodzie prefiksowym patrząc na słowo kodowe nie mamy wątpliwości czy to już koniec słowa kodowego czy być może tylko początkowy fragment innego słowa kodowego.

Kody prefiksowe są w oczywisty sposób jednoznacznie dekodowalne.

Jeśli stosujemy kody o zmiennej długości słowa kodowego to ważnym pojęciem jest średnia długość słowa kodowego. W przypadku słów binarnych średnią długość słowa kodowego nazywamy średnią bitową kodu. Dokładniej, niech źródło danych będzie takie, 2 że V₁ {a1 , a2 ,..., an } oraz prawdopodobieństwa P(a_i)  p_i dla i  1, 2,..., n . Średnią długością kodu k : V₁  V₂ ^ nazywamy liczbę

l  $\displaystyle\sum^{n}_{i=1}$ P(a_i)l(k(a_i))

gdzie l( ) oznacza długość słowa 

Twierdzenie (warunek konieczny dekodowalności kodu, nierówność Krafta-McMillana):

Jeśli K jest zbiorem słów kodowych (binarnych) o długościach l₁, l₂,..., l_n N i kod k : V₁ K jest jednoznacznie dekodowany to spełniony jest następujący warunek n tzw. nierówność Krafta-McMillana

$\displaystyle\sum^{n}_{i=1}$ 2^^l^_i 1

Twierdzenie (warunek wystarczający istnienia kodu prefiksowego):

Jeśli l₁, l₂,..., l_n N spełniają nierówność

$\displaystyle\sum^{n}_{i=1}$ 2^^l^_i 1

to można znaleźć dla n elementowego alfabetu V₁ {a1 , a2 ,..., an } kod prefiksowy k : V₁  {0,1}^o długościach słów kodowych wynoszących l , l ,..., l_n.