Séminaire du 17 novembre 03, Julien Fayolle

Arbres suffixes et sources simples

L'algorithme zip, qui permet de compresser de manière performante un fichier, fonctionne sur une structure arborescente très efficace pour retrouver un motif dans un grand texte : le trie suffixe ou arbre digital. La connaissance du comportement de cette structure via les paramètres usuels d'un arbre sert à déterminer la complexité de zip.

Lors de cet exposé, on montrera que la moyenne de certains paramètres (la longueur de cheminement externe et la taille) des tries et des tries suffixes ne diffèrent asymptotiquement qu'en $o(n)$. Les comportements asymptotiques des deux paramètres étudiés pour un trie étant déjà connus, on en déduit les premiers termes pour un trie suffixe. Cette étude est menée pour un alphabet binaire sous un modèle de source dynamique sans mémoire.