Levenshtein Entfernung Algorithmus besser als O (n * m)?

Question

Ich habe für einen fortgeschrittenen levenshtein Abstand Algorithmus gesucht, und das Beste, was ich gefunden habe bisher O (n * m), wobei n und m sind die Längen der zwei Zeichenketten. Der Grund, warum der Algorithmus in diesem Maßstab ist, weil der Raum, keine Zeit, mit der Schaffung einer Matrix der beiden Strings wie diese:

Gibt es einen öffentlich zugänglichen levenshtein Algorithmus, der als O besser ist (n * m)? Ich bin abgeneigt, nicht an fortgeschrittener Informatik Papiere zu suchen und Forschung habe, aber nicht in der Lage gewesen, irgendetwas finden. Ich habe eine Firma, Exorbyte gefunden, die angeblich ein Super-Fortgeschrittene und superschnellen Levenshtein Algorithmus aufgebaut hat aber das ist natürlich ein Geschäftsgeheimnis ist. Ich baue eine iPhone App, die Ich mag würde die Levenshtein-Distanz-Berechnung verwenden. Es ist ein Ziel-c Implementierung verfügbar , aber mit der begrenzten Menge an Speicher auf iPods und iPhones, ich möchte einen besseren Algorithmus, wenn möglich finden.

Answer 1

Haben Sie Interesse die Zeitkomplexität oder die Speicherkomplexität zu reduzieren? Die durchschnittliche Zeitkomplexität O kann reduziert werden (n + d ^ 2), wobei n die Länge der längeren Zeichenfolge und d der Abstand bearbeiten. Wenn Sie nur in der Edit-Distanz interessiert sind und nicht daran interessiert, die Editiersequenz zu rekonstruieren, müssen Sie nur die letzten beiden Zeilen der Matrix im Speicher zu halten, so wird diese Ordnung (n) sein.

Wenn Sie sich leisten können zu nähern, gibt es Poly-logarithmische Annäherungen.

Für die O (n + d ^ 2) Algorithmus sucht Ukkonen der Optimierung oder seine Erweiterung verbesserte Ukkonen . Die beste Annäherung, die ich kenne ist dies eines von Andoni, Krauthgamer, Onak

Answer 2

Wenn Sie nur die Schwellenfunktion wollen - zum Beispiel zu testen, ob der Abstand unter einer bestimmten Schwelle liegt - Sie die Zeit und Raum Komplexität, indem nur die Berechnung die n-Werte auf beiden Seiten der Hauptdiagonale in der Anordnung reduzieren. Sie können auch Levenshtein Automata viele Worte gegen bewerten ein einziges Grundwort in O (n) Zeit -. und der Aufbau der Automaten können in O (m) Zeit auch getan werden

Answer 3

Schauen Sie in Wiki - sie haben einige Ideen, diesen Algorithmus zu einer besseren Speicherkomplexität zu verbessern:

Wiki-Link-: Levenshtein Abstand

Zitiert:

  

Wir können den Algorithmus anpassen weniger Raum zu verwenden, O (m) anstelle von O (mn), da es erfordert nur, dass die vorhergehende Zeile und aktuelle Zeile zu einem bestimmten Zeitpunkt gespeichert werden.

Answer 4

fand ich eine weitere Optimierung, die Ansprüche O sein (max (m, n)):

http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/ Levenshtein_distance # C

(die zweite C-Implementierung)