Longest Common Subsequence

Question

Considérons 2 séquences X [1..m] et Y [1..n]. L'algorithme de memoization calculerait le LCS en temps O (m * n). Y at-il un meilleur algorithme pour trouver le temps LCS wrt? Je suppose que memoization fait en diagonale peut nous donner O (min (m, n)) la complexité du temps.

Answer 1

Gene Myers en 1986 est venu avec un algorithme très agréable pour cela, comme décrit ici: Une différence O (ND) Algorithme et ses variations .

Cet algorithme prend un temps proportionnel à la distance d'édition entre les séquences, il est donc beaucoup plus rapide lorsque la différence est faible. Il fonctionne en boucle sur toutes les distances d'édition possibles, à partir de 0, jusqu'à ce qu'il trouve une distance pour laquelle un script d'édition (en quelque sorte le double d'un LCS) peut être construit. Cela signifie que vous pouvez « renflouer tôt » si la différence croît au-dessus d'un certain seuil, ce qui est parfois commode.

Je crois que cet algorithme est encore utilisé dans de nombreuses implémentations diff.

Answer 2

Si vous connaissez a priori une limite supérieure de la taille maximale k que vous aimez, vous pouvez forcer l'algorithme de LCS pour quitter tôt en ajoutant un contrôle supplémentaire dans la boucle intérieure. Cela signifie alors quand k << min (m, n) vous pouvez obtenir de petits temps de course malgré le fait que vous faites LCS.

Answer 3

Oui, nous pourrions créer un meilleur algorithme que l'ordre O (m * n) --- i.e. O (min (m, n)). pour trouver une longueur ..... il suffit de comparer la elements.and diagonale à chaque fois que l'incrément est fait supposer qu'il est produit dans c [2,2], puis incrémenter toute la valeur de c [2,2 ++] et c [2 ++, 2] par 1 .. et procéder à c [m, m] .. (m On suppose que