Direction de recherche : Michèle SORIA

Compression de données sans perte et combinatoire analytique

Résumé : Cette thèse est centrée autour de l’étude de deux algorithmes de compression de données sans perte. L’algorithme de Lempel et Ziv (LZ’77) est basé sur une structure de données sur les textes appelée arbre des suffixes. Nous analysons certains paramètres des arbres des suffixes en montrant, `a l’aide des méthodes de la combinatoire analytique (séries génératrices, combinatoire, analyse complexe et probabilités), qu’ils sont asymptotiquement assez proches de ceux des tries. Or nous connaissons bien ceux des tries ; nous déterminons donc le comportement asymptotique de la moyenne de la taille, de la longueur de cheminement et de la profondeur typique des arbres des suffixes pour des textes engendrés sous des modèles sans mémoire et markovien. Nous obtenons aussi un résultat sur la variance de la taille et de la longueur de cheminement des tries. Enfin, nous analysons un algorithme récent de compression de données sans perte qui utilise les anti-dictionnaires. Mots-clés : Combinatoire analytique, compression de données, théorie de l’information, analyse d’algorithmes, tries, arbres des suffixes.

Publications 2006

• 2006
  • J. Fayolle : “Compression de données sans perte et combinatoire analytique”, soutenance de thèse, soutenance 02/03/2006, direction de recherche Soria, Michèle (2006)