LISTA DE PROBLEMAS

La más larga subsecuencia común ( LCS ) problema es el problema de encontrar la más larga subsecuencia común a todas las secuencias en un conjunto de secuencias (a menudo apenas dos secuencias). Difiere del problema de subcadena más común : a diferencia de las subcadenas, no se requieren subsecuencias para ocupar posiciones consecutivas dentro de las secuencias originales. El problema de subsecuencia común más largo es un problema clásico de ciencias de la computación , la base de programas de comparación de datos como la utilidad diff , y tiene aplicaciones en lingüística computacional y bioinformática . También es ampliamente utilizado porsistemas de control de revisión como Git para conciliar múltiples cambios realizados en una colección de archivos controlada por revisión.

Complejidad [ editar ]

Para el caso general de un número arbitrario de secuencias de entrada, el problema es NP-hard . ^[1] Cuando el número de secuencias es constante, el problema se puede resolver en tiempo polinómico mediante programación dinámica (ver Solución a continuación). Asume que tienes$${\ displaystyle N} secuencias de longitudes $${\ displaystyle n_ {1}, ..., n_ {N}}. Una búsqueda ingenua probaría cada uno de los$${\ displaystyle 2 ^ {n_ {1}}}subsecuencias de la primera secuencia para determinar si también son subsecuencias de las secuencias restantes; cada subsecuencia se puede probar en tiempo lineal en las longitudes de las secuencias restantes, por lo que el tiempo para este algoritmo sería

{\ displaystyle O \ left (2 ^ {n_ {1}} \ sum _ {i> 1} n_ {i} \ right).}

Para el caso de dos secuencias de n y m elementos, el tiempo de funcionamiento del enfoque de programación dinámica es O ( n × m ). ^[2] Para un número arbitrario de secuencias de entrada, el enfoque de programación dinámica da una solución en

$${\ displaystyle O \ left (N \ prod _ {i = 1} ^ {N} n_ {i} \ right).}

Existen métodos con menor complejidad, ^[3] que a menudo dependen de la longitud del LCS, el tamaño del alfabeto o ambos.

Tenga en cuenta que el LCS no es necesariamente único; por ejemplo, el LCS de "ABC" y "ACB" es "AB" y "AC". De hecho, el problema de LCS a menudo se define como encontrar todas las subsecuencias comunes de una longitud máxima. Este problema tiene inherentemente una mayor complejidad, ya que el número de tales subsecuencias es exponencial en el peor de los casos, ^[4] incluso para solo dos cadenas de entrada.

Solución para dos secuencias [ editar ]

El problema de LCS tiene una subestructura óptima : el problema se puede dividir en "subproblemas" más pequeños y simples, que se pueden dividir en subproblemas aún más simples, y así sucesivamente, hasta que, finalmente, la solución se vuelve trivial. El problema de LCS también tiene subproblemas superpuestos : la solución a subproblemas de alto nivel a menudo reutiliza subproblemas de nivel inferior. Los problemas con estas dos propiedades (subestructura óptima y subproblemas superpuestos) pueden abordarse mediante una técnica de resolución de problemas llamada programación dinámica , en la que las soluciones de subproblemas se memorizan en lugar de calcularse una y otra vez. El procedimiento requiere memorización: guardar las soluciones a un nivel de subproblema en una tabla (análogo a escribirlas en una nota, de ahí el nombre) para que las soluciones estén disponibles para el siguiente nivel de subproblemas. Este método se ilustra aquí.

Prefijos [ editar ]

Los subproblemas se vuelven más simples a medida que las secuencias se acortan. Las secuencias más cortas se describen convenientemente usando el término prefijo . Un prefijo de una secuencia es la secuencia con el final cortado. Sea S la secuencia (AGCA). Entonces, la secuencia (AG) es uno de los prefijos de S . Los prefijos se denotan con el nombre de la secuencia, seguido de un subíndice para indicar cuántos caracteres contiene el prefijo. ^[5] El prefijo (AG) se denota S ₂ , ya que contiene los 2 primeros elementos de S . Los posibles prefijos de S son

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

