Ermitteln der nächsten Zeichenfolgenübereinstimmung

Ich brauche eine Möglichkeit, mehrere Zeichenfolgen mit einer Testzeichenfolge zu vergleichen und die Zeichenfolge zurückzugeben, die dieser sehr ähnlich ist:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

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

(Wenn ich das richtig gemacht habe) Die dem "TEST STRING" am nächsten liegende Zeichenfolge sollte "CHOICE C" sein. Was ist der einfachste Weg, dies zu tun?

Ich plane, dies in mehreren Sprachen zu implementieren, einschließlich VB.net, Lua und JavaScript. Zu diesem Zeitpunkt ist Pseudocode akzeptabel. Wenn Sie ein Beispiel für eine bestimmte Sprache angeben können, wird dies ebenfalls geschätzt!

Ich wurde vor ungefähr einem Jahr mit diesem Problem konfrontiert, als ich nach vom Benutzer eingegebenen Informationen über eine Bohrinsel in einer Datenbank mit verschiedenen Informationen suchte. Das Ziel war eine Art Fuzzy-String-Suche, die den Datenbankeintrag mit den häufigsten Elementen identifizieren konnte.

Ein Teil der Forschung umfasste die Implementierung des Levenshtein-Distanzalgorithmus , der bestimmt, wie viele Änderungen an einer Zeichenfolge oder Phrase vorgenommen werden müssen, um sie in eine andere Zeichenfolge oder Phrase umzuwandeln.

Die Implementierung, die ich mir ausgedacht habe, war relativ einfach und beinhaltete einen gewichteten Vergleich der Länge der beiden Phrasen, der Anzahl der Änderungen zwischen den einzelnen Phrasen und der Frage, ob jedes Wort im Zieleintrag gefunden werden konnte.

Der Artikel befindet sich auf einer privaten Website, daher werde ich mein Bestes tun, um die relevanten Inhalte hier anzuhängen:

Fuzzy String Matching ist der Prozess der Durchführung einer menschenähnlichen Schätzung der Ähnlichkeit zweier Wörter oder Phrasen. In vielen Fällen geht es darum, Wörter oder Phrasen zu identifizieren, die einander am ähnlichsten sind. Dieser Artikel beschreibt eine interne Lösung für das Fuzzy-String-Matching-Problem und seine Nützlichkeit bei der Lösung einer Vielzahl von Problemen, mit denen wir Aufgaben automatisieren können, für die zuvor eine mühsame Benutzerbeteiligung erforderlich war.

Einführung

Die Notwendigkeit, einen Fuzzy-String-Abgleich durchzuführen, entstand ursprünglich bei der Entwicklung des Validator-Tools für den Golf von Mexiko. Was existierte, war eine Datenbank mit bekannten Golfbohrinseln und Plattformen in Mexiko, und die Leute, die Versicherungen kauften, gaben uns einige schlecht getippte Informationen über ihr Vermögen, und wir mussten sie mit der Datenbank bekannter Plattformen abgleichen. Wenn nur sehr wenige Informationen gegeben wurden, können wir uns am besten darauf verlassen, dass ein Versicherer denjenigen, auf den er sich bezieht, "erkennt" und die richtigen Informationen aufruft. Hier bietet sich diese automatisierte Lösung an.

Ich habe einen Tag lang nach Methoden des Fuzzy-String-Matchings gesucht und bin schließlich auf den sehr nützlichen Levenshtein-Distanzalgorithmus auf Wikipedia gestoßen.

Implementierung

Nachdem ich über die Theorie dahinter gelesen hatte, implementierte ich und fand Wege, sie zu optimieren. So sieht mein Code in VBA aus:

'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

Einfach, schnell und eine sehr nützliche Metrik. Auf diese Weise habe ich zwei separate Metriken erstellt, um die Ähnlichkeit zweier Zeichenfolgen zu bewerten. Eine nenne ich "valuePhrase" und eine nenne ich "valueWords". valuePhrase ist nur der Levenshtein-Abstand zwischen den beiden Phrasen, und valueWords teilt die Zeichenfolge in einzelne Wörter auf, basierend auf Trennzeichen wie Leerzeichen, Bindestrichen und allem, was Sie möchten, und vergleicht jedes Wort mit dem anderen Wort, wobei es das kürzeste zusammenfasst Levenshtein Abstand, der zwei beliebige Wörter verbindet. Im Wesentlichen wird gemessen, ob die Informationen in einer 'Phrase' tatsächlich in einer anderen enthalten sind, ebenso wie eine wortweise Permutation. Ich habe ein paar Tage als Nebenprojekt verbracht, um die effizienteste Methode zum Teilen einer Zeichenfolge anhand von Trennzeichen zu finden.

