VBA : Distance de Jaro-Winkler

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

Public Function JaroWinkler(ByVal s1 As String, ByVal s2 As String, _
                            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.

Public Function testJW()
   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

Chaîne 1      Chaîne 2      Attendue      Obtenue
--------      --------      ---------     -------
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","cba") '0,556
?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","cba") '0,556
?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

Laisser un commentaire