Vergleicht man Saitenabstand basierend auf vorberechneten Hash-Werte

Question

habe ich eine große Liste (über 200.000) von Strings, dass ich möchte auf eine bestimmte Zeichenfolge zu vergleichen. Die angegebene Zeichenfolge wird von einem Benutzer eingeführt, so dass es leicht falsch sein.

Was ich hatte gehofft, auf jeder Saite eine Art von vorberechneten Hash zu tun war, erstellen auf ihn der Liste hinzuzufügen. Dieser Hash würde Informationen wie String-Länge, Addition aller Zeichen usw.

Meine Frage ist, ist so etwas wie dies bereits vorhanden? Sicher würde es etwas sein, das ich laufen läßt vermeiden Levenshtein Abstand auf jeder Zeichenfolge in der Liste?

Oder vielleicht ist es eine dritte Option, die ich noch nicht gedacht haben?

Answer 1

Sounds wie Sie wollen eine Fuzzy-Hash von einer Art verwenden. Es gibt viele Hash-Funktionen zur Verfügung, die Dinge wie dies tun können. Der klassische alte " SOUNDEX " Algorithmus könnte auch Arbeit.

Ein weiterer Gedanke - wenn Sie davon aus, dass die Wahrscheinlichkeit einer falschen Eingabe niedrig ist, dann könnten Sie eigentlich in Ordnung sein einem Volltreffer 99,9% der Zeit ist, zu SOUNDEX zurückzufallen, die 90% der übrigen Fälle hängen bleiben könnten und dann die ganze Liste für das restliche 0,01% der Zeit mit der Suche.

Auch lohnt diese Diskussion: So finden Sie am besten Fuzzy-Match nach einer Zeichenkette in einer großen Zeichenfolge Datenbank