valueWords-, valuePhrase- und Split-Funktion:

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

Ähnlichkeitsmaße

Mit diesen beiden Metriken und einer dritten, die einfach den Abstand zwischen zwei Zeichenfolgen berechnet, habe ich eine Reihe von Variablen, mit denen ich einen Optimierungsalgorithmus ausführen kann, um die größte Anzahl von Übereinstimmungen zu erzielen. Fuzzy-String-Matching ist selbst eine Fuzzy-Wissenschaft. Wenn wir also linear unabhängige Metriken zur Messung der String-Ähnlichkeit erstellen und über einen bekannten Satz von Strings verfügen, die wir miteinander abgleichen möchten, können wir die Parameter finden, die für unsere spezifischen Stile von Saiten, geben Sie die besten Fuzzy-Match-Ergebnisse.

Anfänglich bestand das Ziel der Metrik darin, einen niedrigen Suchwert für eine genaue Übereinstimmung zu haben und die Suchwerte für zunehmend permutierte Kennzahlen zu erhöhen. In einem unpraktischen Fall war es ziemlich einfach, dies unter Verwendung eines Satzes gut definierter Permutationen zu definieren und die endgültige Formel so zu konstruieren, dass sie nach Wunsch steigende Suchwertergebnisse hatten.

Im obigen Screenshot habe ich meine Heuristik angepasst, um etwas zu finden, das meiner Meinung nach gut auf meinen wahrgenommenen Unterschied zwischen Suchbegriff und Ergebnis skaliert ist. Die Heuristik, für Value Phrasedie ich in der obigen Tabelle verwendet habe, war =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)). Ich habe die Strafe für die Levenstein-Distanz effektiv um 80% des Unterschieds in der Länge der beiden "Phrasen" reduziert. Auf diese Weise erleiden "Phrasen", die die gleiche Länge haben, die volle Strafe, aber "Phrasen", die "zusätzliche Informationen" (länger) enthalten, aber ansonsten meistens dieselben Zeichen haben, werden weniger bestraft. Ich habe die Value WordsFunktion so verwendet , wie sie ist, und dann wurde meine endgültige SearchValHeuristik definiert als=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2- ein gewichteter Durchschnitt. Welche der beiden Bewertungen niedriger war, wurde mit 80% und 20% der höheren Bewertung gewichtet. Dies war nur eine Heuristik, die zu meinem Anwendungsfall passte, um eine gute Übereinstimmungsrate zu erzielen. Diese Gewichte können dann angepasst werden, um die beste Übereinstimmungsrate mit ihren Testdaten zu erzielen.

Wie Sie sehen können, haben die letzten beiden Metriken, bei denen es sich um Fuzzy-String-Matching-Metriken handelt, bereits die natürliche Tendenz, Strings, die übereinstimmen sollen (in der Diagonale), niedrige Punktzahlen zu verleihen. Das ist sehr gut.

Anwendung Um die Optimierung des Fuzzy-Matchings zu ermöglichen, gewichte ich jede Metrik. Daher kann jede Anwendung der Fuzzy-String-Übereinstimmung die Parameter unterschiedlich gewichten. Die Formel, die das Endergebnis definiert, ist eine einfache Kombination der Metriken und ihrer Gewichte:

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

