Problema de subsequência comum mais longo - Longest common subsequence problem

Comparação de duas revisões de um arquivo de exemplo, com base em sua maior subsequência comum (preto)

O maior subsequência comum ( LCS ) problema é o problema de encontrar o maior subsequência comum a todas as seqüências em um conjunto de seqüências (frequentemente apenas duas sequências). Ele difere do mais longo problema comum de substrings : ao contrário de substrings, subsequências não precisam ocupar posições consecutivas dentro das sequências originais. O problema de subsequência comum mais longo é um problema clássico de ciência da computação , a base de programas de comparação de dados , como o utilitário diff , e tem aplicações em linguística computacional e bioinformática . Também é amplamente utilizado porsistemas de controle de revisão , como o Git, para reconciliar várias alterações feitas em uma coleção de arquivos controlada por revisão.

Por exemplo, considere as sequências (ABCD) e (ACBAD). Eles têm 5 comprimento-2 subseqüências comuns: (AB), (AC), (AD), (BD) e (CD); 2 comprimento-3 subsequências comuns: (ABD) e (ACD); e não mais subseqüências comuns. Portanto, (ABD) e (ACD) são suas subsequências comuns mais longas.

Complexidade

Para o caso geral de um número arbitrário de sequências de entrada, o problema é NP-difícil . Quando o número de sequências é constante, o problema pode ser resolvido em tempo polinomial por programação dinâmica .

Dadas sequências de comprimentos , uma pesquisa ingênua testaria cada uma das subsequências da primeira sequência para determinar se elas também são subsequências das sequências restantes; cada subsequência pode ser testada no tempo linear nos comprimentos das sequências restantes, então o tempo para este algoritmo seria ${\ displaystyle N}$ ${\ displaystyle n_ {1}, ..., n_ {N}}$ ${\ displaystyle 2 ^ {n_ {1}}}$

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

Para o caso de duas sequências de n e m elementos, o tempo de execução da abordagem de programação dinâmica é O ( n × m ). Para um número arbitrário de sequências de entrada, a abordagem de programação dinâmica oferece uma solução em

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

Existem métodos com menor complexidade, que muitas vezes dependem do comprimento do LCS, do tamanho do alfabeto ou de ambos.

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

Solução para duas sequências

O problema LCS tem uma subestrutura ótima : o problema pode ser dividido em subproblemas menores e mais simples, que podem, por sua vez, ser decompostos em subproblemas mais simples, e assim por diante, até que, finalmente, a solução se torne trivial. LCS, em particular, tem subproblemas sobrepostos : as soluções para subproblemas de alto nível frequentemente reutilizam soluções para subproblemas de nível inferior. Problemas com essas duas propriedades são passíveis de programação dinâmica se aproxima, em que as soluções dos subproblemas são memoized , isto é, as soluções de subproblemas são guardados para reutilização.

Prefixos

O prefixo S _n de S é definida como os primeiros n caracteres de S . Por exemplo, os prefixos de S = (AGCA) são

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA).

Deixe LCS ( X , Y ) ser uma função que calcula um comum maior subsequência para X e Y . Essa função tem duas propriedades interessantes.

Primeira propriedade

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y ) ^ A , para todas as strings X , Y e todos os símbolos A , onde ^ denota a concatenação de strings. Isso permite simplificar o cálculo LCS para duas sequências que terminam no mesmo símbolo. Por exemplo, LCS ("BANANA", "ATANA") = LCS ("BANAN", "ATAN") ^ "A", Continuando para os símbolos comuns restantes, LCS ("BANANA", "ATANA") = LCS (" BAN "," AT ") ^" ANA ".

Segunda propriedade

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

Por exemplo, LCS ("ABCDEFG", "BCDGK") é a cadeia mais longa entre LCS ("ABCDEFG", "BCDG") e LCS ("ABCDEF", "BCDGK"); se ambos tivessem o mesmo comprimento, um deles poderia ser escolhido arbitrariamente.

Para realizar a propriedade, diferencie 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").

Função LCS definida

Sejam duas sequências definidas como segue: e . Os prefixos de são ; os prefixos de são . Deixe representar o conjunto da maior subsequência comum de prefixos e . Este conjunto de sequências é dado a seguir. ${\ displaystyle X = (x_ {1} x_ {2} \ cdots x_ {m})}$ ${\ displaystyle Y = (y_ {1} y_ {2} \ cdots y_ {n})}$ ${\ displaystyle X}$ ${\ displaystyle X_ {1,2, \ dots, m}}$ ${\ displaystyle Y}$ ${\ displaystyle Y_ {1,2, \ dots, n}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j})}$ ${\ displaystyle X_ {i}}$ ${\ displaystyle Y_ {j}}$

