Indexation et recherche de sous-arbres

Nous avons étudié au cours du chapitre précédent différentes méthodes de hachage d’arbres de syntaxe ainsi que plusieurs stratégies d’abstraction afin de pouvoir adopter la recherche de similarité à un niveau de détail plus ou moins important. Au-delà de l’obtention des valeurs de hachage pour différents profils d’abstraction se pose la question de leur stockage en vue de re- chercher des sous-arbres similaires sur un ensemble conséquent d’unités structurelles de code. À cet effet, nous proposons ici une méthodologie pour l’indexation de différentes valeurs de ha- chage liées à des sous-arbres hachés pour des profils d’abstraction différents. Cette indexation permet le regroupement des sous-arbres par classes d’équivalence selon différents critères de similarité. L’étude des sous-arbres similaires internes à un ensemble de projets peut ainsi être réalisée par exploitation directe d’une base de classes d’équivalence obtenue après l’indexation de ces projets. Une unité structurelle externe requête peut également être confrontée, après calcul de ses empreintes, à une base afin de déterminer les sous-arbres similaires entre l’unité requête et les projets indexés de la base.Dans un premier temps, nous souhaitons représenter chaque sous-arbre par une empreinte unique correspondant à un profil d’abstraction fixé. Un procédé classique d’indexation implique la maintenance d’une table d’association entre empreintes de hachage et identificateur du sous-arbre correspondant. Les clés de cette table peuvent être indexés par une structure de B+-k-tree, arbre k-aire adapté au stockage de masse limitant les opérations d’entrée-sortie à(N )) opérations pour la recherche ou l’ajout d’une empreinte pour N empreintes déjà indexées.

De la longueur des empreintes et de la duplication de sous-arbres

Longueur des empreintes Le principal écueil réside dans la difficulté à choisir une lon- gueur d’empreinte adéquate. En supposant la fonction de hachage sous-jacente parfaite et l’espace des sous-arbres de cardinalité infinie, la probabilité que deux sous-arbres représentés par la même valeur de hachage de longueur k bits soit différents est defigure 10.1. Une longueur de valeur de hachage confortable peut rendre négligeable le risque de collision accidentelle et dispense ainsi d’une vérification approfondie de l’égalité de sous- arbres hachés identiquement. Cependant un souci d’économie de mémoire de masse peut nous conduire à limiter cette longueur : un compromis doit être réalisé. Nous proposons donc de choisir une longueur de valeur de hachage faible au démarrage de la constitution de la base et de vérifier incrémentalement, plutôt qu’a posteriori lors d’interrogations, la présence de col- lisions accidentelles. Dans ce cas, nous augmentons la longueur des nouvelles empreintes. La similarité des sous-arbres référencés en base par une valeur de hachage commune et garantie : une telle valeur définit ainsi une classe d’équivalence de sous-arbres selon le profil choisi.

Une unité de compilation est généralement représentée par des arbres de syntaxe de grand volume : indexer chacun des nœuds correspondant à un sous-arbre peut s’avérer peu perti- nent. Un compromis doit être adopté quant au volume minimal des sous-arbres à indexer. Un volume trop faible conduira à l’indexation de petits sous-arbres comprenant de multiples oc- currences, peu utiles pour la mise en évidence de similarités intéressantes s’inscrivant au-delà de clones idiomatiques. Quant à un volume trop élevé, il ne peut permettre la localisation que des clones les plus massifs, laissant masqués des clones plus modestes. L’adoption de cer- taines techniques d’abstractions comme l’abstraction de petits sous-arbres d’expression peut permettre d’augmenter le seuil de volume minimal d’indexation.Lorsqu’un volume seuil d’indexation est fixé, les sous-arbres possédant un grand nombre de sous-arbres enfants de volume faible peuvent être eux-mêmes indexés mais pas leurs en- fants. Cette situation est rencontrée pour de gros blocs d’instructions où chaque instruction prise individuellement n’est pas indexée mais le bloc entier l’est sous la forme d’une unique empreinte. La granularité d’indexation est alors trop importante. Nous introduisons alors une indexation des sous-arbres enfants sur fenêtre de taille variable : il s’agit d’une généralisation de l’indexation sur fenêtre de taille 1 utilisée jusqu’ici. Pour chaque sous-arbre d’une fratrie, nous démarrons une fenêtre d’indexation. Si le sous-arbre est de volume supérieur au seuil d’indexation, une empreinte le concernant est créée et indexée (fenêtre de taille 1). Dans le cas contraire, la fenêtre d’indexation est étendue aux sous-arbres frères à droite jusqu’à ce que celle-ci englobe une séquence de sous-arbres dont le volume dépasse le seuil d’indexation. Ainsi, l’ensemble d’une fratrie de sous-arbres est couvrable par des empreintes indexées, à l’exception éventuelle des sous-arbres les plus à droite dont le volume cumulé est inférieur au seuil d’indexation