Die nächste Übereinstimmung der Zeichenfolge erhalten

Question

Ich brauche eine Möglichkeit, mehrere Zeichenfolgen mit einer Testzeichenfolge zu vergleichen und die Zeichenfolge zurückzugeben, die ihr am ähnlichsten ist:

TESTSTRING: DER BRAUNE FUCHS SPRANG ÜBER DIE ROTE KUH

WAHL A   : DIE ROTE KUH SPRANG ÜBER DAS GRÜNE HUHN
WAHL B   : DIE ROTE KUH SPRANG ÜBER DIE ROTE KUH
WAHL C   : DER ROTE FUCHS SPRANG ÜBER DIE BRAUNE KUH

(Wenn ich das richtig gemacht habe) Die ähnlichste Zeichenfolge zum "TESTSTRING" sollte "WAHL C" sein. Was ist der einfachste Weg, dies zu tun?

Ich plane, dies in mehreren Sprachen wie VB.net, Lua und JavaScript zu implementieren. Zu diesem Zeitpunkt ist Pseudocode akzeptabel. Wenn Sie ein Beispiel für eine bestimmte Sprache bereitstellen können, wäre das ebenfalls sehr hilfreich!

Answer 1

Vor etwa einem Jahr wurde ich mit diesem Problem konfrontiert, als es darum ging, vom Benutzer eingegebene Informationen über eine Bohrinsel in einer Datenbank mit verschiedenen Informationen nachzuschlagen. Das Ziel war es, eine Art unscharfe Stringsuche durchzuführen, die den Datenbankeintrag mit den häufigsten Elementen identifizieren konnte.

Ein Teil der Forschung umfasste die Implementierung des Levenshtein-Abstand Algorithmus, der bestimmt, wie viele Änderungen an einer Zeichenkette oder einem Satz vorgenommen werden müssen, um sie in eine andere Zeichenkette oder einen anderen Satz zu verwandeln.

Die Umsetzung, die ich mir ausgedacht habe, war relativ einfach und umfasste einen gewichteten Vergleich der Länge der beiden Sätze, der Anzahl der Änderungen zwischen den einzelnen Sätzen 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 einzufügen:

---

Beim Fuzzy String Matching wird eine menschenähnliche Schätzung der Ähnlichkeit zweier Wörter oder Sätze vorgenommen. In vielen Fällen geht es darum, Wörter oder Ausdrücke zu identifizieren, die einander am ähnlichsten sind. Dieser Artikel beschreibt eine firmeninterne Lösung für das Fuzzy-String-Matching-Problem und seine Nützlichkeit bei der Lösung einer Vielzahl von Problemen, die es uns ermöglichen, Aufgaben zu automatisieren, die zuvor eine mühsame Beteiligung des Benutzers erforderten.

Einführung

Der Bedarf an Fuzzy-String-Matching entstand ursprünglich bei der Entwicklung des Validator-Tools für den Golf von Mexiko. Es gab eine Datenbank mit bekannten Bohrinseln und Plattformen im Golf von Mexiko, und die Versicherungsnehmer gaben uns einige schlecht getippte Informationen über ihre Anlagen, die wir mit der Datenbank bekannter Plattformen abgleichen mussten. Wenn nur sehr wenige Informationen angegeben wurden, konnten wir uns bestenfalls darauf verlassen, dass ein Versicherer die betreffende Plattform "erkennt" und die richtigen Informationen abruft. An dieser Stelle kommt diese automatisierte Lösung ins Spiel.

Ich verbrachte einen Tag damit, Methoden für die unscharfe Abgleichung von Zeichenketten zu recherchieren, und stieß schließlich auf den sehr nützlichen Levenshtein-Distanzalgorithmus auf Wikipedia.

Umsetzung

Nach der Lektüre der Theorie, die dahinter steckt, habe ich sie umgesetzt und Wege gefunden, 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 zur Bewertung der Ähnlichkeit von zwei Zeichenfolgen erstellt. Die eine nenne ich "valuePhrase" und die andere "valueWords". valuePhrase ist einfach der Levenshtein-Abstand zwischen den beiden Phrasen, und valueWords teilt die Zeichenkette in einzelne Wörter auf, basierend auf Begrenzungszeichen wie Leerzeichen, Bindestriche und alles andere, was Sie möchten, und vergleicht jedes Wort mit jedem anderen Wort, wobei der kürzeste Levenshtein-Abstand zwischen zwei beliebigen Wörtern summiert wird. Im Wesentlichen misst es, ob die Informationen in einem "Satz" wirklich in einem anderen enthalten sind, einfach als wortweise Permutation. Als Nebenprojekt habe ich einige Tage damit verbracht, eine möglichst effiziente Methode zur Aufteilung einer Zeichenkette auf der Grundlage von Begrenzungszeichen 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

