Résumé : La compression sans perte d’un texte par anti-dictionnaire (DCA) est une technique de compression efficace introduite par Crochemore et alii à la fin des années quatre-vingt dix. Son principe repose sur la construction de l’anti-dictionnaire du texte : un dictionnaire formé de certains mots n’apparaissant pas dans le texte (mots appelés mots minimaux interdits). Après une introduction à cet algorithme, je montre que sous un modèle sans mémoire de génération des textes, le nombre moyen de mots dans l’anti-dictionnaire sur l’ensemble des textes de taille n se comporte asymptotiquement en $\frac{Kn}{h}+o(n)$, où la constante $K$ est determinée explicitement et $h$ est l’entropie du modèle probabiliste. Les outils que j’utilise proviennent de la combinatoire analytique et des probabilités.

 [Slides.pdf]

Dernière modification : Thursday 27 March 2025

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr