Métriques de similarité

Métriques de similarité

Métriques directes pour la comparaison d’arbres de syntaxe

Les arbres de syntaxe, comme explicité en 9.1.1, peuvent faire l’objet d’une quantification vectorielle de certaines propriétés syntaxiques et sémantiques. Ces métriques sont facilement modifiables par certains procédés d’obfuscation. En revanche, lorsque du code copié sans volonté obfuscatoire est recherché, celles-ci peuvent présenter un intérêt afin de constituer des groupements préalables dont les paires pourront être analysées avec plus d’attention. La détermination de distance d’édition sur les arbres (cf 5.5) permet parallèlement la détermination de correspondances approchées avec fossés au prix d’une complexité temporelle quadratique en lexèmes traités. Le calcul de distance d’édition est donc utilisable plutôt dans une optique d’approfondissement de la comparaison d’unités que pour une préselection de celles-ci. 12.2 Métriques directes pour la comparaison de chaînes de lexèmes Quantifier la similarité entre deux chaînes de lexèmes peut être réalisé en utilisant plusieurs types de distance dont leur distance de Hamming ou leur distance d’édition. La distance de Hamming [12] nécessite la simple comparaison de lexèmes de même indice alors que la distance d’édition requiert l’utilisation de méthodes d’alignement par programmation dynamique comme décrites dans le chapitre 5, de complexité temporelle quadratique. Lorsque la détermination de la similarité deux à deux de k chaînes de n lexèmes est requise, calculer la distance d’édition pour toutes les paires nécessite O(k 2n 2 ) opérations. La distance de Hamming n’est, elle, pas adapté à la comparaison de chaînes pouvant faire l’objet d’insertion ou de suppression de lexèmes. La table de suffixes d’un ensemble de chaînes peut être mise à profit pour quantifier leur similarité. Ainsi, lorsque deux suffixes de chaînes différentes sont proches dans la table de suffixes et partagent un préfixe commun de longueur L, les chaînes sous-jacentes partagent au moins un facteur de longueur L. Des chaînes partageant de multiples suffixes proches

Métriques de similarité dans la table de suffixes partagent autant de facteurs communs

De cette observation, nous déduisons deux heuristiques de calcul de matrice de similarité sur un ensemble de k chaînes. La première, inspirée de [17] quantifie les alternances dans la table de suffixes. Quant à la seconde, elle permet le calcul d’une matrice de similarité creuse, seules les paires de chaînes de similarité notable étant considérées. 

Quantification des alternances sur table de suffixes

Pourquoi quantifier l’alternance ? Considérons deux chaînes de lexèmes u et v dont la table de suffixes t = SA ({u, v}) est calculée. Si u et v possèdent des suffixes communs de longueur non nulle, ceux-ci sont ordonnés dans t selon l’ordre lexicographique de u et v. Si u = v, par convention, les suffixes de u précèdent ceux de v dans la table t. Dans cette situation, il y a alternance parfaite de suffixes égaux de u et de v. Si l’on substitue à chaque suffixe sa chaîne d’appartenance dans la table, nous obtenons t ′ = (u)(v)(u)(v)· · ·(u)(v). De manière générale, t ′ est de la forme (u) i1 (v) j1 (u) i2 (v) j2 · · ·(u) iz (v) jz avec tous les ik et jk non nuls pour k ∈ [1..z], sauf éventuellement pour i1 et jz. Nous pouvons alors quantifier le degré d’alternance alter(t) de la table t par la formule suivante : alter(t) = X k∈[1..z]/ik>0 (ik − 1) + X k∈[1..z]/jk>0 (jk − 1) En particulier, si u = v, alter(t) = 0. Ceci est également le cas si |u| = |v| et que pour tout lexème d’indice i de u, u[i] < v[i]. En supposant |u| = |v| avec u et v générés aléatoirement, la proababilité d’obtention d’une séquence de taille ik est de 1 2 ik . La valeur moyenne de alter(t) est donc de |u| /2 et sa valeur maximale de |u| + |v| − 2. Afin de gérer les cas où |u| < |v| et obtenir une valeur inférieure à 1 nous normalisons alter(t) et déduisons une métrique de similarité salter : altern(t) = 1 |u|+|v|−2 (alter(t) − (|v| − |u|)) salter(t) = 1 − altern(t) Ainsi, si u est un facteur de v, altern(t) = 0 et salter(t) = 1. Intuitivement, alter(t) peut donc être considérée comme une métrique de similarité entre u et v, calculable en temps O(|u|+|v|) par l’emploi d’un algorithme de construction de table de suffixes linéaire. Celle-ci pourrait donc être utilisée afin de calculer une matrice de similarité sur un ensemble de chaînes de lexèmes, issues par exemple, de la lexémisation de projets à comparer. Les paires de chaînes de similarité importante pourraient ensuite faire l’objet d’une comparaison plus coûteuse comme par la détermination d’une séquence d’opérations d’édition par alignement. Exemple Nous reprenons les chaînes α = abcdef, β = gbcdehef,γ = cijkcdeh dont la table de suffixe a été exposée en figure 6.1. Nous obtenons la séquence de chaînes t ′ = α 2βαβγ2αβγαβγβαβ3γ 4 . Nous filtrons t ′ sur α et β pour obtenir alter(t < α, β >) : t ′ < α,β >= α 2βαβαβαβ2αβ3 , soit une valeur de 4. Nous faisons de même pour les couples (α,γ) et (β,γ) pour obtenir finalement la matrice de valeurs suivante (les valeurs normalisées sont  parenthésées) : α β γ β 4(1/6) γ 6(1/3) 8(1/2) Calcul de la métrique d’alternance pour chaque paire de chaînes d’un ensemble Nous proposons deux méthodes de calcul de la métrique d’alternance pour chacune des paires d’un ensemble de chaînes. La première méthode est la plus naturelle : elle consiste à établir une table de suffixes pour chaque paire et à y quantifier les alternances. Pour k chaînes de n lexèmes, la matrice de valeurs de métrique d’alternance est donc calculée en temps k(k−1) 2 (T(n)+O(n)) avec T(n) le temps de calcul de chaque table de suffixes (généralement en Θ(n)). Pour la seconde méthode, nous supposons qu’une table de suffixes pour l’ensemble des chaînes est déjà calculée (en T(kn)) : une méthode de filtrage dichotomique peut alors être employée afin de déterminer la métrique d’alternance pour chaque paire en un temps global équivalent.

