Problema de subsecuencia común más larga

El problema de subsecuencia común más larga (en inglés: longest common subsequence problem, abreviado LCS problem), se trata de encontrar una subsecuencia más larga que es común en un conjunto de secuencias (Aunque en la mayor parte solamente se toman dos secuencias). Es diferente del problema de substring común más largo; a diferencia de los substrings, las subsecuencias no necesitan tener posiciones consecutivas en la secuencia original. El problema de LCS es uno de los problemas clásicos de las ciencias computacionales y es la base de programas que comparan datos como la utilidad diff, y ha tenido usos en bioinformática. También es usado ampliamente para los sistemas de control de revisión como Git para reconciliar múltiples cambios sobre archivos controlados de revisión.

Complejidad[editar]

En los casos generales de un número arbitrario de secuencias de entrada, el problema llega a ser NP-hard.^[1] Cuando el número de secuencias es constante, el problema se puede resolver en un tiempo polinómico a través de programación dinámica. Supongamos que se tiene $N$ secuencias de longitudes $n_{1},...,n_{N}$ . Una búsqueda nativa probaría los $2^{n_{1}}$ subsecuancias de la primera secuencia para determinar si son subsecuencias de las otras secuencias. Cada subsecuencia debe ser probado en un tiempo lineal en longitud de las secuencias restantes así que el algoritmo sería como:

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 ejecución para la programación dinámica es de O(n × m). Para un número arbitrario de secuencias, la programación dinámica encontraría la solución en

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

Existen métodos con una complejidad menor,^[2] la cual suele depender de la longitud del LCS, el tamaño del alfabeto o ambos.

Cabe mencionar que LCS no es único; por ejemplo el LCS de "ABC" y "ACB" son ambos "AB" y "AC". Por eso LCS a veces se define como encontrar todas las subsecuencias comunes en una longitud máxima. Este problema tiene una complejidad mayor ya que los números de estas subsecuencias pueden ser exponenciales en el peor de los casos,^[3] aun cuando solamente sean dos strings de entrada.

Solución para dos secuencias[editar]

El problema de LCS tiene una estructura óptima: el problema puede ser dividido en subproblemas más pequeños y simples, el cual puede ser dividido en subproblemas más simples y así hasta que la solución llega a ser trivial. El problema de LCS también tiene subproblemas que se traslapan: las soluciones de subproblemas de nivel mayor utilizan soluciones de subproblemas menores. Los problemas con estas dos propiedades: estructura óptima y subproblemas que traslapan pueden ser resueltos por una técnica de programación llamada programación dinámica, en la que las soluciones de los subproblemas se almacenan en lugar de ser calculadas una y otra vez. Para esto se necesita la técnica de memoización en la cual se tabulan las soluciones de los subproblemas más pequeños (como si se estuviera tomando una nota "memo" en inglés) para que esas soluciones puedan ser utilizadas para resolver a los de más alto nivel.

Prefijos[editar]

El subproblema se hace más simple en cuanto la secuencia se hace más corta. Las secuencias cortas pueden ser descritos como prefijos. Un prefijo de la secuencia es una secuencia en donde su parte trasera se corta. Supongamos que S es la secuencia (AGCA). Entonces (AG) es uno de los prefijos de S. Los prefijos se denotan con el nombre de la secuencia seguido por un índice inferior de cuántos caracteres contiene el prefijo.^[4] El prefijo (AG) es denotado como S₂, ya que contiene a los primeros 2 elementos de la secuencia S. los posibles prefijos de S son:

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA).

La solución al problema LCS de dos cadenas arbitrarias X y Y pueden formar una función LCS(X,Y) tal que regrese la subsecuencia común más larga de X y Y. Esta función depende de las siguientes dos propiedades.

Primera propiedad[editar]

Supongamos que las dos secuencias terminan con el mismo elemento. Para encontrar su LCS, podemos acortar las dos secuencias eliminando el último elemento, encontrando el LCS de las dos secuencias acortadas y agregando el elemento eliminado

Por ejemplo, tenemos dos secuencias que tienen el mismo elemento final: (BANANA) y (ATANA).

Eliminamos el último elemento en las dos cadenas. Repetimos hasta que lleguemos a un elemento no común. Los elementos removidos son (ANA)