La solución al problema LCS para dos secuencias arbitrarias, X y Y , asciende a la construcción de alguna función, LCS ( X , Y ), que da la más larga subsecuencias común para X y Y . Esa función se basa en las siguientes dos propiedades.

Primera propiedad [ editar ]

Supongamos que dos secuencias terminan en el mismo elemento. Para encontrar su LCS, acorte cada secuencia eliminando el último elemento, encuentre el LCS de las secuencias acortadas, y a ese LCS agregue el elemento eliminado.

Por ejemplo, aquí hay dos secuencias que tienen el mismo último elemento: (BANANA) y (ATANA).

Eliminar el mismo último elemento. Repita el procedimiento hasta que no encuentre un último elemento común. La secuencia eliminada será (ANA).

Las secuencias ahora bajo consideración: (BAN) y (AT)

El LCS de estas dos últimas secuencias es, por inspección, (A).

Agregue el elemento eliminado, (ANA), dando (AANA), que, por inspección, es el LCS de las secuencias originales.

En general, para cualquier secuencia de X y de Y de longitud n y m , si denotamos sus elementos x ₁ a x _n y y ₁ a y _m y sus prefijos X ₁ a X _n-1 y Y ₁ a Y _m-1 , entonces podemos decir esto:

Si: x _n = y _m

entonces: LCS ( X _n , Y _m ) = LCS ( X _n-1 , Y _m-1 ) ^ x _n

donde caret ^ indica que el siguiente elemento, x _n , se agrega a la secuencia. Tenga en cuenta que el LCS para X _n e Y _m implica determinar el LCS de las secuencias más cortas, X _n-1 e Y _m-1 .

Segunda propiedad [ editar ]

Suponga que las dos secuencias X e Y no terminan en el mismo símbolo. Entonces el LCS de X e Y es la más larga de las dos secuencias LCS (X _n , Y _m-1 ) y LCS (X _n-1 , Y _m ).

Para comprender esta propiedad, considere las dos secuencias siguientes:

secuencia X: ABCDEFG (n elementos)
secuencia Y: BCDGK (m elementos)

El LCS de estas dos secuencias termina con una G (el último elemento de la secuencia X) o no.

Caso 1: la LCS termina con una G
Entonces no puede terminar con una K. Por lo tanto, no está de más eliminar la K de la secuencia Y: si K estuviera en la LCS, sería su último carácter; Como consecuencia, K no está en la LCS. Entonces podemos escribir: LCS (X _n , Y _m ) = LCS (X _n , Y _m-1 ).

Caso 2: el LCS no termina con una G
Entonces no está de más eliminar la G de la secuencia X (por el mismo motivo que el anterior). Y luego podemos escribir: LCS (X _n , Y _m ) = LCS (X _n-1 , Y _m ).

En cualquier caso, el LCS que estamos buscando es uno de LCS (X _n , Y _m-1 ) o LCS (X _n-1 , Y _m ). Esos dos últimos LCS son subsecuencias comunes a X e Y. LCS (X, Y) es el más largo. Por lo tanto, su valor es la secuencia más larga de LCS (X _n , Y _m-1 ) y LCS (X _n-1 , Y _m ).

Función LCS definida [ editar ]

Deje que dos secuencias se definan 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_ {1,2, \ dots, m}}; los prefijos de$${\ displaystyle Y} son $${\ displaystyle Y_ {1,2, \ puntos, n}}. Dejar$${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j})} representa el conjunto de subsecuencias comunes más largas 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} \ emptyset & {\ mbox {if}} i = 0 {\ mbox {or}} j = 0 \\ {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1}) {\ hat {}} x_ {i} y {\ mbox {if}} i, j> 0 {\ mbox {and}} x_ {i} = y_ {j} \\\ operatorname {\ max} \ {{\ mathit {LCS}} (X_ {i}, Y_ {j-1}), {\ mathit {LCS }} (X_ {i-1}, Y_ {j}) \} & {\ mbox {if}} i, j> 0 {\ mbox {y}} x_ {i} \ neq y_ {j}. \ End {casos}}}

