Subsecuencia común más larga

El prefijo S _n de S se define como los primeros n caracteres de S. ^{[ 5} ] Por ejemplo, los prefijos de S = ⁽ AGCA) son

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Sea LCS ( X , Y ) una función que calcula la subsecuencia más larga común a X e Y . Dicha función tiene dos propiedades interesantes.

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A , para todas las cadenas X , Y y todos los símbolos A , donde ^ denota la concatenación de cadenas. Esto permite simplificar el cálculo de LCS para dos secuencias que terminan en el mismo símbolo. Por ejemplo, LCS ("BANANA","ATANA") = LCS ("BANAN","ATAN")^"A", Continuando para los símbolos comunes restantes, LCS ("BANANA","ATANA") = LCS ("BAN","AT")^"ANA".

Si A y B son símbolos distintos ( A ≠ B ), entonces LCS (X^A,Y^B) es una de las cadenas de longitud máxima en el conjunto { LCS ( X ^ A , Y ), LCS ( X , Y ^ B ) }, para todas las cadenas X , Y .

Por ejemplo, LCS ("ABCDEFG","BCDGK") es la cadena más larga entre LCS ("ABCDEFG","BCDG") y LCS ("ABCDEF","BCDGK"); si ambas tuvieran la misma longitud, se podría elegir una de ellas arbitrariamente.

Para realizar la propiedad, distinguimos dos casos:

• Si LCS ("ABCDEFG","BCDGK") termina con una "G", entonces la "K" final no puede estar en LCS, por lo tanto LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEFG","BCDG").
• Si LCS ("ABCDEFG","BCDGK") no termina con una "G", entonces la "G" final no puede estar en LCS, por lo tanto LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEF","BCDGK").

Sean dos secuencias definidas de la siguiente manera: ${\displaystyle X=(x_{1}x_{2}\cdots x_{m})}$y${\ Displaystyle Y = (y_ {1} y_ {2} \ cdots y_ {n})}$. Los prefijos de${\displaystyle X}$son${\displaystyle X_{0},X_{1},X_{2},\dots ,X_{m}}$; los prefijos de${\displaystyle Y}$son${\displaystyle Y_{0},Y_{1},Y_{2},\dots,Y_{n}}$. Dejar${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})}$representan el conjunto de la subsecuencia común más larga de prefijos${\displaystyle X_{i}}$y${\displaystyle Y_{j}}$Este conjunto de secuencias viene dado por lo siguiente.

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\epsilon &{\mbox{si }}i=0{\mbox{ o }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{si }}i,j>0{\mbox{ y }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{si }}i,j>0{\mbox{ y }}x_{i}\neq y_{j}.\end{cases}}}$

Para encontrar el LCS de${\displaystyle X_{i}}$y${\displaystyle Y_{j}}$, comparar${\displaystyle x_{i}}$y${\displaystyle y_{j}}$. Si son iguales, entonces la secuencia${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j-1})}$se extiende mediante ese elemento,${\displaystyle x_{i}}$. Si no son iguales, entonces la más larga entre las dos secuencias,${\displaystyle {\mathit {LCS}}(X_{i},Y_{j-1})}$, y${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j})}$, se conserva. (Si tienen la misma longitud, pero no son idénticas, entonces se conservan ambas). El caso base, cuando cualquiera${\displaystyle X_{i}}$o${\displaystyle Y_{i}}$está vacío, es la cadena vacía ,${\displaystyle \epsilon }$.

Se encontrará la subsecuencia más larga común a R = (GAC) y C = (AGCAT). Dado que la función LCS utiliza un elemento "cero", es conveniente definir prefijos cero que estén vacíos para estas secuencias: R ₀ = ε; y C ₀ = ε. Todos los prefijos se colocan en una tabla con C en la primera fila (convirtiéndola en encabezado de columna ) y R en la primera columna (convirtiéndola en encabezado de fila ).

Esta tabla se utiliza para almacenar la secuencia LCS para cada paso del cálculo. La segunda columna y la segunda fila se han rellenado con ε, ya que cuando se compara una secuencia vacía con una no vacía, la subsecuencia común más larga siempre es una secuencia vacía.

LCS ( R ₁ , C ₁ ) se determina comparando los primeros elementos de cada secuencia. G y A no son iguales, por lo que este LCS obtiene (usando la "segunda propiedad") la más larga de las dos secuencias, LCS ( R ₁ , C ₀ ) y LCS ( R ₀ , C ₁ ). Según la tabla, ambas están vacías, por lo que LCS ( R ₁ , C ₁ ) también está vacía, como se muestra en la tabla siguiente. Las flechas indican que la secuencia proviene tanto de la celda superior, LCS ( R ₀ , C ₁ ) como de la celda de la izquierda, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) se determina comparando G y G. Coinciden, por lo que G se agrega a la secuencia superior izquierda, LCS ( R ₀ , C ₁ ), que es (ε), dando (εG), que es (G).

