Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 26 février 2008 à 14h en B107, Julien Fayolle nous parlera de : Analyse de la compression par anti-dictionnaire

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 : mercredi 06 juillet 2011 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr