Ich habe ein Wörterbuch von 50K bis 100K Strings (kann bis zu 50 + Zeichen) und ich versuche zu finden, ob eine gegebene Zeichenfolge im Wörterbuch mit einigen "Bearbeiten" Abstandstoleranz ist. (Levenshtein zum Beispiel). Ich bin in Ordnung vor der Berechnung jeder Art von Datenstruktur vor der Suche.
Mein Ziel ist es, Tausende von Strings so schnell wie möglich gegen dieses Wörterbuch zu laufen und den nächsten Nachbarn zurück zu geben. Es würde mir gut gehen, wenn ich nur einen Boolean erhalte, der sagt, ob ein gegebener Teil im Wörterbuch ist oder nicht, wenn es einen wesentlich schnelleren Algorithmus dafür gibt
Dafür habe ich zuerst versucht, alle Levenshtein-Abstände zu berechnen und das Minimum zu nehmen, und es war offensichtlich schrecklich langsam. Also habe ich versucht, eine Levenshtein Trie basierend auf diesem Artikel Ссылка
zu implementierenSehen Sie meinen Kern hier, um den Benchmark zu reproduzieren: Ссылка
Hier sind ein paar Benchmarks, die ich auf meinem Rechner bekommen habe:
Entfernung von 0 (perfekte Übereinstimmung) bearbeiten
%Vor%* Bearbeiten Entfernung von 2, wird es viel langsamer *
%Vor%Und es geht von dort abwärts und wird extrem langsam für Bearbeitungsabstand größer als 2. (1+ Sekunde im Durchschnitt pro getesteten String).
Ich würde gerne wissen, wie / wenn ich das deutlich beschleunigen könnte. Wenn bereits bestehende Lösungen in Ruby / Gems implementiert sind, möchte ich das Rad auch nicht neu erfinden ...
EDIT 1: In meinem Fall erwarte ich, dass die meisten Strings, die ich mit dem Dictionary abgleiche, NICHT dort sind. Also, wenn es einen Algorithmus gibt, um einen String schnell zu verwerfen, könnte das wirklich helfen.
Danke, Nicolas
Ich habe ein paar Edelsteine geschrieben, fuzzily und verschwommen , die auf Trigrammen basierende Fuzzy-Anpassung verwenden. Angesichts Ihrer (geringen) Datenmenge wird Fuzzily einfacher zu integrieren sein und ungefähr so schnell, dass Sie entweder Antworten innerhalb von 5-10ms auf moderner Hardware erhalten würden.
Da beide auf Trigrammen basieren (die indexierbar sind), nicht auf die Bearbeitungsentfernung (was nicht der Fall ist), müssten Sie dies wahrscheinlich in zwei Durchgängen tun:
In Ruby (wie du es verlangst), unter Verwendung von Fuzzily + dem Text-Juwel , würde das Erhalten der Datensätze mit dem Bearbeitungsdistanzschwellenwert aussehen wie:
%Vor%Dies führt zu einer Handvoll gut optimierter Datenbankabfragen und ein paar
Vorbehalte:
Vor ungefähr 15 Jahren schrieb ich eine unscharfe Suche, die N Nachbarn finden kann. Dies ist meine Modifikation von Wilbur Trigram-Algorithmus, und diese Änderung namens "Wilbur-Khovayko-Algorithmus".
Grundidee: Strings durch Trigramme teilen und maximale Schnittpunkte suchen.
Zum Beispiel haben wir die Zeichenfolge "Hallo Welt". Diese Zeichenkette erzeugt Trigramme: hel ell llo "lo", "o_w", e und so weiter; Außerdem werden spezielle Präfix- / Suffix-Trigramme für jedes Wort erzeugt, wie $ he $ wo lo $ ld $.
Danach wird für jedes in Trigramm eingebaute Index angegeben, in welchem Term es steht.
Also, das ist eine Liste von term_ID für jedes Trigramm.
Wenn der Benutzer einen String aufruft - er teilt sich auch in Trigramme und programmiert den maximalen Schnittpunktwert für die Suche und erzeugt eine Liste in N-Größe.
Es funktioniert schnell: Ich erinnere mich, auf alten Sun / Solaris, 256 MB RAM, 200MHz CPU, es 100 suchen nächsten Begriff im Wörterbuch 5.000.000 Begriffe, in 0,25 s
Sie können meine alte Quelle bekommen von: Ссылка
UPDATE:
Ich habe ein neues Archiv erstellt, wo Makefile für moderne Linux / BSD-Versionen angepasst ist. Sie können die neue Version hier herunterladen: Ссылка
Machen Sie ein Verzeichnis und extrahieren Sie das Archiv hier:
%Vor%Gehe zum Testverzeichnis, kopiere die Termlistendatei (das ist der feste Name, die Termlist.txt) und make index:
%Vor%In diesem Test verwendete ich ~ 380.000 abgelaufene Domain-Namen:
%Vor%Führen Sie die Findetest-Anwendung aus:
%Vor%Wenn Sie bereit sind, sich mit maschinellen Lernansätzen zu beschäftigen, dann ist dieser Artikel von Geoff Hinton ein guter Ausgangspunkt
Diese Art von Ansätzen wird in Orten wie Google usw. verwendet.
Im Wesentlichen clustern Sie Ihre Wörterbuchzeichenfolgen basierend auf Ähnlichkeit. Wenn der Abfrage-String kommt, vergleichen Sie nicht den Bearbeitungsabstand mit dem gesamten Datensatz, sondern vergleichen Sie einfach den Cluster, wodurch sich die Abfragezeit erheblich verkürzt.
PS Ich habe ein wenig gegoogelt und eine Ruby-Implementierung eines anderen ähnlichen Ansatzes namens Locality Sensitive Hashing gefunden Ссылка
Tags und Links ruby algorithm performance fuzzy-search levenshtein-distance