Après l’algorithme de Damerau-Levenshtein qui mesure la distance minimale d’édition entre deux textes, je présente un algorithme plus simple et donc plus rapide qui calcule différents indices de similarité (Cosinus, Dice, Jaccard, Kulczynski,…) à partir de n-grammes (n-grams/q-grams en anglais) ou sous-séquences continues de caractères.
Les fonctions
Placer l’ensemble du code suivant dans un module standard.
L’énumération pour faciliter le choix du coefficient de similarité :
eCosinus = 1
eDice = 2
eJaccard = 3
eKulczynski = 4
eBraunBlanquet = 5
eSimpson = 6
End Enum
La fonction Ngram appelée par la fonction principale pour créer les grammes de la chaîne :
Dim i As Integer, n As Integer, Fin As String
If Q > 0 Then
If Q > 1 Then
If InversionGram Then Fin = vbVerticalTab Else: Fin = vbFormFeed
s = String(Q - 1, vbVerticalTab) & s & String(Q - 1, Fin)
End If
n = Len(s) - Q: ReDim qgs(0 To n)
For i = 0 To n: qgs(i) = Mid$(s, i + 1, Q): Next i
Ngram = n + 1
Else
qgs = Split(s, " ", , vbBinaryCompare)
Ngram = UBound(qgs) + 1
End If
End Function
La fonction principale :
Optional ByVal Indice As eIndiceSimilarite = eIndiceSimilarite.eDice, _
Optional ByVal TypeNgram As Integer = 1, _
Optional ByVal InversionGram As Boolean = False, _
Optional ByVal MaxDistance As Integer = -1, _
Optional ByVal TypeComparaison As VbCompareMethod = vbBinaryCompare) As Single
'Retourne un indice de similarité [0 à 1] entre deux phrases
'Options : Indice : Choix de l'indice calculé (Cosinus, Dice, Jaccard, Kulczynski, BraunBlanquet)
' : TypeNgram : longueur des sous-séquences (0 : mot, 1 = caractère,...,5)
' : InversionGram : Recherche une inversion du gram :'ch' -> 'hc' (sauf pour TypeNgram = 1 !)
' : MaxDistance : distance maximum (en gram) de recherche (-1 = pas de limite)
' : TypeComparaison : binaire ou textuelle
'Remarque: parfois nécessaire de prétraiter les chaînes (ucase(),trim(),sans diacritique,...)
'Auteur : Philben - v1.0 - Free to use
Const cMaxLen As Long = 256&, cMinNgram As Integer = 0, cMaxNgram As Integer = 5
Dim l1 As Long, l2 As Long, i As Integer, j As Integer, jMin As Integer, jMax As Integer
Dim c As Integer, n As Integer, n1 As Integer, n2 As Integer
Dim aq1() As String, aq2() As String, q1 As String, q1Inv As String, Idx As Single, Res As Boolean
l1 = Len(s1): l2 = Len(s2)
If l1 >= 1 And l2 >= 1 And l1 <= cMaxLen And l2 <= cMaxLen And TypeNgram >= cMinNgram And TypeNgram <= cMaxNgram Then
If TypeNgram = 1 And InversionGram Then InversionGram = False
n1 = Ngram(aq1, s1, TypeNgram, InversionGram)
n2 = Ngram(aq2, s2, TypeNgram, InversionGram)
n = n2 - 1
For i = 0 To n1 - 1
q1 = aq1(i)
If InversionGram Then q1Inv = StrReverse(q1)
jMin = 0: jMax = n
If MaxDistance > -1 Then
If i > MaxDistance Then jMin = i - MaxDistance
If jMax > i + MaxDistance Then jMax = i + MaxDistance
End If
For j = jMin To jMax
If aq2(j) <> vbNullString Then
Res = (StrComp(q1, aq2(j), TypeComparaison) = 0)
If Not Res And InversionGram Then Res = (StrComp(q1Inv, aq2(j), TypeComparaison) = 0)
If Res Then
c = c + 1
aq2(j) = vbNullString
Exit For
End If
End If
Next j
Next i
Select Case Indice
Case eCosinus 'Ochiai, Otsuka
Idx = c / Sqr(CLng(n1) * n2) 'Cast pour éviter un overflow
Case eDice 'Pirlot's index, Sorensen, Tversky (alpha=beta=0.5), ~Czekanowski
Idx = 2 * c / (n1 + n2)
Case eJaccard 'Tversky (alpha=beta=1), ~Tanimoto
Idx = c / (n1 + n2 - c)
Case eKulczynski '2nd coeff
Idx = 0.5 * (c / n1 + c / n2)
Case eBraunBlanquet 'c/max(n1,n2)
If n1 >= n2 Then Idx = c / n1 Else Idx = c / n2
Case eSimpson 'c/min(n1,n2)
If n1 <= n2 Then Idx = c / n1 Else Idx = c / n2
End Select
Else
Idx = -1
End If
IndiceSimilarite = Idx
End Function
Définition
Un gramme (ou gram en anglais) est une sous-séquences continues de caractères de la chaîne.
Explications
Cette fonction ne mesure pas une distance entre les deux chaînes, elle compte seulement les grammes communs entre les deux chaînes S1 et S2. Ce compte est ensuite divisé par un coefficient qui distingue les indices entre eux : Ce dénominateur peut être la moyenne géométrique du nombre de n-grams (n1 et n2), la moyenne arithmétique, le nombre maxi, mini…
Le choix des indices est :
- Cosinus (équivalence : coefficients de Ochiai et de Otsuka)
- Dice (équivalence : Pirlot’s index, Sorensen, Tversky (alpha=beta=0.5), ~Czekanowski)
- Jaccard (équivalence : Tversky (alpha=beta=1), ~Tanimoto)
- Kulczynski (son second coefficient)
- Braun-Blanquet (dénominateur : max(n1,n2))
- Simpson (dénominateur : min(n1,n2))
Si le nombre de n-grams est identique entre les deux chaînes, les indices retournent la même valeur mis à part l’index de Jaccard. Par défaut le coefficient de Dice est utilisé.
La longueur des sous-séquences (paramètre TypeNgram) peut varier entre 0 et 5. Zéro indique qu’un n-gramme correspond à un mot, 1-gramme ou unigramme correspond à chaque caractère de la chaîne, 2-gramme ou bigramme est composé de deux caractères, jusqu’à 5-grammes. Au-dessus de 5-grammes la Prévention Informatique ne conseille pas de prendre le clavier !
Par exemple, les bigrammes de ‘abc’ seront ‘%a’, ‘ab’, ‘bc’ et ‘c#’ avec % et # des caractères non utilisés.
Le paramètre suivant (InversionGram) autorise ou non de compter un gramme inversé. Par exemple, ‘ab’ et ‘ba’ seront communs si InversionGram = True.
Le paramètre MaxDistance définit ou non une distance maximale (en valeur absolue) entre deux grammes communs. Si deux grammes communs sont trop éloignés, ils ne seront pas comptabilisés. Par exemple, la similarité calculée est égale à 0 si les chaînes sont ‘ab’ et ‘ba’ avec n-gram=1 et une distance maxi de zéro. Aucune limite de distance n’est définie si MaxDistance = -1.
Enfin, le dernier paramètre définit le type de comparaison entre les deux chaînes (binaire ou textuelle).
Ces indices et celui de Damerau-Levenshtein n’ont pas une réelle corrélation car ils ne mesurent pas la même chose.
Exemples
Des anagrammes qui retournent un indice de similarité parfait (1) :
?IndiceSimilarite("mammifere","mari femme",eIndiceSimilarite.eSimpson)
?IndiceSimilarite("pascal obispo","pablo picasso")
?IndiceSimilarite("stromae","maestro")
Dans le deuxième exemple, on utilise l’indice de Simpson car il divise le nombre de grammes communs par le plus petit nombre de n-grams entre n1 et n2 ce qui permet d’obtenir un indice égal à 1.
Via une requête SQL, une recherche d’anagrammes sur des mots de 12 lettres dans une table a donné (après suppression des accents) :
Conversation Conservation
Premierement Empierrement
Horticulture Horticulteur
Resurrection Reconstruire
Ternissement Ressentiment
Egalisatrice Eclairagiste
Photogravure Photograveur
Si on reprend l’exemple de ‘pascal obispo’ mais avec des bigrammes, l’indice tombe à 0,36 et remonte à 0,43 si on autorise les inversions car ‘… o…’ est commun à ‘…o …’ de ‘Pablo Picasso’. L’indice chute à 0,2 avec des trigrammes.
?IndiceSimilarite("pascal obispo","pablo picasso",,2,True)
?IndiceSimilarite("pascal obispo","pablo picasso",,3,True)
On peut aussi jouer sur la distance maxi pour modifier sensiblement le résultat :
?IndiceSimilarite("rehcehcre","recherche",,,,2) '1
?IndiceSimilarite("rehcehcre","recherche",,,,1) '0,78
?IndiceSimilarite("rehcehcre","recherche",,,,0) '0,56
?IndiceSimilarite("rehcehcre","recherche",,2,True) '1
?IndiceSimilarite("rehcehcre","recherche",,2,False) '0,3
?IndiceSimilarite("rehcehcre","recherche",,2,True,2) '0,8
?IndiceSimilarite("rehcehcre","recherche",,2,True,0) '0,4
?IndiceSimilarite("rehcehcre","recherche",,3,True,0) '0,36
Performance
Cette fonction semble être 5 à 6 fois plus rapide que la fonction de Damerau-Levenshtein. Le principe mis en jeu est différent et les différentes possibilités de réglages permettent d’adapter l’algorithme à de nombreux cas de figures.
Voir aussi le billet sur la distance de Jaro-Winkler.
@+
Philippe