Ich habe eine Datenbank von 350,000 Strings mit einer durchschnittlichen Länge von etwa 500 . Die Zeichenfolgen bestehen nicht aus Wörtern, sie sind eine im Wesentlichen zufällige Zusammenstellung von Zeichen.
Ich muss sicherstellen, dass keine der beiden Strings zu ähnlich sind, wobei Ähnlichkeit definiert ist als edit distance dividiert durch avg length of string . Die Aufteilung ist, weil kleinere Bearbeitungsabstände für kleinere Zeichenfolgen akzeptabler sind. Es ist in Ordnung, wenn aus Leistungsgründen eine andere Metrik verwendet wird, aber die Bearbeitungsentfernung ist die bevorzugte Grundmetrik.
Naiv, berechnen wir Entfernung bearbeiten mit Laufzeit O(a*b) , wobei a,b die Länge der beiden Strings sind . Wir machen das für alle n^2 -Paare, was eine Gesamtlaufzeit von O(n^2*a*b) ergibt, die mit n=350,000, a,b=500 eindeutig zu groß ist.
Die Datenbank hat die Form einer Python-Liste, die aus einer CSV-Datei gelesen wird. Ich würde es gerne auf eine pythonische Weise verarbeiten, wenn möglich.
Wie kann dies beschleunigt werden? Ich bin mir nicht sicher, wie lange der naive Algorithmus dauern wird (in der Größenordnung von Wochen), aber idealerweise sollte er weniger als einen Tag dauern.
Ich habe einen sehr kurzen Prototyp eines einfachen Lokalisierungs-sensitiven Hashalgorithmus in Python geschrieben. Allerdings gibt es ein paar Vorbehalte und Sie möchten vielleicht auch einige Stücke optimieren. Ich werde sie erwähnen, wenn wir sie sehen.
Angenommen, alle Ihre Strings sind in strings gespeichert.
Zunächst ist dies eine leichte Variante der Bit-Sampling-Funktion, die am besten für die allgemeine Hamming-Distanz geeignet ist. Im Idealfall, wenn alle Ihre Saiten gleich lang sind, kann dies eine theoretische Wahrscheinlichkeit für die Hamming-Distanz geben. Wenn die Hamming-Distanz zwischen zwei Strings klein ist, ist es sehr unwahrscheinlich, dass sie unterschiedliche Hash-Werte haben. Dies kann durch den Parameter SAMPLING_LENGTH festgelegt werden. Ein größerer SAMPLING_LENGTH wird es wahrscheinlicher machen, dass eine ähnliche Zeichenkette mit einem anderen Hash verglichen wird, aber auch die Wahrscheinlichkeit einer Hashing-Zeichenkette, die nicht sehr ähnlich ist, zum selben Hash reduziert wird. Für die Hamming-Distanz können Sie diesen Kompromiss leicht berechnen.
Wenn Sie dieses Snippet mehrere Male ausführen, können Sie sicher sein, dass Sie keine ähnlichen Strings mehr haben, da Sie jedes Mal verschiedene Orte ausprobieren.
Um Ihrem Zweck gerecht zu werden, verschiedene Längenzeichenfolgen zu vergleichen, besteht ein möglicher Ansatz darin, den kürzeren Zeichenfolgenabstand auf kürzeren Zeichenfolgen zu belassen und Kopien davon zu erstellen.
Obwohl alle Operationen in diesem Snippet linear sind (O (n)), kann es dennoch viel Speicher und Laufzeit verbrauchen und es könnte möglich sein, einen konstanten Faktor zu reduzieren.
Sie können auch einen komplizierteren Algorithmus für die lokale Empfindlichkeit verwenden, wie er hier beschrieben wird: Ссылка
Tags und Links python python-3.x similarity edit-distance