2001:16B8:A71:5000:E0F5:2E05:C2A1:BE5: Anhängen eines Links zum echten Paper (Source Code in PostScript)

2023-01-31T17:27:39Z

Anhängen eines Links zum echten Paper (Source Code in PostScript)

Neue Seite

{{lang|en|'''Prediction by Partial Matching'''}} ('''PPM''', {{enS}}) ist eine Familie anpassender [[Statistik|statistischer]] [[Datenkompression]]salgorithmen, die auf Kontextmodellen und [[Prognose]]n 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, <math>n</math>, 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 <math>n-1</math> 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-Kette|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 [[Arithmetisches Kodieren|arithmetisch kodiert]], obwohl auch [[Huffman-Kodierung]] oder auch eine Art [[Wörterbuchkompression|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ürliche Sprache|natürlichen Sprachen]].

Der Versuch, PPM-Algorithmen zu verbessern, führte zu den [[PAQ]]-Kompressionsalgorithmen.

== Literatur ==
* {{Literatur |Autor=J. Cleary, I. Witten |Titel=Data Compression Using Adaptive Coding and Partial String Matching |Sammelwerk=Communications, IEEE Transactions on |Band=32 |Nummer=4 |Datum=1984 |Seiten=396–402 |DOI=10.1109/TCOM.1984.1096090}}
* {{Literatur |Autor=A. Moffat |Titel=Implementing the PPM data compression scheme |Sammelwerk=Communications, IEEE Transactions on |Band=38 |Nummer=11 |Datum=1990 |Seiten=1917–1921 |DOI=10.1109/26.61469}}
* {{Literatur |Autor=J. G. Cleary, W. J. Teahan, I. H. Witten |Titel=Unbounded length contexts for PPM |Sammelwerk=Proceedings DCC-95 |Verlag=IEEE Computer Society Press |Datum=1995 |Online=[http://www.cs.waikato.ac.nz/~ihw/papers/95JC-WT-IHW-Unbound.pdf cs.waikato.ac.nz] |Format=PDF |KBytes=}} Alternativ: {{Literatur |Autor=J. G. Cleary, W. J. Teahan |Titel=Unbounded Length Contexts for PPM |Sammelwerk=The Computer Journal |Band=40 |Nummer=2–3 |Datum=1997 |Seiten=67–75 |DOI=10.1093/comjnl/40.2_and_3.67}}
* C. Bloom, [http://www.cbloom.com/papers/ppmz.zip Solving the problems of context modeling] ([[ZIP-Dateiformat|ZIP]]; 43 kB).
* {{Literatur |Autor=W. J Teahan |Titel=Probability estimation for PPM |Sammelwerk=Proceedings NZCSRSC'95 |Datum=1995 |Online=[http://cotty.16x16.com/compress/peppm.htm cotty.16x16.com] [https://web.archive.org/web/20010605194536/http://www.cs.waikato.ac.nz/~wjt/papers/NZCSRSC.ps.gz Original Source from archive.org] |Abruf=2023-01-31}}
* {{Literatur |Autor=Thomas Schürmann, [[Peter Grassberger]] |Titel=Entropy estimation of symbol sequences |Sammelwerk=Chaos: An Interdisciplinary Journal of Nonlinear Science |Band=6 |Nummer=3 |Datum=1996 |Seiten=414 |arXiv=cond-mat/0203436v1 |DOI=10.1063/1.166191}}

== Weblinks ==
* [http://mattmahoney.net/dc/text.html Paket von PPM Kompressoren mit Benchmarks]
* [http://www3.sympatico.ca/mt0000/bicom/bicom.html BICOM, a bijective PPM compressor]
* [http://dogma.net/markn/articles/arith/part2.htm "Arithmetic Coding + Statistical Modeling = Data Compression", Part 2]
* [http://compression.ru/ds/ PPMd compressor] von Dmitri Shkarin

[[Kategorie:Datenkompression]]

Prediction by Partial Matching - Versionsgeschichte

2001:16B8:A71:5000:E0F5:2E05:C2A1:BE5: Anhängen eines Links zum echten Paper (Source Code in PostScript)