Maior subsequência comum

Predefinição:Wikificação O problema da maior subsequência comum(LCS) é sobre achar a maior subsequência em todas as sequências em um conjunto de sequências(normalmente duas). O problema da maior subsequência comum é um clássico da ciência da computação, é a base de programas de comparação de dados como o diff, e tem aplicações em computação linguística e bioinformática. Também é amplamente usado em sistemas de versionamento como Git para mesclar múltiplas mudanças feitas em arquivos.

Por exemplo, considere as sequências $ABCD$ e $ACBAD$. Ambos têm 5 subsequências comuns de tamanho 2: $AB$, $AC$, $BD$ e $CD$; e 2 subsequências comuns de tamanho 3: $ABD$ e $ACD$. Então $ABD$ e $ACD$ são as maiores subsequências comuns.

Complexidade

Para os casos gerais de um número arbitrário de sequências, o problema é NP-difícil(veja complexidade de tempo). E quando o número de sequências é constante, pode ser resolvido em tempo polinomial com uso da programação dinâmica.

Dado $N$ sequências de tamanho $n_1,...,n_N$, uma pesquisa pode testar cada uma das $2^{n_1}$ subsequências da primeira sequência para determinar se é também subsequência das sequências restantes; cada subsequência pode ser testada em tempo linear nos tamanhos das sequências, então o tempo para isso seria:

$O\left(2^{n_1}\sum _{i>1}{n}_i\right)$

Para o caso das 2 sequências de $n$ e $m$ elementos, o tempo de processamento usando a programação dinâmica seria $O(nm)$. Para um número arbitrário de sequências, a programação dinâmica nos daria a solução em

$O\left(N\prod _{i=1}^N{n}_i\right)$

Existem métodos com menor complexidade, que geralmente necessitam do tamanho do LCS, ou tamanho do alfabeto quando não ambos.

O LCS não é necessariamente exclusivo; no pior caso, o número de subsequências comuns é exponencial nos tamanhos das sequências, então a complexidade deve ser pelo menos exponencial.

Solução para duas sequências

O problema LCS tem uma estrutura ideal: o problema pode ser quebrado em partes menores; problemas mais simples, que podem ser quebrados em menores; e então, a solução se torna trivial. O LCS em particular permite que soluções complexas possam ser quebradas em soluções mais simples e reutilizáveis. Problemas com essas características podem ser abordados com a programação dinâmica, em que as soluções para problemas menores podem ser memorizadas e reutilizadas

Prefixos

O prefixo $S_n$ de $S$ é definido como os $n$ primeiros caracteres de $S$. Por exemplo, os prefixos de $S=AGCA$ são:

$S_0=\text{nenhum}$

$S_1=A$

$S_2=AG$

$S_3=AGC$

$S_4=AGCA$

Considere que $LCS(X,Y)$ seja uma função que compute a maior subsequência comum de $X$ e $Y$. Esta função tem duas propriedades muito interessantes.

Primeira propriedade

$LCS(X\stackrel{}{^}A,Y\stackrel{}{^}A)=LCS(X,Y)\stackrel{}{^}A$, para todas as strings $X$, $Y$ e todos os símbolos $A$, onde '^' representa a concatenação de strings. Isso permite simplificar o processo de LCS para as duas sequências que terminam com o mesmo símbolo. Por exemplo, LCS("BANANA","ATANA") = LCS("BANAN","ATAN")^A, continuam com o mesmo símbolo comum, LCS("BANANA","ATANA") = LCS("BAN","AT")^"ANA".

Segunda propriedade

Se $A$ e $B$ são símbolos distintos ($A\ne B$), então $LCS(X\stackrel{}{^}A,Y\stackrel{}{^}B)$ é uma das strings de tamanho máximo no conjunto $\{LCS(X\stackrel{}{^}A,Y),LCS(X,Y\stackrel{}{^}B)\}$, para todas as strings $X$, $Y$.

Por exemplo, LCS ("ABCDEFG", "BCDGK") é a sequência mais longa de <mathLCS ("ABCDEFG", "BCDG") e LCS ("ABCDEF", "BCDGK"); se ambos tivessem o mesmo comprimento, um deles poderia ser escolhido arbitrariamente.

Para prosseguir, diferencie os dois casos:

Se LCS ("ABCDEFG", "BCDGK") termina com um "G", então o "K" final não pode estar no LCS, portanto LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEFG", "BCDG ").

Se LCS ("ABCDEFG", "BCDGK") não terminar com um "G", então o "G" final não pode estar no LCS, portanto, LCS ("ABCDEFG", "BCDGK") = LCS ("ABCDEF", "BCDGK").

Definição da função

Considere duas sequências definidas da seguinte forma: $X=(x_1,X_2,...,X_m)$ e $Y=(Y_1,Y_2,...,Y_n)$. Os prefixos de $X$ são $X_1,X_2,...,m$; os prefixos de $Y$ são $Y_1,Y_2,...,n$. Considere que $LCS(X_i,Y_j)$ represente o conjunto das maiores subsequências comuns dos prefixos $X_i$ e $Y_j$. Esse conjunto de subsequências é dado por:

$𝐿𝐶𝑆(X_i,Y_j)=\{\begin{array}{cc}\mathrm{\varnothing }& \text{se }i=0\text{ ou }j=0\\ 𝐿𝐶𝑆(X_{i-1},Y_{j-1})\stackrel{}{^}{x}_i& \text{se }i,j>0\text{ e }{x}_i=y_j\\ \max \{𝐿𝐶𝑆(X_i,Y_{j-1}),𝐿𝐶𝑆(X_{i-1},Y_j)\}& \text{se }i,j>0\text{ e }{x}_i\ne y_j\end{array}$

Para achar o LCS de $X_i$ e $Y_j$, compare $x_i$ e $y_j$. Se forem iguais, então a sequência $LCS(X_{i-1},Y_j)$ é estendida pelo elemento $x_i$. Se não forem iguais, então a mais longa das duas sequências, $LCS(X_i,Y_{j-1})$ e $LCS(X_{i-1},Y_j)$ é retida. (Se forem do mesmo tamanho mas não idênticas, ambas serão retidas)