Obtenir la correspondance de chaîne la plus proche

Question

J'ai besoin d'un moyen de comparer plusieurs chaînes à une chaîne de test et de renvoyer la chaîne qui lui ressemble le plus :

CHAÎNE DE TEST : THE BROWN FOX JUMPED OVER THE RED COW

CHOIX A     : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOIX B     : THE RED COW JUMPED OVER THE RED COW
CHOIX C     : THE RED FOX JUMPED OVER THE BROWN COW

(Si j'ai bien fait) La chaîne la plus proche de la "CHAÎNE DE TEST" devrait être "CHOIX C". Quel est le moyen le plus simple de faire cela ?

Je prévois d'implémenter cela dans plusieurs langages, y compris VB.net, Lua et JavaScript. À ce stade, un pseudo-code est acceptable. Si vous pouvez fournir un exemple pour un langage spécifique, cela est également apprécié !

Answer 1

J'ai été confronté à ce problème il y a environ un an lorsqu'il s'est agi de rechercher des informations saisies par l'utilisateur sur une plate-forme pétrolière dans une base de données d'informations diverses. L'objectif était de faire une sorte de recherche de chaîne floue qui pourrait identifier l'entrée de la base de données avec les éléments les plus communs.

Une partie de la recherche a consisté à mettre en œuvre le distance de Levenshtein qui détermine combien de modifications doivent être apportées à une chaîne ou à une phrase pour la transformer en une autre chaîne ou phrase.

L'implémentation que j'ai trouvée était relativement simple, et impliquait une comparaison pondérée de la longueur des deux phrases, du nombre de changements entre chaque phrase, et si chaque mot pouvait être trouvé dans l'entrée cible.

L'article se trouve sur un site privé, je vais donc faire de mon mieux pour ajouter le contenu pertinent ici :

---

La correspondance floue de chaînes de caractères est le processus qui consiste à effectuer une estimation de type humain de la similarité de deux mots ou phrases. Dans de nombreux cas, il s'agit d'identifier les mots ou les phrases qui sont les plus similaires les uns aux autres. Cet article décrit une solution interne au problème de la correspondance floue de chaînes de caractères et son utilité dans la résolution de divers problèmes qui peuvent nous permettre d'automatiser des tâches qui nécessitaient auparavant la participation fastidieuse d'un utilisateur.

Introduction

La nécessité d'effectuer une correspondance floue de chaînes de caractères est apparue à l'origine lors du développement de l'outil Gulf of Mexico Validator. Il existait une base de données des plates-formes et des plateformes pétrolières connues dans le golfe du Mexique. Les personnes qui souscrivaient une assurance nous donnaient des informations mal saisies sur leurs biens et nous devions les faire correspondre à la base de données des plateformes connues. Lorsque les informations fournies étaient très limitées, le mieux que nous pouvions faire était de compter sur un souscripteur pour "reconnaître" la plate-forme à laquelle ils faisaient référence et appeler les informations appropriées. C'est là que cette solution automatisée s'avère utile.

J'ai passé une journée à rechercher des méthodes de correspondance floue de chaînes de caractères, et je suis finalement tombé sur l'algorithme très utile de la distance de Levenshtein sur Wikipedia.

Mise en œuvre

Après avoir lu la théorie qui se cache derrière, j'ai mis en œuvre et trouvé des moyens de l'optimiser. Voici à quoi ressemble mon code en VBA :

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

Simple, rapide, et une métrique très utile. J'ai ainsi créé deux métriques distinctes pour évaluer la similarité de deux chaînes de caractères. L'une s'appelle "valuePhrase" et l'autre "valueWords". valuePhrase est simplement la distance de Levenshtein entre les deux phrases, et valueWords divise la chaîne en mots individuels, sur la base de délimiteurs tels que des espaces, des tirets et tout ce que vous voulez, et compare chaque mot à chaque autre mot, en additionnant la distance de Levenshtein la plus courte reliant deux mots. Essentiellement, il mesure si l'information contenue dans une "phrase" est réellement contenue dans une autre, tout comme une permutation de mots. J'ai passé quelques jours, dans le cadre d'un projet parallèle, à trouver la manière la plus efficace possible de diviser une chaîne de caractères en fonction des délimiteurs.

valueWords, valuePhrase, et la fonction Split :

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

Mesures de similarité

À l'aide de ces deux mesures, et d'une troisième qui calcule simplement la distance entre deux chaînes de caractères, je dispose d'une série de variables sur lesquelles je peux faire tourner un algorithme d'optimisation pour obtenir le plus grand nombre de correspondances. La correspondance floue des chaînes de caractères est, en soi, une science floue. Ainsi, en créant des paramètres linéairement indépendants pour mesurer la similarité des chaînes de caractères et en disposant d'un ensemble connu de chaînes de caractères que nous souhaitons faire correspondre, nous pouvons trouver les paramètres qui, pour nos styles spécifiques de chaînes de caractères, donnent les meilleurs résultats de correspondance floue.

Initialement, l'objectif de la mesure était d'avoir une valeur de recherche faible pour une correspondance exacte, et des valeurs de recherche croissantes pour des mesures de plus en plus permutées. Dans un cas peu pratique, cela a été assez facile à définir en utilisant un ensemble de permutations bien définies, et en élaborant la formule finale de manière à obtenir des valeurs de recherche croissantes comme souhaité.

Dans la capture d'écran ci-dessus, j'ai modifié mon heuristique pour obtenir quelque chose qui, selon moi, s'adapte bien à la différence que je perçois entre le terme de recherche et le résultat. L'heuristique que j'ai utilisée pour Value Phrase dans la feuille de calcul ci-dessus était =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) . Je réduisais effectivement la pénalité de la distance de Levenstein de 80 % de la différence de longueur des deux "phrases". De cette façon, les "phrases" qui ont la même longueur subissent la totalité de la pénalité, mais les "phrases" qui contiennent des "informations supplémentaires" (plus longues) mais qui, à part cela, partagent essentiellement les mêmes caractères subissent une pénalité réduite. J'ai utilisé le Value Words tel quel, et ensuite ma fonction finale SearchVal L'heuristique a été définie comme suit =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - une moyenne pondérée. Celui des deux scores qui était le plus bas était pondéré à 80 %, et 20 % pour le score le plus élevé. C'était juste une heuristique qui convenait à mon cas d'utilisation pour obtenir un bon taux de correspondance. Ces pondérations peuvent être modifiées pour obtenir le meilleur taux de correspondance avec les données de test.

Comme vous pouvez le voir, les deux dernières métriques, qui sont des métriques de correspondance de chaînes floues, ont déjà une tendance naturelle à donner des scores faibles aux chaînes qui sont censées correspondre (en bas de la diagonale). C'est une très bonne chose.

Application Pour permettre l'optimisation de la correspondance floue, je pondère chaque métrique. Ainsi, chaque application de la correspondance floue de chaînes de caractères peut pondérer les paramètres différemment. La formule qui définit le score final est une simple combinaison des paramètres et de leurs pondérations :

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

En utilisant un algorithme d'optimisation (le réseau neuronal est le meilleur ici car c'est un problème discret et multidimensionnel), le but est maintenant de maximiser le nombre de correspondances. J'ai créé une fonction qui détecte le nombre de correspondances correctes de chaque ensemble entre eux, comme on peut le voir dans cette capture d'écran finale. Une colonne ou une ligne reçoit un point si le score le plus bas est attribué à la chaîne qui devait être assortie, et des points partiels sont donnés s'il y a une égalité pour le score le plus bas, et que la correspondance correcte est parmi les chaînes assorties à égalité. Je l'ai ensuite optimisé. Vous pouvez voir qu'une cellule verte est la colonne qui correspond le mieux à la ligne actuelle, et qu'un carré bleu autour de la cellule est la ligne qui correspond le mieux à la colonne actuelle. Le score dans le coin inférieur est en gros le nombre de correspondances réussies et c'est ce que nous demandons à notre problème d'optimisation de maximiser.

