Algorithme de distance de Levenshtein meilleur que O (n * m)?

Question

Je cherchais un algorithme de distance levenshtein avancé, et the best I have found so far est O (n * m) où n et m sont les longueurs des deux chaînes. La raison pour laquelle l'algorithme est à cette échelle est en raison de l'espace, pas le temps, avec la création d'une matrice des deux chaînes comme celle-ci:

Y at-il un algorithme levenshtein accessible au public qui est meilleur que O (n * m)? Je ne suis pas opposé à regarder des documents de pointe en informatique & recherche, mais n'ont pas été en mesure de trouver quoi que ce soit. J'ai trouvé une société, Exorbyte, qui a supposément construit un algorithme Levenshtein super-avancé et super-rapide, mais bien sûr, c'est un secret commercial. Je construis une application iPhone dont j'aimerais utiliser le calcul de distance Levenshtein. There is an objective-c implementation available, mais avec la quantité limitée de mémoire sur les iPods et les iPhones, je voudrais trouver un meilleur algorithme si possible.

Answer 1

Êtes-vous intéressé par la réduction de la complexité temporelle ou de la complexité de l'espace? La complexité temporelle moyenne peut être réduite O (n + d^2), où n est la longueur de la chaîne la plus longue et d la distance d'édition. Si vous êtes uniquement intéressé par la distance d'édition et que vous n'êtes pas intéressé par la reconstruction de la séquence d'édition, il vous suffit de garder en mémoire les deux dernières lignes de la matrice, donc ce sera order (n).

Si vous pouvez vous permettre d'approximer, il existe des approximations poly-logarithmiques. Pour l'algorithme O (n + d^2), recherchez l'optimisation ou l'amélioration de Ukkonen Enhanced Ukkonen. La meilleure approximation que je connaisse est celle-ci par Andoni, Krauthgamer, Onak

Answer 2

Rechercher dans Wiki - ils ont des idées pour améliorer cet algorithme pour mieux la complexité de l'espace:

Wiki-Link: Levenshtein distance

cite:

Nous pouvons adapter l'algorithme à utiliser moins d'espace, O (m) au lieu de O (mn), car il nécessite seulement que la ligne précédente et la ligne courante soient stockées à un moment donné.

Answer 3

Si vous voulez seulement la fonction de seuil - par exemple, pour tester si la distance est inférieure à un certain seuil - vous pouvez réduire la complexité de temps et d'espace en calculant seulement le n Valeurs de chaque côté de la diagonale principale dans le tableau. Vous pouvez également utiliser Levenshtein Automata pour évaluer plusieurs mots par rapport à un seul mot de base en temps O (n) - et la construction des automates peut également être effectuée en temps O (m).

Answer 4

je trouve une autre optimisation qui prétend être O (max (m, n)):

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

(la deuxième mise en œuvre de C)