PPM (kompresja)

Z Wikipedii

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 tworzenie statystycznego rankingu występowania symboli. Pewna ilość 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. Obecnie implementacje algorytmu PPM są jednymi z najlepszych algorytmów do kompresji języków naturalnych.

[edytuj] Zobacz też

• Kompresja danych (informatyka)
• Kompresja bezstratna
• Kodowanie Huffmana
• Kodowanie arytmetyczne

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

[edytuj] Linki zewnętrzne

• Lista zasobów, źródeł oraz samouczków dotyczących PPM (en)
• Dyskusja w Usenecie dotyczące kompresji wyższego rzędu (en)
• Źródło kompresora PAQ4 wykorzystującego PPM (en)
• BICOM, kompresor PPM (en)
• Artykuł dotyczący PPM: "Kodowane artytmetyczne + Modelowanie statystyczne = Kompresja danych", część 2 (en)