L'algorithme a été un merveilleux succès, et les paramètres de la solution en disent long sur ce type de problème. Vous remarquerez que le score optimisé était de 44, et que le meilleur score possible est de 48. Les 5 colonnes à la fin sont des leurres, et ne correspondent pas du tout aux valeurs des lignes. Plus il y a de leurres, plus il sera difficile de trouver la meilleure correspondance.

Dans ce cas particulier de correspondance, la longueur des chaînes n'est pas pertinente, car nous nous attendons à des abréviations qui représentent des mots plus longs. Le poids optimal pour la longueur est donc de -0,3, ce qui signifie que nous ne pénalisons pas les chaînes dont la longueur varie. Nous réduisons le score en prévision de ces abréviations, ce qui laisse plus de place aux correspondances partielles de mots pour remplacer les correspondances de non-mots qui nécessitent simplement moins de substitutions parce que la chaîne est plus courte.

Le poids du mot est de 1,0 alors que celui de la phrase n'est que de 0,5, ce qui signifie que nous pénalisons les mots entiers manquants dans une chaîne et valorisons davantage la phrase entière intacte. C'est utile parce que beaucoup de ces chaînes ont un mot en commun (le péril) où ce qui importe vraiment est de savoir si la combinaison (région et péril) est maintenue ou non.