Para encontrar las subsecuencias más largas comunes a $${\ displaystyle X_ {i}} y $${\ displaystyle Y_ {j}}, compara los elementos $${\ displaystyle x_ {i}} y $${\ displaystyle y_ {j}}. Si son iguales, entonces la secuencia$${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1})} se extiende por ese elemento, $${\ displaystyle x_ {i}}. Si no son iguales, entonces la más larga de las dos secuencias,$${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j-1})}y $${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j})}, Es retenido. (Si ambos tienen la misma longitud, pero no son idénticos, ambos se conservan). Observe que los subíndices se reducen en 1 en estas fórmulas. Eso puede resultar en un subíndice de 0. Dado que los elementos de secuencia están definidos para comenzar en 1, fue necesario agregar el requisito de que el LCS está vacío cuando un subíndice es cero.

Ejemplo trabajado [ editar ]

Se encontrará la subsecuencia más larga común a R = (GAC) y C = (AGCAT). Debido a que la función LCS usa 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 mesa con C en la primera fila (lo que es una c OLUMNA cabecera) y R en la primera columna (lo que es una r ow cabecera).

Cuerdas LCS

	Ø	UNA	sol	do	UNA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
sol	Ø
UNA	Ø
do	Ø

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 Ø, porque cuando se compara una secuencia vacía con una secuencia 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 en cada secuencia. G y A no son lo mismo, por lo que este LCS obtiene (utilizando la "segunda propiedad") la más larga de las dos secuencias, LCS ( R ₁ , C ₀ ) y LCS ( R ₀ , C ₁ ). Según la tabla, ambos están vacíos, por lo que LCS ( R ₁ , C ₁ ) también está vacío, como se muestra en la tabla a continuación. Las flechas indican que la secuencia proviene tanto de la celda anterior, LCS ( R₀ , C ₁ ) y 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 ( R ₁ , C ₃ ), G y C no coinciden. La secuencia anterior está vacía; el de la izquierda contiene un elemento, G. Seleccionando el más largo de estos, LCS ( R ₁ , C ₃ ) es (G). La flecha apunta a la izquierda, ya que es la más larga de las dos secuencias.

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

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

Fila "G" completada

	Ø	UNA	sol	do	UNA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
sol	Ø	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}Ø	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)
UNA	Ø
do	Ø

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

Para LCS ( R ₂ , C ₂ ), A y G no coinciden, por lo que el más largo de LCS ( R ₁ , C ₂ ), que es (G), y LCS ( R ₂ , C ₁ ), que es (A ), se utiliza. En este caso, cada uno contiene un elemento, por lo que este LCS tiene 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á contenido 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 (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).

Filas "G" y "A" completadas

	Ø	UNA	sol	do	UNA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
sol	Ø	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}Ø	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)
UNA	Ø	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(UNA)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(A) y (G)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(A) y (G)	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(GEORGIA)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(GEORGIA)
do	Ø

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 (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).

Tabla LCS completada

	Ø	UNA	sol	do	UNA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
sol	Ø	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}Ø	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(SOL)
UNA	Ø	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(UNA)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(A) y (G)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(A) y (G)	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(GEORGIA)	$${\ displaystyle {\ overset {\} {\ leftarrow}}}(GEORGIA)
do	Ø	$${\ displaystyle {\ overset {\ \ uparrow} {\}}}(UNA)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(A) y (G)	$${\ displaystyle {\ overset {\ nwarrow} {\}}}(AC) y (GC)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(AC) y (GC) y (GA)	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}(AC) y (GC) y (GA)

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

