Journée-séminaire de combinatoire

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

Le 26 février 2008 à en , 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.


Dernière modification : jeudi 10 août 2017 Valid HTML 4.01! Valid CSS! Organisateurs : Cyril.Banderier & Gerard.Duchamp at lipn.univ-paris13.fr