Problema de subsecuencia comú més llarga

El problema de subsecuencia comú més llarga (en inglés: longest common subsequence problem, abreviat LCS problem), es tracta de trobar una subsecuencia més llarga que és comuna en un conjunt de seqüències (Encara que en la major part solament es prenen dos seqüències). És diferent del problema de substring comú més llarc; a diferència dels substrings, les subsecuencias no necessiten tindre posicions consecutives en la seqüència original. El problema de LCS és un dels problemes clàssics de les ciències computacionals i és la base de programes que comparen senyes com l'utilitat diff, i ha tingut usos en bioinformática. També és usat àmpliament per als sistemes de control de revisió com Git per a reconciliar múltiples canvis sobre archius controlats de revisió.

Complexitat

En els casos generals d'un número arbitrari de seqüències d'entrada, el problema aplega a ser NP-hard.^[1] Quan el número de seqüències és constant, el problema es pot resoldre en un temps polinòmic a través de programació dinàmica. Supongam que es té $N$ seqüències de llongituts $n_{1}, ..., n_{N}$ . Una busca nativa provaria els $2^{n_{1}}$ subsecuancias de la primera seqüència per a determinar si són subsecuencias de les atres seqüències. Cada subsecuencia deu ser provat en un temps llineal en llongitut de les seqüències restants aixina que l'algoritme seria com:

O (2^{n_{1}} \sum_{i > 1} n_{i}) .

Per al cas de dos seqüències de n i m elements, el temps d'eixecució per a la programació dinàmica és d'O(n × m). Per a un número arbitrari de seqüències, la programació dinàmica trobaria la solució en

O (N \prod_{i = 1}^{N} n_{i}) .

Existixen métodos en una complexitat menor,^[2] la qual sol dependre de la llongitut de el LCS, el tamany de l'alfabet o abdós.

cal mencionar que LCS no és únic; per eixemple el LCS de "ABC" i "ACB" són abdós "AB" i "AC". Per això LCS a voltes es definix com trobar totes les subsecuencias comunes en una llongitut màxima. Este problema té una complexitat major ya que els números d'estes subsecuencias poden ser exponencials en el pijor dels casos,^[3] aun cuando solament siguen dos strings d'entrada.

Solució per a dos seqüències

El problema de LCS té una estructura òptima: el problema pot ser dividit en subproblemas més chicotets i simples, el qual pot ser dividit en subproblemas més simples i aixina fins que la solució aplega a ser trivial. El problema de LCS també té subproblemas que es traslapan: les solucions de subproblemas de nivell major utilisen solucions de subproblemas menors. Els problemes en estes dos propietats: estructura òptima i subproblemas que traslapan poden ser resolts per una tècnica de programació anomenada programació dinàmica, en la que les solucions dels subproblemas s'almagasenen en lloc de ser calculades una i una atra volta. Per a açò es necessita la tècnica de memoisació en la qual es tabulan les solucions dels subproblemas més chicotets (com si s'estiguera prenent una nota "memo" en anglés) per a que eixes solucions puguen ser utilisades per a resoldre als de més alt nivell.

Prefixos

El subproblema es fa més simple en quant la seqüència es fa més curta. Les seqüències curtes poden ser descrits com a prefixos. Un prefix de la seqüència és una seqüència en a on la seua part atrassera es talla. Supongam que S és la seqüència (AGCA). Llavors (AG) és un dels prefixos de S. Els prefixos es denoten en el nom de la seqüència seguit per un índex inferior de quants caràcters conté el prefix. El prefix (AG) és denotat com a S₂, ya que conté als primers 2 elements de la seqüència S. els possibles prefixos de S són:

S₁ = (A)

S₂ = (AG)

S₃ = (AGC)

S₄ = (AGCA).

La solució al problema LCS de dos cadenes arbitràries X i I poden formar una funció LCS(X,I) tal que retorne la subsecuencia comuna més llarga de X i Y. Esta funció depén de les següents dos propietats.

Primera propietat

