Prediction by Partial Matching

Prediction by Partial Matching

Prédiction par reconnaissance partielle

Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d'algorithmes de compression de données sans perte, statistiques et adaptatifs inventée par John Cleary et Ian Witten en 1984.

Sommaire

Principe

La prédiction par reconnaissance partielle se base sur une modélisation de contexte pour évaluer la probabilité des différents symboles.

Usuellement, le contexte est un ensemble de symboles déjà rencontrés dans la source de données (fichier, flux). La longueur du contexte utilisé pour la prédiction confère son ordre au PPM. On note PPM(N) un PPM d'ordre N. Par exemple, un PPM(1) est un PPM d'ordre 1 ; c'est-à-dire qu'il prédit le motif suivant en fonction du seul symbole précédent. On note PPM* un PPM d'ordre infini ; c'est-à-dire qu'il prédit le motif suivant en fonction de l'intégralité de la source de données déjà analysée.

Le contexte permet de déterminer la probabilité des différents symboles grâce à un historique des entrées : à chaque contexte sont associées les fréquences d'apparition des différents symboles.

En général, plus le contexte utilisé est long, meilleure est la prédiction.

Un problème posé par l'utilisation de longs contextes est le cas de l'historique vide : lorsqu'un contexte donné est rencontré pour la première fois. Les deux solutions les plus fréquemment apportées sont l'utilisation de probabilités fixées à l'avance et le changement dynamique de l'ordre du prédicteur. Par exemple, si un PPM(8) ne dispose pas d'historique pour un contexte de longueur 8, il cherche un historique pour un contexte de longueur 7, puis 6... jusqu'à trouver un historique ou à tomber à l'ordre -1, auquel cas des probabilités fixées à l'avance sont utilisées.

La prédiction obtenue sert d'entrée à un codage entropique, le plus souvent un codage arithmétique, bien que n'importe quel codage entropique (codage de Huffman...) puisse être utilisé.

Plusieurs PPM peuvent être combinés entre eux et avec d'autres types de prédicteurs par pondération de contextes, ce qui permet d'étendre le domaine modélisé, ou d'améliorer la précision de la modélisation.

Propriétés

PPM est un algorithme symétrique. Cela signifie qu'il fait la même chose à la compression et à la décompression. Cela signifie aussi que sa vitesse est la même dans les deux cas (si l'on ne tient pas compte des subtilités des entrées-sorties), et que la quantité de mémoire nécessaire (pour stocker l'historique et les contextes) est identique.

La plupart des implémentations de PPM mettent à jour leur modèle au cours de la compression (on parle de compression statistique adaptative), ce qui rend l'algorithme capable de traiter des flux de données (streaming) car il n'est jamais nécessaire de connaître les symboles à venir.

Performances

Les taux de compression obtenus par les PPMs sont parmi les meilleurs obtenus aujourd'hui, notamment sur le texte.

La quantité de mémoire nécessaire varie de très peu à énormément. Un PPM(0) nécessite très peu de mémoire, alors qu'un PPM* peut exploiter une quantité infinie de mémoire.

La vitesse, notamment de la décompression, est le point faible des PPMs. En effet, contrairement à des algorithmes asymétriques (comme la famille des Lempel-Ziv), pour lesquels la décompression comporte beaucoup moins d'étapes que la compression, les PPMs ont une décompression strictement identique à la compression.

Variantes

PPM basé sur d'autres symboles que des octets

Bien que la plupart des implémentations de PPM travaillent sur des octets, pouvant ainsi traiter n'importe quel type de fichier sans adaptation particulière, certaines variantes utilisent d'autres types de symboles. Une variante spécialisée sur le texte consiste à utiliser des mots comme symboles, plutôt que des caractères.

Modélisation de Markov dynamique

Article détaillé : Modélisation de Markov dynamique.

Une approche similaire est utilisée par les algorithmes de modélisation de Markov dynamique.

Pondération de contextes

Article détaillé : Pondération de contextes.

Afin d'obtenir des prédictions plus fiables, certains algorithmes combinent plusieurs modèles statistiques.

Notes

PPM est également utilisé pour l'autocomplétion des commandes dans certains systèmes Unix.

Voir aussi

Articles connexes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Pr%C3%A9diction par reconnaissance partielle ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Prediction by Partial Matching de Wikipédia en français (auteurs)

См. также в других словарях:

  • Prediction by Partial Matching — (PPM) is an adaptive statistical data compression technique based on context modeling and prediction. PPM models use a set of previous symbols in the uncompressed symbol stream to predict the next symbol in the stream.Predictions are usually… …   Wikipedia

  • Prediction by Partial Matching — (PPM, englisch) 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… …   Deutsch Wikipedia

  • Prediction by Partial Matching (Algoritmo de compresión) — Saltar a navegación, búsqueda El algoritmo Prediction by Partial Matching (en español Predicción por Coincidencia Parcial) o PPM es una técnica adaptativa estadística de compresión de datos basada en el modelo de contexto y predicción. Los… …   Wikipedia Español

  • Prediction par reconnaissance partielle — Prédiction par reconnaissance partielle Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d algorithmes de compression de données sans perte, statistiques et adaptatifs …   Wikipédia en Français

  • Prédiction par reconnaissance partielle — Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d algorithmes de compression de données sans perte, statistiques et adaptatifs inventée par John Cleary et Ian Witten… …   Wikipédia en Français

  • Memory-prediction framework — The memory prediction framework is a theory of brain function that was created by Jeff Hawkins and described in his 2004 book On Intelligence. This theory concerns the role of the mammalian neocortex and its associations with the hippocampus and… …   Wikipedia

  • PPMII — Prédiction par reconnaissance partielle Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d algorithmes de compression de données sans perte, statistiques et adaptatifs …   Wikipédia en Français

  • 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… …   Deutsch Wikipedia

  • PPMdH — 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… …   Deutsch Wikipedia

  • Data compression — Source coding redirects here. For the term in computer programming, see Source code. In computer science and information theory, data compression, source coding or bit rate reduction is the process of encoding information using fewer bits than… …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»