Enfin, la pondération minimale est optimisée à 10 et la pondération maximale à 1. Cela signifie que si le meilleur des deux scores (expression et mots de valeur) n'est pas très bon, la correspondance est fortement pénalisée, mais nous ne pénalisons pas fortement le pire des deux scores. Essentiellement, cela met l'accent sur l'exigence soit le valueWord ou le valuePhrase pour avoir un bon score, mais pas les deux. Une sorte de mentalité "on prend ce qu'on peut avoir".

Il est vraiment fascinant de voir ce que la valeur optimisée de ces 5 poids révèle sur le type de correspondance floue des chaînes de caractères qui a lieu. Pour des cas pratiques complètement différents de correspondance floue de chaînes de caractères, ces paramètres sont très différents. Je l'ai utilisé pour 3 applications différentes jusqu'à présent.

Bien qu'elle n'ait pas été utilisée dans l'optimisation finale, une feuille d'évaluation comparative a été établie, qui fait correspondre les colonnes à elles-mêmes pour tous les résultats parfaits en bas de la diagonale, et permet à l'utilisateur de modifier les paramètres pour contrôler le taux auquel les scores divergent de 0, et de noter les similitudes innées entre les phrases de recherche (qui pourraient en théorie être utilisées pour compenser les faux positifs dans les résultats).

Autres applications

Cette solution peut être utilisée partout où l'utilisateur souhaite qu'un système informatique identifie une chaîne de caractères dans un ensemble de chaînes de caractères pour lesquelles il n'existe pas de correspondance parfaite. (Comme un vlookup de correspondance approximative pour les chaînes de caractères).

---

Ce que vous devez retenir de tout cela, c'est que vous voulez probablement utiliser une combinaison d'heuristiques de haut niveau (trouver les mots d'une phrase dans l'autre phrase, la longueur des deux phrases, etc.) avec l'implémentation de l'algorithme de distance de Levenshtein. ) ainsi que l'implémentation de l'algorithme de distance de Levenshtein. Étant donné que la détermination de la "meilleure" correspondance est une détermination heuristique (floue), vous devrez définir un ensemble de pondérations pour toutes les mesures que vous proposez pour déterminer la similarité.

Avec un ensemble approprié d'heuristiques et de pondérations, votre programme de comparaison prendra rapidement les décisions que vous auriez prises.

Answer 2

