Méthodes de groupement de correspondances

Méthodes de groupement de correspondances

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

Anti-unification Introduction L’opération d’anti-unification consiste à générer, pour plusieurs éléments e1, e2, · · · , en, 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 e1, e2, · · · , en 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 première approche, si E est l’élément anti-unificateur avec les symboles substitutifs σ1, σ2, · · · , σk et ei dérivable de E en substituant σ1 par σ1(ei), …, σk par σk(ei), nous cherchons à minimiser la fonction f suivante de somme de coûts de substitution : f : E −→ X i∈[0..n] X j∈[0..k] |σj (ei)| L’anti-unification peut être réalisée sur des éléments tels que des chaînes de lexèmes, les termes substitués étant des facteurs, ou alors sur des arbres de syntaxe avec pour termes susbtitués des séquences de sous-arbres frères.

Exemple Nous traitons pour exemple les deux fonctions f1 et f2 suivantes réalisant pour l’une la moyenne arithmétique des valeurs d’un tableau et pour l’autre la moyenne quadratique : Après lexèmisation des fonctions f1 et f2, nous déterminons sa chaîne de lexèmes antiunifiante :  double moyenneA(double[] tab) { double somme = 0.0; 4 for (int i=0; i < tab.length(); i++) somme = somme + tab[i]; return somme / tab.length(); } 1 double moyenneA(double[] c) { 3 double addition = 0.0; for (int i=0; i < c.length(); i++) addition = addition + c[i] ∗ c[i]; return somme / c.length(); } f1 : moyenne arithmétique f2 : moyenne quadratique Fig. 13.1 – Deux fonctions de calcul de moyenne double ID1(tab [] ID2) { double ID3 = 0.0; for (int ID4=0; ID4 < ID2 . length; ID4++) ID3 = ID3 + EXPR; return ID3 / ID2 . length ;

Algorithme d’anti-unification de deux éléments

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. Anti-unification de deux chaînes de lexèmes

Déterminer un anti-unifié de deux chaînes u et v consiste à calculer une chaîne w = α1σ1α2σ2 · · · αkσk telle que l’on puisse obtenir u et v à partir de w en substituant σ1, σ2, …, et σk par des facteurs de u (σ1(u)) et v (σ1(v)) respectivement. Nous nous intéressons à la recherche d’un anti-unifié minimisant la somme des coûts de substitution (i.e. |σ1(u)| + · · · + |σk(u)| et |σ1(v)| + · · · + |σk(v)|). Cela revient à maximiser la longueur de la séquence de facteurs communs α1, α2, · · · , αk, une des séquences satisfaisant cette condition peut être obtenue par le calcul d’un LCS entre u et v en temps Θ(|u| |v|). La séquence des facteurs communs α1, · · · , αk étant calculée, nous pouvons déduire les substitutions pour chaque σi intersticiels pour u et v.

Nous disposons alors d’un jeu de k symboles substitutifs potentiellement réductible en identifiant les substitutions similaires sur u et v. Ainsi si σi(u) = σj (u) et σi(v) = σj (v), nous remplaçons le symbole substitutif de σj par une occurrence supplémentaire de σi .

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

Anti-unification de deux arbres de syntaxe

Nous proposons une méthode récursive d’anti-unification de deux arbres de syntaxe s’inspirant 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 = α1σ1α2σ2 · · · αkσk utilisée pour anti-unifier les chaînes des sous-arbres enfants directs de A et B. Afin de rendre la comparaison des sous-arbres enfants plus aisée, nous identifions chacun d’eux par une empreinte calculée au moyen d’une fonction de hachage : on supposera celle-ci suffisamment longue pour éviter toute collision.

L’obtention de la chaîne des facteurs identifiés αi entremelés de fossés σi 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écursivement, selon la même méthode, deux à deux les arbres σi(A) et σi(B) correspondant aux fossés. Lorsqu’aucune des racines des fossés ne correspondent, la récursion est stoppée.