Indexation et recherche de sous-arbres

Indexation de sous-arbres par empreinte unique

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 à Θ(logk (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 longueur 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 de 1 2 k . La probabilité de l’existence d’au moins une collision accidentelle sur une base de N empreintes (N ≤ 2 k ) s’élève à pc(k,N) = 1 − 2 k(2k−1)···(2k−N+1) 2NK . En supposant que chaque ligne de code soit représentée par 5 empreintes en moyenne1 , la probabilité de l’existence d’une collision accidentelle pour certains projets avec différentes longueurs de valeurs de hachage parfaites est exprimée en figure 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 sousarbres 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 collisions 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. 

Sélection des empreintes à indexer

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 pertinent. 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 occurrences, 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 certaines 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 enfants. 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’indexation2 . On notera que des empreintes peuvent concerner des séquences chevau chantes de sous-arbres. La figure 10.2 illustre l’indexation d’une fratrie (le dernier frère n’est pas indexé et deux empreintes chevauchent le deuxième frère). Duplication de sous-arbres Deux sous-arbres A(a1, a2, · · · , ak) et A′ (a ′ 1 , a′ 2 , · · · , a′ k ) identiques ne doivent pas cacher la forêt de sous-arbres n’ayant pas pour parents A ou A′ et pourtant identiques avec un des sous-arbres enfants de A ou A′ . Toutefois si les sous-arbres a1 = a ′ 1 , a2 = a ′ 2 , · · · , ak = a ′ k ne sont partagés que par A et A′ , il paraît superflu de les mentionner explicitement dans la base d’indexation. Nous pourrions ainsi associer leurs valeurs de hachage à un pointeur vers la classe d’équivalence de leur parent (classe contenant A et A′ ) avec leur place dans la fratrie de nœuds. Ainsi, si un nouveau sous-arbre A′′ est indexé, celui-ci étant égal à A et A′ et rejoignant ainsi leur classe d’équivalence, aucune opération d’indexation n’est nécessaire pour les descendants de A′′ .

Table de classes d’équivalence et ensembles de membres de classe

Une classe d’équivalence identifie l’ensemble des sous-arbres égaux selon le profil choisi. Une condition nécessaire à l’appartenance de sous-arbres à une même classe réside dans le partage d’une même valeur de hachage. Elle n’est pas suffisante en raison de possibles collisions accidentelles : on considère toutefois l’égalité des sous-arbres acquise lorsque la longueur des valeurs est suffisamment importante. Au sein d’une structure de table de classes d’équivalence nous associons valeurs de hachage avec un identifiant de classe. Les valeurs de hachage peuvent être de longueur variable ; toutefois il n’existe pas de classe dont la valeur de hachage est préfixe de celle d’une autre classe, ces valeurs représentant donc un code préfixe. Chaque classe est identifiée par un entier séquentiel. Nous associons à chacune de ces classes l’ensemble de ses membres. Un sous-arbre membre peut être explicité de deux manières : 1. Soit par un pointeur vers lui-même (explicitation directe). Il s’agit généralement d’expliciter l’identificateur de l’arbre englobant d’appartenance, ainsi que la place du sous-arbre membre lors d’un parcours en largeur de l’arbre englobant.