Subseqüência comum mais longa

Question

Considere 2 seqüências x [1..m] e y [1..n]. O algoritmo de memorização calcularia o LCS no tempo O (m*n). Existe algum algoritmo melhor para descobrir o tempo do LCS? Eu acho que a memórias feita na diagonal pode nos dar complexidade do tempo (min (m, n)).

Answer 1

Gene Myers em 1986 criou um algoritmo muito bom para isso, descrito aqui: Um algoritmo de diferença O (ND) e suas variações.

Esse algoritmo leva tempo proporcional à distância de edição entre as sequências, por isso é muito mais rápido quando a diferença é pequena. Funciona loop sobre todas as distâncias de edição possíveis, a partir de 0, até encontrar uma distância para a qual um script de edição (de certa forma o dual de um LCS) pode ser construído. Isso significa que você pode "resgatar cedo" se a diferença crescer acima de algum limite, o que às vezes é conveniente.

Eu acredito que esse algoritmo ainda é usado em muitos diff implementações.

Answer 2

Se você conhece a priori um limite superior no tamanho máximo k Você se importa, você pode forçar o algoritmo LCS a sair mais cedo, adicionando uma verificação extra no loop interno. Isso significa então quando k << min (m, n) Você pode obter pequenos tempos de execução, apesar do fato de estar fazendo LCS.

Answer 3

Sim, poderíamos criar um algoritmo melhor do que a ordem O (m*n) --- ie o (min (m, n)). Para encontrar um comprimento ..... basta comparar os elementos diagonais. E sempre que o incremento é feito, suponha que ocorra em C [2,2], aumente todo o valor de C [2,2 ++] e C [2+ +, 2] por 1 .. e prossiga até C [M, M] .. (suponha M