Maior subsequência comum

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{\hat {}}A,Y{\hat {}}A)=LCS(X,Y){\hat {}}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\neq {}B$), então $LCS(X{\hat {}}A,Y{\hat {}}B)$ é uma das strings de tamanho máximo no conjunto $\{LCS(X{\hat {}}A,Y),LCS(X,Y{\hat {}}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:

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\emptyset &{\mbox{se }}i=0{\mbox{ ou }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{se }}i,j>0{\mbox{ e }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{se }}i,j>0{\mbox{ e }}x_{i}\neq y_{j}\end{cases}}}$

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)