Más larga subsecuencia común

Question

Considere 2 secuencias X [1..m] e Y [1..n]. El algoritmo memoization sería calcular los LCS en tiempo O (m * n). ¿Hay algo mejor algoritmo para averiguar el tiempo LCS WRT? Supongo memoization hecho en diagonal puede darnos O (min (m, n)) Tiempo de complejidad.

Answer 1

Gen Myers en 1986 llegó con un muy buen algoritmo para esto, se describe aquí: Un O (ND) Diferencia Algoritmo y sus variaciones .

Este algoritmo toma un tiempo proporcional a la distancia de edición entre secuencias, por lo que es mucho más rápido cuando la diferencia es pequeña. Funciona mediante el bucle sobre todas las posibles distancias de edición, empezando desde 0, hasta que encuentra una distancia para la que una secuencia de comandos de edición (en cierto modo el dual de un LCS) se puede construir. Esto significa que se puede "rescatar a los principios de" si la diferencia crece por encima de cierto umbral, que a veces es conveniente.

Creo que este algoritmo se sigue utilizando en muchas implementaciones diff.

Answer 2

Si conoce a priori un límite superior en el tamaño máximo de k te importan, puede forzar el algoritmo LCS a la temprana mediante la adición de una comprobación adicional en el bucle interno. Este medio después, cuando k << min (m, n) puede obtener pequeños tiempos de funcionamiento a pesar del hecho de que está haciendo LCS.

Answer 3

sí que podría crear un mejor algoritmo de orden O (m * n) --- es decir O (min (m, n)). para encontrar una longitud ..... Basta con comparar el elements.and diagonal siempre que el incremento se realiza supongamos que se produjo en c [2,2] entonces Incremento todo el valor de c [2,2 ++] y c [2 ++, 2] por 1 .. y proceder hasta c [m, m] .. (supongamos m