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

Sie könnten an diesem Blog-Beitrag interessiert sein.

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

Fuzzywuzzy ist eine Python-Bibliothek, die einfache Distanzmaße wie die Levenshtein-Distanz für Zeichenfolgenvergleiche bereitstellt. Es basiert auf difflib in der Standardbibliothek und verwendet bei Verfügbarkeit die C-Implementierung von Python-Levenshtein.

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

Answer 2

Wenn Sie dies im Zusammenhang mit einer Suchmaschine oder einem Frontend gegen eine Datenbank tun, sollten Sie in Betracht ziehen, ein Tool wie Apache Solr mit dem ComplexPhraseQueryParser Plugin zu verwenden. Diese Kombination ermöglicht es Ihnen, gegen einen Index von Zeichenfolgen zu suchen, wobei die Ergebnisse nach Relevanz sortiert sind, wie durch die Levenshtein-Distanz bestimmt.

Wir haben es gegen eine große Sammlung von Künstlern und Songtiteln verwendet, wenn die eingehende Abfrage einen oder mehrere Druckfehler haben könnte, und es hat ziemlich gut funktioniert (und das trotz der Tatsache, dass die Sammlungen aus Millionen von Zeichenfolgen bestehen).

Zusätzlich können Sie mit Solr gegen den Index auf Abruf per JSON suchen, sodass Sie die Lösung nicht zwischen den verschiedenen Sprachen, die Sie betrachten, neu erfinden müssen.

Answer 3

Das Problem ist schwer zu implementieren, wenn die Eingabedaten zu groß sind (sagen wir Millionen von Zeichenfolgen). Ich habe Elasticsearch 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 DB ein und Sie können schnell nach jeder Zeichenfolge basierend auf beliebiger Editierdistanz suchen. Hier ist ein C#-Codeausschnitt, der Ihnen eine Liste von Ergebnissen sortiert nach Editierdistanz (kleiner zu größer) liefert

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

Answer 4

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

Leider ist die großartige Website mit vielen Dokumentationen verschwunden :( Falls sie wieder online geht, war ihre vorherige Adresse diese: 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 den Quellcode studieren, es gibt Dutzende von Algorithmen für solche Vergleiche, jeder mit einem anderen Kompromiss. Die Implementierungen sind in Java.

Answer 5

Um eine große Menge Text auf effiziente Weise abzufragen, können Sie das Konzept der Edit Distance/Prefix Edit Distance verwenden.

Edit Distance ED(x,y): minimale Anzahl von Transformationen, um vom Begriff x zum Begriff y zu gelangen

Die Berechnung der ED zwischen jedem Begriff und Abfragetext ist jedoch ressourcen- und zeitaufwändig. Daher können wir anstatt die ED für jeden Begriff zu berechnen, zunächst mögliche übereinstimmende Begriffe extrahieren, indem wir eine Technik namens Qgramm-Index verwenden und dann die ED-Berechnung auf diese ausgewählten Begriffe anwenden.

Ein Vorteil der Qgramm-Index-Technik ist, dass sie die Fuzzy-Suche unterstützt.

Ein möglicher Ansatz, um den QGramm-Index anzupassen, besteht darin, einen Invertierten Index unter Verwendung von Qgrammen zu erstellen. Dort speichern wir alle Wörter, die mit einem bestimmten Qgramm übereinstimmen, unter diesem Qgramm (anstatt den vollständigen String zu speichern, können Sie für jeden String eine eindeutige ID verwenden). Sie können die Datenstruktur Tree Map in Java dafür verwenden. Im Folgenden finden Sie ein kleines Beispiel zum Speichern von Begriffen

col : colmbia, colombo, gancola, tacolama

Dann berechnen wir beim Abfragen die Anzahl der gemeinsamen Qgramme zwischen dem Abfragetext und den verfügbaren Begriffen.

Beispiel: x = HILLARY, y = HILARI(Anfragebegriff)
Qgramme
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
Anzahl gemeinsamer Q-Gramme = 4

Anzahl gemeinsamer Q-Gramme = 4.

Für Begriffe mit einer großen Anzahl von gemeinsamen Qgrammen berechnen wir die ED/PED gegen den Abfragebegriff und schlagen dann den Begriff dem Endbenutzer vor.

Sie finden eine Implementierung dieser Theorie in folgendem Projekt (Siehe "QGramIndex.java"). Zögern Sie nicht, Fragen zu stellen. https://github.com/Bhashitha-Gamage/City_Search

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