Méta-lexémisation

La manipulation de longues chaînes de lexèmes peut être particulièrement contraignante pour les applications de recherches de similitudes sur des projets de taille importante. Une approche présentée dans le chapitre 6 consiste à utiliser des structures d’indexation de suffixes. Elle présente l’avantage de permettre la détection de similitudes avec un seuil minimal de lexèmes paramétrable mais au prix d’une utilisation importante de mémoire de masse, même pour les implantations les plus économes.

Afin de permettre un passage à l’échelle, l’usage d’empreintes afin de représenter des échantillons des séquences de lexèmes à indexer en base s’avère intéressant. Nous étudions tout d’abord la génération d’empreintes à partir de k-grams pour ensuite nous interroger sur les méthodes de sélection d’empreintes. Celles-ci permettent de choisir uniquement certaines empreintes de méta-lexèmes à référencer afin de diviser la taille de la base d’indexation par un facteur fixe. Ces empreintes sont ensuite utilisées pour la recherche de zones de similarité entre projets indexés et un projet requête.

Dans un dernier temps, nous nous intéressons à la recherche de correspondances exactement similaires et non chevauchantes entre séquences de lexèmes : à cet effet, nous utilisons une méthode de méta-lexémisation avec longueur de k-gram variable. Ceci est l’occasion de présenter la méthode de tuilage Greedy String Tiling [82] avec quelques améliorations que nous proposons afin d’améliorer la complexité temporelle dans certaines situations. Cette technique est alors adaptée à la recherche de correspondances sur une base de projets indexés.

Génération d’empreintes 

Translation d’une chaîne en k-grams

Définition 8.1. Soit t = t1t2 · · ·tn une chaîne de lexèmes de Σ. Nous définissons la chaîne de k-grams dérivée de t comme la chaîne Gk(t) = u = u1u2 · · · un−k+1 avec : u1 = t1 t2 · · · tk u2 = t2 t3 · · · tk+1 · · · ui = ti ti+1 · · · ti+k−1 · · · un−k+1 = tn−k+1 tn−k+2 · · · tn 131 8. Méta-lexémisation La représentation d’une chaîne en k-grams permet l’introduction d’un nouvel alphabet de méta-lexèmes de Σ k pour représenter la chaîne originale.

Les similitudes sont ensuite recherchées en utilisant le nouveau méta-alphabet de cardinalité plus importante mais dont la fréquence d’apparition de chaque méta-lexème est diminuée. Nous notons qu’aucune similitude portant sur des séquences identiques de lexèmes de taille inférieure à k ne peut plus alors être détectée. Un mot sur la cardinalité de l’alphabet des k-grams La cardinalité de l’alphabet des k-grams est bornée par |Σ| k ; cependant parmi tous les k-uplets de lexèmes, seule une faible proportion représentent des successions de lexèmes grammaticalement et sémantiquement admissibles.

Ainsi, par exemple en langage C, le 2-gram « ({ » est interdit alors que le 2-gram « ){ » peut être rencontré. Les k-grams grammaticalement valides peuvent ainsi être énumérés par analyse de la grammaire pour des valeurs faibles de k. Nous présentons en figure 8.1 le nombre de k-grams différents pour un projet Java de volume important (OpenJDK 1.6 avec environ 1 million de lignes de code) ainsi que la répartition de leur fréquence. Ayant considéré les lexèmes obtenus après parcours en profondeur de l’arbre de syntaxe concret, nous constatons qu’il existe |Σ| = 154 1-grams, 1670 2-grams, 7480 3-grams et 20666 4-grams1 dont le nombre n’augmente que peu avec le volume de code analysé.

En revanche le nombre de k-grams distincts pour des valeurs plus élevées de k est approximativement linéaire avec le volume de code traité : il s’établit à N − k + 1 − d, d étant le nombre de k-grams dupliqué (avec typiquement d −→ 0 lorsque k −→ N). 8.1.2 Hachage des k-grams Introduction Étant donné l’espace des k-grams Σ k issu de l’alphabet de lexèmes Σ, nous souhaitons représenter chaque k-gram par un entier. À cet effet, nous introduisons une fonction de hachage réalisant cette correspondance. Si l’alphabet Σ est de cardinalité finie, il est possible d’utiliser la fonction de hachage bijective fpb suivante : fpb : (g1, g2, · · · , gk) −→ b k−1 g1 + b k−2 g2 + · · · + b 0 gk où b = |Σ| et les lexèmes g1, g2, · · · , gk de Σ sont confondus avec une valeur entière les représentant en utilisant un ordre total arbitraire sur Σ.

Il peut cependant être avantageux de limiter l’étendue de l’intervalle des entiers représentatifs en sacrifiant l’injectivité de la fonction de hachage afin de limiter l’espace mémoire occupé par chaque valeur de hachage. Afin de tester si deux valeurs de hachage désignent le même k-gram, il est alors nécessaire d’accompagner chacune de ces valeurs d’un lien vers l’occurrence de k-gram qu’elle désigne afin de pouvoir vérifier si deux valeurs de hachage sont des faux-positifs ou non.

Nous pouvons toutefois noter que seule une certaine portion de l’espace Σ k des k-grams est intersectée par des k-grams en pratique. Cela peut rendre intéressant l’ajout d’un niveau d’indirection pour la représentation des k-grams. Ceux-ci sont indexés dans une base par une valeur de hachage non obligatoirement bijective ou un arbre lexicographique et associés à une valeur entière bijective pour k petit.