Enfoque de rastreo [ editar ]

Calcular el LCS de una fila de la tabla LCS requiere solo las soluciones para la fila actual y la fila anterior. Aún así, para secuencias largas, estas secuencias pueden ser numerosas y largas, lo que requiere mucho espacio de almacenamiento. El espacio de almacenamiento se puede guardar guardando no las subsecuencias reales, sino la longitud de la subsecuencia y la dirección de las flechas, como en la tabla a continuación.

Almacenamiento de longitud, en lugar de secuencias

	Ø	UNA	sol	do	UNA	T
Ø	0 0	0 0	0 0	0 0	0 0	0 0
sol	0 0	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}0 0	$${\ displaystyle {\ overset {\ nwarrow} {\}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1
UNA	0 0	$${\ displaystyle {\ overset {\ nwarrow} {\}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ nwarrow} {\}}}2	$${\ displaystyle {\ overset {\} {\ leftarrow}}}2
do	0 0	$${\ displaystyle {\ overset {\ \ uparrow} {\}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ nwarrow} {\}}}2	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}2	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}2

Las subsecuencias reales se deducen en un procedimiento de "rastreo" 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 varios caminos cuando se muestran dos flechas en una celda. A continuación se muestra la tabla para dicho análisis, con números coloreados en celdas donde la longitud está a punto de disminuir. Los números en negrita trazan la secuencia, (GA). ^[6]

Ejemplo de rastreo

	Ø	UNA	sol	do	UNA	T
Ø	0 0	0 0	0 0	0 0	0 0	0 0
sol	0 0	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}0 0	$${\ displaystyle {\ overset {\ nwarrow} {\}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\} {\ leftarrow}}}1
UNA	0 0	$${\ displaystyle {\ overset {\ nwarrow} {\}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ nwarrow} {\}}}2	$${\ displaystyle {\ overset {\} {\ leftarrow}}}2
do	0 0	$${\ displaystyle {\ overset {\ \ uparrow} {\}}}1	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}1	$${\ displaystyle {\ overset {\ nwarrow} {\}}}2	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}2	$${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}2

Relación con otros problemas [ editar ]

Para dos cuerdas $${\ displaystyle X_ {1 \ puntos m}} y $${\ displaystyle Y_ {1 \ puntos n}}, la longitud de la supersecuencia común más corta está relacionada con la longitud de la LCS en ^[3]

$${\ displaystyle \ left | SCS (X, Y) \ right | = n + m- \ left | LCS (X, Y) \ right |.}

La distancia de edición cuando solo se permite la inserción y eliminación (sin sustitución), o cuando el costo de la sustitución es el doble del costo de una inserción o eliminación, es:

