DAA - Subsecuencia común más larga

El problema de subsecuencia común más largo es encontrar la secuencia más larga que existe en ambas cadenas dadas.

Subsiguiente

Consideremos una secuencia S = <s 1 , s 2 , s 3 , s 4 ,…, s n >.

Una secuencia Z = <z 1 , z 2 , z 3 , z 4 ,…, z m > sobre S se denomina subsecuencia de S, si y sólo si puede derivarse de la eliminación de S de algunos elementos.

Subsecuencia común

Suponer, X y Yson dos secuencias sobre un conjunto finito de elementos. Podemos decir esoZ es una subsecuencia común de X y Y, Si Z es una subsecuencia de ambos X y Y.

Subsecuencia común más larga

Si se proporciona un conjunto de secuencias, el problema de subsecuencia común más largo es encontrar una subsecuencia común de todas las secuencias que sea de longitud máxima.

El problema de subsecuencia común más extenso es un problema clásico de las ciencias de la computación, la base de los programas de comparación de datos, como el diff-utility, y tiene aplicaciones en bioinformática. También es ampliamente utilizado por los sistemas de control de revisiones, como SVN y Git, para conciliar múltiples cambios realizados en una colección de archivos controlados por revisiones.

Método ingenuo

Dejar X ser una secuencia de longitud m y Y una secuencia de longitud n. Verifique cada subsecuencia deX si es una subsecuencia de Yy devuelve la subsecuencia común más larga encontrada.

Existen 2m subsecuencias de X. Probar secuencias, sea o no una subsecuencia deY toma O(n)hora. Por lo tanto, el algoritmo ingenuo tomaríaO(n2m) hora.

Programación dinámica

Sean X = <x 1 , x 2 , x 3 ,…, x m > e Y = <y 1 , y 2 , y 3 ,…, y n > las secuencias. Para calcular la longitud de un elemento se utiliza el siguiente algoritmo.

En este procedimiento, la tabla C[m, n] se calcula en orden de fila principal y otra tabla B[m,n] se calcula para construir la solución óptima.

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X) 
n := length(Y) 
for i = 1 to m do 
   C[i, 0] := 0 
for j = 1 to n do 
   C[0, j] := 0 
for i = 1 to m do 
   for j = 1 to n do 
      if xi = yj 
         C[i, j] := C[i - 1, j - 1] + 1 
         B[i, j] := ‘D’ 
      else 
         if C[i -1, j] ≥ C[i, j -1] 
            C[i, j] := C[i - 1, j] + 1 
            B[i, j] := ‘U’ 
         else 
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’ 
return C and B
Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0 
   return  
if B[i, j] = ‘D’ 
   Print-LCS(B, X, i-1, j-1) 
   Print(xi) 
else if B[i, j] = ‘U’ 
   Print-LCS(B, X, i-1, j) 
else 
   Print-LCS(B, X, i, j-1)

Este algoritmo imprimirá la subsecuencia común más larga de X y Y.

Análisis

Para poblar la mesa, el exterior for bucle itera m tiempos y el interior for bucle itera nveces. Por tanto, la complejidad del algoritmo es O (m, n) , dondem y n son la longitud de dos cuerdas.

Ejemplo

En este ejemplo, tenemos dos cadenas X = BACDB y Y = BDCB para encontrar la subsecuencia común más larga.

Siguiendo el algoritmo LCS-Length-Table-Formulation (como se indicó anteriormente), hemos calculado la tabla C (que se muestra en el lado izquierdo) y la tabla B (que se muestra en el lado derecho).

En la tabla B, en lugar de 'D', 'L' y 'U', estamos usando la flecha diagonal, la flecha hacia la izquierda y la flecha hacia arriba, respectivamente. Después de generar la tabla B, el LCS se determina mediante la función LCS-Print. El resultado es BCB.