Ahora las dos secuencias son (BAN) y (AT).

El LCS de las dos secuencias es (A).

Ahora anexamos los elementos eliminados al LCS y obtenemos (AANA), el cual es LCS de las secuencias originales

En términos de los prefijos.

Si x_n=y_m, LCS(X_n, Y_m) = append(LCS( X_n -1, Y_m-1), x_n)

Nótese que el LCS para X_n y Y_m involucran determinar el LCS de secuencias más cortas: X_n-1 and Y_m-1.

Segunda propiedad[editar]

Supongamos que las dos secuencias X y Y no terminan con el mismo símbolo. Entonces el LCS de X y Y es la más larga de las secuencias LCS(X_n,Y_m-1) y LCS(X_n-1,Y_m).

Para entender esta propiedad, se considera lo siguiente:

secuencia X: ABCDEFG (n elementos)

secuencia Y: BCDGK (m elementos)

El LCS de estas dos secuencias podría terminar en G (último elemento de X) o puede que no.

Caso 1: LCS termina con G

Si termina con G no puede terminar con K. Por lo tanto no pasa nada si nosotros eliminamos K de la secuencia Y. Si K estuviera en LCS, tendría que ser el último carácter por eso nosotros sabemos que no está en LCS. Entonces podemos decir que LCS(X_n,Y_m) = LCS(X_n, Y_m-1).

Caso 2: LCS no termina con G
Si no termina con G, no afectaría en nada eliminar G de la secuencia de X. Por la misma razón. Entonces podemos escribir LCS(X_n,Y_m) = LCS(X_n-1, Y_m).

En cualquier caso, el LCS que nosotros buscamos es uno de los siguientes LCS(X_n, Y_m-1) o LCS(X_n-1, Y_m). Ambas funciones van a regresar una subsecuencia común de X y Y. Nada más que para LCS nosotros necesitamos el más largo.

Definición de la función LCS[editar]

Dadas dos secuencias:X = (x₁, x₂...x_m) y Y = (y₁, y₂...y_n). Los prefijos de X son X_{1, 2,...m}; los prefijos de Y son Y_{1, 2,...n}. Supongamos que LCS(X_i, Y_j) representa la subsecuencia común más larga de los prefijos X_i y Y_j. Este conjunto de secuencia se define como el siguiente:

LCS\left(X_{i},Y_{j}\right)={\begin{cases}\emptyset &{\mbox{ if }}\ i=0{\mbox{ or }}j=0\\{\textrm {}}LCS\left(X_{i-1},Y_{j-1}\right)\frown x_{i}&{\mbox{ if }}x_{i}=y_{j}\\{\mbox{longest}}\left(LCS\left(X_{i},Y_{j-1}\right),LCS\left(X_{i-1},Y_{j}\right)\right)&{\mbox{ if }}x_{i}\neq y_{j}\\\end{cases}}

Para encontrar la subsecuencia común más larga de X_i y Y_j, comparamos los elementos x_i y y_j. Si son iguales, entonces la secuencia LCS(X_i-1, Y_j-1) será extendido por el elementos x_i. Si no son iguales, entonces el más largo de LCS(X_i, Y_j-1), y LCS(X_i-1, Y_j), será la respuesta (Si ambos son del mismo tamaño pero no son idénticos, ambas soluciones serán resultados). Nótese que los subscripts se reducen por 1 en estas fórmulas. Y así se podría llegar a 0. Como las secuencias deben empezar en 1, fue necesario definir que ninguna de las dos secuencias fueran de logintud 0.

Ejemplo trabajado[editar]

La subsecuencia común más larga a C = (AGCAT) y R = (GAC) se está buscando. Como la función LCS utiliza un elemento en la casilla cero, es conveniente definir un zero como prefijo que representará a la cadena vacía. C₀ = Ø; y R₀ = Ø. Todos los prefijos se colocarán en la tabla siendo C la fila y R la columna

LCS Strings
	0	A	G	C	A	T
0	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
A	Ø
C	Ø

Esta tabla se utiliza para almacernar las secuencias LCS para cada paso del cálculo. La segunda columna y la segunda fila se llenaron con Ø porque cuando una secuencia vacía se compara con una no vacía, el LCS siempre será vacía.

