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
'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("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
Bravo pour cet excellente fonction, très utile pour qualifier des données quand on n’a plus que le nom sur lequel s’appuyer…
Encore merci.