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:Algorithme de distance de Levenshtein meilleur que O (n * m)?
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.
Je l'utilise pour l'alignement de l'ADN; Nous vérifions d'abord la longueur des séquences car la logique de mise à jour de la barrière d'Ukkonen est plus lourde que le simple calcul de l'ensemble du tableau. Jetez également un coup d'œil à "Time Warps, String Edits, et Macromolecules: The Theory and Practice of Sequence Comparison" pour plus de détails. – nlucaroni
Le document original pour l'algorithme Ukkonen Approximate String Matching Algorithm est, http://www.cs.helsinki.fi/u/ukkonen/InfCont85.PDF. – nlucaroni
En fait, vous n'avez pas besoin des deux dernières lignes de la matrice. La dernière rangée, plus le nombre précédent dans la rangée actuelle, est suffisante. Notez également que l'implémentation de Levenshtein de cette manière est nettement plus rapide que l'utilisation de la matrice complète, probablement en raison de la mise en cache du processeur. – larsga