LCS(R₁, C₁) se determina comparando el primer elemento de cada secuencia. G y A no son la misma, así que LCS se calcula con la segunda propiedad LCS(R₁, C₀) y LCS(R₀, C₁). Según la tabla, ambos son vacíos por lo tanto LCS(R₁, C₁) también es vacío como se puede ver en la tabla de abajo. Las flechas indican que la secuencia viene de ambas casillas anteriores, la celda de arriba LCS(R₀, C₁) y la celda de izquierda LCS(R₁, C₀).

LCS(R₁, C₂) se determina comparando G con G. Como son idénticas, G se agrega a la secuencia que está arriba a la izquierda LCS(R₀, C₁), la cual es (Ø), dando (ØG), que sería (G).

Para LCS(R₁, C₃), G y C no son iguales. La secuencia de arriba es vacío; y la de izquierda contiene el elemento G. Así que la secuencia más larga sería LCS(R₁, C₃) que es (G). La flecha apunta hacia la izquierda ya que esa es la secuencia más larga.

LCS(R₁, C₄), también, es (G).

LCS(R₁, C₅), también, es (G).

Fila "G" completada
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø
C	Ø

Para LCS(R₂, C₁), A se compara con A. Como los elementos son iguales, A se anexa a Ø, dando como resultado (A).

Para LCS(R₂, C₂), como A y G no son iguales, la secuencia más larga de LCS(R₁, C₂), la cual es (G), y LCS(R₂, C₁), la cual es (A), se escribe. En este cado como cada uno contiene a un solo elemento, el LCS son ambos (A) y (G)

Para LCS(R₂, C₃), A no es igual que C. LCS(R₂, C₂) contiene la secuencia (A) y (G); LCS(R₁, C₃) es (G), la cual ya está contenido en LCS(R₂, C₂). Como resultado LCS(R₂, C₃) también contiene a las dos secuencias (A) y (G)

Para LCS(R₂, C₄), A es igual que A, entonces A se anexa a la celda superior izquierdo dando como secuencia (GA)

Para LCS(R₂, C₅), A no es igual que T. Se comparan las dos secuencias (GA) y (G). La secuencia más larga que es (GA) se queda como resultado

Filas "G" & "A" Completeda
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø

Para LCS(R₃, C₁), C y A son diferentes, así que LCS(R₃, C₁) llega a ser la secuencia más larga que es, (A).

Para LCS(R₃, C₂), C y G son diferentes. Ambos LCS(R₃, C₁) y LCS(R₂, C₂) tienen un elemento. Y da como resultado de LCS(R₃, C₂) las dos subsecuencias, (A) and (G).

Para LCS(R₃, C₃), C y C son iguales, así que C se anexa a LCS(R₂, C₂), la cual contiene dos secuencias, (A) y (G), dando como resultado (AC) y (GC).

Para LCS(R₃, C₄), C y A no son iguales. Combinanado LCS(R₃, C₃), que contiene (AC) y (GC), y LCS(R₂, C₄), que contiene (GA), da como resultado tres secuencias: (AC), (GC), y (GA).

Finalmente, para LCS(R₃, C₅), C y T son diferentes. Entonces LCS(R₃, C₅) también llega a tener tres secuencias, (AC), (GC), y (GA).

