PPM (kompresja)

PPM (ang. Prediction by Partial Matching – przewidywanie przez częściowe dopasowanie) – adaptacyjny algorytm kompresji danych oparty na kontekstowym modelowaniu statystycznym oraz predykcji. Algorytm PPM wykorzystuje układ symboli w strumieniu danych do przewidywania kolejnego symbolu. Zwykle predykcja opiera się na tworzeniu statystycznego rankingu występowania symboli. Pewna liczba poprzednich symboli wykorzystywanych w danym kroku do predykcji (n) jest określana jako rząd modelu PPM, który oznacza się jako PPM(n). Istnieją warianty algorytmu, w których rząd modelu nie jest z góry narzucany, oznaczane jako PPM*. Jeżeli przewidywanie nie może zostać dokonane na podstawie modelu o rzędzie n-tym, to jego rząd jest zmniejszany o jeden. Proces jest powtarzany aż do uzyskania poprawnej predykcji lub gdy strumień danych został wyczerpany. W tym momencie wykonywana jest ustalona predykcja.

Implementacje algorytmu PPM często różnią się znacznie wieloma szczegółami. Symbole mogą być kodowane poprzez kodowanie arytmetyczne, Huffmana bądź też pewne typy kodowania słownikowego. Podstawowy algorytm może zostać rozszerzony, aby przewidywać kilka symboli naraz. Rozmiar symbolu jest najczęściej stały i odpowiada jednemu bajtowi, co ułatwia przetwarzanie różnorodnych typów plików.

Algorytm PPM opracowali i opublikowali w 1984 roku Cleary oraz Witten, jednak implementacje nie stały się powszechne do wczesnych lat 90., ponieważ algorytmy PPM mają duże wymagania odnośnie do pamięci RAM. Drugą negatywną cechą, która wpływa na rzadkie stosowanie algorytmu PPM, jest czas dekompresji, który jest podobny do czasu samej kompresji. Obecnie implementacje algorytmu PPM są jednymi z najlepszych algorytmów do kompresji języków naturalnych, a co za tym idzie – do kompresji plików tekstowych i baz danych zawierających duże ilości znaków alfanumerycznych.

Zobacz też

Bibliografia

T. Bell, J. Cleary, and I. Witten (University of Waikato, New Zealand)(1984) Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, Vol. 32 (4), p. 396-402.
A. Moffat (1990) Implementing the PPM data compression scheme. IEEE Transactions on Communications, Vol. 38 (11), p. 1917-1921.
J. Cleary, W. Teahan, and I. Witten (1995) Unbounded length contexts for PPM. In J.A. Storer and M. Cohn, editors, Proceedings DCC-95. IEEE Computer Society Press.
C. Bloom (nieznany) Rozwiązywanie problemów przez modelowanie kontekstowe.
W. Teahan (nieznany) Szacowanie prawdopodobieństwa dla PPM.

Linki zewnętrzne

Lista zasobów, źródeł oraz samouczków dotyczących PPM. compression-links.info. [zarchiwizowane z tego adresu (2006-10-17)]. (ang.).
Dyskusja w Usenecie dotycząca kompresji wyższego rzędu (ang.)
Źródło kompresora PAQ4 wykorzystującego PPM (ang.)
BICOM, kompresor PPM (ang.)
Artykuł dotyczący PPM: „Kodowane artytmetyczne + Modelowanie statystyczne = Kompresja danych”, część 2. dogma.net. [zarchiwizowane z tego adresu (2006-05-02)]. (ang.).