Vorhersage durch partielle Übereinstimmung - Prediction by partial matching

Prediction by Partial Matching ( PPM ) ist eine adaptive statistische Datenkompressionstechnik , die auf Kontextmodellierung und Vorhersage basiert . PPM-Modelle verwenden einen Satz vorheriger Symbole im unkomprimierten Symbolstrom, um das nächste Symbol im Strom vorherzusagen. PPM-Algorithmen können auch verwendet werden, um Daten bei der Clusteranalyse zu vorhergesagten Gruppierungen zu gruppieren .

Theorie

Vorhersagen werden normalerweise auf Symbolrankings reduziert. Jedes Symbol (ein Buchstabe, Bit oder jede andere Datenmenge) wird vor der Komprimierung in eine Rangfolge gebracht, und das Rangordnungssystem bestimmt das entsprechende Codewort (und damit die Komprimierungsrate). In vielen Komprimierungsalgorithmen entspricht die Rangfolge der Schätzung der Wahrscheinlichkeitsmassenfunktion. Ausgehend von den vorherigen Buchstaben (oder einem gegebenen Kontext) wird jedem Symbol eine Wahrscheinlichkeit zugewiesen. Bei der arithmetischen Codierung werden die Symbole beispielsweise nach ihrer Wahrscheinlichkeit geordnet, nach vorherigen Symbolen zu erscheinen, und die gesamte Sequenz wird in einen einzelnen Bruchteil komprimiert, der gemäß diesen Wahrscheinlichkeiten berechnet wird.

Die Anzahl der vorherigen Symbole, n , bestimmt die Ordnung des PPM-Modells, die als PPM( n ) bezeichnet wird. Unbegrenzte Varianten, bei denen der Kontext keine Längenbeschränkungen hat, existieren ebenfalls und werden als PPM* bezeichnet . Wenn keine Vorhersage basierend auf allen n Kontextsymbolen gemacht werden kann, wird eine Vorhersage mit n  − 1 Symbolen versucht . Dieser Vorgang wird wiederholt, bis eine Übereinstimmung gefunden wird oder keine Symbole mehr im Kontext verbleiben. An diesem Punkt wird eine feste Vorhersage gemacht.

Ein Großteil der Arbeit bei der Optimierung eines PPM-Modells besteht darin, Eingaben zu verarbeiten, die noch nicht im Eingabestrom aufgetreten sind. Der offensichtliche Weg, mit ihnen umzugehen, besteht darin, ein "nie gesehenes" Symbol zu erstellen, das die Escape-Sequenz auslöst . Aber welche Wahrscheinlichkeit sollte einem noch nie gesehenen Symbol zugeordnet werden? Dies wird als Nullfrequenzproblem bezeichnet . Eine Variante verwendet den Laplace-Schätzer, der dem "never-seen"-Symbol einen festen Pseudocount von eins zuweist . Eine Variante namens PPMd inkrementiert den Pseudozähler des "never-seen"-Symbols jedes Mal, wenn das "never-seen"-Symbol verwendet wird. (Mit anderen Worten, PPMd schätzt die Wahrscheinlichkeit eines neuen Symbols als das Verhältnis der Anzahl einzigartiger Symbole zur Gesamtzahl der beobachteten Symbole).

Implementierung

Die Implementierungen der PPM-Komprimierung unterscheiden sich in anderen Details stark. Die tatsächliche Symbolauswahl wird normalerweise unter Verwendung einer arithmetischen Codierung aufgezeichnet , obwohl es auch möglich ist, eine Huffman-Codierung oder sogar eine Art Wörterbuchcodierungstechnik zu verwenden. Das zugrunde liegende Modell, das in den meisten PPM-Algorithmen verwendet wird, kann auch erweitert werden, um mehrere Symbole vorherzusagen. Es ist auch möglich, eine Nicht-Markov-Modellierung zu verwenden, um die Markov-Modellierung entweder zu ersetzen oder zu ergänzen. Die Symbolgröße ist normalerweise statisch, normalerweise ein einzelnes Byte, was die allgemeine Handhabung jedes Dateiformats erleichtert.

Bereits Mitte der 1980er Jahre gibt es veröffentlichte Forschungen zu dieser Familie von Algorithmen. Softwareimplementierungen waren bis Anfang der 1990er Jahre nicht populär, da PPM-Algorithmen eine beträchtliche Menge an RAM benötigen . Neuere PPM-Implementierungen gehören zu den leistungsstärksten verlustfreien Komprimierungsprogrammen für Text in natürlicher Sprache .

PPMd ist eine Implementierung von PPMII von Dmitry Shkarin. Es wird standardmäßig im RAR verwendet . Es wird auch von 7-Zip als eine von mehreren möglichen Komprimierungsmethoden im 7z- Dateiformat verwendet.

Versuche, die PPM-Algorithmen zu verbessern, führten zur PAQ- Serie von Datenkomprimierungsalgorithmen.

Anstatt zur Komprimierung verwendet zu werden, wird ein PPM-Algorithmus verwendet, um die Effizienz der Benutzereingabe im Programm Dasher mit alternativer Eingabemethode zu erhöhen .

Siehe auch

Quellen

  • Cleary, J.; Witten, I. (April 1984). „Datenkomprimierung mit adaptiver Codierung und partiellem String-Matching“. IEEE-Trans. Komm. 32 (4): 396–402. CiteSeerX  10.1.1.14.4305 . doi : 10.1109/TCOM.1984.1096090 .
  • Moffat, A. (November 1990). „Implementieren des PPM-Datenkompressionsschemas“. IEEE-Trans. Komm. 38 (11): 1917–1921. CiteSeerX  10.1.1.120.8728 . doi : 10.1109/26.61469 .
  • Cleary, JG; Teahan, WJ; Witten, IH "Kontexte mit unbegrenzter Länge für PPM" . Das Computerjournal . Oxford, England: Oxford University Press. 40 (2_und_3): Seiten 67–75. doi : 10.1093/comjnl/40.2_and_3.67 . ISSN  0010-4620 .
  • C. Bloom, Lösung der Probleme der Kontextmodellierung .
  • WJ Teahan, Wahrscheinlichkeitsschätzung für PPM .
  • SchüRmann, T.; Grassberger, P. (September 1996). „Entropieschätzung von Symbolfolgen“. Chaos . 6 (3): 414–427. arXiv : cond-mat/0203436 . Bibcode : 1996Chaos...6..414S . doi : 10.1063.1.166191 . PMID  12780271 .

Verweise

Externe Links