Tabla LCS completada
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\overset {\ \ \uparrow }{\leftarrow }}$ Ø	${\overset {\nwarrow }{\ }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)	${\overset {\ }{\leftarrow }}$ (G)
A	Ø	${\overset {\nwarrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (GA)	${\overset {\ }{\leftarrow }}$ (GA)
C	Ø	${\overset {\ \uparrow }{\ }}$ (A)	${\overset {\ \ \uparrow }{\leftarrow }}$ (A) & (G)	${\overset {\nwarrow }{\ }}$ (AC) & (GC)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)	${\overset {\ \ \uparrow }{\leftarrow }}$ (AC) & (GC) & (GA)

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

Reconstrucción de la solución[editar]

Calculando el LCS de una fila de la tabla solamente requiere la fila actual y la fila anterior. Aun así, para las secuencias largas, estas secuencias pueden ser numerosas y largas. Requeriendo grandes cantidades de espacio de almacenamiento. El espacio de almacenamiento se puede reducir guardando solamente la longitud de la subsecuencia y la dirección de las flechas como se muestra a continuación.

Almacenando longitud y dirección
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Las subsecuencias pueden ser deducidas en una reconstrucción que sigue las flechas, empezando por la última celda de la tabla. Cuando la longitud decrece, la subsecuencia obtiene un elemento común. Como notamos varios caminos son posibles cuando se muestran dos flechas en la celda. A continuación se muestra el análisis y los números de color son celdas donde su número decrece. Los números en negrita reconstruyen la secuencia (GA)^[5]

Ejemplo de reconstrucción
	A	G	C	A	T
Ø	0	0	0	0	0
G	${\overset {\ \ \uparrow }{\leftarrow }}$ 0	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1	${\overset {\ }{\leftarrow }}$ 1
A	${\overset {\nwarrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ }{\leftarrow }}$ 2
C	${\overset {\ \uparrow }{\ }}$ 1	${\overset {\ \ \uparrow }{\leftarrow }}$ 1	${\overset {\nwarrow }{\ }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2	${\overset {\ \ \uparrow }{\leftarrow }}$ 2

Relación a otros problemas[editar]

Para dos cadenas $X_{1\dots m}$ y $Y_{1\dots n}$ , la longitud de la supersecuencia común más corta (SCS) se relaciona a la longitud del LCS:^[2]

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

La distancia de edición cuando solamente la inserción y el borrado es permitido (no hay sustitución), o cuando el costo de la sustitución es el doble del costo de inserción o borrado:

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

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

Calculando la longitud del LCS[editar]

La función que se muestra en seguida recibe dos secuencias de entrada X[1..m] y Y[1..n] . Y Calcula el LCS entre X[1..i] y Y[1..j] para todo 1 ≤ i ≤ m y 1 ≤ j ≤ n, Y lo almacena en C[i,j]. C[m,n] guardará la longitud de LCS de X y Y.

function LCSLength(X[1..m], Y[1..n])
    C = array(0..m, 0..n)
    for i := 0..m
       C[i,0] = 0
    for j := 0..n
       C[0,j] = 0
    for i := 1..m
        for j := 1..n
            if X[i] = Y[j]
                C[i,j] := C[i-1,j-1] + 1
            else
                C[i,j] := max(C[i,j-1], C[i-1,j])
    return C[m,n]

Alternativamente, memoización podría ser utilizado.

Reconstruyendo un LCS[editar]

La función que se muestra en seguida reconstruye las decisiones tomadas cuando calculaba la tabla C. Si el último carácter en el prefijo son iguales, entonces deberían ser LCS. Si no, debería verificar cual tiene el mayor LCS almacenando $x_{i}$ y $y_{j}$ , y tomando la misma decisión. Solamente elige uno cuando son igual de largos. Se llama la función con i=m y j=n.

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return ""
    else if  X[i] = Y[j]
        return backtrack(C, X, Y, i-1, j-1) + X[i]
    else
        if C[i,j-1] > C[i-1,j]
            return backtrack(C, X, Y, i, j-1)
        else
            return backtrack(C, X, Y, i-1, j)

Reconstruyendo todos los LCSs[editar]

Si al elegir $x_{i}$ y $y_{j}$ están en una cadena de igual longitud, se leen las dos subsecuencias resultantes. Esto se devuelve como un conjunto por la función. Nótese que la función no es polinomica ya que podría crear ramas en cada paso si las cadenas son parecidas.

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    else if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    else
        R := {}
        if C[i,j-1] ≥ C[i-1,j]
            R := R ∪ backtrackAll(C, X, Y, i, j-1)
        if C[i-1,j] ≥ C[i,j-1]
            R := R ∪ backtrackAll(C, X, Y, i-1, j)
        return R

Imprimir las diferencias[editar]

Esta función recorre la matriz C en reverso e imprime la diferencia entre las dos secuencias. Nótese que se obtendrá un resultado diferentes si se intercambian ≥ y <, con > y ≤

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i > 0 and j > 0 and X[i] = Y[j]
        printDiff(C, X, Y, i-1, j-1)
        print "  " + X[i]
    else if j > 0 and (i = 0 or C[i,j-1] ≥ C[i-1,j])
        printDiff(C, X, Y, i, j-1)
        print "+ " + Y[j]
    else if i > 0 and (j = 0 or C[i,j-1] < C[i-1,j])
        printDiff(C, X, Y, i-1, j)
        print "- " + X[i]
    else
        print ""

Ejemplo[editar]

Supongamos que $X$ es “XMJYAUZ” y $Y$ es “MZJAWXU”. el LCS de $X$ y $Y$ es “MJAU”. La tabla C que se muestra a continuación, la cual fue generada por la función LCSLength, muestra las longitudes de las subsecuencias comunes más largas entre los prefijos de $X$ y $Y$ . La fila $i$ y la columna $j$ muestra la longitud de LCS entre $X_{1..i}$ y $Y_{1..j}$ .

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	A	W	X	U
0	Ø	0	0	0	0	0	0	0	0
1	X	0	0	0	0	0	0	1	1
2	M	0	1	1	1	1	1	1	1
3	J	0	1	1	2	2	2	2	2
4	Y	0	1	1	2	2	2	2	2
5	A	0	1	1	2	3	3	3	3
6	U	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Los números marcados muestran el camino de la función de la reconstrucción que seguiría empezando desde la celda inferior derecha, cuando se está leyendo un LCS. Si los símbolos actuales de $X$ y $Y$ son iguales, se forman parte de LCS y se pasa a la celda superior izquierda (se muestra en negrita). Si no, se pasa hacia la celda superior o a la celda izquierda dependiendo del número que escrito en la celda. Este proceso corresponde a tomar el LCS entre $X_{1..i-1}$ y $Y_{1..j}$ , ó $X_{1..i}$ y $Y_{1..j-1}$ .

Optimización de código[editar]

Varias optimizaciones son posibles en el algoritmo para reducir el tiempo en casos reales.

Reducir el conjunto del problema[editar]

La matriz C en el algoritmo original crece cuadráticamente con la longitud de las secuencias. Para dos secuencias de 100 elementos se debe crear una matriz de 10,000 elementos la cual necesitaría el cálculo de 10000 comparaciones. En muchos casos de la vida real, especialmente en los códigos fuente de diff y patch, el comienzo y el fin cambia raramente y casi nunca cambian las dos al mismo tiempo. Si solamente algunos elementos cambiaron en medio de la secuencias, El comienzo y el fin podrían ser eliminados. Esto reduce no solamente la memoria que se requiere para generar la matriz, pero también el número de comparaciones que se deben ejecutar.

function LCS(X[1..m], Y[1..n])
    start := 1
    m_end := m
    n_end := n
    trim off the matching items at the beginning
    while start ≤ m_end and start ≤ n_end and X[start] = Y[start]
        start := start + 1
    trim off the matching items at the end
    while start ≤ m_end and start ≤ n_end and X[m_end] = Y[n_end]
        m_end := m_end - 1
        n_end := n_end - 1
    C = array(start-1..m_end, start-1..n_end)
    only loop over the items that have changed
    for i := start..m_end
        for j := start..n_end
            the algorithm continues as before ...

En el mejor de los casos, en una secuencia sin cambios, esta optimización eliminaría completamente la necesidad por la matriz C. En el peor de los casos, cuando los cambios están en los primeros elementos y en los últimos elementos solamente dos comparaciones adicionales serán ejecutadas.

Reduciendo el tiempo de comparación[editar]

La mayoría del tiempo es gastado en las comparaciones que se hacen entre dos elementos de las secuencias. Para secuencias textuales como códigos fuente, se quiere ver las líneas como los elementos de las secuencias en lugar de caracteres individuales. Esto hace que se tenga que comparar cadenas relativamente largas para cada paso del algoritmo. Dos optimizaciones se pueden hacer para reducir el tiempo.

Reduciendo las cadenas a hash[editar]

Una función hash puede ser utilizada para reducir el tamaño de las cadenas en las secuencias. Esto es que para códigos fuente donde cada línea es de 60 o más caracteres, el hash podría reducirse a una de 8 a 40 caracteres. Además, la naturaleza aleatorizada de los hashes pueden garantizar que las comparaciones serían más rápidas ya que el los códigos fuentes no cambian frecuentemente desde el principio.

Pero existen tres desventajas en esta optimización. Primero el tiempo necesario para calcular al hash de las dos secuencias antes de la comparación. Segundo, memoria adicional requerida para alocar las secuencias en hash. Pero aun así estas desventajas son mínimas emparadas al algoritmo original.

La tercera desventaja son las colisiones. Ya que el hash no garantiza ser único, hay una pequeña probabilidad de que dos cadenas diferentes resultaran en el mismo hash. Esto casi no es susceptible en códigos fuente, pero sí es posible. Un hash criptográfico podría ser más adecuado para esta optimización, ya que la entropía va a ser mucho más alta que la de un hash simple. Aun así, los beneficios podrían no ser suficientemente valiosos en comparación a la preparación y el poder computacional que se requiere.

Reduciendo el espacio requerido[editar]

Si solamente la longitud de LCS es necesario, la matriz puede ser reducida a $2\times \min(n,m)$ con facilidad, o a un vector de $\min(m,n)+1$ ya que la programación dinámica solamente requiere las columna actual y el anterior. El algoritmo de Hirschberg permite la construcción de secuencias óptimas en el mismo tiempo cuadrático y límites de espacio lineal^[6]

Algoritmos más optimizados[editar]

Existen varios algoritmos que son más rápidos que el peor de los casos del algoritmo presentado con programación dinámica.^[7] Para problemas con tamaños de alfabeto limitado, el método de los Cuatro Rusos puede ser utilizado para reducir el tiempo de ejecución de la programación dinámica a un factor logarítmico.^[8] Para $r$ (donde $n>m$ ), el número de equivalencias entre las dos cadenas, existe un algoritmo que lo hace en un tiempo de $O((n+r)\log(n))$ ^[9]

Comportamiento en cadenas aleatorias[editar]

Empezando porChvátal y Sankoff (1975),^[10] varios investigadores han trabajado en el comportamiento de la longitud de LCS cuando se tiene dos cadenas aleatorias que se forman del mismo alfabeto. Cuando el tamaño del alfabeto es constante, el número esperado de la longitud de LCS es proporcional a la longitud de dos cadenas, y las constante de la proporción se les conoce como constantes de Chvátal-Sankoff. Sus valores exactos no se conocen pero sus límites superiores e inferiores se han comprobado,^[11] y también se conoce que crecen inversamente proporcional al la raíz cuadrada del tamaño del alfabeto.^[12] Modelos simples matemáticos de LCS han sido probados que son regidos por la distribución Tracy-Widom.^[13]

Referencias[editar]

↑ David Maier (1978). «The Complexity of Some Problems on Subsequences and Supersequences». J. ACM (ACM Press) 25 (2): 322-336. doi:10.1145/322063.322075.
↑ ^a ^b L. Bergroth and H. Hakonen and T. Raita (2000). «A Survey of Longest Common Subsequence Algorithms». SPIRE (IEEE Computer Society) 00: 39-48. ISBN 0-7695-0746-8. doi:10.1109/SPIRE.2000.878178.
↑ Ronald I. Greenberg (6 de agosto de 2003). «Bounds on the Number of Longest Common Subsequences». arXiv:cs.DM/0301030.
↑ Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. Nueva York: Springer. p. 24. ISBN 0-387-71336-0.
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). «15.4». Introduction to Algorithms (2nd edición). MIT Press and McGraw-Hill. pp. 350-355. ISBN 0-262-53196-8.
↑ Hirschberg, D. S. (1975). «A linear space algorithm for computing maximal common subsequences». Communications of the ACM 18 (6): 341-343. doi:10.1145/360825.360861.
↑ http://books.google.com/books?id=mFd_grFyiT4C&pg=PA132&lpg=PA132&dq=hunt+szymanski+algorithm&source=bl&ots=sMc-HtvNTQ&sig=FtrZ_b5JdJ25Ighwc1-XOfysaf8&hl=en&sa=X&ei=-BU9VPK7OpS7ggT0gYEQ&ved=0CDsQ6AEwAw#v=onepage&q&f=false
↑ Masek, William J.; Paterson, Michael S. (1980), «A faster algorithm computing string edit distances», Journal of Computer and System Sciences 20 (1): 18-31, MR 566639, doi:10.1016/0022-0000(80)90002-1 ..
↑ http://www.cs.bgu.ac.il/~dpaa111/wiki.files/HuntSzymanski.pdf
↑ Chvatal, Václáv; Sankoff, David (1975), «Longest common subsequences of two random sequences», Journal of Applied Probability 12: 306-315, MR 0405531, doi:10.2307/3212444 ..
↑ Lueker, George S. (2009), «Improved bounds on the average length of longest common subsequences», Journal of the ACM 56 (3), A17, MR 2536132, doi:10.1145/1516512.1516519 ..
↑ Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), «Expected length of the longest common subsequence for large alphabets», Advances in Mathematics 197 (2): 480-498, MR 2173842, doi:10.1016/j.aim.2004.10.012 ..
↑ Majumdar, Satya N.; Nechaev, Sergei (2005), «Exact asymptotic results for the Bernoulli matching model of sequence alignment», Physical Review E 72 (2): 020901, 4, MR 2177365, doi:10.1103/PhysRevE.72.020901 ..

