Recherche et Tests
Nous avons testé plusieurs algorithmes pour comparer des chaînes et sélectionné celui qui correspondrait le mieux à nos besoins.
Nous avons comparé la chaîne A et la chaîne B pour avoir des métriques sur les différents algorithmes.
Les règles de similitude de chaîne peuvent différer d’un cas à l’autre. Si vous voulez considérer « niche » et « chien » similaires, vous utiliseriez un algorithme de similarité de chaîne qui détecte les anagrammes. Pas dans notre cas. Une application nommée « niche » et une autre nommée « chien » sont très susceptibles d’être deux applications complètement différentes.
Après quelques réflexions et recherches, nous avons trouvé des méthodes d’algorithme qui aideraient notre cas. L’algorithme du cosinus s’est avéré hors de propos pour nous, car par exemple il ne semble pas prendre en compte l’ordre des lettres, ce qui conduit à un indice de 1 (chaîne similaire) sur une anagramme (« niche » et « chien »).
Voici ce que nous avons remarqué:
Algorithme de Levenshtein
La distance de Levenshtein est le nombre minimum de modifications à un seul caractère nécessaires pour changer un mot en l’autre, de sorte que le résultat est un entier positif, sensible à la longueur de la chaîne. Ce qui rend plus difficile de dessiner un motif.
Par exemple,
- la distance de Levenshtein entre « foo » et « bar » est de 3
- la distance de Levenshtein entre « beautés » et « belles » est également de 3
- Pour nous, les humains, la paire « beautés » / « belle » est beaucoup plus similaire que la paire « foo » / « bar ». Mais la distance de Levenshtein est la même.
La métrique que nous utilisons ici est l’inverse de la distance de Levenshtein (1 / levenshtein_distance), donc le résultat est un pourcentage et est plus facilement lu par nous. Mais le problème mentionné ci-dessus est resté le même.
Où 1 est le résultat de la comparaison de chaînes identiques, « ShazamIphone » et « ShazamAndroid » ont une similitude de 0,167. « chien » et « niche » ont une similitude de 0,25.
Donc, du point de vue de l’algorithme de Levenshtein, Chien / Niche sont plus similaires que « ShazamIphone » / « ShazamAndroid » car moins de modifications sont nécessaires pour passer de « chien » à « niche », que pour passer de « ShazamIphone » à « ShazamAndroid ».
Comparaison des trigrammes
Un algorithme de trigrammes est un cas de n-gramme, une séquence contiguë de n (trois, dans ce cas) éléments d’un échantillon donné. Dans notre cas, un nom d’application est un échantillon et un caractère est un élément.
Donc La séquence « martha » a 4 trigrammes {mar art rth tha}.
Nous pouvons utiliser la méthode du trigramme pour comparer deux chaînes.
En prenant par exemple « martha » et le même mot avec une faute de frappe, « marhta », et nous pouvons calculer leurs trigrammes:
Trigrammes « martha »: {mar art rth tha}
Trigrammes « marhta »: {mar arh rht hta}
Pour mesurer la similitude, nous divisons le nombre de trigrammes correspondants dans les deux chaînes : 1 {mar} par le nombre de trigrammes uniques: 7 {mar art rth tha arh rht hta }
The result is 1/7 = 14%
Pour équilibrer l’inconvénient des caractères extérieurs (un peu pour renforcer la similitude des chaînes commençant et se terminant par les mêmes trigrammes), nous tapotons la chaîne avec des blancs de chaque côté, ce qui entraîne dans ces cas trois autres trigrammes « _ma », « ha_ » et « ta_ ».
Trigrammes « martha »: {_ma mar art rth tha ha_}
Trigrammes « marhta »: {_ma mar arh rht hta ta_}
Cela fait, le nombre de trigrammes correspondants est jusqu’à: 2 {_ma mar}
Le nombre de tous les trigrammes uniques: 9 {_ma mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
En utilisant cette méthode pour comparer « Twitter v1 » et « Twitter v2 », nous avons:
Le nombre de trigrammes correspondants: 7 {_tw twi avec itt tte ter er_}
Le nombre de tous les trigrammes uniques: 11 {tw twi avec itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
La limite de la méthode trigramme pour comparer les chaînes est que les chaînes courtes avec une (ou deux..) différents trigrammes ont tendance à produire une similitude plus faible que les longs.
C’est ainsi que nous obtenons un 0.2 similitude entre « ShazamAndroid » et « ShazamIphone », car ils ont plus de trigrammes différents.
Le nombre de trigrammes correspondants est: 5 {_sh sha haz aza zam}
Le nombre de tous les trigrammes uniques: 20
Comme il existe une forte dépendance avec la longueur de la chaîne, cela ne donne pas une bonne comparaison pour nous.
Algorithme de Jaro-Winkler
» En informatique et en statistique, la distance de Jaro-Winkler est une métrique de chaîne permettant de mesurer la distance d’édition entre deux séquences.
De manière informelle, la distance Jaro entre deux mots est le nombre minimum de transpositions à un seul caractère nécessaires pour changer un mot en l’autre.
La distance Jaro-Winkler utilise une échelle de préfixe qui donne des notes plus favorables aux chaînes qui correspondent depuis le début pour une longueur de préfixe définie »
Source : Wikipédia.
Donner « plus d’importance » aux mots avec des préfixes identiques a rendu la distance Jaro-Winkler très intéressante pour notre cas d’utilisation.
En commençant par le début avec la formule de distance Jaro, voici comment cela fonctionne. Pas de panique, on y va pas à pas :
La Distance Jaro entre deux séquences s1 et s2 est définie par:
dj est la distance Jaro
m est le nombre de caractères correspondants (caractères qui apparaissent dans s1 et dans s2)
t est la moitié du nombre de transpositions (comparer le i-th caractère de s1 et le i-th caractère de s2 divisé par 2)
|s1 | est la longueur de la première chaîne
| s2 | est la longueur de la deuxième chaîne
Avec un exemple. Prenons « martha » et « marhta ».
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
Juste en remplaçant les nombres est la formule, on obtient:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
Maintenant, nous savons quelle est la distance Jaro, passons à la distance Jaro-Winkler.
La similitude Jaro-Winkler utilise une échelle de préfixe p qui donne des notes plus favorables aux chaînes qui correspondent depuis le début pour une longueur de préfixe définie l.
p est un facteur d’échelle constant pour la mesure dans laquelle le score est ajusté à la hausse pour avoir des préfixes communs. La valeur standard de cette constante dans le travail de Winkler est p = 0,1.
l est la longueur du préfixe commun au début de la chaîne (jusqu’à un maximum de 4 caractères).
Revenons donc à l’exemple « martha » / « marhta », prenons une longueur de préfixe de l = 3 (qui fait référence à « mar »). Nous arrivons à:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
En utilisant la formule de JaroWinkler, nous allons de la distance de Jaro à 94% de similitude à 96%.
Dans notre cas, la plupart des applications similaires commencent par le même préfixe (« twitter v1 » vs « twitter v2 » ou « ShazamIphone » vs « ShazamAndroid » etc. Voir le tableau de test des algorithmes ci-dessus). C’est donc un critère important à prendre en compte.
