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. La prédiction par reconnaissance partielle se base sur une modélisation de contexte pour évaluer la probabilité d'apparition 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.