Ligas Externas[editar]

Wikilibros alberga un libro o manual sobre Strings/Longest common subsequence.
Dictionary of Algorithms and Data Structures: longest common subsequence
A collection of implementations of the longest common subsequence in many programming languages

Datos: Q141001

[1] David Maier (1978). «The Complexity of Some Problems on Subsequences and Supersequences». J. ACM (ACM Press) 25 (2): 322-336. doi:10.1145/322063.322075.

[BHR00-2] L. Bergroth and H. Hakonen and T. Raita (2000). «A Survey of Longest Common Subsequence Algorithms». SPIRE (IEEE Computer Society) 00: 39-48. ISBN 0-7695-0746-8. doi:10.1109/SPIRE.2000.878178.

[1-3] Ronald I. Greenberg (6 de agosto de 2003). «Bounds on the Number of Longest Common Subsequences». arXiv:cs.DM/0301030.

[4] Xia, Xuhua (2007). Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. Nueva York: Springer. p. 24. ISBN 0-387-71336-0.

[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). «15.4». Introduction to Algorithms (2nd edición). MIT Press and McGraw-Hill. pp. 350-355. ISBN 0-262-53196-8.

[6] Hirschberg, D. S. (1975). «A linear space algorithm for computing maximal common subsequences». Communications of the ACM 18 (6): 341-343. doi:10.1145/360825.360861.