Para LCS ( R1 _, C3 ₎ , G y C no coinciden. La secuencia anterior está vacía; la de la izquierda contiene un elemento, G. Seleccionando la más larga de estas, LCS ( R1 _, C3 ) es (G). La flecha apunta hacia la izquierda, ya que es la más larga de las dos _secuencias .

LCS ( R ₁ , C ₄ ), asimismo, es (G).

LCS ( R ₁ , C ₅ ), asimismo, es (G).

Para LCS ( R ₂ , C ₁ ), A se compara con A. Los dos elementos coinciden, por lo que A se agrega a ε, dando como resultado (A).

Para LCS ( R ₂ , C ₂ ), A y G no coinciden, por lo que se utiliza la más larga de LCS ( R ₁ , C ₂ ), que es (G), y LCS ( R ₂ , C ₁ ), que es (A). En este caso, cada una contiene un elemento, por lo que a esta LCS se le dan dos subsecuencias: (A) y (G).

Para LCS ( R ₂ , C ₃ ), A no coincide con C. LCS ( R ₂ , C ₂ ) contiene las secuencias (A) y (G); LCS ( R ₁ , C ₃ ) es (G), que ya está contenida en LCS ( R ₂ , C ₂ ). El resultado es que LCS ( R ₂ , C ₃ ) también contiene las dos subsecuencias, (A) y (G).

Para LCS ( R ₂ , C ₄ ), A coincide con A, que se agrega a la celda superior izquierda, dando como resultado (GA).

Para LCS ( R ₂ , C ₅ ), A no coincide con T. Comparando las dos secuencias, (GA) y (G), la más larga es (GA), por lo que LCS ( R ₂ , C ₅ ) es (GA).

Para LCS ( R ₃ , C ₁ ), C y A no coinciden, por lo que LCS ( R ₃ , C ₁ ) obtiene la más larga de las dos secuencias, (A).

Para LCS ( R ₃ , C ₂ ), C y G no coinciden. Tanto LCS ( R ₃ , C ₁ ) como LCS ( R ₂ , C ₂ ) tienen un elemento. El resultado es que LCS ( R ₃ , C ₂ ) contiene las dos subsecuencias, (A) y (G).

Para LCS ( R ₃ , C ₃ ), C y C coinciden, por lo que C se agrega a LCS ( R ₂ , C ₂ ), que contiene las dos subsecuencias, (A) y (G), dando como resultado (AC) y (GC).

Para LCS ( R ₃ , C ₄ ), C y A no coinciden. La combinación de LCS ( R ₃ , C ₃ ), que contiene (AC) y (GC), y LCS ( R ₂ , C ₄ ), que contiene (GA), da un total de tres secuencias: (AC), (GC) y (GA).

Finalmente, para LCS ( R ₃ , C ₅ ), C y T no coinciden. El resultado es que LCS ( R ₃ , C ₅ ) también contiene las tres secuencias, (AC), (GC) y (GA).

El resultado final es que la última celda contiene todas las subsecuencias más largas comunes a (AGCAT) y (GAC); estas son (AC), (GC) y (GA). La tabla también muestra las subsecuencias comunes más largas para cada par posible de prefijos. Por ejemplo, para (AGC) y (GA), las subsecuencias comunes más largas son (A) y (G).

Para calcular la subsecuencia común más larga (LCS) de una fila de la tabla LCS, solo se necesitan las soluciones de la fila actual y la anterior. Sin embargo, para secuencias largas, estas pueden ser numerosas y extensas, lo que requiere mucho espacio de almacenamiento. Se puede ahorrar espacio de almacenamiento guardando no las subsecuencias en sí, sino su longitud y la dirección de las flechas, como se muestra en la tabla siguiente.

Las subsecuencias reales se deducen mediante un procedimiento de "retroceso" que sigue las flechas hacia atrás, comenzando desde la última celda de la tabla. Cuando la longitud disminuye, las secuencias deben haber tenido un elemento común. Son posibles varias rutas cuando se muestran dos flechas en una celda. A continuación se muestra la tabla para dicho análisis, con números coloreados en las celdas donde la longitud está a punto de disminuir. Los números en negrita trazan la secuencia (GA). ^{[ 6 ]}

La siguiente función toma como entrada las secuencias X[1..m]y Y[1..n], calcula la LCS entre X[1..i]y Y[1..j]para todos 1 ≤ i ≤ my 1 ≤ j ≤ n, y la almacena en C[i,j]. C[m,n]contendrá la longitud de la LCS de Xy Y. ^{[ 7 ]}

función LCSLength(X[1..m], Y[1..n]) C = array(0..m, 0..n) para i := 0..m C[i,0] = 0 para j := 0..n C[0,j] = 0 para i := 1..m para j := 1..n si X[i] = Y[j] C[i,j] := C[i-1,j-1] + 1 demás C[i,j] := max(C[i,j-1], C[i-1,j]) devolver C[m,n]

Como alternativa, se podría utilizar la memorización .

La siguiente función retrocede las elecciones tomadas al calcular la Ctabla. Si los últimos caracteres de los prefijos son iguales, deben estar en un LCS. Si no, comprueba qué dio el LCS más grande de mantener${\displaystyle x_{i}}$y${\displaystyle y_{j}}$y toma la misma decisión. Simplemente elige uno si tienen la misma longitud. Llama a la función con i=my j=n.

función backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i = 0 o j = 0 devolver "" si X[i] = Y[j] devolver backtrack(C, X, Y, i-1, j-1) + X[i] si C[i,j-1] > C[i-1,j] devolver backtrack(C, X, Y, i, j-1) devolver backtrack(C, X, Y, i-1, j)

Si elige${\displaystyle x_{i}}$y${\displaystyle y_{j}}$Esto daría un resultado de igual longitud; lea ambas subsecuencias resultantes. Esta función devuelve este resultado como un conjunto. Tenga en cuenta que esta función no es polinómica, ya que podría bifurcarse en casi cada paso si las cadenas son similares.

función backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i = 0 o j = 0 devolver {""} si X[i] = Y[j] devolver {Z + X[i] para todo Z en backtrackAll(C, X, Y, i-1, j-1)} R := {} si C[i,j-1] ≥ C[i-1,j] R := backtrackAll(C, X, Y, i, j-1) si C[i-1,j] ≥ C[i,j-1] R := R ∪ backtrackAll(C, X, Y, i-1, j) devolver R

Esta función retrocederá a través de la matriz C e imprimirá la diferencia entre las dos secuencias. Tenga en cuenta que obtendrá una respuesta diferente si intercambia ≥y <, con >y ≤a continuación.

función printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j) si i >= 0 y j >= 0 y X[i] = Y[j] printDiff(C, X, Y, i-1, j-1) imprimir " " + X[i] de lo contrario, si j > 0 y (i = 0 o C[i,j-1] ≥ C[i-1,j]) printDiff(C, X, Y, i, j-1) imprimir "+ " + Y[j] de lo contrario, si i > 0 y (j = 0 o C[i,j-1] < C[i-1,j]) printDiff(C, X, Y, i-1, j) imprimir "- " + X[i] de lo contrario imprime ""