Quantification des suffixes sur fenêtre

Déterminer exhaustivement les valeurs de similarité d’une matrice pour un ensemble conséquent de chaînes est particulièrement coûteux : il pourrait être préférable de ne s’intéresser qu’aux valeurs de similarité pour les paires de chaînes présentant le plus haut niveau de ressemblance. À cet effet nous introduisons une métrique quantifiant la similitude entre deux chaînes par la proximité, bornée par une fenêtre, de leurs suffixes dans la table de suffixes. Découpage de deux chaînes en facteurs communs Afin d’introduire la métrique, nous considérons le problème du découpage de chaînes en facteurs commun. Il s’agit pour deux chaînes u et v de trouver une décomposition en facteurs communs maximisant la couverture. Celle-ci n’est pas unique : une stratégie exposée par l’algorithme de Greedy String Tiling exposé en 8.4 consiste à identifier les facteurs communs du plus long au plus court. Plus qu’aux facteurs eux-mêmes, nous nous intéressons à leur couverture en nombre de lexèmes des deux chaînes. À cet effet nous proposons la méthode suivante. Dans un premier temps, nous établissons la table de suffixes de T = {u, v}. Chaque u[i] est en position p = rSA (T) [(1, i)]. Pour tout suffixe de v, nous déterminons la valeur de lcp L avec u[i..] : si celle-ci n’est pas nulle et que l’occurrence de facteur sur u et v n’intersecte pas avec des occurrences déjà prises en compte, nous incrémentons la valeur de similarité s(u, v) de L. s(u, v) correspond à la couverture maximale par facteurs non-recouvrants communs de u et de v. La métrique précédemment définie ne présente cependant pas un réel intérêt pratique : une unité syntaxique peut contenir l’ensemble des lexèmes d’une autre unité, avec des facteurs communs courts avec s(u, v). Seule la considération de facteurs assez longs est intéressante. 229 12. Métriques de similarité Détermination de la métrique sur un ensemble de chaînes Nous introduisons une métrique variante de la couverture maximale en facteurs définie par les modalités de calcul suivantes pour un ensemble de chaînes T = {t1, t2, · · · , tk}. Nous calculons la table de suffixes pour T. Pour chaque chaîne ti nous parcourons la table de suffixes de l’occurrence de suffixe ti [1] à ti [n]. Pour le suffixe ti [j] de position p dans la table, nous considérons l’ensemble des suffixes de la table dans l’intervalle [p..p+ζ] où ζ est la taille fixée de la fenêtre afin de rechercher les préfixes de suffixes communs. Pour chaque l ∈ [1..ζ], il s’agit de déterminer le LCP de ti [j] et SA (T) [p+l], suffixe de la chaîne ti ′ (par exemple en déterminant le LCA des intervalles parent de ces deux occurrences de suffixe). Nous incrémentons s(ti , ti ′) de la valeur du LCP, en supposant que les occurrences de facteur ne sont pas en intersection avec d’autres facteurs déjà considérés pour le calcul. La limitation de la taille de la fenêtre permet d’éviter la prise en compte des facteurs courts. Elle rend également la métrique sensible à l’environnement des chaînes : deux chaînes ne possèdent pas la même valeur de similarité selon les autres chaînes incluses dans l’ensemble T considéré. La présence d’environ ζ chaînes identiques dans T avec une fenêtre d’examen de ζ camoufle la similarité éventuelle pour des paires comprenant une des ces chaînes et une autre chaîne de l’ensemble. Normalisation La valeur de similarité s(ti , ti ′) peut être normalisée en la rapportant sur la valeur maximale potentielle min (|ti | , |ti ′|). Complexité Cette heuristique permet le calcul d’une matrice creuse comprenant au maximum ζN valeurs (où N = |t1| + |t2| + · · · + |tk|). Si ζ << k, cette méthode prend tout son intérêt en évitant le calcul exhaustif des valeurs de similarité pour chacun des couples des chaînes.