Utilisation de structures d’indexation de suffixes

Introduction

Étant donnée une représentation de code source sous la forme de chaînes de lexèmes, une première approche à la recherche de similarité réside dans la recherche de sous-chaînes exactes répétées. Les facteurs répétés en multiples occurrences au sein d’une unique chaîne (représentation d’un unique projet ou unité de compilation) ou de multiples chaînes (représentation de plusieurs projets ou unités de compilation) témoignent de la présence d’un groupe de clones. La validité du clone ainsi détecté est dépendante du niveau d’abstraction choisi pour la représentation en lexèmes ainsi que de la longueur du facteur répété. Pour la suite, nous confondrons les facteurs répétés avec leurs occurrences associées sur les chaînes traitées.

Facteurs répétés : définitions

Nous considérons ainsi k projets chacun représenté par une chaîne de lexèmes (de longueurs respectives ℓ1, ℓ2, .. . ,ℓn) T = {T1 = t1,1 · · ·t1,ℓ1 , · · · , Tn = tn,1 · · ·tn,ℓn }. Nous notons la longueur cumulée L = ℓ1 +ℓ2 +· · ·+ℓn. L’alphabet de lexèmes manipulé est doté d’une opération transitive d’égalité = sur les lexèmes. Nous introduisons quelques définitions pour nous mener à la recherche de facteurs répétés maximaux (farmax). Ceux-ci peuvent être associés à l’ensemble exhaustif de leurs occurrences qui ne peuvent être étendus par l’incorporation de lexèmes contigus (maximalité). Ainsi par exemple, l’instruction lexemisée x = (a+ 1) ∗ (a−1) avec une opération d’égalité confondant les opérateurs conduit à l’obtention d’un famax de longueur d’au moins trois lexèmes : (a op 1). Définition 6.1. (Facteur répété) R est un facteur répété (far) de T ssi il existe k ≥ 2 occurrences de R (que nous noterons {r1 = Ti1 [α1|ℓ] , · · · , rk = Tik [αk|ℓ]}). Nous avons alors 91 6. Utilisation de structures d’indexation de suffixes égalité lexème par lexème pour les occurrences deux à deux (∀1 ≤ p ≤ q ≤ k, 1 ≤ t ≤ ℓ, rp[αp + t] = rq[αq + t]). Définition 6.2. (Facteur répété maximal — farmax —) Un facteur répété R d’occurrences {r1, · · · , rk} est maximal (farmax) ssi ses occurrences ne peuvent être étendues ni sur la gauche, ni sur la droite, i.e. il n’existe pas d’occurrences r ′ 1 = Ti1 [α1 − u|l + v], …, r ′ k = Tik [αk − u|αk + v] avec u ≥ 0, v ≥ 0 et u + v > 0 tels que R′ : {r ′ 1 , · · · , r′ k } soit un facteur répété. Définition 6.3. (Occurrence propre) Une occurrence d’un facteur répété est dite occurrence propre si celle-ci n’est pas comprise dans un autre facteur répété. Lorsqu’un facteur répété ne comprend aucune occurrence propre, celui-ci est dit facteur répété unificateur. Ainsi, déterminer les facteurs répétés maximaux farmax(T) et leurs ensembles d’occurrences associés équivaut à trouver l’ensemble des groupes de clones pertinents, complets et maximaux comme explicité en section 2.2. L’oracle de pertinence utilisé considère comme pertinents un groupes de clones ssi leurs représentations lexemisées (occurrences de facteurs de lexèmes) sont égales deux à deux, lexème par lexème. 

Indexation de suffixes

Une structure d’indexation de suffixes permet de calculer aisément l’ensemble des facteurs répétés complets d’un ensemble de chaînes de lexèmes. Elle autorise un accès rapide à tous les suffixes des sous-chaînes débutant par un préfixe donné. Nous introduisons dans le reste de ce chapitre les structures d’arbre (section 6.2) et de table de suffixes (section 6.3) permettant l’indexation de suffixes en temps linéaire (sous-sections 6.2.2 et 6.3.2) de la taille cumulée des sous-chaînes manipulées. Nous ne nous intéresserons pas à la structure d’automate de suffixes (ou de facteurs) plus adaptée à la recherche de facteurs sur un corpus de chaînes fixes avec une contrainte mémorielle forte qu’à l’énumération exhaustive des facteurs répétés. Nous nous concentrerons spécifiquement sur la structure de table de suffixes et étudierons des structures annexes telle que l’arbre des intervalles (section 6.4) afin de déterminer les facteurs répétés (dont ceux maximaux) d’un ensemble de séquences de lexèmes.

Implantations

Les structures d’indexation de suffixes ont pour principal intérêt la recherche rapide de chaînes requêtes sur un ensemble de chaînes indexées. Elles présentent également une utilité pour la recherche de chaînes répétées. À l’origine celles-ci ont été utilisées pour la manipulation de séquences biologiques ou pour la recherche de facteurs requêtes sur du texte en langue naturelle. Elles ont ensuite également été employées par certaines implantations d’outil de recherche de similarité sur du code source (ou sur du langage naturel [132]). Nous pouvons ainsi citer Phoenix [78] et CCFinder [71, 89] qui réalisent une recherche de facteurs répétés par table ou arbre de suffixes sur des chaînes issues de la lexémisation de code source. Dans [72], Koschke et al. proposent une approche équivalente en travaillant sur une représentation par arbre de syntaxe abstrait qui est ensuite transformé en chaîne de lexèmes par parcours de l’arbre. Une recherche de facteurs répétés est ensuite réalisée après construction d’un arbre de suffixes.