Prediction by Partial Matching
Prediction by Partial Matching (PPM, englisch) ist eine Familie anpassender statistischer Datenkompressionsalgorithmen, die auf Kontextmodellen und Prognosen aufbaut. PPM-Modelle benutzen einen Satz von Symbolen aus dem vorangegangenen Symbolstrom, um das nächste Symbol des Stromes vorherzusagen.
Voraussagen werden üblicherweise auf Wertungen der Symbole beschränkt. Die Zahl vorhergehender Symbole, , legt die Ordnung des PPM-Modelles fest, das als PPM(n) festgehalten wird. Unbegrenzte Varianten ohne Beschränkungen der Länge des Kontextes existieren auch und werden mit PPM* bezeichnet. Wenn aufgrund aller n Kontextsymbole keine Vorhersage gemacht werden kann, so wird eine Prognose aufgrund von versucht. Dieses Vorgehen wird wiederholt, bis ein Treffer gefunden wird oder keine Symbole im Kontext verbleiben. Zu diesem Zeitpunkt wird eine Vorhersage festgelegt. Dieser Prozess ist die Umkehrung dessen, gefolgt von dynamischen Markow-Vorhersagen, die von einem Modell der Ordnung 0 aufbauen.
Ein großer Teil der Arbeit an der Optimierung eines PPM-Modells betrifft den Umgang mit Eingaben, die im Eingabestrom noch nicht auftraten. Der offensichtliche Weg damit umzugehen besteht darin, ein „Unbekannt-Symbol“ zu erzeugen, das die Escape-Sequenz auslöst. Doch welche Wahrscheinlichkeit soll einem Symbol zugeordnet werden, das noch nie aufgetreten ist? Dies wird das Problem der 0-Häufigkeit genannt. Eine Vorgehensweise teilt dem „Unbekannt-Symbol“ einen festgelegten Pseudowert von 1 zu. Eine PPM-D genannte Variante erhöht den Pseudowert bei jedem Auftritt des „Unbekannt-Symbols“. (Anders ausgedrückt schätzt PPM-D also die Wahrscheinlichkeit eines neuen Symbols als das Verhältnis der Anzahl einzigartiger Symbole zur Anzahl aller Symbole insgesamt.)
Umsetzungen von Kompression mittels PPM sind in anderen Details sehr unterschiedlich. Die eigentliche Symbolauswahl wird üblicherweise arithmetisch kodiert, obwohl auch Huffman-Kodierung oder auch eine Art Wörterbuchkodierung möglich sind. Das zugrunde liegende Modell der meisten PPM-Algorithmen kann auch erweitert werden, um mehrere Symbole vorherzusagen. Es ist auch möglich, andere als die Markow-Modellerstellung zu verwenden, um diese entweder ganz zu ersetzen oder zu ergänzen. Die Symbolgröße ist für gewöhnlich statisch, typischerweise ein einzelnes Byte, was die generische Unterstützung jeglicher Dateiformate leicht macht.
Veröffentlichungen über Forschungen an dieser Algorithmusfamilie finden sich bis zurück in die Mitte der 1980er Jahre. Softwareumsetzungen erfreuten sich bis zu den frühen 1990er Jahren keiner Beliebtheit, da PPM-Algorithmen eine beachtliche Menge an Arbeitsspeicher benötigen. Neuere Umsetzungen von PPM finden sich unter den leistungsfähigsten verlustfreien Datenkompressionsverfahren für Text in natürlichen Sprachen.
Der Versuch, PPM-Algorithmen zu verbessern, führte zu den PAQ-Kompressionsalgorithmen.
Literatur
- J. Cleary, I. Witten: Data Compression Using Adaptive Coding and Partial String Matching. In: Communications, IEEE Transactions on. Band 32, Nr. 4, 1984, S. 396–402, doi:10.1109/TCOM.1984.1096090.
- A. Moffat: Implementing the PPM data compression scheme. In: Communications, IEEE Transactions on. Band 38, Nr. 11, 1990, S. 1917–1921, doi:10.1109/26.61469.
- J. G. Cleary, W. J. Teahan, I. H. Witten: Unbounded length contexts for PPM. In: Proceedings DCC-95. IEEE Computer Society Press, 1995 (cs.waikato.ac.nz [PDF]). Alternativ: J. G. Cleary, W. J. Teahan: Unbounded Length Contexts for PPM. In: The Computer Journal. Band 40, Nr. 2–3, 1997, S. 67–75, doi:10.1093/comjnl/40.2_and_3.67.
- C. Bloom, Solving the problems of context modeling (ZIP; 43 kB).
- W. J Teahan: Probability estimation for PPM. In: Proceedings NZCSRSC'95. 1995 (cotty.16x16.com [abgerufen am 28. Februar 2011]).
- Thomas Schürmann, Peter Grassberger: Entropy estimation of symbol sequences. In: Chaos: An Interdisciplinary Journal of Nonlinear Science. Band 6, Nr. 3, 1996, S. 414, doi:10.1063/1.166191, arxiv:cond-mat/0203436v1.