Supongam que les dos seqüències terminen en el mateix element. Per a trobar el seu LCS, podem acurtar les dos seqüències eliminant l'últim element, trobant el LCS de les dos seqüències acurtades i agregant l'element eliminat

Per eixemple, tenim dos seqüències que tenen el mateix element final: (BANANA) i (ATANA).

Eliminem l'últim element en les dos cadenes. Repetim fins que apleguem a un element no comú. Els elements remoguts són (ANA)

Ara les dos seqüències són (BAN) i (AT).

El LCS de les dos seqüències és (A).

Ara anexem els elements eliminats al LCS i obtenim (AANA), el qual és LCS de les seqüències originals

En térmens dels prefixos.

Si x_n=i_m, LCS(X_n, I_m) = append(LCS( X_n -1, I_m-1), x_n)

Note's que el LCS per a X_n i I_m involucren determinar el LCS de seqüències més curtes: X_n-1 and I_m-1.

Segona propietat

Supongam que les dos seqüències X i I no terminen en el mateix símbol. Llavors el LCS de X i I és la més llarga de les seqüències LCS(X_n,I_m-1) i LCS(X_n-1,I_m).

Per a entendre esta propietat, es considera lo següent:

seqüència X: ABCDEFG (n elements)

seqüència I: BCDGK (m elements)

El LCS d'estes dos seqüències podria terminar en G (últim element de X) o pot ser que no.

Cas 1: LCS termina en G

Si termina en G no pot terminar en K. Per lo tant no passa res si nosatres eliminem K de la seqüència Y. Si K estiguera en LCS, tindria que ser l'últim caràcter per això nosatres sabem que no està en LCS. Llavors podem dir que LCS(X_n,I_m) = LCS(X_n, I_m-1).

Cas 2: LCS no termina en G
Si no termina en G, no afectaria en res eliminar G de la seqüència de X. Per la mateixa raó. Llavors podem escriure LCS(X_n,I_m) = LCS(X_n-1, I_m).

En qualsevol cas, el LCS que nosatres busquem és un dels següents LCS(X_n, I_m-1) o LCS(X_n-1, I_m). Abdós funcions van a retornar una subsecuencia comuna de X i Y. Res més que per a LCS nosatres necessitem el més llarc.

Definició de la funció LCS

Donades dos seqüències:X = (x₁, x₂...x_m) i I = (i₁, i₂...i_n). Els prefixos de X són X_{1, 2,...m}; els prefixos d'I són I_{1, 2,...n}. Supongam que LCS(X_i, I_j) representa la subsecuencia comuna més llarga dels prefixos X_i i I_j. Este conjunt de seqüència es definix com el següent:

