Eine Beschleunigung levenshtein / similar_text in PHP

Question

Ich bin derzeit mit similar_text einer Zeichenfolge vergleichen gegen eine Liste von ~ 50.000, das die Anzahl der Vergleiche aufgrund funktioniert, obwohl es sehr langsam ist. Es dauert etwa 11 Minuten ~ 500 eindeutige Zeichenfolge zu vergleichen.

Vor diesen läuft ich die Datenbanken zu überprüfen, um zu sehen, ob es so jedes Mal in der Vergangenheit verarbeitet wurde nach dem inital Laufe ist es in der Nähe Augenblick.

Ich bin sicher, mit levenshtein wäre etwas schneller und die Levenshtein-Distanz-Funktion jemand im Handbuch geschrieben sieht interessant aus. Fehle ich etwas, das dies deutlich schneller machen könnte?

Answer 1

Am Ende beide levenshtein und similar_text waren beide zu langsam mit der Anzahl der Saiten es durch gehen musste, auch mit vielen Kontrollen und nur sie einen von ihnen als letztes Mittel verwendet wird.

Als ein Experiment, ich portierte einige des Code in C #, um zu sehen, wie viel schneller es über interperated Code wäre. Es lief in ca. 3 Minuten mit der gleichen Datenmenge.

Als nächstes habe ich ein zusätzliches Feld auf den Tisch und verwendet, um die Doppel Metaphone PECL-Erweiterung Schlüssel für jede Zeile zu erzeugen. Die Ergebnisse waren gut, obwohl da einige Zahlen enthalten diese Duplikate verursacht. Ich glaube, ich dann jeder durch die oben genannten Funktionen ausgeführt haben könnte, aber beschlossen, nicht zu.

Am Ende habe ich für die einfachste Ansatz entschieden, MySQLs Volltext, die sehr gut funktioniert. Gelegentlich gibt es Fehler, obwohl sie leicht zu erkennen und zu korrigieren sind. Auch ist es läuft sehr schnell, in etwa 3-4 Sekunden.

Answer 2

Vielleicht könnten Sie ‚Kurzschluss‘ einige Kontrollen, indem zuerst die Zeichenfolge für eine exakte Übereinstimmung zu vergleichen (und durch ersten Vergleich, wenn die Länge identisch), und wenn es den teurer similar_text Anruf überspringt.

Wie @ Jason erwähnte, ein O (N ^ 3) Algorithmus ist nie eine gute Wahl sein.

Answer 3

Wenn levenshtein Automat mit (Automaten, die einen String mit Abstand k matches) Sie einen Scheck für den Abgleich in O(n) tun können, wo n die Länge der Zeichenfolge, die Sie prüfen. die Automaten Constructing nehmen O(kn), wo k max Abstand und n Länge des Basis-String ist.