{\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j}) = {\ begin {cases} \ emptyset & {\ mbox {if}} i = 0 {\ mbox {ou}} j = 0 \\ {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1}) {\ hat {}} x_ {i} & {\ mbox {if}} 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 {if}} i, j> 0 {\ mbox {e}} x_ {i} \ neq y_ {j}. \ End {casos}}}

Para encontrar o LCS de e , compare e . Se eles forem iguais, a sequência é estendida por esse elemento ,. Se eles não forem iguais, então o mais longo entre as duas sequências , e , é retido. (Se eles tiverem o mesmo comprimento, mas não idênticos, ambos serão mantidos.) ${\ displaystyle X_ {i}}$ ${\ displaystyle Y_ {j}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {j}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j-1})}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i}, Y_ {j-1})}$ ${\ displaystyle {\ mathit {LCS}} (X_ {i-1}, Y_ {j})}$

Exemplo trabalhado

A maior subsequência comum a R = (GAC) e C = (AGCAT) será encontrada. Como a função LCS usa um elemento "zero", é conveniente definir prefixos zero que estão vazios para essas sequências: R ₀ = Ø; e C ₀ = Ø. Todos os prefixos são colocados numa mesa com C na primeira linha (tornando-o um c olumn cabeçalho) e R na primeira coluna (tornando-o uma r OW cabeçalho).

LCS Strings
	Ø	UMA	G	C	UMA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø
UMA	Ø
C	Ø

Esta tabela é usada para armazenar a sequência LCS para cada etapa do cálculo. A segunda coluna e a segunda linha foram preenchidas com Ø, porque quando uma sequência vazia é comparada com uma sequência não vazia, a maior subsequência comum é sempre uma sequência vazia.

LCS ( R ₁ , C ₁ ) é determinado comparando os primeiros elementos em cada sequência. G e A não são iguais, então este LCS obtém (usando a "segunda propriedade") a mais longa das duas sequências, LCS ( R ₁ , C ₀ ) e LCS ( R ₀ , C ₁ ). De acordo com a tabela, ambos estão vazios, portanto LCS ( R ₁ , C ₁ ) também está vazio, conforme mostrado na tabela abaixo. As setas indicam que a sequência vem tanto da célula acima, LCS ( R ₀ , C ₁ ) e da célula à esquerda, LCS ( R ₁ , C ₀ ).

LCS ( R ₁ , C ₂ ) é determinado comparando G e G. Eles correspondem, então G é anexado à sequência superior esquerda, LCS ( R ₀ , C ₁ ), que é (Ø), dando (ØG), que é (G).

Para LCS ( R ₁ , C ₃ ), G e C não correspondem. A sequência acima está vazia; o que está à esquerda contém um elemento, G. Selecionando o mais longo deles, LCS ( R ₁ , C ₃ ) é (G). A seta aponta para a esquerda, pois é a mais longa das duas sequências.

LCS ( R ₁ , C ₄ ), da mesma forma, é (G).

LCS ( R ₁ , C ₅ ), da mesma forma, é (G).

Linha "G" concluída
	Ø	UMA	G	C	UMA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
UMA	Ø
C	Ø

Para LCS ( R ₂ , C ₁ ), A é comparado com A. Os dois elementos combinam, então A é anexado a Ø, dando (A).

Para LCS ( R ₂ , C ₂ ), A e G não correspondem, então o mais longo de LCS ( R ₁ , C ₂ ), que é (G), e LCS ( R ₂ , C ₁ ), que é (A ), é usado. Nesse caso, cada um deles contém um elemento, então este LCS recebe duas subsequências: (A) e (G).

Para LCS ( R ₂ , C ₃ ), A não corresponde a C. LCS ( R ₂ , C ₂ ) contém as sequências (A) e (G); LCS ( R ₁ , C ₃ ) é (G), que já está contido em LCS ( R ₂ , C ₂ ). O resultado é que LCS ( R ₂ , C ₃ ) também contém as duas subsequências, (A) e (G).

Para LCS ( R ₂ , C ₄ ), A corresponde a A, que é anexado à célula superior esquerda, dando (GA).

Para LCS ( R ₂ , C ₅ ), A não corresponde a T. Comparando as duas sequências, (GA) e (G), a mais longa é (GA), então LCS ( R ₂ , C ₅ ) é (GA).

Linhas "G" e "A" concluídas
	Ø	UMA	G	C	UMA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
