Typiquement, l'utilisation en est faites pour Wysistat, outil de mesure d'audience dans lequel une analyse des mots clés saisis sur les moteurs de recherche est proposé afin de regrouper les mots clés similaires pour afficher un résultat synthétique. Les recherches ont montré qu'il existait 2 principes pour comparer 2 mots ou termes :
Le Soundex : qui transforme un mot en un code basé sur la sonorité
Il y a plusieurs cas spéciaux en calculant un code de soundex : Les lettres donnant le même soundex qui sont immédiatement à côté l'une de l'autre sont supprimées (dédoublonnage). Ainsi Pfizer devient Pizer, le sac devient sac, Czar devient voiture (;-) enfin ... car), Collins devient Colins, et Mroczak devient Mrocak. Exemples de Soundex :
Mot
Soundex
Washington
W252
Wu
W000
DeSmet
D253
Gutierrez
G362
Pfister
P236
Jackson
J250
Tymczak
T522
Ashcraft
A261
On voit que le soundex est très grossier dans son analyse : seuls les 3 premières consonnes sont conservées. De plus, il n'est pas adapté à des mots longs voir à des expressions (du type "application soundex"). Le point intéressant est surtout le principe d'amalgame des lettres resemblantes, i.e. m et n sont équivalentes ...
On voit que cet algorythme est en o(n2) ce qui peut rapidement poser des soucis en terme de temps de traitement. Exemple de script PERL qui réalise ce calcul : sub LCS_Length($s1, $s2) { my($s1,$s2)=@_; my(@LCS_Length_Table,$m,$n,$i,$j); $m = length($s1); $n = length($s2); for($i=1; $i < $m; $i++){$LCS_Length_Table[$i][0]=0;} for($j=0; $j < $n; $j++){$LCS_Length_Table[0][$j]=0;}
Cette algorythme est bien adapté à la comparaison de terme, par contre il manque de souplesse au niveau des effets de bord (lettre quasi similaire, erreur de frappe, pluriel, ...).
IV : Algorythme de comparaison textuel En réalisant un agglomérat de ces 2 algorythmes, nous allons pouvoir faire un regroupement efficace de notre liste de termes. Le principe est simple :
Prendre la correspondance des lettres du soundex (en l'adaptant quelque peu)
Puis calculer la similarité entre les termes obtenus
Le travail sur les sonorités va se faire sur toute la longueur des chaîne de caractère, mais sans supprimer les voyelles. Nous aboutissons alors aux transformations faites dans la fonction add_soundex_rule ci-dessous. Cette partie peut être modifiée aisément à souhait en s'adaptant aux problématiques linguistiques spécifiques. Ensuite, une fois les 2 termes transformés, on va mesure leur taux de ressemblance grâce à l'algorythme similar text.
Exemple sur un script PERL : sub LCS_Length($s1, $s2) { my($s1,$s2)=@_; my(@LCS_Length_Table,$m,$n,$i,$j); $m = length($s1); $n = length($s2); for($i=1; $i < $m; $i++){$LCS_Length_Table[$i][0]=0;} for($j=0; $j < $n; $j++){$LCS_Length_Table[0][$j]=0;}
$lcs=0; if (abs(length($s1)-length($s2))<6){$lcs = &LCS_Length($s1,$s2);} #longest common sub sequence else{$lcs = 0;} $ms = (length($s1) + length($s2)) / 2;
if ($ms>0){ $tab[0]=($lcs*100)/$ms; $tab[1]=$lcs;} else{$tab[0]=0;$tab[1]=0;} return (@tab); }
V : Conclusions
En s'appuyant sur 2 algorythme bien connu, cette étude amène à la réalisation d'un algorythme assez puissant dans la comparaison des termes d'une liste. La transformation soundex peut être adaptée à une langue particulière pour prendre en compte une propriété linguistique spéciale. La fonction get_lcs retourne un pourcentage représentant la ressemblance entre les 2 termes. On peut donc jouer sur le taux de ressemblance à atteindre pour regrouper plus ou moins. Le seul inconvénient de cet algorythme est son temps d'exécussion qui est en o(n2) ou plus justement o(n*m) où n et m sont les longueurs des chaines traitées. Une optimisation peut être mise en place en restreignant la comparaison de type similar text qu'au terme de longueur proche (ABS(long(chaine1)-long(chaine2))<5).
