| Résumé | La structure de données qu'est le graphe est aujourd'hui utilisée dans tous les domaines de la science pour la représentation de l'information manipulée. Le problème de comparaison de ces structures de graphes occupe ainsi une place prépondérante dans le domaine de la recherche d'information et de la visualisation. Cette thèse s'inscrit dans la problématique de la reconnaissance de motifs dans des graphes.
Dans une première partie, nous proposons un algorithme de recherche de motifs similaires dans de grands graphes décliné en trois variantes selon la manière dont se propage la similarité. A chaque variante correspond un algorithme spécifique de recherche de motifs similaires. Nous proposons ici le détail de deux applications à des problématiques particulières.
Une première adaptation de la méthode concerne la reconnaissance d'objets extraits de la vidéo basse résolution pour l'indexation grossière. Une deuxième application a été développée pour la visualisation de l'évolution de projets logiciels. Le principe est de permettre à l'utilisateur d'identifier visuellement les blocs de codes restés stables au fil des différentes versions d'un même fichier source.
La seconde partie de cette thèse traite de l'étude des arborescences de fichiers, structure de données pour laquelle la méthode de reconnaissance de motifs originelle a été développé. Dans cette partie, nous proposons une étude statistique des propriétés des arborescences issues d'un système de fichiers utilisateurs réel. Nous avons d'autre part développé un modèle stochastique, basé sur les observations, pour la génération aléatoire de structures arborescentes proches des systèmes de fichiers utilisateurs.
|