Similarité entre deux chaînes de caractères

Pour tenter de réduire l’imperfection des ITCC, IPCC, ITPCC voire ITPCCC et plus généralement ICC(*), de nombreux algorithmes sont proposés (Soundex, Jaro-Winkler, …) et l’algorithme de Damerau-Levenshtein que j’ai implémenté ici en VBA.
Voir aussi le billet sur les indices de similarité et le billet sur la distance de Jaro-Winkler.

Le code source

Public Function DamerauLevenshteinSimilarite(ByVal s1 As String, ByVal s2 As String) As Single
'Calcul la similarité (de [0 à 1]) entre deux chaines d'après l'algorithme de Damerau-Levenshtein
'références : http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
'             http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance/
'             http://www-igm.univ-mlv.fr/~lecroq/seqcomp/node2.html
'Remarques  : Préparer les chaines car les comparaisons sont binaires : UCase(), Trim(),...
'Philben v1.0 - Free to Use
  Const cFacteur As Long = &H100&, cMaxLen As Long = 256&   'Longueur maxi autorisée des chaines analysées
  Dim l1 As Long, l2 As Long, c1 As Long, c2 As Long
   Dim r() As Integer, rp() As Integer, rpp() As Integer, i As Integer, j As Integer
   Dim c As Integer, x As Integer, y As Integer, z As Integer, f1 As Integer, f2 As Integer
   Dim dls As Single, ac1() As Byte, ac2() As Byte

   l1 = Len(s1): l2 = Len(s2)
   If l1 > 0 And l1 <= cMaxLen And l2 > 0 And l2 <= cMaxLen Then
      ac1 = s1: ac2 = s2   'conversion des chaines en tableaux de bytes

      'Initialise la ligne précédente (rp) de la matrice
     ReDim rp(0 To l2)
      For i = 0 To l2: rp(i) = i: Next i

      For i = 1 To l1
         'Initialise la ligne courante de la matrice
        ReDim r(0 To l2): r(0) = i

         'Calcul le CharCode du caractère courant de la chaine
        f1 = (i - 1) * 2: c1 = ac1(f1 + 1) * cFacteur + ac1(f1)

         For j = 1 To l2
            f2 = (j - 1) * 2: c2 = ac2(f2 + 1) * cFacteur + ac2(f2)
            c = -(c1 <> c2)   'Cout : True = -1 => c = 1

            'suppression, insertion, substitution
           x = rp(j) + 1: y = r(j - 1) + 1: z = rp(j - 1) + c
            If x < y Then
               If x < z Then r(j) = x Else r(j) = z
            Else
               If y < z Then r(j) = y Else r(j) = z
            End If

            'transposition
           If i > 1 And j > 1 And c = 1 Then
               If c1 = ac2(f2 - 1) * cFacteur + ac2(f2 - 2) And c2 = ac1(f1 - 1) * cFacteur + ac1(f1 - 2) Then
                  If r(j) > rpp(j - 2) + c Then r(j) = rpp(j - 2) + c
               End If
            End If
         Next j
         'Reculer d'un niveau la ligne précédente (rp) et courante (r)
        rpp = rp: rp = r
      Next i
      'Calcul la similarité via la distance entre les chaines r(l2)
     If l1 >= l2 Then dls = 1 - r(l2) / l1 Else dls = 1 - r(l2) / l2
   ElseIf l1 > cMaxLen Or l2 > cMaxLen Then
      dls = -1   'indique un dépassement de longueur de chaine
  ElseIf l1 = 0 And l2 = 0 Then
      dls = 1   'cas particulier
  End If

   DamerauLevenshteinSimilarite = dls
End Function

 
Explications
L’algorithme de Levenshtein mesure la distance entre deux chaînes de caractères qui est basée sur le nombre minimal de suppressions/insertions/substitutions de caractères pour passer d’une chaîne à l’autre.
L’algorithme de Damerau-Levenshtein ajoute en plus la transposition bien connue des dyslexiques du clavier (‘rehcerhce’ au lieu de ‘recherche’)…

Mon implémentation ne retourne pas une distance mais un indice de similarité allant de 0 à 1. La valeur 1 indique une similarité maximale entre deux chaînes. De plus, elle réalise une comparaison binaire des caractères, d’où parfois la nécessité de prétraiter les chaînes (UCase(), Trim(), sans accent,…)

La complexité de l’algorithme est O(m*n) avec m et n la longueur des chaînes ce qui limite son usage à des chaînes relativement courtes, des mots.
 
Exemples
On peut utiliser cette fonction dans une requête SQL pour rechercher des doublons sur une petite(!) base de données en se basant sur une ou des colonnes (nom/prénom/adresse/…) ou afficher les données les plus similaires à une chaîne de recherche.

Par exemple, mon doigt a rippé par deux fois sur mon clavier AZERTY et j’ai enchaîné un redressement un peu tardif qui a eu pour résultat : ‘tbalrette’

La recherche de similarité dans une table de synonymes (+ de 36 000 entrées) a affiché :

  • barette (0,78)
  • tablette (0,78)
  • turlurette (0,70)
  • targette (0,67)

Je voulais écrire ‘tablette’.

Comme d’habitude, vous pouvez tester la fonction dans la fenêtre Exécution du VBE :

?DamerauLevenshteinSimilarite("tbalrette","tablette") '=>0,7777778
?DamerauLevenshteinSimilarite("apple","appel") '=>0,8
?DamerauLevenshteinSimilarite("chrizantème","chrysanthème") '=>0,75
?DamerauLevenshteinSimilarite("rehcerche","recherche") '=>0,8888889
?DamerauLevenshteinSimilarite("dnas","dans") '=>0,75
?DamerauLevenshteinSimilarite("machine","appareil") '=>0,125
?DamerauLevenshteinSimilarite("le jour se lève","le jour se couche") '=>0,7058824

 
(*)

  • ICC : Interface Chaise-Clavier
  • ITCC : Interface Téléphone-Chaise-Clavier
  • IPCC : Interface Papier-Chaise-Clavier
  • ITPCC : Interface Téléphone-Papier-Chaise-Clavier
  • ITPCCC : Interface Téléphone-Papier-Collègue-Chaise-Clavier

Pour en savoir plus sur le thème errare humanum est

@+

Philippe

Une réflexion au sujet de « Similarité entre deux chaînes de caractères »

Laisser un commentaire