Longest sottosequenza comune

Question

Si consideri 2 sequenze X [1..m] e Y [1..n]. L'algoritmo Memoizzazione sarebbe calcolare le LCS nel tempo O (m * n). Esiste un algoritmo migliore per scoprire il tempo LCS WRT? Credo che Memoizzazione fatto in diagonale può darci O (min (m, n)) complessità.

Answer 1

Gene Myers nel 1986 si avvicinò con un bel algoritmo per questo, descritto qui: Un O (ND) Algoritmo Differenza e le sue variazioni .

Questo algoritmo richiede tempo proporzionale alla distanza di montaggio tra le sequenze, quindi è molto più veloce quando la differenza è piccola. Funziona loop su tutte le possibili modificare le distanze, a partire da 0, finché non trova una distanza per la quale uno script di modifica (per certi versi il duale di un LCS) può essere costruito. Questo significa che si può "tirare fuori dai guai presto" se la differenza cresce sopra una certa soglia, che a volte è conveniente.

Credo che questo algoritmo è ancora usato in molte implementazioni diff.

Answer 2

Se si conosce a priori un limite superiore alla dimensione massima k a cui tieni, è possibile forzare l'algoritmo LCS per uscire presto con l'aggiunta di un controllo supplementare nel ciclo interno. Questo significa poi quando k << min (m, n) è possibile ottenere piccoli tempi di esecuzione, nonostante il fatto che si sta facendo LCS.

Answer 3

sì, abbiamo potuto creare un algoritmo migliore rispetto Order O (m * n) --- cioè O (min (m, n)). per trovare una lunghezza ..... basta confrontare l'elements.and diagonale ogniqualvolta l'incremento avviene supponiamo che si è verificato in c [2,2] quindi incrementare tutto il valore di c [2,2 ++] ec [2 ++, 2] da 1 .. e proseguire fino al c [m, m] .. (supponiamo m