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
[modifier | modifier le code]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
[modifier | modifier le code]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
[modifier | modifier le code]Prédiction par reconnaissance partielle
[modifier | modifier le code]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
[modifier | modifier le code]Afin d'obtenir des prédictions plus fiables, certains algorithmes combinent plusieurs modèles statistiques.
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]Bibliographie
[modifier | modifier le code]- (en) Gordon V. Cormack et Nigel S. Horspool, « Data Compression Using Dynamic Markov Modelling », The Computer Journal, vol. 30, no 6, , p. 541-550 (DOI 10.1093/comjnl/30.6.541)
