Les arbres sont des données qui apparaissent naturellement dans de nombreux domaines scientifiques. Leur nature intrinsèquement non euclidienne ainsi que le phénomène d’explosion combinatoire rendent leur analyse délicate. On s’intéresse dans cette thèse à trois approches permettant de comparer des arbres, sous le prisme notamment d’une technique de compression sans perte des arbres par des graphes dirigés acycliques.
D’abord, concernant l’isomorphisme d’arbres, nous considérons une extension de la définition classique aux arbres étiquetés, qui requiert que les arbres soient identiques à réécriture des étiquettes près. Ce problème est aussi dur que l’isomorphisme de graphes, et nous avons développé un algorithme qui réduit drastiquement la taille de l’espace de recherche des solutions qui est ensuite exploré avec une stratégie de retour sur trace.
Lorsque deux arbres sont différents, on peut chercher à en trouver des sous-structures communes. Si cette question a déjà été traitée pour les sous-arbres, nous nous intéressons à un problème plus large, celui de trouver des ensembles de sous-arbres apparaissant simultanément. Cela nous amène à considérer l’énumération des forêts, pour laquelle nous proposons un algorithme de type « reverse search » qui construit un arbre d’énumération dont le facteur de branchement est linéaire.
Enfin, à partir d’une liste de sous-structures communes, on peut construire un noyau de convolution qui permet d’aborder des problèmes de classification. Nous reprenons de la littérature le noyau des sous-arbres, et construisons un algorithme qui les énumère explicitement (contrairement à la méthode originale). Notre approche permet notamment de paramétrer plus finement le noyau, améliorant significativement les capacités de classification.
Gratuit
Mots clés
Disciplines