Résumé de séminaire

Résumé :

L'oracle de facteur d'un mot w est une structure d'index qui reconnait au moins tous les facteurs de w. C'est une structure très compacte, facile à construire et à stocker, d'abord conçue pour la recherche de mot. Nous montrons comment employer l'oracle pour calculer des répétitions afin de comparer de très longs mots tels que des séquences biologiques. Le calcul des répétitions d'un mot mêne naturellement à établir une factorisation du mot qui donne un schéma séquentiel de compression. Il est également possible d'obtenir une méthode globale de compression en utilisant des règles de grammaire qui décrivent le mot. Enfin nous montrons comment l'oracle peut aider à estimer l'entropie topologique des séquences biologiques.

Travail en collaboration avec Arnaud Lefebvre (Université de Rouen).

Références :

Ma page web : http://www-igm.univ-mlv.fr/~lecroq/