Dejar${\displaystyle X}$ser " XMJYAUZ" y${\displaystyle Y}$ser " MZJAWXU". La subsecuencia común más larga entre${\displaystyle X}$y${\displaystyle Y}$es " MJAU". La tabla Cque se muestra a continuación, que es generada por la función LCSLength, muestra las longitudes de las subsecuencias comunes más largas entre prefijos de${\displaystyle X}$y${\displaystyle Y}$. El${\displaystyle i}$fila y${\displaystyle j}$La columna muestra la longitud del LCS entre${\displaystyle X_{1..i}}$y${\displaystyle Y_{1..j}}$.

Los números resaltados muestran la ruta backtrackque seguiría la función desde la esquina inferior derecha hasta la esquina superior izquierda al leer un LCS. Si los símbolos actuales en${\displaystyle X}$y${\displaystyle Y}$son iguales, son parte del LCS, y vamos hacia arriba y hacia la izquierda (mostrado en negrita ). Si no, vamos hacia arriba o hacia la izquierda, dependiendo de qué celda tenga un número mayor. Esto corresponde a tomar el LCS entre${\displaystyle X_{1..i-1}}$y${\displaystyle Y_{1..j}}$, o${\displaystyle X_{1..i}}$y${\displaystyle Y_{1..j-1}}$.

La matriz C en el algoritmo ingenuo crece cuadráticamente con la longitud de las secuencias. Para dos secuencias de 100 elementos, se necesitaría una matriz de 10 000 elementos y se requerirían 10 000 comparaciones. En la mayoría de los casos reales, especialmente en las comparaciones y parches de código fuente, los inicios y finales de los archivos rara vez cambian, y casi con seguridad no ambos a la vez. Si solo han cambiado unos pocos elementos en medio de la secuencia, se pueden eliminar el inicio y el final. Esto reduce no solo los requisitos de memoria para la matriz, sino también la cantidad de comparaciones necesarias.