L C S (X_{i}, Y_{j}) = {\begin{matrix} \emptyset & if i = 0 or j = 0 \\ <mo stretchy="false"></mo> L C S (X_{i - 1}, Y_{j - 1}) ⌢ x_{i} & if x_{i} = y_{j} \\ longest (L C S (X_{i}, Y_{j - 1}), L C S (X_{i - 1}, Y_{j})) & if x_{i} \neq y_{j} \end{matrix}

Per a trobar la subsecuencia comuna més llarga de X_i i I_j, comparem els elements x_i i i_j. Si són iguals, llavors la seqüència LCS(X_i-1, I_j-1) serà estés per l'element x_i. Si no són iguals, llavors el més llarc de LCS(X_i, I_j-1), i LCS(X_i-1, I_j), serà la resposta (Si abdós són del mateix tamany pero no són idèntics, abdós solucions seran resultats). Note's que els subscripts es reduïxen per 1 en estes fòrmules. I aixina es podria aplegar a 0. Com les seqüències deuen escomençar en 1, va ser necessari definir que cap de les dos seqüències anaren de logintud 0.

Eixemple treballat

La subsecuencia comuna més llarga a C = (AGCAT) i R = (GAC) s'està buscant. Com la funció LCS utilisa un element en la casella zero, és convenient definir un zero com a prefix que representarà a la cadena buida. C₀ = Ø; i R₀ = Ø. Tots els prefixos es colocaran en la taula sent C la fila i R la columna

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

Esta taula s'utilisa per a almacernar les seqüències LCS per a cada pas del càlcul. La segona columna i la segona fila es varen omplir en Ø perque quan una seqüència buida es compara en una no buida, el LCS sempre serà buida.

LCS(R₁, C₁) es determina comparant el primer element de cada seqüència. G i A no són la mateixa, aixina que LCS es calcula en la segona propietat LCS(R₁, C₀) i LCS(R₀, C₁). Segons la taula, abdós són buits per lo tant LCS(R₁, C₁) també és buit com es pot vore en la taula d'avall. Les fleches indiquen que la seqüència ve d'abdós caselles anteriors, la cela de dalt LCS(R₀, C₁) i la cela d'esquerra LCS(R₁, C₀).

LCS(R₁, C₂) es determina comparant G en G. Com són idèntiques, G s'agrega a la seqüència que està dalt a l'esquerra LCS(R₀, C₁), la qual és (Ø), donant (ØG), que seria (G).

Per a LCS(R₁, C₃), G i C no són iguals. La seqüència de dalt és buit; i la d'esquerra conté l'element G. Aixina que la seqüència més llarga seria LCS(R₁, C₃) que és (G). La flecha apunta cap a l'esquerra ya que eixa és la seqüència més llarga.

LCS(R₁, C₄), també, és (G).

LCS(R₁, C₅), també, és (G).

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

Per a LCS(R₂, C₁), As compara en A. Com els elements són iguals, A s'anexa a Ø, donant com a resultat (A).

Per a LCS(R₂, C₂), com A i G no són iguals, la seqüència més llarga de LCS(R₁, C₂), la qual és (G), i LCS(R₂, C₁), la qual és (A), s'escriu. En este cado com cada u conté a un sol element, el LCS són abdós (A) i (G)

Per a LCS(R₂, C₃), A no és igual que C. LCS(R₂, C₂) conté la seqüència (A) i (G); LCS(R₁, C₃) és (G), la qual ya està contingut en LCS(R₂, C₂). Com a resultat LCS(R₂, C₃) també conté a les dos seqüències (A) i (G)

Per a LCS(R₂, C₄), A és igual que A, llavors A s'anexa a la cela superior esquerre donant com a seqüència (GA)

Per a LCS(R₂, C₅), A no és igual que T. Es comparen les dos seqüències (GA) i (G). La seqüència més llarga que és (GA) es queda com a resultat

Files "G" & "A" Completeda
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	$\overset{↑}{\leftarrow}$ Ø	$\overset{↖}{}$ (G)	$\overset{}{\leftarrow}$ (G)	$\overset{}{\leftarrow}$ (G)	$\overset{}{\leftarrow}$ (G)
Ø	$\overset{↖}{}$ (A)	$\overset{↑}{\leftarrow}$ (A) & (G)	$\overset{↑}{\leftarrow}$ (A) & (G)	$\overset{↖}{}$ (GA)	$\overset{}{\leftarrow}$ (GA)
C	Ø

Per a LCS(R₃, C₁), C i A sò diferents, aixina que LCS(R₃, C₁) aplega a ser la seqüència més llarga que és, (A).

Per a LCS(R₃, C₂), C i G són diferents. Abdós LCS(R₃, C₁) i LCS(R₂, C₂) tenen un element. I dona com a resultat de LCS(R₃, C₂) les dos subsecuencias, (A) and (G).

Per a LCS(R₃, C₃), C i C són iguals, aixina que C s'anexa a LCS(R₂, C₂), la qual conté dos seqüències, (A) i (G), donant com a resultat (AC) i (GC).

Per a LCS(R₃, C₄), C i A no són iguals. Combinanado LCS(R₃, C₃), que conté (AC) i (GC), i LCS(R₂, C₄), que conté (GA), dona com a resultat tres seqüències: (AC), (GC), i (GA).

Finalment, per a LCS(R₃, C₅), C i T són diferents. Llavors LCS(R₃, C₅) també aplega a tindre tres seqüències, (AC), (GC), i (GA).

Taula LCS completada
	Ø	A	G	C	A	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	$\overset{↑}{\leftarrow}$ Ø	$\overset{↖}{}$ (G)	$\overset{}{\leftarrow}$ (G)	$\overset{}{\leftarrow}$ (G)	$\overset{}{\leftarrow}$ (G)
Ø	$\overset{↖}{}$ (A)	$\overset{↑}{\leftarrow}$ (A) & (G)	$\overset{↑}{\leftarrow}$ (A) & (G)	$\overset{↖}{}$ (GA)	$\overset{}{\leftarrow}$ (GA)
C	Ø	$\overset{↑}{}$ (A)	$\overset{↑}{\leftarrow}$ (A) & (G)	$\overset{↖}{}$ (AC) & (GC)	$\overset{↑}{\leftarrow}$ (AC) & (GC) & (GA)	$\overset{↑}{\leftarrow}$ (AC) & (GC) & (GA)

El resultat final és l'última cela que conté la subsecuencia comuna més llarga de (AGCAT) i (GAC); estos són (AC), (GC), i (GA). La taula també mostra que la subsecuencia comuna més llarga de totes les combinacions de prefixos. Per eixemple para (AGC) i (GA), la subsecuencia comuna més llarga són (A) i (G).

Reconstrucció de la solució

Calculant el LCS d'una fila de la taula solament requerix la fila actual i la fila anterior. Aixina i tot, per a les seqüències llargues, estes seqüències poden ser numeroses i llargues. Requerint grans cantitats d'espai d'almagasenament. L'espai d'almagasenament es pot reduir guardant solament la llongitut de la subsecuencia i la direcció de les fleches com es mostra a continuació.

Almagasenant llongitut i direcció
	Ø	A	G	C	A	T
Ø	0	0	0	0	0	0
G	0	$\overset{↑}{\leftarrow}$ 0	$\overset{↖}{}$ 1	$\overset{}{\leftarrow}$ 1	$\overset{}{\leftarrow}$ 1	$\overset{}{\leftarrow}$ 1
0	$\overset{↖}{}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↖}{}$ 2	$\overset{}{\leftarrow}$ 2
C	0	$\overset{↑}{}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↖}{}$ 2	$\overset{↑}{\leftarrow}$ 2	$\overset{↑}{\leftarrow}$ 2