Mithilfe eines Optimierungsalgorithmus (neuronales Netzwerk ist hier am besten geeignet, da es sich um ein diskretes, mehrdimensionales Problem handelt) besteht das Ziel nun darin, die Anzahl der Übereinstimmungen zu maximieren. Ich habe eine Funktion erstellt, die die Anzahl der korrekten Übereinstimmungen zwischen den einzelnen Sätzen erkennt, wie in diesem letzten Screenshot zu sehen ist. Eine Spalte oder Zeile erhält einen Punkt, wenn die niedrigste Punktzahl der Zeichenfolge zugewiesen wird, die abgeglichen werden soll, und Teilpunkte werden vergeben, wenn für die niedrigste Punktzahl ein Gleichstand besteht und die richtige Übereinstimmung unter den gebundenen übereinstimmenden Zeichenfolgen liegt. Ich habe es dann optimiert. Sie können sehen, dass eine grüne Zelle die Spalte ist, die am besten zur aktuellen Zeile passt, und ein blaues Quadrat um die Zelle die Zeile, die am besten zur aktuellen Spalte passt. Die Punktzahl in der unteren Ecke entspricht in etwa der Anzahl der erfolgreichen Spiele, und dies ist es, was wir unserem Optimierungsproblem mitteilen, um es zu maximieren.

Der Algorithmus war ein wunderbarer Erfolg, und die Lösungsparameter sagen viel über diese Art von Problem aus. Sie werden feststellen, dass die optimierte Punktzahl 44 und die bestmögliche Punktzahl 48 beträgt. Die 5 Spalten am Ende sind Lockvögel und stimmen überhaupt nicht mit den Zeilenwerten überein. Je mehr Köder es gibt, desto schwieriger wird es natürlich, die beste Übereinstimmung zu finden.

In diesem speziellen Übereinstimmungsfall ist die Länge der Zeichenfolgen irrelevant, da wir Abkürzungen erwarten, die längere Wörter darstellen. Das optimale Gewicht für die Länge beträgt also -0,3, was bedeutet, dass Zeichenfolgen mit unterschiedlicher Länge nicht bestraft werden. Wir reduzieren die Punktzahl in Erwartung dieser Abkürzungen und geben mehr Platz für Teilwortübereinstimmungen, um Nichtwortübereinstimmungen zu ersetzen, die einfach weniger Substitutionen erfordern, da die Zeichenfolge kürzer ist.

Das Wortgewicht beträgt 1,0, während das Phrasengewicht nur 0,5 beträgt. Dies bedeutet, dass wir ganze Wörter, die in einer Zeichenfolge fehlen, bestrafen und mehr Wert darauf legen, dass die gesamte Phrase intakt ist. Dies ist nützlich, da viele dieser Zeichenfolgen ein Wort gemeinsam haben (die Gefahr), bei dem es wirklich darauf ankommt, ob die Kombination (Region und Gefahr) beibehalten wird oder nicht.

Schließlich wird das Mindestgewicht auf 10 und das Höchstgewicht auf 1 optimiert. Dies bedeutet, dass wenn die beste der beiden Bewertungen (Wertphrase und Wertwörter) nicht sehr gut ist, die Übereinstimmung stark bestraft wird, aber wir ziehen nicht an Das schlechteste der beiden Ergebnisse wird nicht stark bestraft. Im Wesentlichen wird dabei betont, dass entweder das valueWord oder die valuePhrase eine gute Punktzahl haben müssen, aber nicht beide. Eine Art "nimm was wir bekommen können" Mentalität.

Es ist wirklich faszinierend, was der optimierte Wert dieser 5 Gewichte über die Art des Fuzzy-String-Matchings aussagt. Für völlig unterschiedliche praktische Fälle der Fuzzy-String-Anpassung sind diese Parameter sehr unterschiedlich. Ich habe es bisher für 3 verschiedene Anwendungen verwendet.

Während es in der endgültigen Optimierung nicht verwendet wurde, wurde ein Benchmarking-Blatt erstellt, das die Spalten für alle perfekten Ergebnisse in der Diagonale mit sich selbst vergleicht und es dem Benutzer ermöglicht, Parameter zu ändern, um die Rate zu steuern, mit der die Punktzahlen von 0 abweichen, und angeborene Ähnlichkeiten zwischen Suchphrasen festzustellen ( was theoretisch verwendet werden könnte, um falsch positive Ergebnisse auszugleichen)

Weitere Anwendungen

Diese Lösung kann überall dort eingesetzt werden, wo der Benutzer möchte, dass ein Computersystem eine Zeichenfolge in einer Reihe von Zeichenfolgen identifiziert, bei denen keine perfekte Übereinstimmung vorliegt. (Wie eine ungefähre Übereinstimmungsansicht für Zeichenfolgen).