[7] ttp://books.google.com/books?id=mFd_grFyiT4C&pg=PA132&lpg=PA132&dq=hunt+szymanski+algorithm&source=bl&ots=sMc-HtvNTQ&sig=FtrZ_b5JdJ25Ighwc1-XOfysaf8&hl=en&sa=X&ei=-BU9VPK7OpS7ggT0gYEQ&ved=0CDsQ6AEwAw#v=onepage&q&f=false

[8] Masek, William J.; Paterson, Michael S. (1980), «A faster algorithm computing string edit distances», Journal of Computer and System Sciences 20 (1): 18-31, MR 566639, doi:10.1016/0022-0000(80)90002-1 ..

[9] ttp://www.cs.bgu.ac.il/~dpaa111/wiki.files/HuntSzymanski.pdf

[10] Chvatal, Václáv; Sankoff, David (1975), «Longest common subsequences of two random sequences», Journal of Applied Probability 12: 306-315, MR 0405531, doi:10.2307/3212444 ..

[11] Lueker, George S. (2009), «Improved bounds on the average length of longest common subsequences», Journal of the ACM 56 (3), A17, MR 2536132, doi:10.1145/1516512.1516519 ..

[12] Kiwi, Marcos; Loebl, Martin; Matoušek, Jiří (2005), «Expected length of the longest common subsequence for large alphabets», Advances in Mathematics 197 (2): 480-498, MR 2173842, doi:10.1016/j.aim.2004.10.012 ..

[13] Majumdar, Satya N.; Nechaev, Sergei (2005), «Exact asymptotic results for the Bernoulli matching model of sequence alignment», Physical Review E 72 (2): 020901, 4, MR 2177365, doi:10.1103/PhysRevE.72.020901 ..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]