Prédiction par reconnaissance partielle 2024234 22084043 2007-10-23T09:34:35Z Chtonomute 305528 /* Principe */ '''PPM''' (pour ''Prediction by Partial Matching'' ou ''Prédiction par reconnaissance partielle'') est un [[Algorithmique|algorithme]] de [[compression de données]] sans perte, statistique et adaptatif. == Principe == La prédiction par reconnaissance partielle se base une 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 est utilisée comme entrée d'un autre algorithme, le plus souvent d'un [[codage arithmétique]] ou d'une [[pondération de contextes]]. == 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. == 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 [[LZ77 et LZ78|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. == Notes == PPM est également utilisé pour l'autocomplétion des commandes dans certains systèmes Unix. ==Liens externes== ==Références== <references/> [[Catégorie:Algorithme de compression sans perte]] [[Catégorie:Théorie de l'information]]