Cet algorithme mesure la similarité entre deux chaînes de caractères pour la recherche de doublons par exemple. Tout comme les algorithmes de Damerau-Levenshtein et les indices de similarité Cosinus, Dice, Jaccard…, la distance est normalisée entre 0 et 1. Plus la similarité est forte plus la distance tend vers 1.
La fonction VBA
Optional ByVal LongueurPrefixe As Byte = 3, _
Optional ByVal TypeComparaison As VbCompareMethod = vbBinaryCompare) As Single
'La distance de jaro_Winkler mesure la similarité entre deux chaines de caractères (s1 et s2)
'La distance est normalisée entre 0 et 1 (1 = similarité maximale)
'si LongueurPrefixe [0,4] = 0 => Distance de Jaro
'Référence : http://fr.wikipedia.org/wiki/Distance_de_Jaro-Winkler et références
'Remarques : Préparation parfois nécessaire des chaînes : ucase(),trim(),diacritiques
' Quelques libertés prises pour le calcul de la fenêtre (dMax) / Wikipédia
'Auteur : Philben v1.0 - Free to use
Const cMaxLongueurPrefixe As Byte = 4, cCoeffPrefixe As Single = 0.1
Dim l1 As Long, l2 As Long, dMax As Long, i As Long, j As Long, k As Long
Dim jMin As Long, jMax As Long, m As Long, t As Long, p As Long, lam1 As Long
Dim c1 As String, r As Single, aUsed() As Boolean, ac2() As String, am1() As Long
l1 = Len(s1): l2 = Len(s2)
If l1 > 0 And l2 > 0 Then
ReDim aUsed(1 To l2): ReDim ac2(1 To l2)
For i = 1 To l2: ac2(i) = Mid$(s2, i, 1): Next i
If l1 >= l2 Then
'dMax (1/2 fenêtre) calculée avec la + courte chaîne et non la + longue ! (voir blog)
dMax = (l2 + 1) \ 2 - 1 'arrondi sup. de dMax (l=1 => 0, l=2 => 0, l=3 => 1)
Else
dMax = (l1 + 1) \ 2 - 1
End If
If LongueurPrefixe > cMaxLongueurPrefixe Then LongueurPrefixe = cMaxLongueurPrefixe
jMin = 1
If dMax < l2 Then jMax = dMax Else: jMax = l2
For i = 1 To l1
c1 = Mid$(s1, i, 1)
If i > dMax + 1 Then jMin = jMin + 1
If jMax < l2 Then jMax = jMax + 1
If jMin > jMax Then Exit For 'définitivement hors fenêtre => Fin
For j = jMin To jMax
If Not aUsed(j) Then
If StrComp(c1, ac2(j), TypeComparaison) = 0 Then
m = m + 1 'Match
If i = j And i <= LongueurPrefixe And p = i - 1 Then
p = p + 1 'Préfixe commun
Else
lam1 = lam1 + 1: ReDim Preserve am1(1 To lam1): am1(lam1) = i
End If
aUsed(j) = True
Exit For
End If
End If
Next j
Next i
'Compte les tranpositions
k = p + 1
For i = 1 To lam1
For j = k To l2
If aUsed(j) Then Exit For
Next j
If StrComp(Mid$(s1, am1(i), 1), ac2(j), TypeComparaison) <> 0 Then t = t + 1
k = j + 1
Next i
t = t \ 2
If m > 0 Then
r = (m / l1 + m / l2 + (m - t) / m) / 3 'Distance de Jaro
r = r + (p * cCoeffPrefixe * (1 - r)) 'Extension de Winkler
End If
End If
JaroWinkler = r
End Function
Paramètres de la fonction
‘S1′ et ‘S2′ correspondent aux deux chaînes de caractères à étudier.
‘LongueurPrefixe’ permet de choisir la longueur du préfixe commun entre les deux chaînes. Cette longueur permet de calculer l’apport de Winkler à l’algorithme de Jaro. Cette longueur est comprise entre 0 et 4 (3 par défaut). La distance de Jaro est retournée lorsque ce paramètre est égal à 0.
‘TypeComparaison’ permet de choisir le type de comparaison entre les deux chaînes : Soit une comparaison binaire (par défaut) soit une comparaison textuelle (moins restrictive car ne tient pas compte de la casse des caractères mais généralement moins performante).
Il sera souvent nécessaire de prétraiter les chaînes par UCase()/LCase() (casse uniforme des caractères), Trim() (suppression des espaces en début et fin de chaîne) et remplacer les caractères diacritiques pour ne pas ‘parasiter’ l’algorithme (voir ici).
Tests
J’ai récolté dans une publication de W. E. Winkler (voir référence plus bas) et sur le Web des exemples pour tester les résultats de mon code. La longueur du préfixe est fixée à 4.
Dim i As Integer, r As Single, v() As Variant
v = Array("SHACKLEFORD", "SHACKELFORD", 0.982, "DUNNINGHAM", "CUNNIGHAM", 0.896, "NICHLESON", "NICHULSON", 0.956, _
"JONES", "JOHNSON", 0.832, "MASSEY", "MASSIE", 0.933, "ABROMS", "ABRAMS", 0.922, "HARDIN", "MARTINEZ", 0#, _
"ITMAN", "SMITH", 0#, "JERALDINE", "GERALDINE", 0.926, "MARHTA", "MARTHA", 0.961, "MICHELLE", "MICHAEL", 0.921, _
"JULIES", "JULIUS", 0.933, "TANYA", "TONYA", 0.88, "DWAYNE", "DUANE", 0.84, "SEAN", "SUSAN", 0.805, _
"JON", "JOHN", 0.933, "JON", "JAN", 0#, "DIXON", "DICKSONX", 0.813, "VOYAGE", "AGENDA", 0.444, _
"TRAVEL", "TRAIN", 0.9, "ABCVWXYZ", "CABVWXYZ", 0.958)
Debug.Print "Chaîne 1", "Chaîne 2", "Attendue", "Obtenue"
Debug.Print "--------", "--------", "---------", "-------"
For i = LBound(v) To UBound(v) Step 3
r = JaroWinkler(v(i), v(i + 1), 4) 'Longueur Prefixe = 4
Debug.Print v(i), v(i + 1), v(i + 2), Round(r, 3), IIf(Abs(r - v(i + 2)) > 0.001, "*** Ecart ***", "")
Next i
End Function
Résultats et commentaires
-------- -------- --------- -------
SHACKLEFORD SHACKELFORD 0,982 0,982
DUNNINGHAM CUNNIGHAM 0,896 0,896
NICHLESON NICHULSON 0,956 0,956
JONES JOHNSON 0,832 0,832
MASSEY MASSIE 0,933 0,933
ABROMS ABRAMS 0,922 0,922
HARDIN MARTINEZ 0 0,722 *** Ecart ***
ITMAN SMITH 0 0,622 *** Ecart ***
JERALDINE GERALDINE 0,926 0,926
MARHTA MARTHA 0,961 0,961
MICHELLE MICHAEL 0,921 0,921
JULIES JULIUS 0,933 0,933
TANYA TONYA 0,88 0,88
DWAYNE DUANE 0,84 0,84
SEAN SUSAN 0,805 0,805
JON JOHN 0,933 0,933
JON JAN 0 0,8 *** Ecart ***
DIXON DICKSONX 0,813 0,813
VOYAGE AGENDA 0,444 0,444
TRAVEL TRAIN 0,9 0,79 *** Ecart ***
ABCVWXYZ CABVWXYZ 0,958 0,958
Les distances obtenues sont parfois différentes des distances attendues (4 écarts constatés).
Concernant les couples HARDIN/MARTINEZ, ITMAN/SMITH, JON/JAN, ils sont fournis par W. E. Winkler qui devait utiliser un algo un peu différent de celui décrit dans Wikipédia (en effet, sa fonction strcomp.c est plus complexe…)
Concernant le couple TRAVEL/TRAIN et la distance attendue de 0,9, je pense qu’il s’agit d’une coquille de l’auteur car la distance de Jaro dans la même publication était seulement de 0,7.
De plus, l’applet java de ce site donne des résultats proches ou identiques aux miens.
Remarque
L’éloignement maximal (variable dMax dans mon code) devrait être calculé à l’aide de la plus grande longueur de chaîne. J’ai préféré utiliser la plus courte pour éviter des résultats ‘étonnants’ avec certaines chaînes de caractères.
Par exemple, en allongeant la seconde chaîne ‘cba’ et en utilisant la plus grande longueur des deux chaînes de caractères, on obtient :
?JaroWinkler("abc","cbau") '0,528
?JaroWinkler("abc","cbauu") '0,756
?JaroWinkler("abc","cbauuu") '0,722
La similarité diminue avec 4 caractères (0,528) puis augmente paradoxalement avec 5 caractères (‘cbauu’ donne 0,756)!
Pourquoi ?
Dans le 1er exemple, l’éloignement maximal (variable dMax dans le code) est égal à 1 et on obtient une seule concordance (lettre ‘b’) entre les 2 chaînes.
Dans le 2ème exemple, la similarité chute légèrement car la longueur de la chaîne n°2 est de 4 au lieu de 3 et celle-ci intervient en tant que dénominateur dans le calcul de la distance de Jaro. L’éloignement maximal reste égal à 1.
Dans le 3ème exemple, l’éloignement maximal est égal à 2 car la longueur de la chaîne n°2 est de 5 caractères (arrondi supérieur de 5/2 – 1 = 2). Cet éloignement permet d’obtenir 3 correspondances (‘a’, ‘b’, ‘c’) et une transposition (‘a’ et ‘c’). Ces 3 correspondances au lieu d’une seule augmentent la similarité malgré la transposition et la longueur de la chaîne n°2.
Pour éviter ce problème, une solution consiste donc à utiliser la plus petite longueur des deux chaînes :
?JaroWinkler("abc","cbau") '0,528
?JaroWinkler("abc","cbauu") '0,511
?JaroWinkler("abc","cbauuu") '0,5
Conclusion
Algorithme rapide et efficace sur des chaînes relativement courtes.
Références
Wikipédia: Distance de Jaro-Winkler
Publication de W. E. Winkler.
@+
Philippe