KiK-Modul-4.pdf

(192 KB) Pobierz
Kodowanie predykcyjne.
Jak wielokrotnie wspominaliśmy wykorzystanie wiedzy o charakterystycznej strukturze
kodowanych danych umożliwia uzyskanie znacznie lepszego stopnia kompresji.
Wiemy na przykład, że entropia dla modelu probabilistycznego o zróżnicowanych
prawdopodobieństwach jest niższa niż dla modelu, w którym prawdopodobieństwa
rozłożone są równomiernie na wszystkie litery alfabetu źródła. W kodowaniu Huffmana
symbole o największym prawdopodobieństwie mają najkrótsze słowa kodowe, więc
zwiększenie liczby takich symboli wpływa na skrócenie długości kodu. W kodowaniu
arytmetycznym również uzyskujemy znacznie lepszą kompresję jeśli
prawdopodobieństwa są zróżnicowane.
Możemy zastosować przekształcenie odwzorowujące elementy oryginalnego ciągu w
ciąg symboli o bardziej zróżnicowanym prawdopodobieństwie ich występowania.
Moglibyśmy również starać się spowodować aby każdy kodowany symbol miał jak
największe prawdopodobieństwo wystąpienia. Aby to uczynić można, na przykład,
używać innego rozkładu prawdopodobieństwa dla każdego z kodowanych symboli, tak
by ten rozkład miał pożądane właściwości maksymalizacji prawdopodobieństwa
wystąpienia danego symbolu.
Oczywiście aby zakodowany ciąg można było odkodować dekoder musi wiedzieć z
jakiego rozkładu prawdopodobieństwa w danej chwili korzystał koder.
Generowanie tych dodatkowych informacji dla dekodera może być nieefektywne i
powodować znaczne zwiększenie długości kodowanego ciągu. Dlatego też należałoby
znaleźć takie rozwiązanie aby dekoder mógł tą informację utworzyć samodzielnie.
Metodą, która się tu narzuca jest wykorzystanie wiedzy o wcześniejszych, już
zakodowanych symbolach (historii ciągu) do przewidywania wartości kolejnych
elementów kodowanego ciągu.
Wtedy dekoder odkodowując sukcesywnie elementy ciągu będzie miał dostęp do tej
samej informacji co koder i będzie mógł dokonywać analogicznych operacji
przewidując rozkład prawdopodobieństwa lub przekształcenia użyte przez koder do
zakodowania kolejnych symboli.
Kodowanie, w którym wykorzystujemy wiedzę o wcześniej zakodowanej części ciągu
do kodowania następnych jego elementów nazywamy kodowaniem predykcyjnym.
Rozważmy następujący następujący fragment ciągu symboli generowanych niezależnie
przez źródło:
1 2 5 7 2 -2 0 -5 -3 -1 1 -2 -7 -4 -2 1 3 4
Zakładając, że prawdopodobieństwa wszystkich liczb z przedziału [-7, 7] są bardzo
zbliżone otrzymujemy szacunkową wartość entropii około
4 bity na symbol.
Zdefiniujmy przekształcenie:
x
n
= 2 + x
n-1
+ r
n
, gdzie
x
n
kolejnym n-tym elementem
oryginalnego,
x
n-1
jest poprzedzającym go elementem ciągu, a
r
n
jest n-tym elementem
ciągu odchyleń (odchylenie wartości elementu x
n
od przewidywanej wartości 2 + x
n-1
).
Zapiszmy ciąg odchyleń:
1 -1 1 0 -7 -4 0 -7 0 0 0 -5 -7 1 0 1 0 -1
Przekształcenie to przewiduje wartość następnego elementu ciągu na podstawie
znajomości wartości poprzednich elementów (tutaj tylko poprzedniego) czyli historii
ciągu.
W tym przypadku zależność ta jest bardzo prosta: przewidujemy, że wartość następnego
elementu jest o 2 większa od wartości poprzedniego elementu. To co kodujemy to
odchylenia od wartości przewidywanej.
Ciąg odchyleń ma tę samą długość co ciąg oryginalny ale prawdopodobieństwa są tu dużo
bardziej zróżnicowane - wartości
0, -1, 1
występują znacznie częściej (mają znacznie
większe prawdopodobieństwo występowania) niż inne wartości.
Entropia dla tego rozkładu wynosi szacunkowo około
2 bity na symbol,
czyli możliwa jest
znacznie lepsza kompresja niż dla ciągu oryginalnego.
W przykładzie tym użyliśmy predykcji, czyli przewidywania wartości kolejnych symboli
na podstawie znajomości symboli ich poprzedzających. Jednak predykcja polegająca na
wykorzystaniu prostych przekształceń matematycznych ma znikome zastosowanie przy
kodowaniu danych nienumerycznych, a w szczególności tekstu.
To co jest przydatne przy predykcyjnym kodowaniu tekstów to kontekst, czyli rozkład
prawdopodobieństwa występowania poszczególnych liter w zależności od ciągu liter
bezpośrednio poprzedzającego daną literę. Wiemy na przykład, że dla tekstu w języku
polskim prawdopodobieństwo tego, iż po literze
a
wystąpi
a, o, ó
czy
ą
jest znikome a
prawdopodobieństwa wystąpienia spółgłosek
t
czy
r
są bardzo duże. Uzyskaliśmy, więc
zwiększenie zróżnicowanie rozkładu prawdopodobieństwa w porównaniu z rozkładem
występowania poszczególnych liter bez kontekstu. Jak łatwo zauważyć zwiększając
długość kontekstu (czyli liczbę branych pod uwagę liter poprzedzających) zwiększamy
zróżnicowanie rozkładu.
Liczba poprzedzających liter tworzących kontekst jest nazywana
rzędem kontekstu.
Na przykład
raw
jest kontekstem rzędu 3 dla litery
d
w wyrazie
prawdopodobieństwo.
Czym wyższy będzie rząd kontekstu użytego do zakodowania
d,
tym większe będzie
prawdopodobieństwo występowania tej litery i tym mniej bitów będziemy musieli użyć
do jej zakodowania.
Niestety występuje tu już wcześniej wspomniany problem: liczba możliwych
kontekstów rzędu
k
dla alfabetu o rozmiarze
M
wynosi
M
k
co jest wielkością rosnącą
wykładniczo przy zwiększaniu rzędu kontekstu. Wyznaczenie tak wielkich zbiorów
prawdopodobieństw jest niepraktyczne, a często wręcz niemożliwe.
Algorytmy, które rozwiązują ten problem noszą nazwę predykcji z częściowym
dopasowaniem (prediction with partial matching, ppm).
Predykcja z częściowym
dopasowaniem (ppm).
A
lgorytm ppm został opublikowany w 1984 roku przez Cleary’ego i Wittena.
Idea algorytmu polega na tym aby wyznaczać prawdopodobieństwa
występowania symboli ciągu w poszczególnych kontekstach dopiero
podczas kodowania (czyli tylko dla symboli i kontekstów, które już
wystąpiły w zakodowanej części ciągu).
P
ozwala na stosowanie stosunkowo długich kontekstów bez konieczności
wstępnego obliczania ogromnej ilości prawdopodobieństw warunkowych.
W
celu zakodowania liter, które pojawiają się w określonym kontekście po raz
pierwszy używa się tu specjalnego symbolu dodanego do alfabetu źródła. Symbol
ten nazwiemy symbolem wyjścia. Jego zakodowanie oznacza, że dana litera nie
pojawiła się wcześniej w danym kontekście.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin