Accueil🇫🇷Chercher

Modélisation de Markov dynamique

Les algorithmes de modélisation de Markov dynamique ou de compression de Markov dynamique (ou DMC pour Dynamic Markov compression) constituent une famille d'algorithmes de compression de données sans perte, statistiques et adaptatifs inventée par Gordon Cormack et Nigel Horspool en 1986.

Principe

Les algorithmes de cette famille se basent sur une modélisation de Markov dynamique pour évaluer la probabilité d'apparition des différents symboles.

La prédiction obtenue sert d'entrée à un codage arithmétique, bien qu'en théorie, n'importe quel codage entropique (codage de Huffman…) pourrait être utilisé à la place.

Une DMC peut être combinée avec d'autres types de prédicteurs (des PPM, par exemple) 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

DMC 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 le modèle de Markov) est identique.

Il y a relativement peu d'implémentations de DMC, mais il apparaît qu'elles ont un coût en mémoire supérieur à une implémentation correcte d'un PPM, pour des performances comparables.

Variantes

Prédiction par reconnaissance partielle

Une approche similaire est utilisée par les algorithmes de prédiction par reconnaissance partielle. Légèrement plus ancienne, elle est également beaucoup plus fréquemment employée.

Pondération de contextes

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

Voir aussi

Articles connexes

Bibliographie

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.