UMA	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (UMA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) e (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) e (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø

Para LCS ( R ₃ , C ₁ ), C e A não correspondem, então LCS ( R ₃ , C ₁ ) obtém a mais longa das duas sequências, (A).

Para LCS ( R ₃ , C ₂ ), C e G não correspondem. Ambos LCS ( R ₃ , C ₁ ) e LCS ( R ₂ , C ₂ ) têm um elemento. O resultado é que LCS ( R ₃ , C ₂ ) contém as duas subsequências, (A) e (G).

Para LCS ( R ₃ , C ₃ ), C e C coincidem, então C é anexado a LCS ( R ₂ , C ₂ ), que contém as duas subsequências, (A) e (G), dando (AC) e (GC )

Para LCS ( R ₃ , C ₄ ), C e A não correspondem. Combinando LCS ( R ₃ , C ₃ ), que contém (AC) e (GC), e LCS ( R ₂ , C ₄ ), que contém (GA), dá um total de três sequências: (AC), (GC) , e (GA).

Finalmente, para LCS ( R ₃ , C ₅ ), C e T não correspondem. O resultado é que LCS ( R ₃ , C ₅ ) também contém as três sequências, (AC), (GC) e (GA).

Tabela LCS concluída
	Ø	UMA	G	C	UMA	T
Ø	Ø	Ø	Ø	Ø	Ø	Ø
G	Ø	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (G)
UMA	Ø	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (UMA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) e (G)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) e (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (GA)	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ (GA)
C	Ø	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ (UMA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (A) e (G)	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ (AC) e (GC)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) e (GC) e (GA)	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ (AC) e (GC) e (GA)

O resultado final é que a última célula contém todas as subsequências mais longas comuns a (AGCAT) e (GAC); estes são (AC), (GC) e (GA). A tabela também mostra as subseqüências comuns mais longas para cada par possível de prefixos. Por exemplo, para (AGC) e (GA), a maior subsequência comum é (A) e (G).

Abordagem Traceback

Calcular o LCS de uma linha da tabela LCS requer apenas as soluções para a linha atual e a linha anterior. Ainda assim, para sequências longas, essas sequências podem ser numerosas e longas, exigindo muito espaço de armazenamento. O espaço de armazenamento pode ser economizado salvando não as subsequências reais, mas o comprimento da subsequência e a direção das setas, como na tabela abaixo.

Armazenamento de comprimento, em vez de sequências
	UMA	G	C	UMA	T
Ø	0	0	0	0	0
G	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 0	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1
UMA	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 2
C	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2

As subsequências reais são deduzidas em um procedimento de "rastreamento" que segue as setas para trás, começando da última célula da tabela. Quando o comprimento diminui, as sequências devem ter um elemento comum. Vários caminhos são possíveis quando duas setas são mostradas em uma célula. Abaixo está a tabela para tal análise, com números coloridos nas células onde o comprimento está prestes a diminuir. Os números em negrito traçam a sequência, (GA).

Exemplo de traceback
	UMA	G	C	UMA	T
Ø	0	0	0	0	0
G	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 0	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 1
UMA	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\} {\ leftarrow}}}$ 2
C	${\ displaystyle {\ overset {\ \ uparrow} {\}}}$ 1	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 1	${\ displaystyle {\ overset {\ nwarrow} {\}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2	${\ displaystyle {\ overset {\ \ \ uparrow} {\ leftarrow}}}$ 2

Relação com outros problemas

Para duas strings e , o comprimento da supersequência comum mais curta está relacionado ao comprimento do LCS por ${\ displaystyle X_ {1 \ dots m}}$ ${\ displaystyle Y_ {1 \ dots n}}$

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

A distância de edição quando apenas a inserção e exclusão são permitidas (sem substituição), ou quando o custo da substituição é o dobro do custo de uma inserção ou exclusão, é:

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

Código para a solução de programação dinâmica

Calculando o comprimento do LCS

A função abaixo recebe como sequências de entrada X[1..m]e Y[1..n], calcula o LCS entre X[1..i]e Y[1..j]para todos 1 ≤ i ≤ me 1 ≤ j ≤ n, e o armazena em C[i,j]. C[m,n]conterá o comprimento do LCS de Xe 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, memoização pode ser usada.

Exemplo em C #

static int[,] LcsLength(string a, string b)
{
    int[,] C = new int[a.Length + 1, b.Length + 1]; // (a, b).Length + 1
    for (int i = 0; i < a.Length; i++)
        C[i, 0] = 0;
    for (int j = 0; j < b.Length; j++)
        C[0, j] = 0;
    for (int i = 1; i <= a.Length; i++)
        for (int j = 1; j <= b.Length; j++)
        {
            if (a[i - 1] == b[j - 1])//i-1,j-1
                C[i, j] = C[i - 1, j - 1] + 1;
            else
                C[i, j] = Math.Max(C[i, j - 1], C[i - 1, j]);
        }
    return C;
}

Lendo um LCS

A função a seguir rastreia as escolhas feitas ao calcular a Ctabela. Se os últimos caracteres nos prefixos forem iguais, eles devem estar em um LCS. Caso contrário, verifique o que deu o maior LCS de manutenção e , e faça a mesma escolha. Basta escolher um se forem igualmente longos. Chame a função com e . ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {j}}$ i=mj=n

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

Exemplo em C #

string Backtrack(int[,] C, char[] aStr, char[] bStr, int x, int y)
{
    if (x == 0 | y == 0)
        return "";
    if (aStr[x - 1] == bStr[y - 1]) // x-1, y-1
        return backtrack(C, aStr, bStr, x - 1, y - 1) + aStr[x - 1]; // x-1
    if (C[x, y - 1] > C[x - 1, y])
        return backtrack(C, aStr, bStr, x, y - 1);
    return backtrack(C, aStr, bStr, x - 1, y);
}

Lendo todos os LCSs

Se escolher e der um resultado igualmente longo, leia as duas subseqüências resultantes. Isso é retornado como um conjunto por esta função. Observe que essa função não é polinomial, pois ela pode se ramificar em quase todas as etapas se as strings forem semelhantes. ${\ displaystyle x_ {i}}$ ${\ displaystyle y_ {j}}$

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j)
    if i = 0 or j = 0
        return {""}
    if X[i] = Y[j]
        return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)}
    R := {}
    if C[i,j-1] ≥ C[i-1,j]
        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

