Méthodes de groupement de correspondances

Méthodes de groupement de correspondances

Idéalement, un procédé de recherche de similitude devrait proposer nativement un groupe- ment des morceaux de code présentant un certain degré de similarité. C’est le cas, dans une certaine mesure, lors de la recherche de facteurs répétés sur des chaînes de lexèmes à l’aide d’une structure d’indexation de suffixes (cf chapitre 6) et de graphe de farmax : un facteur répété est complet et comprend toutes les occurrences de ce facteur (le groupe formé n’est ni peuplable, ni dépeuplable). La même remarque s’applique à la recherche de chaînes de sous-arbres frères répétés (cf chapitre 10). Cependant la méthode de consolidation de corres- pondances présentée au chapitre 11 se contente d’obtenir des 2-correspondances approchées. Sachant que ces 2-correspondances comprennent une composante sur un arbre requête ainsi qu’une autre sur un arbre de la base, il est possible de calculer des empreintes par une tech- nique de hachage pour chacune des composantes de l’arbre requête participant à une corres- pondance : si (ASi le regroupement par hachage des composantes demeure simple, cette méthode ne permetde regrouper des composantes (et ainsi les correspondances où elles sont abritées) que sur la base d’une similarité plus ou moins exacte (selon un profil d’abstraction utilisé lors du hachage). Des métriques vectorielles peuvent être utilisées avec l’emploi ensuite d’une fonction de hachage localement sensible [52] comme l’utilise Deckard [70]. Une vérification des éléments de chaque groupe demeure néanmoins indispensable afin de gérer les cas de fausse-positivité.Nous examinons ici deux techniques de regroupement de correspondances de similarité ap- proximative. La première utilise directement une représentation par arbre de syntaxe (ou chaînes de lexèmes) et réalise un regroupement par anti-unification : il s’agit de trouver un squelette commun à plusieurs arbres (ou chaînes) avec abstraction de leurs petits sous-arbres discordants (ou petits facteurs discordants) pour les regrouper. Cette méthode présente l’avan- tage de conserver un représentant abstrait pour chaque groupe. Pour la seconde méthode, nous calculons préalablement une matrice de similarité entre les composantes des correspondances. Cette matrice sert de base au regoupement.

Groupement direct de chaînes de lexèmes ou d’arbres de syntaxe par anti-unification

 un élément représentatif plus général E permettant de retrouver chacun des éléments originels par une opération de substitution de ses termes. Il existe plusieurs éléments E plus généraux que e dont par exemple l’élément le plus général E = Σ où le symbole Σ peut être remplacé par chacun des éléments originels. L’objectif est alors de trouver un des éléments E minimisant pour chacun des éléments originels les coûts de substitution. Il reste ainsi à définir la fonction de minimisation des coûts de substitution sur les éléments originels. Pour une pre- mière approche, si E est l’élément anti-unificateur avec les symboles substitutifs σNous proposons ici une méthode calculant l’anti-unifié en minimisant la somme des coûts de substitution qui repose sur la détermination de la plus longue sous-séquence commune (LCS) entre deux chaînes de lexèmes ou chaînes de sous-arbres frères.Nous proposons une méthode récursive d’anti-unification de deux arbres de syntaxe s’ins- pirant de celle décrite pour les chaînes. Étant donnés deux arbres A et B dont l’on souhaite trouver un anti-unifié, nous comparons tout d’abord les racines de A et de B. N’admettant que des opérations de substitution de sous-arbres entiers et non de nœuds, si les racines sont diffé- rentes, A et B n’admettent que l’arbre anti-unifié le plus général σ. Si les racines concordent, nous cherchons à identifier chacun des éléments de la chaîne C = αest suffisante pour déduire un arbre anti-unifié, cet arbre n’étant que de profondeur 2. Si un arbre anti-unifié de profondeur plus importante est recherchée, nous comparons récursi- vement, selon la même méthode, deux à deux les arbres σ.

En prenant pour exemple les deux versions de la sommation des fonctions présen- tées, A = affectation(somme, binop(+, somme, acces(tab,i))) pour la moyenne arithmétique et B = affectation(addition, binop(+, addition, binop(*, accès(tab,i), accès(tab,i)))) pour la moyenne quadratique, nous comparons les racines (affectation) de types égaux. Nous obte- nons ensuite la décomposition suivante sur les chaînes de sous-arbre enfants : C = σ Étant donné un ensemble d’éléments syntaxiques distincts provenant du code examiné et représenté soit par séquence de lexèmes, soit par arbre de syntaxe, nous pouvons maintenir des groupes d’éléments partageant le même anti-unifié. Concrètement, nous déterminons pour chaque élément syntaxique si celui-ci peut appartenir à un des groupes existants. Pour le vérifier, nous calculons pour chacun des groupes le nouvel anti-unifié du groupe si l’élément devait y être ajouté avec le coût de substitution associé : nous sélectionons le groupe de coût le plus faible. Soit ce coût est inférieur à un seuil fixé de coût de substitution : l’élement est alors ajouté à ce groupe. Dans le cas contraire, un nouveau groupe ne comprenant que cet élément est créé.Cette méthode de regroupement par anti-unification est notammant utilisée par l’outil de recherche de similarité CloneDigger [90]. Celui-ci réalise dans une première passe le regroupe- ment des arbres de syntaxe représentant des instructions similaires par anti-unification. Cha- cune des instructions est alors remplacée par un nœud signifiant son groupe d’appartenance et une seconde passe réalise l’anti-unification des fonctions. Cette méthode est cependant de complexité temporelle prohibitive.