Maße der Ähnlichkeit

Mit Hilfe dieser 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. Der unscharfe Abgleich von Zeichenketten ist selbst eine unscharfe Wissenschaft. Wenn wir also linear unabhängige Metriken zur Messung der Ähnlichkeit von Zeichenketten erstellen und eine bekannte Menge von Zeichenketten haben, die wir miteinander abgleichen möchten, können wir die Parameter finden, die für unsere spezifischen Zeichenketten die besten Ergebnisse für den unscharfen Abgleich liefern.

Ursprünglich war das Ziel der Metrik, einen niedrigen Suchwert für eine exakte Übereinstimmung und steigende Suchwerte für zunehmend permutierte Maßnahmen zu haben. In einem unpraktischen Fall war dies recht einfach zu definieren, indem man eine Reihe von gut definierten Permutationen verwendete und die endgültige Formel so gestaltete, dass sie wie gewünscht steigende Suchwerte ergab.

Im obigen Screenshot habe ich meine Heuristik so angepasst, dass sie meiner Meinung nach gut zu dem von mir wahrgenommenen Unterschied zwischen dem Suchbegriff und dem Ergebnis passt. Die Heuristik, die ich für Value Phrase in der obigen Tabelle war =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) . Ich habe die Strafe für den Levenstein-Abstand effektiv um 80 % des Längenunterschieds zwischen den beiden "Sätzen" verringert. Auf diese Weise erleiden "Phrasen", die die gleiche Länge haben, die volle Strafe, aber "Phrasen", die "zusätzliche Informationen" (länger) enthalten, aber abgesehen davon immer noch größtenteils die gleichen Zeichen haben, erleiden eine geringere Strafe. Ich habe die Value Words Funktion so wie sie ist, und dann meine endgültige SearchVal Heuristik wurde definiert als =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - ein gewichteter Durchschnitt. Die niedrigere der beiden Punktzahlen wurde mit 80 % gewichtet, die höhere mit 20 %. Dies war nur eine Heuristik, die für meinen Anwendungsfall geeignet war, um eine gute Trefferquote zu erzielen. Diese Gewichtungen kann man dann anpassen, um die beste Trefferquote mit den eigenen Testdaten zu erzielen.

Wie Sie sehen können, haben die letzten beiden Metriken, die Fuzzy-String-Matching-Metriken sind, bereits eine natürliche Tendenz, Strings, die übereinstimmen sollen, eine niedrige Punktzahl zu geben (auf der Diagonale). Dies ist sehr gut.

Anmeldung Um die Optimierung des Fuzzy-Matchings zu ermöglichen, gewichte ich jede Metrik. So kann jede Anwendung des Fuzzy String Matching die Parameter unterschiedlich gewichten. Die Formel, die die endgültige Punktzahl bestimmt, ist eine einfache Kombination aus den Metriken und ihren Gewichtungen:

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

Mit Hilfe eines Optimierungsalgorithmus (am besten eignet sich hier ein neuronales Netz, da es sich um ein diskretes, mehrdimensionales Problem handelt) soll nun die Anzahl der Übereinstimmungen maximiert werden. Ich habe eine Funktion erstellt, die die Anzahl der korrekten Übereinstimmungen der einzelnen Sätze untereinander ermittelt, wie in diesem letzten Screenshot zu sehen ist. Eine Spalte oder Zeile erhält einen Punkt, wenn die niedrigste Punktzahl der Zeichenkette zugewiesen wird, die übereinstimmen sollte, und Teilpunkte werden vergeben, wenn es einen Gleichstand bei der niedrigsten Punktzahl gibt und die richtige Übereinstimmung unter den übereinstimmenden Zeichenketten ist. Dann habe ich es optimiert. Sie können sehen, dass eine grüne Zelle die Spalte ist, die am besten mit der aktuellen Zeile übereinstimmt, und ein blaues Quadrat um die Zelle ist die Zeile, die am besten mit der aktuellen Spalte übereinstimmt. Die Punktzahl in der unteren Ecke ist ungefähr die Anzahl der erfolgreichen Übereinstimmungen, und das ist es, was wir unserem Optimierungsproblem zu maximieren vorgeben.

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