Imprima o diff

Esta função retrocederá pela matriz C e imprimirá a diferença entre as duas sequências. Observe que você obterá uma resposta diferente se trocar ≥e <, com >e ≤abaixo.

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 ""

Exemplo

Seja “ ” e seja “ ”. A maior subsequência comum entre e é “ ”. A tabela mostrada abaixo, que é gerada pela função , mostra os comprimentos das maiores subsequências comuns entre os prefixos de e . A linha e a coluna mostram o comprimento do LCS entre e . ${\ displaystyle X}$ XMJYAUZ ${\ displaystyle Y}$ MZJAWXU ${\ displaystyle X}$ ${\ displaystyle Y}$ MJAUCLCSLength ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle i}$ ${\ displaystyle j}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j}}$

		0	1	2	3	4	5	6	7
		Ø	M	Z	J	UMA	C	X	você
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	UMA	0	1	1	2	3	3	3	3
6	você	0	1	1	2	3	3	3	4
7	Z	0	1	2	2	3	3	3	4

Os números destacados mostram o caminho que a função backtrackseguiria do canto inferior direito ao canto superior esquerdo, ao ler um LCS. Se os símbolos atuais em e são iguais, eles fazem parte do LCS e vamos para cima e para a esquerda (mostrado em negrito ). Do contrário, subimos ou saímos, dependendo de qual célula tiver um número maior. Isso corresponde a tomar o LCS entre e , ou e . ${\ displaystyle X}$ ${\ displaystyle Y}$ ${\ displaystyle X_ {1..i-1}}$ ${\ displaystyle Y_ {1..j}}$ ${\ displaystyle X_ {1..i}}$ ${\ displaystyle Y_ {1..j-1}}$

Otimização de código

Várias otimizações podem ser feitas no algoritmo acima para acelerá-lo para casos do mundo real.

Reduza o conjunto de problemas

A matriz C no algoritmo ingênuo cresce quadraticamente com os comprimentos das sequências. Para duas sequências de 100 itens, uma matriz de 10.000 itens seria necessária e 10.000 comparações precisariam ser feitas. Na maioria dos casos do mundo real, especialmente diffs e patches de código-fonte, o início e o fim dos arquivos raramente mudam, e quase certamente não os dois ao mesmo tempo. Se apenas alguns itens foram alterados no meio da sequência, o início e o fim podem ser eliminados. Isso reduz não apenas os requisitos de memória para a matriz, mas também o número de comparações que devem ser feitas.

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

Na melhor das hipóteses, uma sequência sem alterações, essa otimização eliminaria completamente a necessidade da matriz C. No pior cenário, uma mudança nos primeiros e nos últimos itens da sequência, apenas duas comparações adicionais são realizadas.