Ce problème se présente tout le temps en bioinformatique. La réponse acceptée ci-dessus (qui était excellente d'ailleurs) est connue en bioinformatique sous les noms d'algorithmes Needleman-Wunsch (comparer deux chaînes) et Smith-Waterman (trouver une sous-chaîne approximative dans une chaîne plus longue). Ils fonctionnent très bien et ont été des chevaux de bataille depuis des décennies.

Mais que se passe-t-il si vous avez un million de chaînes à comparer? Cela représente un trillion de comparaisons par paire, chacune étant en O(n*m)! Les séquenceurs d'ADN modernes génèrent facilement des milliards de courtes séquences d'ADN, chacune contenant environ 200 "lettres" d'ADN. En général, nous voulons trouver, pour chaque chaîne, la meilleure correspondance avec le génome humain (3 milliards de lettres). Clairement, l'algorithme Needleman-Wunsch et ses dérivés ne suffiront pas.

Ce problème d'«alignement» est un domaine de recherche actif. Les algorithmes les plus populaires sont actuellement capables de trouver des correspondances inexates entre 1 milliard de courtes chaînes et le génome humain en quelques heures sur un matériel raisonnable (disons, huit coeurs et 32 Go de RAM).

La plupart de ces algorithmes fonctionnent en trouvant rapidement de courtes correspondances exactes (graines) puis en les étendant à la chaîne entière en utilisant un algorithme plus lent (par exemple, le Smith-Waterman). La raison pour laquelle cela fonctionne est que nous ne sommes vraiment intéressés que par quelques correspondances proches, il est donc rentable de se débarrasser des 99,9...% des paires qui n'ont rien en commun.

Comment trouver des correspondances exactes aide à trouver des correspondances inexactes? Eh bien, disons que nous n'autorisons qu'une seule différence entre la requête et la cible. Il est facile de voir que cette différence doit se produire dans la moitié droite ou gauche de la requête, et donc l'autre moitié doit correspondre exactement. Cette idée peut être étendue à plusieurs inexactitudes et est à la base de l'algorithme ELAND couramment utilisé avec les séquenceurs d'ADN Illumina.

Il existe de très bons algorithmes pour effectuer des correspondances exactes de chaînes. Étant donné une chaîne de requête de longueur 200, et une chaîne cible de longueur 3 milliards (le génome humain), nous voulons trouver n'importe quel endroit dans la cible où il y a une sous-chaîne de longueur k qui correspond exactement à une sous-chaîne de la requête. Une approche simple consiste à commencer par indexer la cible : prendre toutes les sous-chaînes de longueur k, les mettre dans un tableau et les trier. Ensuite, prendre chaque sous-chaîne de longueur k de la requête et rechercher l'index trié. La recherche peut s'effectuer en O(log n) temps.

Mais le stockage peut poser problème. Un index de la cible à 3 milliards de lettres aurait besoin de contenir 3 milliards de pointeurs et 3 milliards de mots de longueur k. Il semblerait difficile de le faire tenir dans moins de plusieurs dizaines de gigaoctets de RAM. Mais étonnamment, nous pouvons grandement compresser l'index, en utilisant la transformée de Burrows-Wheeler, et il sera toujours interrogeable efficacement. Un index du génome humain peut tenir dans moins de 4 Go de RAM. Cette idée est à la base des aligneurs de séquence populaires comme Bowtie et BWA.

Alternativement, nous pouvons utiliser un tableau de suffixes, qui stocke seulement les pointeurs, mais représente un index simultané de tous les suffixes dans la chaîne cible (essentiellement, un index simultané pour toutes les valeurs possibles de k; la même chose est vraie de la transformée de Burrows-Wheeler). Un index de tableau de suffixes du génome humain nécessitera 12 Go de RAM si nous utilisons des pointeurs de 32 bits.

Les liens ci-dessus contiennent une mine d'informations et des liens vers des articles de recherche primaires. Le lien ELAND renvoie à un PDF avec des figures utiles illustrant les concepts impliqués, et montre comment traiter les insertions et les suppressions.

Enfin, bien que ces algorithmes aient essentiellement résolu le problème de (re)séquençage des génomes humains (un milliard de courtes chaînes), la technologie de séquençage d'ADN progresse encore plus rapidement que la loi de Moore, et nous approchons rapidement des ensembles de données de trillions de lettres. Par exemple, il existe actuellement des projets en cours pour séquencer les génomes de 10 000 espèces de vertébrés, chacun contenant environ un milliard de lettres. Naturellement, nous voudrons effectuer des correspondances de chaînes inexactes par paire sur les données...

Answer 3

Je conteste que le choix B soit plus proche de la chaîne de caractères de test, car il n'est qu'à 4 caractères (et 2 suppressions) de la chaîne originale. Alors que vous voyez le C comme plus proche car il inclut à la fois le brun et le rouge. Cependant, il aurait une distance d'édition plus grande.

Il existe un algorithme appelé Distance de Levenshtein qui mesure la distance d'édition entre deux entrées.

Ici se trouve un outil pour cet algorithme.

1. Évalue le choix A à une distance de 15.
2. Évalue le choix B à une distance de 6.
3. Évalue le choix C à une distance de 9.

ÉDIT : Désolé, je continue à mélanger les chaînes dans l'outil de levenshtein. Mis à jour pour corriger les réponses.

Answer 4

Implémentation Lua, pour la postérité:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end

Answer 5

Vous pourriez être intéressé par ce billet de blog.

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy est une bibliothèque Python qui fournit des mesures de distance faciles telles que la distance de Levenshtein pour la correspondance de chaînes. Il est construit au-dessus de difflib dans la bibliothèque standard et utilisera l'implémentation en C Python-levenshtein si disponible.

http://pypi.python.org/pypi/python-Levenshtein/