Prédiction par reconnaissance partielle
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
Les points d'amélioration suivants sont les cas les plus fréquents :
- Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
- Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »...
- Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
- L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
- Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
- Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
- Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil «
Source») sont à placer entre la fin de phrase et le point final[comme ça]. - Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
- Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
- La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
- Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.
Pour une aide détaillée, merci de consulter Aide:Wikification.
Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.
Les algorithmes de prédiction par reconnaissance partielle (ou PPM pour Prediction by Partial Matching) constituent une famille d'algorithmes statistiques et adaptatifs inventés par John Cleary et Ian Witten en 1984 [1] . Ils sont destinés à prétraiter des données pour permettre un codage entropique plus optimal[2] .
Principe
[modifier | modifier le code ]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). Un contexte d’ordre N est alors la suite de N symboles du fichier. On le note PPM(N). Par exemple, un PPM d’ordre 1 (noté « PPM(1) »), 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, etc. 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
[modifier | modifier le code ]PPM est un algorithme symétrique (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
[modifier | modifier le code ]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 PPM. 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 PPM ont une décompression strictement identique à la compression.
Variantes
[modifier | modifier le code ]PPM basé sur d'autres symboles que des octets
[modifier | modifier le code ]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
[modifier | modifier le code ]Une approche similaire est utilisée par les algorithmes de modélisation de Markov dynamique.
Pondération de contextes
[modifier | modifier le code ]Afin d'obtenir des prédictions plus fiables, certains algorithmes combinent plusieurs modèles statistiques.
Autres applications
[modifier | modifier le code ]PPM est également utilisé pour l'autocomplétion des commandes dans certains systèmes Unix.
Références
[modifier | modifier le code ]- ↑ Ted Gueniche et Philippe Fournier-Viger, « Réduction de la complexité spatiale et temporelle du Compact Prediction Tree pour la prévision de séquences » [PDF]
- ↑ (en) Radu Rădescu, « Experimental Results in Prediction by Partial Matching and Star Transformation Applied in Lossless Compression of Text Files », sur Research Gate, (consulté le )
Voir aussi
[modifier | modifier le code ]Articles connexes
[modifier | modifier le code ]- PPMd
- Compression de données
- Dmitry Shkarin
- Modélisation de Markov dynamique
- Pondération de contextes
- Structure de données compressée
Techniques de compression de données |
|||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Sans perte |
|
||||||||||||||
| Avec pertes |
|
||||||||||||||