función LCS(X[1..m], Y[1..n]) inicio := 1 m_fin := m n_fin := n recortar los elementos coincidentes al principio mientras inicio ≤ m_fin y inicio ≤ n_fin y X[inicio] = Y[inicio] inicio := inicio + 1 recortar los elementos coincidentes al final mientras inicio ≤ m_fin y inicio ≤ n_fin y X[m_fin] = Y[n_fin] m_end := m_end - 1 n_fin := n_fin - 1 C = array(inicio-1..m_fin, inicio-1..n_fin) Solo se itera sobre los elementos que han cambiado: para i := inicio..m_fin y para j := inicio..n_fin, el algoritmo continúa como antes...

En el mejor de los casos, una secuencia sin cambios, esta optimización eliminaría la necesidad de la matriz C. En el peor de los casos, un cambio en el primer y último elemento de la secuencia, solo se realizan dos comparaciones adicionales.

La mayor parte del tiempo que tarda el algoritmo ingenuo se emplea en realizar comparaciones entre los elementos de las secuencias. Para secuencias de texto, como el código fuente, conviene considerar las líneas como elementos de la secuencia en lugar de caracteres individuales. Esto puede implicar comparaciones de cadenas relativamente largas en cada paso del algoritmo. Se pueden realizar dos optimizaciones que ayudan a reducir el tiempo que consumen estas comparaciones.

Se puede utilizar una función hash o una suma de verificación para reducir el tamaño de las cadenas en las secuencias. Es decir, para el código fuente donde la línea promedio tiene 60 caracteres o más, el hash o la suma de verificación para esa línea podría tener solo entre 8 y 40 caracteres. Además, la naturaleza aleatoria de los hashes y las sumas de verificación garantizaría que las comparaciones se realicen más rápidamente, ya que las líneas de código fuente rara vez se modifican al principio.

Esta optimización presenta tres inconvenientes principales. En primer lugar, requiere tiempo para precalcular los hashes de las dos secuencias. En segundo lugar, se necesita memoria adicional para las nuevas secuencias hash. Sin embargo, en comparación con el algoritmo ingenuo utilizado, ambos inconvenientes son relativamente mínimos.

El tercer inconveniente son las colisiones . Dado que no se garantiza la unicidad de la suma de verificación o el hash, existe una pequeña probabilidad de que dos elementos diferentes se reduzcan al mismo hash. Si bien esto es improbable en el código fuente, es posible. Por lo tanto, un hash criptográfico sería mucho más adecuado para esta optimización, ya que su entropía será significativamente mayor que la de una simple suma de verificación. Sin embargo, los beneficios podrían no compensar los requisitos de configuración y computación de un hash criptográfico para secuencias cortas.

Si solo se requiere la longitud del LCS, la matriz se puede reducir a una${\displaystyle 2\times \min(n,m)}$matriz, o a una${\displaystyle \min(m,n)+1}$El vector, como enfoque de programación dinámica, solo requiere las columnas actual y anterior de la matriz. El algoritmo de Hirschberg permite la construcción de la secuencia óptima en los mismos límites de tiempo cuadrático y espacio lineal. ^{[ 8 ]}

Chowdhury y Ramachandran idearon un algoritmo de tiempo cuadrático y espacio lineal ^{[ 9 ] [ 10 ]} para encontrar la longitud de LCS junto con una secuencia óptima que se ejecuta más rápido que el algoritmo de Hirschberg en la práctica debido a su rendimiento de caché superior. ^{[ 9 ]} El algoritmo tiene una complejidad de caché asintóticamente óptima bajo el modelo de caché ideal . ^{[ 11 ]} Curiosamente, el algoritmo en sí es ajeno a la caché ^{[ 11 ]} lo que significa que no toma ninguna decisión basada en los parámetros de caché (por ejemplo, tamaño de caché y tamaño de línea de caché) de la máquina.

Existen varios algoritmos que se ejecutan más rápido que el enfoque de programación dinámica presentado. Uno de ellos es el algoritmo de Hunt-Szymanski , que normalmente se ejecuta en${\displaystyle O((n+r)\log(n))}$tiempo (para${\displaystyle n>m}$), dónde${\displaystyle r}$es el número de coincidencias entre las dos secuencias. ^{[ 12 ]} Para problemas con un tamaño de alfabeto limitado, el Método de los Cuatro Rusos puede utilizarse para reducir el tiempo de ejecución del algoritmo de programación dinámica en un factor logarítmico. ^{[ 13 ]}