Was Sie daraus ziehen sollten, ist, dass Sie wahrscheinlich eine Kombination von Heuristiken auf hoher Ebene (Suchen von Wörtern aus einer Phrase in der anderen Phrase, Länge beider Phrasen usw.) zusammen mit der Implementierung des Levenshtein-Distanzalgorithmus verwenden möchten. Da die Entscheidung, welches die "beste" Übereinstimmung ist, eine heuristische (unscharfe) Bestimmung ist, müssen Sie für alle Metriken, die Sie erstellen, eine Reihe von Gewichten erstellen, um die Ähnlichkeit zu bestimmen.

Mit den entsprechenden Heuristiken und Gewichten können Sie mit Ihrem Vergleichsprogramm schnell die Entscheidungen treffen, die Sie getroffen hätten.

Dieses Problem tritt in der Bioinformatik immer wieder auf. Die oben akzeptierte Antwort (die übrigens großartig war) ist in der Bioinformatik als Needleman-Wunsch- (vergleiche zwei Strings) und Smith-Waterman-Algorithmen (finde einen ungefähren Teilstring in einem längeren String) bekannt. Sie arbeiten großartig und sind seit Jahrzehnten Arbeitspferde.

Aber was ist, wenn Sie eine Million Zeichenfolgen vergleichen müssen? Das sind Billionen paarweise Vergleiche, von denen jeder O (n * m) ist! Moderne DNA-Sequenzer erzeugen leicht eine Milliarde kurze DNA-Sequenzen mit einer Länge von jeweils etwa 200 DNA-Buchstaben. Normalerweise möchten wir für jede solche Zeichenfolge die beste Übereinstimmung mit dem menschlichen Genom finden (3 Milliarden Buchstaben). Der Needleman-Wunsch-Algorithmus und seine Verwandten werden dies eindeutig nicht tun.

Dieses sogenannte "Alignment-Problem" ist ein Feld aktiver Forschung. Die beliebtesten Algorithmen sind derzeit in der Lage, auf vernünftiger Hardware (z. B. acht Kerne und 32 GB RAM) innerhalb weniger Stunden ungenaue Übereinstimmungen zwischen 1 Milliarde kurzen Zeichenfolgen und dem menschlichen Genom zu finden.

Die meisten dieser Algorithmen funktionieren, indem sie schnell kurze exakte Übereinstimmungen (Seeds) finden und diese dann mithilfe eines langsameren Algorithmus (z. B. Smith-Waterman) auf die gesamte Zeichenfolge erweitern. Der Grund dafür ist, dass wir wirklich nur an ein paar engen Spielen interessiert sind. Es lohnt sich also, die 99,9 ...% der Paare loszuwerden, die nichts gemeinsam haben.

Wie hilft das Finden genauer Übereinstimmungen beim Finden ungenauer Übereinstimmungen? Angenommen, wir erlauben nur einen einzigen Unterschied zwischen der Abfrage und dem Ziel. Es ist leicht zu erkennen, dass dieser Unterschied entweder in der rechten oder in der linken Hälfte der Abfrage auftreten muss und die andere Hälfte daher genau übereinstimmen muss. Diese Idee kann auf mehrere Fehlpaarungen ausgedehnt werden und ist die Grundlage für das ELAND Algorithmus, der üblicherweise bei Illumina-DNA-Sequenzierern verwendet wird.

Es gibt viele sehr gute Algorithmen für die exakte Zeichenfolgenübereinstimmung. Bei einer Abfragezeichenfolge mit einer Länge von 200 und einer Zielzeichenfolge mit einer Länge von 3 Milliarden (dem menschlichen Genom) möchten wir eine beliebige Stelle im Ziel finden, an der es einen Teilstring der Länge k gibt, der genau mit einem Teilstring der Abfrage übereinstimmt. Ein einfacher Ansatz besteht darin, zunächst das Ziel zu indizieren: Nehmen Sie alle k-langen Teilzeichenfolgen, fügen Sie sie in ein Array ein und sortieren Sie sie. Nehmen Sie dann jede k-lange Teilzeichenfolge der Abfrage und durchsuchen Sie den sortierten Index. Sortieren und Suchen kann in O (log n) Zeit erfolgen.

