Levenshtein Distanzalgorithmus besser als O (n * m)?

Question

Ich habe nach einem fortgeschrittenen Levenshtein-Distanzalgorithmus gesucht, und the best I have found so far ist O (n * m), wobei n und m die Längen der beiden Strings sind. 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 Was ist besser als O (n * m)? Ich bin nicht abgeneigt, auf fortgeschrittene Informatikpapiere & Forschung zu schauen, aber war nicht in der Lage, etwas zu finden. Ich habe eine Firma gefunden, Exorbyte, die angeblich einen super-fortgeschrittenen und superschnellen Levenshtein-Algorithmus entwickelt hat, aber das ist natürlich ein Geschäftsgeheimnis. Ich baue eine iPhone App, die Levenshtein Entfernungsberechnung verwenden möchte. There is an objective-c implementation available, aber mit der begrenzten Menge an Speicher auf iPods und iPhones, würde ich gerne einen besseren Algorithmus finden, wenn möglich.

Answer 1

Sind Sie daran interessiert, die Zeitkomplexität oder die Platzkomplexität zu reduzieren? Die durchschnittliche Zeitkomplexität kann reduziert werden O (n + d^2), wobei n die Länge der längeren Zeichenfolge und d die Editierdistanz ist. Wenn Sie nur an der Editierdistanz interessiert sind und nicht daran interessiert sind, die Editiersequenz zu rekonstruieren, müssen Sie nur die letzten zwei Zeilen der Matrix im Speicher behalten, so dass dies die Reihenfolge (n) ist.

Wenn Sie es sich leisten können, zu approximieren, gibt es polylogarithmische Annäherungen.

Für den O (n + d^2) -Algorithmus suchen Sie nach Ukkonen-Optimierung oder seine Verbesserung Enhanced Ukkonen. Die beste Approximation, die ich kenne, ist die von Andoni, Krauthgamer, Onak

Answer 2

Blick in Wiki - sie haben einige Ideen, diesen Algorithmus zu einer besseren Platzkomplexität zu verbessern:

Wiki-Link: Levenshtein distance

Zitiert:

Wir haben den Algorithmus anpassen können weniger Raum nutzen, O (m) anstelle von O (mn), da nur die vorherige Zeile und die aktuelle Zeile gleichzeitig gespeichert werden müssen.

Answer 3

Wenn Sie nur die Schwellenwertfunktion möchten - zB um zu testen, ob der Abstand unter einem bestimmten Schwellenwert liegt - können Sie die Komplexität von Zeit und Raum reduzieren, indem Sie nur das n berechnen Werte auf beiden Seiten der Hauptdiagonalen im Array. Sie können auch Levenshtein Automata verwenden, um viele Wörter gegen ein einzelnes Basiswort in O (n) Zeit auszuwerten - und die Konstruktion der Automaten kann auch in O (m) Zeit erfolgen.

Answer 4

fand ich eine weitere Optimierung, die O (max (m, n)) behauptet zu sein: für die Platzkomplexität

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

(die zweite C-Implementierung)