$${\ displaystyle d '(X, Y) = n + m-2 \ cdot \ left | LCS (X, Y) \ right |.}

Código para la solución de programación dinámica [ editar ]

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material sin fuente puede ser cuestionado y eliminado . Encuentre fuentes:  "El problema de subsecuencia común más largo"  -  noticias  · periódicos  · libros  · erudito  · JSTOR ( marzo de 2013 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Calcular la longitud de la LCS [ editar ]

La siguiente función toma como secuencias de entrada X[1..m]y Y[1..n], calcula el LCS entre X[1..i]y Y[1..j]para todos 1 ≤ i ≤ my 1 ≤ j ≤ n, y lo almacena C[i,j]. C[m,n]contendrá la longitud del LCS de Xy Y.

función LCSLength (X [1..m], Y [1..n])
    C = matriz (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
            más
                C [i, j]: = max (C [i, j-1], C [i-1, j])
    devolver C [m, n]

Alternativamente, se podría utilizar la memorización .

Leer un LCS [ editar ]

La siguiente función retrocede las opciones tomadas al calcular la Ctabla. Si los últimos caracteres en los prefijos son iguales, deben estar en un LCS. Si no, verifique qué le dio el mayor LCS de mantenimiento$${\ displaystyle x_ {i}} y $${\ displaystyle y_ {j}}, y hacer la misma elección. Simplemente elija uno si fueran igualmente largos. Llame a la función con i=my j=n.

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

Leer todos los LCS [ editar ]

Si elegir $${\ displaystyle x_ {i}} y $${\ displaystyle y_ {j}}daría un resultado igualmente largo, lea ambas subsecuencias resultantes. Esto se devuelve como un conjunto por esta función. Tenga en cuenta que esta función no es polinómica, ya que podría ramificarse en casi todos los pasos 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
         devuelven {""}
     si X [i] = Y [j]
         devuelve {Z + X [i] para todas las Z en el backtrackAll (C, X, Y, i-1, j-1)}
     R: = {} 
    si C [i, j- 1] ≥ C [i-1, j]
        R: = R ∪ retroceso Todos (C, X, Y, i, j-1)
    si C [i-1, j] ≥ C [i, j-1]
        R: = R track retroceso Todos (C, X, Y, i-1, j)
    volver R

Imprime el diff [ editar ]

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 ≤debajo.

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] 
        printDiff (C, X, Y, i-1, j)
        imprimir "-" + X [i]
    más
        impresión ""

Ejemplo [ editar ]

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 que se Cmuestra a continuación, que es generada por la función LCSLength, muestra las longitudes de las subsecuencias comunes más largas entre los prefijos de$${\ displaystyle X} y $${\ displaystyle Y}. los$${\ displaystyle i}th fila y $${\ displaystyle j}La columna th muestra la longitud del LCS entre $${\ displaystyle X_ {1..i}} y $${\ displaystyle Y_ {1..j}}.

		0 0	1	2	3	4 4	5 5	6 6	7 7
		Ø	METRO	Z	J	UNA	W	X	U
0 0	Ø	0 0	0 0	0 0	0 0	0 0	0 0	0 0	0 0
1	X	0 0	0 0	0 0	0 0	0 0	0 0	1	1
2	METRO	0 0	1	1	1	1	1	1	1
3	J	0 0	1	1	2	2	2	2	2
4 4	Y	0 0	1	1	2	2	2	2	2
5 5	UNA	0 0	1	1	2	3	3	3	3
6 6	U	0 0	1	1	2	3	3	3	4 4
7 7	Z	0 0	1	2	2	3	3	3	4 4

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 de la LCS, y vamos hacia arriba y hacia la izquierda (en negrita ). Si no, subimos o nos vamos, dependiendo de qué celda tenga un número más alto. 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}}.

Optimización de código [ editar ]

Se pueden hacer varias optimizaciones en el algoritmo anterior para acelerarlo en casos del mundo real.

Reducir el conjunto de problemas [ editar ]

La matriz C en el algoritmo ingenuo crece cuadráticamente con las longitudes de las secuencias. Para dos secuencias de 100 ítems, se necesitaría una matriz de 10,000 ítems y se necesitarían 10,000 comparaciones. En la mayoría de los casos del mundo real, especialmente los parches y las diferencias de código fuente, el comienzo y el final de los archivos rara vez cambian, y casi con certeza no ambos al mismo tiempo. Si solo unos pocos elementos han cambiado en el medio de la secuencia, el principio y el final se pueden eliminar. Esto reduce no solo los requisitos de memoria para la matriz, sino también el número de comparaciones que deben realizarse.

función LCS (X [1..m], Y [1..n])
    inicio: = 1
    m_end: = m
    n_end: = n
    recorte los elementos coincidentes al principio 
    mientras comienza ≤ m_end y comienza ≤ n_end y X [inicio] = Y [inicio]
        inicio: = inicio + 1
    recorte los elementos coincidentes al final 
    mientras comienza ≤ m_end y comienza ≤ n_end y X [m_end] = Y [n_end]
        m_end: = m_end - 1
        n_end: = n_end - 1
    C = matriz (start-1..m_end, start-1..n_end)
    solo
     recorra los elementos que han cambiado para i: = start..m_end
         para j: = start..n_end
             el algoritmo continúa como antes ...

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