Reduza o tempo de comparação

A maior parte do tempo gasto pelo algoritmo ingênuo é gasto na realização de comparações entre itens nas sequências. Para sequências textuais, como código-fonte, você deseja visualizar as linhas como os elementos da sequência em vez de caracteres únicos. Isso pode significar comparações de strings relativamente longas para cada etapa do algoritmo. Duas otimizações podem ser feitas para ajudar a reduzir o tempo que essas comparações consomem.

Reduza strings para hashes

Uma função hash ou checksum pode ser usada para reduzir o tamanho das strings nas sequências. Ou seja, para o código-fonte em que a linha média tem 60 ou mais caracteres, o hash ou checksum dessa linha pode ter apenas 8 a 40 caracteres. Além disso, a natureza aleatória dos hashes e somas de verificação garantiria que as comparações entrariam em curto-circuito mais rápido, já que as linhas do código-fonte raramente serão alteradas no início.

Existem três desvantagens principais para essa otimização. Primeiro, uma quantidade de tempo precisa ser gasta de antemão para pré-calcular os hashes para as duas sequências. Em segundo lugar, memória adicional precisa ser alocada para as novas sequências em hash. No entanto, em comparação com o algoritmo ingênuo usado aqui, essas duas desvantagens são relativamente mínimas.

A terceira desvantagem são as colisões . Como a soma de verificação ou hash não é garantida como única, há uma pequena chance de que dois itens diferentes possam ser reduzidos ao mesmo hash. Isso é improvável no código-fonte, mas é possível. Um hash criptográfico seria, portanto, muito mais adequado para essa otimização, pois sua entropia será significativamente maior do que uma simples soma de verificação. No entanto, os benefícios podem não valer a pena a configuração e os requisitos computacionais de um hash criptográfico para pequenos comprimentos de sequência.

Reduza o espaço necessário

Se apenas o comprimento do LCS for necessário, a matriz pode ser reduzida a uma matriz com facilidade ou a um vetor (mais inteligente), pois a abordagem de programação dinâmica precisa apenas das colunas atuais e anteriores da matriz. O algoritmo de Hirschberg permite a construção da própria sequência ótima no mesmo tempo quadrático e limites de espaço linear. ${\ displaystyle 2 \ times \ min (n, m)}$ ${\ displaystyle \ min (m, n) +1}$

Algoritmos otimizados adicionais

Existem vários algoritmos que funcionam mais rápido do que a abordagem de programação dinâmica apresentada. Um deles é o algoritmo Hunt – Szymanski , que normalmente é executado no tempo (para ), onde é o número de correspondências entre as duas sequências. Para problemas com um tamanho de alfabeto limitado, o Método dos Quatro Russos pode ser usado para reduzir o tempo de execução do algoritmo de programação dinâmica por um fator logarítmico. ${\ displaystyle O ((n + r) \ log (n))}$ ${\ displaystyle n> m}$ ${\ displaystyle r}$

Comportamento em strings aleatórias

Começando com Chvátal & Sankoff (1975) , vários pesquisadores investigaram o comportamento do maior comprimento de subsequência comum quando as duas cadeias de caracteres fornecidas são tiradas aleatoriamente do mesmo alfabeto. Quando o tamanho do alfabeto é constante, o comprimento esperado do LCS é proporcional ao comprimento das duas strings, e as constantes de proporcionalidade (dependendo do tamanho do alfabeto) são conhecidas como constantes Chvátal – Sankoff . Seus valores exatos não são conhecidos, mas os limites superior e inferior de seus valores foram comprovados, e sabe-se que eles crescem inversamente proporcionalmente à raiz quadrada do tamanho do alfabeto. Demonstrou-se que modelos matemáticos simplificados do maior problema de subsequência comum são controlados pela distribuição Tracy – Widom .

Languages

In other projects

Problema de subsequência comum mais longo - Longest common subsequence problem

Conteúdo

Complexidade

Solução para duas sequências

Prefixos

Primeira propriedade

Segunda propriedade

Função LCS definida

Exemplo trabalhado

Abordagem Traceback

Relação com outros problemas

Código para a solução de programação dinâmica

Calculando o comprimento do LCS

Exemplo em C #

Lendo um LCS

Exemplo em C #

Lendo todos os LCSs

Imprima o diff

Exemplo

Otimização de código

Reduza o conjunto de problemas

Reduza o tempo de comparação

Reduza strings para hashes

Reduza o espaço necessário

Algoritmos otimizados adicionais

Comportamento em strings aleatórias

Veja também

Referências

links externos