In diesem speziellen Fall ist die Länge der Zeichenfolgen irrelevant, da wir Abkürzungen erwarten, die längere Wörter darstellen. Daher ist die optimale Gewichtung für die Länge -0,3, was bedeutet, dass wir Zeichenfolgen, die in der Länge variieren, nicht bestrafen. Wir reduzieren die Punktzahl in Erwartung dieser Abkürzungen und geben so mehr Raum für Teil-Wort-Übereinstimmungen, um Nicht-Wort-Übereinstimmungen zu verdrängen, die einfach weniger Substitutionen erfordern, weil die Zeichenfolge kürzer ist.

Die Wortgewichtung beträgt 1,0, während die Phrasengewichtung nur 0,5 beträgt, was bedeutet, dass wir das Fehlen ganzer Wörter in einer Zeichenkette bestrafen und die Unversehrtheit der gesamten Phrase höher bewerten. Dies ist nützlich, weil viele dieser Zeichenfolgen ein Wort gemeinsam haben (die Gefahr), bei dem es wirklich darauf ankommt, ob die Kombination (Region und Gefahr) erhalten bleibt oder nicht.

Schließlich wird die Minimalgewichtung auf 10 und die Maximalgewichtung auf 1 optimiert. Das bedeutet, dass die Übereinstimmung stark benachteiligt wird, wenn die beste der beiden Bewertungen (Wertphrase und Wertwörter) nicht sehr gut ist, aber die schlechteste der beiden Bewertungen nicht stark benachteiligt wird. Im Wesentlichen bedeutet dies, dass der Schwerpunkt auf folgenden Anforderungen liegt soit das valueWord oder die valuePhrase, um eine gute Bewertung zu erhalten, aber nicht beides. Eine Art "Wir nehmen, was wir kriegen können"-Mentalität.

