PPM (kompresja)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

PPM (ang. Prediction by partial matching – przewidywanie przez częściowe dopasowanie) to 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 w oparciu o model 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 na raz. 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 implementacji nie stały się powszechne do wczesnych lat 90. ponieważ algorytmy PPM mają duże wymagania odnośnie pamięci RAM. Drugą 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.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]