Les subsecuencias poden ser deduïdes en una reconstrucció que seguix les fleches, escomençant per l'última cela de la taula. Quan la llongitut decreix, la subsecuencia obté un element comú. Com notem, varis camins són possibles quan es mostren dos fleches en la cela. A continuació es mostra l'anàlisis i els números de color són celes a on el seu número decreix. Els números en negreta reconstruïxen la seqüència (GA)^[4]

Eixemple de reconstrucció
	Ø	A	G	C	A	T
Ø	0	0	0	0	0	0
G	0	$\overset{↑}{\leftarrow}$ 0	$\overset{↖}{}$ 1	$\overset{}{\leftarrow}$ 1	$\overset{}{\leftarrow}$ 1	$\overset{}{\leftarrow}$ 1
0	$\overset{↖}{}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↖}{}$ 2	$\overset{}{\leftarrow}$ 2
C	0	$\overset{↑}{}$ 1	$\overset{↑}{\leftarrow}$ 1	$\overset{↖}{}$ 2	$\overset{↑}{\leftarrow}$ 2	$\overset{↑}{\leftarrow}$ 2

Referències

↑ 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.
↑ L. Bergroth and H. Hakonen and T. Raita(2000).«A Survey of Longest Common Subsequence Algorithms».SPIRE.IEEE Computer Society.00
39–48.doi:10.1109/SPIRE.2000.878178.
↑ arXiv:{{{arxiv}}}
↑ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). «15.4», Introduction to Algorithms, 2nd edició, MIT Press and McGraw-Hill, pp. 350–355. ISBN 0-262-53196-8.

Referències

Este artícul conté una traducció derivada de «Problema de subsecuencia común más larga» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[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.doi:10.1109/SPIRE.2000.878178.

[3] rXiv:{{{arxiv}}}

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

[1]

[2]

[3]

[4]