Algorithmes pour chaînes "floues"

les algorithmes 'Edit Distance' de Levenshtein fonctionneront certainement sur ce que vous essayez de faire: ils vous donneront une mesure de la façon dont deux mots ou adresses ou numéros de téléphone, Psaumes, monologues et articles savants concordent les uns avec les autres, vous permettant de classer les résultats et de choisir la meilleure correspondance.

une approche plus légère est de compter les substrats communs: ce n'est pas aussi bon que Levenshtein, mais il fournit des résultats utilisables et court rapidement dans les langues lentes qui avoir accès à des fonctions d'Insertion rapide.

J'ai publié un Excel 'Fuzzy Lookup' dans Excellerando il y a quelques années, en utilisant la fonction 'FuzzyMatchScore' qui est, pour autant que je puisse dire, exactement ce dont vous avez besoin:

http://excellerando.blogspot.com/2010/03/vlookup-with-fuzzy-matching-to-get.html

il est, bien sûr, en Visual Basic pour les Applications. Procéder avec prudence, crucifix et ail:

Public Function SumOfCommonStrings( _
                            ByVal s1 As String, _
                            ByVal s2 As String, _
                            Optional Compare As VBA.VbCompareMethod = vbTextCompare, _
                            Optional iScore As Integer = 0 _
                                ) As Integer

Application.Volatile False

' N.Heffernan 06 June 2006 
' THIS CODE IS IN THE PUBLIC DOMAIN


' Function to measure how much of String 1 is made up of substrings found in String 2

' This function uses a modified Longest Common String algorithm.
' Simple LCS algorithms are unduly sensitive to single-letter
' deletions/changes near the midpoint of the test words, eg:
' Wednesday is obviously closer to WedXesday on an edit-distance
' basis than it is to WednesXXX. So it would be better to score
' the 'Wed' as well as the 'esday' and add up the total matched

' Watch out for strings of differing lengths:
'
'    SumOfCommonStrings("Wednesday", "WednesXXXday")
'
' This scores the same as:
'
'     SumOfCommonStrings("Wednesday", "Wednesday")
'
' So make sure the calling function uses the length of the longest
' string when calculating the degree of similarity from this score.


' This is coded for clarity, not for performance.

Dim arr() As Integer    ' Scoring matrix
Dim n As Integer        ' length of s1
Dim m As Integer        ' length of s2
Dim i As Integer        ' start position in s1
Dim j As Integer        ' start position in s2
Dim subs1 As String     ' a substring of s1
Dim len1 As Integer     ' length of subs1

Dim sBefore1            ' documented in the code
Dim sBefore2
Dim sAfter1
Dim sAfter2

Dim s3 As String


SumOfCommonStrings = iScore

n = Len(s1)
m = Len(s2)

If s1 = s2 Then
    SumOfCommonStrings = n
    Exit Function
End If

If n = 0 Or m = 0 Then
    Exit Function
End If

's1 should always be the shorter of the two strings:
If n > m Then
    s3 = s2
    s2 = s1
    s1 = s3
    n = Len(s1)
    m = Len(s2)
End If

n = Len(s1)
m = Len(s2)

' Special case: s1 is n exact substring of s2
If InStr(1, s2, s1, Compare) Then
    SumOfCommonStrings = n
    Exit Function
End If

For len1 = n To 1 Step -1

    For i = 1 To n - len1 + 1

        subs1 = Mid(s1, i, len1)
        j = 0
        j = InStr(1, s2, subs1, Compare)

        If j > 0 Then

            ' We've found a matching substring...
            iScore = iScore + len1            

          ' Now clip out this substring from s1 and s2...
          ' And search the fragments before and after this excision:


            If i > 1 And j > 1 Then
                sBefore1 = left(s1, i - 1)
                sBefore2 = left(s2, j - 1)
                iScore = SumOfCommonStrings(sBefore1, _
                                            sBefore2, _
                                            Compare, _
                                            iScore)
            End If


            If i + len1 < n And j + len1 < m Then
                sAfter1 = right(s1, n + 1 - i - len1)
                sAfter2 = right(s2, m + 1 - j - len1)
                iScore = SumOfCommonStrings(sAfter1, _
                                            sAfter2, _
                                            Compare, _
                                            iScore)
            End If


            SumOfCommonStrings = iScore
            Exit Function

        End If

    Next


Next


End Function


