PPMd

PPMd, pour Prediction by Partial Matching by Dmitry, est un compresseur de données développé par Dmitry Shkarin et Dmitry Subbotin entre 1999 et 2006.

Historique modifier

Historique des versions

var.A – 13 juin 1999
var.B – 30 juin 1999
var.C – 22 août 1999
var.D – 6 octobre 1999
var.E – 3 décembre 1999
var.F – 7 avril 2000
var.G – 26 novembre 2000
var.H – 21 avril 2001
var.I rev.1 – 30 avril 2002
var.J rev.1 – 10 mai 2006

PPMd est une implémentation de PPMII, un algorithme de compression de données par prédiction par reconnaissance partielle conçu par Dmitry Shkarin.

À l'origine, son nom était PPMD pour Prediction by Partial Matching, escape method D et faisait suite aux compresseurs PPMA, PPMB et PPMC de John Cleary et Ian Witten. Il a été renommé lors du passage de sa version var.D vers sa version var.E.

La dernière version de PPMd à l'heure actuelle, var.J, parue plus de quatre ans après la précédente, var.I a notamment apporté le support des architectures 64 bits et du multi-tâches.

Usages modifier

PPMd est essentiellement destiné à être intégré dans des compresseurs tiers, comme l'autorise sa licence très permissive. Dans les faits, il est intégré dans les archiveurs ICEOWS, BioArc WinRAR et WinZip. Une version améliorée par Igor Pavlov de PPMd var.H est utilisée par l'archiveur 7-Zip.

PPMd est un compresseur rapide et très efficace. Ainsi, certains utilisateurs de 7-Zip le préfèrent à LZMA (l'algorithme utilisé par défaut) pour compresser du texte. PPMd utilise un algorithme de compression purement symétrique ; c'est-à-dire qu'il nécessite autant de mémoire et de temps à la décompression qu'à la compression. Cela le rend moins intéressant que LZMA pour de nombreux cas d'utilisation, car celui-ci est asymétrique et extrêmement rapide à la décompression.

Formats de fichier modifier

Le format de fichier utilisé par PPMd est peu répandu. En effet, l'implémentation originale de Dmitry Shkarin est rarement utilisée, et les archiveurs utilisant PPMd l'intègrent dans leurs propres formats. Ainsi, PPMd est notamment utilisé dans les formats 7z, ZIP et RAR qui sont incompatibles entre eux.

PPMonstr modifier

PPMonstr est un compresseur dérivé de PPMd optimisé pour obtenir des taux de compression très importants, aux dépens de la vitesse d'exécution et de la mémoire nécessaire. PPMonstr a longtemps été une référence en ce qui concerne les ratios de compression, aux côtés d'autres compresseurs utilisant la prédiction par reconnaissance partielle, comme UHarc, avant que les compresseurs basés sur la pondération de contextes comme PAQ ou WinRK fassent leur apparition.

Même s'il a plus ou moins cédé son statut de référence au profit de PAQ, PPMonstr ne demeure pas moins l'une des implémentations les plus efficaces d'un algorithme de prédiction par reconnaissance partielle. Il reste également utilisé par les chercheurs en compression de données pour analyser l'organisation de certains fichiers et améliorer d'autres compresseurs, car il est capable de modéliser des structures bien plus complexes que n'importe quel autre compresseur, PAQ compris.

PPMs modifier

PPMs est un compresseur dérivé de PPMd optimisé pour fonctionner avec très peu de mémoire, aux dépens du taux de compression.

Licence modifier

PPMd est open-source et placé dans le domaine public. PPMonstr est propriétaire et son code source n'est pas divulgué.

Voir aussi modifier

Articles connexes modifier

Liens externes modifier

(ru) Site officiel de Dmitry Shkarin