La manipulation de longues chaînes de lexèmes

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.

La représentation d’une chaîne en k-grams permet l’introduction d’un nouvel alphabet de méta-lexèmes de Σ 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.; 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-grams 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 ).

Σ 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. polynomiale présentée précédemment, nous pouvons calculer chaque valeur de hachage de k-grams en temps O(k) (seules k additions et k − 1 multiplications sont nécessaires). Nous limitons la cardinalité de l’espace de hachage à N (en pratique une puissance de 2) en considérant la fonction non injective f pDéfinition 8.2. (Incrémentalité simple) Une fonction de hachage f sur des k-grams est dite incrémentale si le k-gram d’indice i (i > 1) est calculable à partir de la donnée du k-gram précédent d’indice i − 1 en un temps constant (indépendant de la valeur de k).(t) est ainsi calculable en temps O(n). Il est alors possible de rechercher un facteur de k lexèmes sur une chaîne en temps linéaire indépendant de k en calculant les valeurs de hachage de tous ses k-grams comme l’ont proposé Karp et Rabin [53]. Nous présentons en figure 8.2 un exemple de hachage incrémental d’une chaîne de lexèmes après attribution d’une valeur numérique à chaque lexème.