FAYOLLE Julien

Docteur
Équipe : SPIRAL
Date de départ : 03/03/2006
https://lip6.fr/Julien.Fayolle

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.

Soutenance : 02/03/2006

Membres du jury :

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.

Date de départ : 03/03/2006

Publications 2006

Mentions légales
Carte du site