LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

FAYOLLE Julien

PhD graduated
Team : SPIRAL
Departure date : 03/03/2006
Supervision : 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.
Defence : 03/02/2006 - 15h - Site Scott - salle C.044
Jury members :
HOFRI Micha, rapporteur
MARCKERT Jean-François, rapporteur
SZPANKOWSKI Wojciech, rapporteur
CARBONE Alessandra, examinateur
FLAJOLET Philippe, directeur de thèse
SORIA Michèle, directrice de thèse
VALLÉE Brigitte, invitée.

2006 Publications

 Mentions légales
Site map |