Die Speicherung kann jedoch ein Problem sein. Ein Index des Ziels von 3 Milliarden Buchstaben müsste 3 Milliarden Zeiger und 3 Milliarden k lange Wörter enthalten. Es scheint schwierig, dies in weniger als einige zehn Gigabyte RAM zu integrieren. Erstaunlicherweise können wir den Index mithilfe der Burrows-Wheeler-Transformation erheblich komprimieren , und er kann weiterhin effizient abgefragt werden. Ein Index des menschlichen Genoms kann in weniger als 4 GB RAM passen. Diese Idee ist die Grundlage für beliebte Sequenz-Aligner wie Bowtie und BWA .

Alternativ können wir ein Suffix-Array verwenden , das nur die Zeiger speichert und dennoch einen simultanen Index aller Suffixe in der Zielzeichenfolge darstellt (im Wesentlichen einen simultanen Index für alle möglichen Werte von k; dasselbe gilt für die Burrows-Wheeler-Transformation ). Ein Suffix-Array-Index des menschlichen Genoms benötigt 12 GB RAM, wenn 32-Bit-Zeiger verwendet werden.

Die obigen Links enthalten eine Fülle von Informationen und Links zu primären Forschungsarbeiten. Der ELAND-Link führt zu einem PDF mit nützlichen Abbildungen, die die beteiligten Konzepte veranschaulichen, und zeigt, wie mit Einfügungen und Löschungen umgegangen wird.

Während diese Algorithmen das Problem der (Neu-) Sequenzierung einzelner menschlicher Genome (eine Milliarde kurze Strings) im Grunde genommen gelöst haben, verbessert sich die DNA-Sequenzierungstechnologie sogar noch schneller als das Moore-Gesetz, und wir nähern uns schnell Datensätzen mit Billionen Buchstaben. Derzeit laufen beispielsweise Projekte zur Sequenzierung der Genome von 10.000 Wirbeltierarten mit einer Länge von jeweils etwa einer Milliarde Buchstaben. Natürlich wollen wir paarweise ungenaue Zeichenfolgenabgleiche für die Daten durchführen ...

Ich bestreite, dass Auswahl B näher an der Testzeichenfolge liegt, da es nur 4 Zeichen (und 2 Löschungen) von der ursprünglichen Zeichenfolge sind. Während Sie C näher sehen, weil es sowohl braun als auch rot enthält. Es hätte jedoch einen größeren Bearbeitungsabstand.

Es gibt einen Algorithmus namens Levenshtein Distance, der den Bearbeitungsabstand zwischen zwei Eingängen misst.

Hier ist ein Werkzeug für diesen Algorithmus.

1. Preise Wahl A als Abstand von 15.
2. Preise Wahl B als Abstand von 6.
3. Preise Wahl C als Abstand von 9.

EDIT: Sorry, ich mische immer wieder Strings im levenshtein Tool. Aktualisiert, um die Antworten zu korrigieren.

Lua-Implementierung für die Nachwelt:

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

Dieser Blog-Beitrag könnte Sie interessieren.

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

Fuzzywuzzy ist eine Python-Bibliothek, die einfache Abstandsmaße wie den Levenshtein-Abstand für den String-Abgleich bietet. Es basiert auf Difflib in der Standardbibliothek und verwendet die C-Implementierung Python-levenshtein, falls verfügbar.

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

Diese Bibliothek könnte hilfreich sein! http://code.google.com/p/google-diff-match-patch/

Es ist derzeit in Java, JavaScript, Dart, C ++, C #, Ziel C, Lua und Python verfügbar

Es funktioniert auch ziemlich gut. Ich benutze es in einigen meiner Lua-Projekte.

Und ich denke nicht, dass es zu schwierig wäre, es in andere Sprachen zu portieren!

Wenn Sie dies im Kontext einer Suchmaschine oder eines Frontends für eine Datenbank tun, können Sie ein Tool wie Apache Solr mit dem ComplexPhraseQueryParser verwenden Plugin verwenden. Mit dieser Kombination können Sie nach einem Index von Zeichenfolgen suchen, wobei die Ergebnisse nach Relevanz sortiert sind, wie durch die Levenshtein-Entfernung bestimmt.