Reduzca el tiempo de comparación [ editar ]

La mayor parte del tiempo empleado por el ingenuo algoritmo se dedica a realizar comparaciones entre los elementos de las secuencias. Para secuencias de texto como el código fuente, desea ver líneas como elementos de secuencia en lugar de caracteres individuales. Esto puede significar comparaciones de cadenas relativamente largas para cada paso en el algoritmo. Se pueden hacer dos optimizaciones que pueden ayudar a reducir el tiempo que consumen estas comparaciones.

Reducir cadenas a hashes [ editar ]

Se puede usar una función hash o suma de comprobació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 o más caracteres de largo, el hash o la suma de verificación para esa línea puede tener solo 8 a 40 caracteres de largo. Además, la naturaleza aleatoria de los hashes y las sumas de verificación garantizaría que las comparaciones se cortocircuiten más rápido, ya que las líneas de código fuente rara vez se cambiarán al principio.

Hay tres inconvenientes principales para esta optimización. Primero, se debe gastar una cantidad de tiempo de antemano para calcular previamente los hash para las dos secuencias. En segundo lugar, se debe asignar memoria adicional para las nuevas secuencias hash. Sin embargo, en comparación con el algoritmo ingenuo utilizado aquí, ambos inconvenientes son relativamente mínimos.

El tercer inconveniente es el de las colisiones . Dado que no se garantiza que la suma de comprobación o el hash sean únicos, existe una pequeña posibilidad de que dos elementos diferentes se puedan reducir al mismo hash. Esto es poco probable en el código fuente, pero 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 suma de comprobación simple. Sin embargo, los beneficios pueden no valer la configuración y los requisitos computacionales de un hash criptográfico para pequeñas secuencias de longitud.

Reduzca el espacio requerido [ editar ]

Si solo se requiere la longitud del LCS, la matriz se puede reducir a un $${\ displaystyle 2 \ times \ min (n, m)} matriz con facilidad, o para un $${\ displaystyle \ min (m, n) +1}vector (más inteligente) como el enfoque de programación dinámica solo necesita las columnas actuales y anteriores de la matriz. El algoritmo de Hirschberg permite la construcción de la secuencia óptima en sí misma en el mismo tiempo cuadrático y límites de espacio lineal. ^[7]

Otros algoritmos optimizados [ editar ]

Existen varios algoritmos que son el peor de los casos más rápido que el enfoque de programación dinámica presentado. ^[8] Para problemas con un tamaño de alfabeto acotado, el Método de los cuatro rusos se puede utilizar para reducir el tiempo de ejecución del algoritmo de programación dinámica mediante un factor logarítmico. ^[9] Hay un algoritmo que funciona 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. ^[10]

Comportamiento en cadenas aleatorias [ editar ]

Artículo principal: constantes de Chvátal-Sankoff

Comenzando con Chvátal y Sankoff (1975) , ^[11] varios investigadores han investigado el comportamiento de la longitud de subsecuencia común más larga cuando las dos cadenas dadas se dibujan al azar del mismo alfabeto. Cuando el tamaño del alfabeto es constante, la longitud esperada del LCS es proporcional a la longitud de las dos cadenas, y las constantes de proporcionalidad (dependiendo del tamaño del alfabeto) se conocen como las constantes de Chvátal-Sankoff . Se desconocen sus valores exactos, pero se han demostrado los límites superior e inferior de sus valores ^[12], y se sabe que crecen de forma inversamente proporcional a la raíz cuadrada del tamaño del alfabeto. ^[13]Se ha demostrado que los modelos matemáticos simplificados del problema de subsecuencia común más largo están controlados por la distribución de Tracy-Widom .