Ich habe ein Wörterbuch mit 50.000 bis 100.000 Zeichenfolgen (kann bis zu 50+ Zeichen lang sein) und versuche herauszufinden, ob eine bestimmte Zeichenfolge mit einer gewissen Toleranz für Bearbeitungsabstände im Wörterbuch enthalten ist. (Levenshtein zum Beispiel). Ich kann jede Art von Datenstruktur gut vorberechnen, bevor ich die Suche durchführe.

Mein Ziel ist es, so schnell wie möglich Tausende von Zeichenfolgen für dieses Wörterbuch auszuführen und den nächsten Nachbarn zurückzugeben. Es wäre in Ordnung, wenn ich nur einen Booleschen Wert erhalten würde, der besagt, ob eine bestimmte Angabe im Wörterbuch enthalten ist oder nicht, wenn es einen wesentlich schnelleren Algorithmus dafür gäbe

Dafür habe ich zuerst versucht, alle Levenshtein-Entfernungen zu berechnen und das Minimum zu nehmen, und es war offensichtlich schrecklich langsam. Also habe ich versucht, einen Levenshtein Trie basierend auf diesem Artikel zu implementierenhttp://stevehanov.ca/blog/index.php?id=114

Sehen Sie sich hier meine Zusammenfassung an, um den Benchmark zu reproduzieren:https://gist.github.com/nicolasmeunier/7493947

Hier sind einige Benchmarks, die ich auf meinem Computer erhalten habe:

Abstand von 0 bearbeiten (perfekte Übereinstimmung)

Benchmark.measure { 10.times { dictionary.search(random_word, 0) } }
<Benchmark::Tms:0x007fa59bad8908 @label="", @real=0.010889, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.00999999999999801, @total=0.00999999999999801> 

*Abstand von 2 ändern, es wird VIEL langsamer *

Benchmark.measure { 10.times { dictionary.search(random_word, 2) } }
<Benchmark::Tms:0x007fa58c9ca778 @label="", @real=3.404604, @cstime=0.0, @cutime=0.0, @stime=0.020000000000000018, @utime=3.3900000000000006, @total=3.4100000000000006>

Und von dort geht es bergab und wird extrem langsam, wenn die Bearbeitungsentfernung größer als 2 ist (durchschnittlich 1+ Sekunde pro getesteter Saite).

Ich würde gerne wissen, wie / ob ich dies erheblich beschleunigen könnte. Wenn es bereits existierende Lösungen in Ruby / Gems gibt, möchte ich das Rad auch nicht neu erfinden ...

EDIT 1: In meinem Fall erwarte ich, dass die meisten Zeichenfolgen, die ich mit dem Wörterbuch abgleichen möchte, NICHT vorhanden sind. Wenn es also einen Algorithmus gibt, mit dem eine Zeichenfolge schnell verworfen werden kann, könnte dies wirklich helfen.

Danke, Nicolas