PPMD

PPMD

Prediction by Partial Matching (PPM) ist eine Familie anpassender statistischer Datenkompressionsalgorithmen, die auf Kontextmodellen und Prognose 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, n, 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 n-1 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-Modelles 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"-Symboles. (Anders ausgedrückt schätzt PPM-D also die Wahrscheinlichkeit eines neuen Symboles 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 zugrundeliegende 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.


Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • PPMd — PPMd, pour Prediction by Partial Matching by Dmitry, est un compresseur de données développé par Dmitry Shkarin et Dmitry Subbotin entre 1999 et 2006. Sommaire 1 Historique 2 Usages 3 Formats de fichier …   Wikipédia en Français

  • PPMd — …   Википедия

  • PPMD — Provincial Performance Management Database [Canada] …   Medical dictionary

  • PPMD — Polished Plate Meteroid Detector Contributor: LaRC …   NASA Acronyms

  • PPMD — • Provincial Performance Management Database [Canada] …   Dictionary of medical acronyms & abbreviations

  • PPMonstr — PPMd PPMd, pour Prediction by Partial Matching by Dmitry, est un compresseur de données développé par Dmitry Shkarin et Dmitry Subbotin entre 1999 et 2006. Sommaire 1 Historique 2 Usages 3 Formats de fichier …   Wikipédia en Français

  • PPMs — PPMd PPMd, pour Prediction by Partial Matching by Dmitry, est un compresseur de données développé par Dmitry Shkarin et Dmitry Subbotin entre 1999 et 2006. Sommaire 1 Historique 2 Usages 3 Formats de fichier …   Wikipédia en Français

  • École supérieure de physique et de chimie industrielles de la ville de Paris — ESPCI ParisTech Nom original École supérieure de physique et de chimie industrielles de la Ville de Paris Informations Fondation 1882 Type …   Wikipédia en Français

  • Dmitry Shkarin — Nationalité  Russie Profession Programmeur Compléments Inventeu …   Wikipédia en Français

  • Mir Environmental Effects Payload — POSA I prior to launch on STS 76. POSA 2 prior to launch on STS 76 T …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”