Développement iOS
  1. Développement iOS
  3. Algorithme de distance de Levenshtein mieux que O (n * m)?
Intereting Posts
Est-ce que iOS peut dériver le time de démarrage? Wikipedia dans le cadre de mon application iOS AVSpeechSynthesizer en mode d'arrière-plan Conversion d'UIImage en NSData et NSData en NSSsortingng pour l'envoi d'images à un server SWRevealViewController en poussant FrontVC ne provoque pas d'animation et ne répond pas aux notifications L'ajout d'une sous-vue laisse un espace entre la sous-vue et la barre de navigation Comment puis-je envoyer une application iOS au client pour qu'il code Pass touche à travers un UIViewController App Crash uitextview lorsque les inputs de l'user via la voix Comment utiliser kAudioSessionProperty_OverrideCategoryMixWithOthers iOS 7 et button et bordure Problème sémantique ARC "methods multiples nommées 'setRotation'" lors de l'archivage uniquement Publication à TestFlight, nouveaux testeurs, dois-je vraiment rebuild / download mon profil d'approvisionnement? Téléchargement de l'image de l'application ionique depuis la camera / photothèque Graphiques à barres dans l'application iOS

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

J'ai recherché un algorithm avancé de distance de levenshtein, et le meilleur que j'ai trouvé jusqu'ici est O (n * m) où n et m sont les longueurs des deux cordes. La raison pour laquelle l'algorithm est à cette échelle est à cause de l'espace, pas du time, avec la création d'une masortingce des deux strings comme celle-ci:

texte alt

Existe-t-il un algorithm de levenshtein disponible publiquement qui soit meilleur que O (n * m)? Je ne suis pas opposé à l'idée de searchs et de documents informatiques avancés, mais je n'ai rien trouvé. J'ai trouvé une société, Exorbyte, qui a supposément construit un algorithm 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. Il existe une implémentation objective-c disponible , mais avec la quantité limitée de memory sur les iPods et les iPhones, j'aimerais find un meilleur algorithm si possible.

    Souhaitez-vous réduire la complexité temporelle ou la complexité de l'espace? La complexité temporelle moyenne peut être réduite O (n + d ^ 2), où n est la longueur de la string 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 conserver en memory les deux dernières lignes de la masortingce, donc ce sera order (n).

    Si vous pouvez vous permettre d'approximer, il existe des approximations poly-logarithmiques.

    Pour l'algorithm O (n + d ^ 2), cherchez l'optimization d'Ukkonen ou son amélioration Enhanced Ukkonen . La meilleure approximation que je connaisse est celle d' Andoni, Krauthgamer, Onak

    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é temporelle et spatiale en ne calculant que les n valeurs de chaque côté de la diagonale principale du tableau. Vous pouvez également utiliser Levenshtein Automata pour évaluer plusieurs mots par rapport à un seul mot de base en time O (n) – et la construction des automates peut également être effectuée en time O (m).

    Regardez dans Wiki – ils ont quelques idées pour améliorer cet algorithm pour une meilleure complexité de l'espace:

    Lien Wiki: Levenshtein distance

    Citant:

    Nous pouvons adapter l'algorithm pour utiliser less 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é.

    J'ai trouvé une autre optimization qui prétend être O (max (m, n)):

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

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