Es ist wirklich faszinierend, was der optimierte Wert dieser 5 Gewichte über die Art des Fuzzy-String-Matchings aussagt, das stattfindet. Für völlig unterschiedliche praktische Fälle von Fuzzy-String-Matching 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 Spalten mit sich selbst für alle perfekten Ergebnisse entlang der Diagonale abgleicht und es dem Benutzer ermöglicht, Parameter zu ändern, um die Rate zu kontrollieren, mit der die Ergebnisse von 0 abweichen, und angeborene Ähnlichkeiten zwischen Suchphrasen zu bemerken (die theoretisch verwendet werden könnten, 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 aus einer Reihe von Zeichenfolgen identifiziert, für die es keine perfekte Übereinstimmung gibt. (Wie eine ungefähre Übereinstimmung vlookup für Zeichenfolgen).

---

Daraus sollten Sie ableiten, dass Sie wahrscheinlich eine Kombination aus hochrangigen Heuristiken (Auffinden 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 eine Reihe von Gewichtungen für alle Metriken festlegen, die Sie zur Bestimmung der Ähnlichkeit verwenden.

Mit den richtigen Heuristiken und Gewichtungen wird Ihr Vergleichsprogramm schnell die Entscheidungen treffen, die Sie auch getroffen hätten.

Answer 2

Dieses Problem tritt in der Bioinformatik immer wieder auf. Die oben akzeptierte Antwort (die übrigens großartig war) ist in der Bioinformatik als die Needleman-Wunsch- (Vergleich zweier Zeichenfolgen) und Smith-Waterman- (Finden einer ungefähren Teilzeichenfolge in einer längeren Zeichenfolge) Algorithmen bekannt. Sie funktionieren großartig und waren jahrzehntelang unverzichtbar.

Aber was ist, wenn man eine Million Zeichenfolgen vergleichen muss? Das sind eine Billion paarweise Vergleiche, von denen jeder O(n*m) ist! Moderne DNA-Sequenzer erzeugen problemlos Milliarden kurze DNA-Sequenzen, jede etwa 200 DNA-"Buchstaben" lang. In der Regel möchten wir für jede solche Zeichenfolge das beste Match gegen das menschliche Genom (3 Milliarden Buchstaben) finden. Klar, der Needleman-Wunsch-Algorithmus und seine Verwandten werden das nicht schaffen.

Dieses sogenannte "Alignierungsproblem" ist ein Forschungsfeld von aktiver Forschung. Die beliebtesten Algorithmen können derzeit in wenigen Stunden auf vernünftiger Hardware (8 Kerne und 32 GB RAM) ungenaue Übereinstimmungen zwischen einer Milliarde kurzer Zeichenfolgen und dem menschlichen Genom finden.

Die meisten dieser Algorithmen funktionieren so, dass sie schnell kurze exakte Übereinstimmungen (Seeds) finden und diese dann mit einem langsameren Algorithmus auf die volle Zeichenfolge erweitern (zum Beispiel Smith-Waterman). Der Grund, warum das funktioniert, ist, dass wir wirklich nur an wenigen nahen Übereinstimmungen interessiert sind, sodass es sich auszahlt, die 99,9...% der Paare loszuwerden, die nichts gemeinsam haben.

Wie hilft das Auffinden exakter Übereinstimmungen beim Finden ungeradener Übereinstimmungen? Nun, angenommen, wir erlauben nur einen einzigen Unterschied zwischen der Abfrage und dem Ziel. Es ist leicht zu erkennen, dass dieser Unterschied entweder im rechten oder linken Teil der Abfrage auftreten muss, und so muss der andere Teil genau übereinstimmen. Diese Idee kann auf mehrere Missverhältnisse erweitert werden und bildet die Grundlage für den ELAND-Algorithmus, der häufig mit Illumina-DNA-Sequenzierern verwendet wird.

Es gibt viele sehr gute Algorithmen für exaktes Zeichenfolgen-Matching. Angenommen, wir haben eine Abfragezeichenfolge der Länge 200 und eine Zielsequenz der Länge 3 Milliarden (das menschliche Genom), möchten wir einen beliebigen Ort im Ziel finden, an dem eine Teilzeichenfolge der Länge k genau mit einer Teilzeichenfolge der Abfrage übereinstimmt. Ein einfacher Ansatz besteht darin, das Ziel zu indizieren: Nehmen Sie alle k-langens Zeichenfolgen, legen Sie sie in ein Array und sortieren Sie sie. Nehmen Sie dann jede k-lange Zeichenfolge der Anfrage und durchsuchen Sie den sortierten Index. Sortieren und suchen kann in O(log n) Zeit durchgeführt werden.

Aber der Speicher kann ein Problem sein. Ein Index des 3 Milliarden Buchstaben langen Ziels müsste 3 Milliarden Zeiger und 3 Milliarden k-lange Wörter enthalten. Es scheint schwierig zu sein, dies in weniger als mehreren zehn Gigabyte RAM unterzubringen. Aber erstaunlicherweise können wir den Index erheblich komprimieren, indem wir die Burrows-Wheeler-Transforms verwenden, und er wird trotzdem effizient abfragbar sein. Ein Index des menschlichen Genoms passt in weniger als 4 GB RAM. Diese Idee ist die Grundlage beliebter Sequenz-Aligner wie Bowtie und BWA.

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

Die obigen Links enthalten eine Fülle von Informationen und Links zu Primärforschungsarbeiten. 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.

Schließlich, obwohl diese Algorithmen im Wesentlichen das Problem des (Re-)Sequenzierens einzelner menschlicher Genome (eine Milliarde kurzer Zeichenfolgen) gelöst haben, verbessert sich die DNA-Sequenzierungstechnologie noch schneller als das Mooresche Gesetz, und wir nähern uns schnell Datensätzen mit Billionen von Buchstaben. Beispielsweise gibt es derzeit Projekte zur Sequenzierung der Genome von 10.000 Wirbeltierarten, die jeweils etwa eine Milliarde Buchstaben lang sind. Natürlich möchten wir diese Daten paarweise mit ungenauen Zeichenfolgenabgleichen bearbeiten...

Answer 3

Ich behaupte, dass die Wahl B näher am Teststring ist, da sie nur 4 Zeichen (und 2 Löschungen) vom Originalstring entfernt ist. Du hingegen siehst C als näher, weil es sowohl braun als auch rot enthält. Es hätte jedoch eine größere Edit-Entfernung.

Es gibt einen Algorithmus namens Levenshtein-Distanz, der die Edit-Entfernung zwischen zwei Eingaben misst.

Hier ist ein Tool für diesen Algorithmus.

1. Bewertet die Wahl A mit einer Entfernung von 15.
2. Bewertet die Wahl B mit einer Entfernung von 6.
3. Bewertet die Wahl C mit einer Entfernung von 9.

BEARBEITEN: Entschuldigung, ich bringe die Zeichenfolgen im Levenshtein-Tool durcheinander. Aktualisiert mit den korrekten Antworten.

Answer 4

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

Answer 5

Du findest diese Bibliothek vielleicht hilfreich! http://code.google.com/p/google-diff-match-patch/

Derzeit ist sie verfügbar in Java, JavaScript, Dart, C++, C#, Objective C, Lua und Python

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

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