Wir haben es gegen eine große Sammlung von Künstlern und Songtiteln verwendet, wenn die eingehende Abfrage einen oder mehrere Tippfehler enthält, und es hat ziemlich gut funktioniert (und ist bemerkenswert schnell, wenn man bedenkt, dass sich die Sammlungen in Millionen von Zeichenfolgen befinden).

Darüber hinaus können Sie mit Solr bei Bedarf über JSON nach dem Index suchen, sodass Sie die Lösung zwischen den verschiedenen Sprachen, die Sie betrachten, nicht neu erfinden müssen.

Eine sehr, sehr gute Ressource für diese Art von Algorithmen ist Simmetrics: http://sourceforge.net/projects/simmetrics/

Leider ist die großartige Website mit einem Großteil der Dokumentation nicht mehr vorhanden :( Falls sie erneut angezeigt wird, lautete die vorherige Adresse: http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Voila (mit freundlicher Genehmigung von "Wayback Machine"): http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

Sie können die Codequelle studieren. Es gibt Dutzende von Algorithmen für diese Art von Vergleichen, von denen jeder einen anderen Kompromiss aufweist. Die Implementierungen sind in Java.

Um einen großen Satz Text effizient abzufragen, können Sie das Konzept Abstand bearbeiten / Präfix Abstand bearbeiten verwenden.

Bearbeitungsabstand ED (x, y): Minimale Anzahl von Transfromen, um von Term x zu Term y zu gelangen

Die Berechnung der ED zwischen jedem Begriff und Abfragetext ist jedoch ressourcen- und zeitintensiv. Anstatt zuerst ED für jeden Term zu berechnen, können wir daher mögliche übereinstimmende Terme mithilfe einer Technik namens Qgram Index extrahieren. und wenden Sie dann die ED-Berechnung auf diese ausgewählten Begriffe an.

Ein Vorteil der Qgram-Index-Technik besteht darin, dass sie die Fuzzy-Suche unterstützt.

Ein möglicher Ansatz zur Anpassung des QGram-Index besteht darin, mithilfe von Qgrams einen invertierten Index zu erstellen. Dort speichern wir alle Wörter, die aus einem bestimmten Qgram bestehen, unter diesem Qgram. (Anstatt die vollständige Zeichenfolge zu speichern, können Sie für jede Zeichenfolge eine eindeutige ID verwenden.) Hierfür können Sie die Tree Map-Datenstruktur in Java verwenden. Es folgt ein kleines Beispiel zum Speichern von Begriffen

col: col mbia, col ombo, gan col a, ta col ama

Bei der Abfrage berechnen wir dann die Anzahl der allgemeinen Qgramme zwischen dem Abfragetext und den verfügbaren Begriffen.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

Anzahl der gemeinsamen q-Gramm = 4.

Für die Begriffe mit einer hohen Anzahl gängiger Qgramme berechnen wir die ED / PED anhand des Abfragebegriffs und schlagen den Begriff dann dem Endbenutzer vor.

Eine Implementierung dieser Theorie finden Sie im folgenden Projekt (siehe "QGramIndex.java"). Fühlen Sie sich frei, Fragen zu stellen. https://github.com/Bhashitha-Gamage/City_Search

Um mehr über Edit Distance, Prefix Edit Distance Qgram Index zu erfahren, schauen Sie sich bitte das folgende Video von Prof. Dr. Hannah Bast an: https://www.youtube.com/embed/6pUg2wmGJRo (Lektion beginnt um 20:06 Uhr )

Das Problem ist schwer zu implementieren, wenn die Eingabedaten zu groß sind (z. B. Millionen von Zeichenfolgen). Ich habe die elastische Suche verwendet, um dies zu lösen.

Schnellstart: https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

Fügen Sie einfach alle Eingabedaten in die Datenbank ein und Sie können jede Zeichenfolge basierend auf jeder Bearbeitungsentfernung schnell durchsuchen. Hier ist ein C # -Schnipsel, mit dem Sie eine Liste der Ergebnisse erhalten, sortiert nach Bearbeitungsabstand (kleiner bis höher).

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));

Hier können Sie einen Golang-POC haben, um die Abstände zwischen den angegebenen Wörtern zu berechnen. Sie können das minDistanceund einstellendifference für andere Bereiche einstellen.

Spielplatz: https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}