Private Function Minimum(ByVal a As Integer, _
                         ByVal b As Integer, _
                         ByVal c As Integer) As Integer
Dim min As Integer

  min = a

  If b < min Then
        min = b
  End If

  If c < min Then
        min = c
  End If

  Minimum = min

End Function

Deux algorithmes que j'ai trouvé pour l'instant:

1. LiquidMetal
2. Mieux Ido Flex-Correspondant À

je suis en train de construire quelque chose de similaire aux plugins Command-T et ctrlp de Vim pour Emacs, juste pour le plaisir. Je viens d'avoir une discussion fructueuse avec quelques collègues intelligents sur les façons de faire cela le plus efficacement possible. L'objectif est de réduire le nombre d'opérations nécessaires pour éliminer les fichiers qui ne correspondent pas. Donc nous créons une carte imbriquée, où au niveau supérieur chaque touche est un caractère qui apparaît quelque part dans le jeu de recherche, la correspondance aux indices de toutes les chaînes dans le jeu de recherche. Chacun ces indices correspondent alors à une liste de décalages de caractères à partir desquels ce caractère particulier apparaît dans la chaîne de recherche.

en pseudo code, pour les chaînes:

• contrôleur
• modèle
• view

Nous aimerions construire une carte comme ceci:

{
  "c" => {
           0 => [0]
         },
  "o" => {
           0 => [1, 5],
           1 => [1]
         },
  "n" => {
           0 => [2]
         },
  "t" => {
           0 => [3]
         },
  "r" => {
           0 => [4, 9]
         },
  "l" => {
           0 => [6, 7],
           1 => [4]
         },
  "e" => {
           0 => [9],
           1 => [3],
           2 => [2]
         },
  "m" => {
           1 => [0]
         },
  "d" => {
           1 => [2]
         },
  "v" => {
           2 => [0]
         },
  "i" => {
           2 => [1]
         },
  "w" => {
           2 => [3]
         }
}

alors maintenant vous avez un mapping comme ceci:

{
  character-1 => {
    word-index-1 => [occurrence-1, occurrence-2, occurrence-n, ...],
    word-index-n => [ ... ],
    ...
  },
  character-n => {
    ...
  },
  ...
}

recherche maintenant la chaîne "oe":

1. Initialiser une nouvelle carte où les touches être les indices des chaînes qui correspondent, et les valeurs de l'offset lu à travers cette chaîne jusqu'à présent.
2. Consommer le premier caractère de la chaîne de recherche "o" et le rechercher dans la table de recherche.
3. puisque les chaînes aux indices 0 et 1 correspondent au "o", mettez-les dans la carte {0 => 1, 1 => 1}.
4. maintenant la recherche consomme le char suivant dans la chaîne de saisie, " e " et le loo vers le haut dans la table.
5. ici 3 cordes correspondent, mais nous savons que nous ne nous soucions que des cordes 0 et 1.
6. Vérifiez s'il y a des offsets > les offsets actuels. Sinon, supprimez les éléments de notre map, sinon mettez à jour le offset:{0 => 9, 1 => 3}.

maintenant, en regardant les clés de notre carte que nous avons accumulées, nous savons quelles chaînes correspondent à la recherche floue.

idéalement, si la recherche est effectuée comme les types d'utilisateur, vous garderez une trace du hachage accumulé des résultats et le passerez de nouveau dans votre fonction de recherche. Je pense que ce sera beaucoup plus rapide que l'itération de toutes les chaînes de recherche et l'exécution d'une recherche Joker complète sur chacun d'eux.

ce qui est intéressant, c'est que vous pouvez également stocker efficacement la Distance Levenstein avec chaque match, en supposant que vous ne vous souciez que des insertions, et non des substitutions ou des suppressions. Mais il n'est peut-être pas difficile d'ajouter cette logique.

j'ai dû récemment résoudre le même problème. Ma solution consiste à marquer des chaînes de caractères avec des lettres appariées consécutivement fortement et en excluant les chaînes qui ne contiennent pas les lettres dactylographiées dans l'ordre.

j'ai documenté l'algorithme en détail ici: http://blog.kazade.co.uk/2014/10/a-fuzzy-filename-matching-algorithm.html

si votre texte est principalement anglais alors vous pouvez essayer votre main à divers algorithmes Soundex 1. Classique soundex 2. Metafone

ces algorithmes vous permettront de choisir des mots qui se ressemblent et seront un bon moyen de trouver des mots Mal orthographiés.