Beschleunigung levenshtein/ähnliche_text in PHP

Question

Ich verwende zZ similar_text, um eine Zeichenkette gegen eine Liste ~ 50.000 zu vergleichen, die funktioniert, obwohl wegen der Zahl Vergleiche es sehr langsam ist. Es dauert ungefähr 11 Minuten, um ~ 500 eindeutige Zeichenfolgen zu vergleichen.

Vor dem Ausführen überprüfe ich die Datenbanken, um zu sehen, ob es in der Vergangenheit verarbeitet wurde, so dass es immer nach dem ersten Durchlauf fast augenblicklich ist.

Ich bin sicher, mit levenshtein wäre etwas schneller und die LevenshteinDistance-Funktion jemand in der Anleitung geschrieben sieht interessant aus. Fehle ich etwas, das das deutlich schneller machen könnte?

Answer 1

Am Ende waren sowohl levenshtein als auch similar_text beide zu langsam mit der Anzahl der Strings, die durchlaufen werden mussten, sogar mit vielen Überprüfungen und nur mit denen, die sie als letztes Mittel benutzten.

Als ein Experiment portierte ich einen Teil des Codes nach C#, um zu sehen, wie viel schneller es über interperierten Code wäre. Es lief in etwa 3 Minuten mit dem gleichen Datensatz.

Als nächstes fügte ich ein zusätzliches Feld zur Tabelle hinzu und verwendete die doppelte metaphone PECL-Erweiterung, um Schlüssel für jede Zeile zu erzeugen. Die Ergebnisse waren gut, obwohl einige Zahlen zu Duplikaten führten. Ich schätze, ich hätte dann jeden einzelnen durch die oben genannten Funktionen laufen lassen können, entschied mich aber dazu nicht.

Am Ende entschied ich mich für den einfachsten Ansatz, MySQL Volltext, der sehr gut funktioniert. Gelegentlich gibt es Fehler, obwohl sie leicht zu erkennen und zu korrigieren sind. Auch läuft es sehr schnell, in ca. 3-4 Sekunden.

Answer 2

Vielleicht könnten Sie einige Checks "kurzschließen", indem Sie zuerst Ihre Zeichenfolge für eine exakte Übereinstimmung vergleichen (und zuerst vergleichen, wenn die Länge identisch ist), und wenn es ist, überspringen Sie den teureren similar_text Aufruf.

Wie @jason bemerkt, wird ein O (N^3) -Algorithmus niemals eine gute Wahl sein.

Answer 3

Wenn levenshtein Automat mit (Automaten, die einen String mit Abstand übereinstimmt k) Sie in O(n) einen Scheck für die Anpassung tun, wo n ist die Länge der Zeichenfolge Sie prüfen. Das Konstruieren des Automaten dauert O(kn), wobei k die maximale Entfernung und n Länge der Basiszeichenfolge ist.