algorithm
La subsecuencia común más larga
Buscar..
Explicación de la subsecuencia común más larga
Una de las implementaciones más importantes de la Programación Dinámica es encontrar la Subsecuencia Común Más Larga . Vamos a definir algunas de las terminologías básicas primero.
Subsecuencia
Una subsecuencia es una secuencia que puede derivarse de otra secuencia al eliminar algunos elementos sin cambiar el orden de los elementos restantes. Digamos que tenemos una cadena ABC . Si borramos cero o uno o más de un carácter de esta cadena obtenemos la subsecuencia de esta cadena. Así que las subsecuencias de la cadena ABC serán { "A" , "B" , "C" , "AB" , "AC" , "BC" , "ABC" , "" }. Incluso si eliminamos todos los caracteres, la cadena vacía también será una subsecuencia. Para averiguar la subsecuencia, para cada carácter de una cadena, tenemos dos opciones: o tomamos el carácter o no. Entonces, si la longitud de la cadena es n , hay 2 n subsecuencias de esa cadena.
Subsecuencia más larga:
Como el nombre sugiere, de todas las subsecuencias comunes entre dos cadenas, la subsecuencia común más larga (LCS) es la que tiene la longitud máxima. Por ejemplo: las subsecuencias comunes entre "HELLOM" y "HMLD" son "H" , "HL" , "HM", etc. Aquí "HLL" es la subsecuencia común más larga que tiene la longitud 3.
Método de fuerza bruta:
Podemos generar todas las subsecuencias de dos cadenas usando backtracking . Luego podemos compararlos para descubrir las subsecuencias comunes. Después tendremos que averiguar el que tiene la longitud máxima. Ya hemos visto que hay 2 n subsecuencias de una cadena de longitud n . Tomaría años resolver el problema si nuestra n cruza 20-25 .
Método de programación dinámica:
Abordemos nuestro método con un ejemplo. Supongamos que tenemos dos cadenas abcdaf y acbcf . Vamos a denotar estos con s1 y s2 . Por lo tanto, la subsecuencia común más larga de estas dos cadenas será "abcf" , que tiene una longitud 4. De nuevo, les recuerdo que las subsecuencias no tienen que ser continuas en la cadena. Para construir "abcf" , ignoramos "da" en s1 y "c" en s2 . ¿Cómo podemos descubrir esto utilizando la programación dinámica?
Comenzaremos con una tabla (una matriz 2D) que tiene todos los caracteres de s1 en una fila y todos los caracteres de s2 en la columna. Aquí la tabla tiene un índice de 0 y colocamos los caracteres de 1 en adelante. Recorreremos la tabla de izquierda a derecha para cada fila. Nuestra mesa se verá como:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Aquí, cada fila y columna representan la longitud de la subsecuencia común más larga entre dos cadenas si tomamos los caracteres de esa fila y columna y agregamos el prefijo anterior. Por ejemplo: la Tabla [2] [3] representa la longitud de la subsecuencia común más larga entre "ac" y "abc" .
La columna 0 representa la subsecuencia vacía de s1 . De manera similar, la fila 0 representa la subsecuencia vacía de s2 . Si tomamos una subsecuencia vacía de una cadena y tratamos de hacerla coincidir con otra, no importa cuán larga sea la longitud de la segunda subcadena, la subsecuencia común tendrá una longitud de 0. Entonces podemos llenar las filas 0-th y las columnas 0-th con 0's. Obtenemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Vamos a empezar. Cuando llenemos la Tabla [1] [1] , nos preguntamos, si tuviéramos una cadena a y otra cadena a y nada más, ¿cuál será la subsecuencia común más larga aquí? La longitud del LCS aquí será 1. Ahora veamos la Tabla [1] [2] . Tenemos la cadena ab y la cadena a . La longitud del LCS será 1. Como puede ver, el resto de los valores también serán 1 para la primera fila, ya que considera solo la cadena a con abcd , abcda , abcdaf . Así nuestra mesa se verá como:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Para la fila 2, que ahora incluirá c . Para la Tabla [2] [1] tenemos ac en un lado y a en el otro lado. Entonces, la longitud del LCS es 1. ¿De dónde obtuvimos este 1? Desde la parte superior, que denota el LCS a entre dos subcadenas. Entonces, lo que estamos diciendo es que si s1 [2] y s2 [1] no son lo mismo, entonces la longitud del LCS será la máxima de la longitud del LCS en la parte superior o en la izquierda . Tomar la longitud del LCS en la parte superior indica que no tomamos el carácter actual de s2 . De manera similar, tomar la longitud del LCS a la izquierda denota eso, no tomamos el carácter actual de s1 para crear el LCS. Obtenemos:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Así que nuestra primera fórmula será:
if s2[i] is not equal to s1[j]
Table[i][j] = max(Table[i-1][j], Table[i][j-1]
endif
Continuando, para la Tabla [2] [2] tenemos la cadena ab y ac . Como c y b no son iguales, ponemos el máximo de la parte superior o izquierda aquí. En este caso, es nuevamente 1. Después de eso, para la Tabla [2] [3] tenemos la cadena abc y ac . Esta vez los valores actuales de la fila y la columna son los mismos. Ahora la longitud de la LCS será igual a la longitud máxima de la LCS hasta ahora + 1. ¿Cómo obtenemos la longitud máxima de la LCS hasta ahora? Verificamos el valor diagonal, que representa la mejor coincidencia entre ab y a . Desde este estado, para los valores actuales, agregamos un carácter más a s1 y s2 que resultó ser el mismo. Por lo tanto, la duración de la LCS por supuesto aumentará. Pondremos 1 + 1 = 2 en la Tabla [2] [3] . Obtenemos,
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | | | | | | |
+-----+-----+-----+-----+-----+-----+-----+-----+
Así que nuestra segunda fórmula será:
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
endif
Hemos definido ambos casos. Usando estas dos fórmulas, podemos rellenar toda la tabla. Después de llenar la mesa, se verá así:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+-----+
| chʳ | | a | b | c | d | a | f |
+-----+-----+-----+-----+-----+-----+-----+-----+
0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+-----+-----+-----+-----+-----+-----+-----+-----+
1 | a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+-----+-----+-----+-----+-----+-----+-----+-----+
2 | c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
3 | b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
+-----+-----+-----+-----+-----+-----+-----+-----+
4 | c | 0 | 1 | 2 | 3 | 3 | 3 | 3 |
+-----+-----+-----+-----+-----+-----+-----+-----+
5 | f | 0 | 1 | 2 | 3 | 3 | 3 | 4 |
+-----+-----+-----+-----+-----+-----+-----+-----+
La longitud del LCS entre s1 y s2 será la Tabla [5] [6] = 4 . Aquí, 5 y 6 son la longitud de s2 y s1 respectivamente. Nuestro pseudo-código será:
Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
Table[0][i] = 0
endfor
for i from 1 to s2.length
Table[i][0] = 0
endfor
for i from 1 to s2.length
for j from 1 to s1.length
if s2[i] equals to s1[j]
Table[i][j] = Table[i-1][j-1] + 1
else
Table[i][j] = max(Table[i-1][j], Table[i][j-1])
endif
endfor
endfor
Return Table[s2.length][s1.length]
La complejidad del tiempo para este algoritmo es: O (mn) donde m y n denota la longitud de cada cadena.
¿Cómo encontramos la subsecuencia común más larga? Comenzaremos desde la esquina inferior derecha. Comprobaremos de donde viene el valor. Si el valor proviene de la diagonal, es decir, si la Tabla [i-1] [j-1] es igual a la Tabla [i] [j] - 1 , presionamos s2 [i] o s1 [j] (ambos son lo mismo) y se mueven en diagonal. Si el valor viene de arriba, eso significa que si la Tabla [i-1] [j] es igual a la Tabla [i] [j] , nos movemos hacia la parte superior. Si el valor viene de la izquierda, eso significa que si la Tabla [i] [j-1] es igual a la Tabla [i] [j] , nos movemos hacia la izquierda. Cuando llegamos a la columna de la izquierda o de la parte superior, nuestra búsqueda termina. Luego sacamos los valores de la pila y los imprimimos. El pseudocódigo:
Procedure PrintLCS(LCSlength, s1, s2)
temp := LCSlength
S = stack()
i := s2.length
j := s1.length
while i is not equal to 0 and j is not equal to 0
if Table[i-1][j-1] == Table[i][j] - 1 and s1[j]==s2[i]
S.push(s1[j]) //or S.push(s2[i])
i := i - 1
j := j - 1
else if Table[i-1][j] == Table[i][j]
i := i-1
else
j := j-1
endif
endwhile
while S is not empty
print(S.pop)
endwhile
Puntos a destacar: si tanto la Tabla [i-1] [j] como la Tabla [i] [j-1] son iguales a la Tabla [i] [j] y la Tabla [i-1] [j-1] no es igual a la Tabla [i] [j] - 1 , puede haber dos LCS para ese momento. Este pseudocódigo no considera esta situación. Tendrás que resolver esto recursivamente para encontrar múltiples LCS.
La complejidad del tiempo para este algoritmo es: O (máx (m, n)) .