Maior subsequência comum de mais de 3 strings
-
15-11-2019 - |
Pergunta
Estou tentando encontrar a maior subsequência comum de 3 ou mais strings.O artigo da Wikipedia tem uma ótima descrição de como fazer isso para 2 cordas, mas não tenho certeza de como estender isso para 3 ou mais strings.
Existem muitas bibliotecas para encontrar o LCS de 2 strings, então gostaria de usar uma delas, se possível.Se eu tiver 3 strings A, B e C, é válido encontrar o LCS de A e B como X e depois encontrar o LCS de X e C, ou esta é a maneira errada de fazer isso?
Eu o implementei em Python da seguinte maneira:
import difflib
def lcs(str1, str2):
sm = difflib.SequenceMatcher()
sm.set_seqs(str1, str2)
matching_blocks = [str1[m.a:m.a+m.size] for m in sm.get_matching_blocks()]
return "".join(matching_blocks)
print reduce(lcs, ['abacbdab', 'bdcaba', 'cbacaa'])
Isso gera "ba", mas deveria ser "baa".
Solução
Apenas generalize a relação de recorrência.
Para três cordas:
dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise
Deve ser fácil generalizar para mais strings a partir disso.
Outras dicas
Para encontrar a maior subsequência comum (LCS) de 2 strings A e B, você pode percorrer uma matriz bidimensional diagonalmente, como mostrado no link que você postou.Cada elemento da matriz corresponde ao problema de encontrar o LCS das substrings A' e B' (A cortado pelo número da linha, B cortado pelo número da coluna).Este problema pode ser resolvido calculando o valor de todos os elementos da matriz.Você deve ter certeza de que, ao calcular o valor de um elemento da matriz, todos os subproblemas necessários para calcular esse valor específico já foram resolvidos.É por isso que você percorre a matriz bidimensional diagonalmente.
Esta solução pode ser dimensionada para encontrar a subsequência comum mais longa entre N strings, mas isso requer uma maneira geral de iterar uma matriz de N dimensões de modo que qualquer elemento seja alcançado somente quando todos os subproblemas para os quais o elemento requer uma solução tiverem sido resolvidos.
Em vez de iterar o array N-dimensional em uma ordem especial, você também pode resolver o problema recursivamente.Com a recursão é importante salvar as soluções intermediárias, pois muitas ramificações necessitarão das mesmas soluções intermediárias.Eu escrevi um pequeno exemplo em C# que faz isso:
string lcs(string[] strings)
{
if (strings.Length == 0)
return "";
if (strings.Length == 1)
return strings[0];
int max = -1;
int cacheSize = 1;
for (int i = 0; i < strings.Length; i++)
{
cacheSize *= strings[i].Length;
if (strings[i].Length > max)
max = strings[i].Length;
}
string[] cache = new string[cacheSize];
int[] indexes = new int[strings.Length];
for (int i = 0; i < indexes.Length; i++)
indexes[i] = strings[i].Length - 1;
return lcsBack(strings, indexes, cache);
}
string lcsBack(string[] strings, int[] indexes, string[] cache)
{
for (int i = 0; i < indexes.Length; i++ )
if (indexes[i] == -1)
return "";
bool match = true;
for (int i = 1; i < indexes.Length; i++)
{
if (strings[0][indexes[0]] != strings[i][indexes[i]])
{
match = false;
break;
}
}
if (match)
{
int[] newIndexes = new int[indexes.Length];
for (int i = 0; i < indexes.Length; i++)
newIndexes[i] = indexes[i] - 1;
string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]];
cache[calcCachePos(indexes, strings)] = result;
return result;
}
else
{
string[] subStrings = new string[strings.Length];
for (int i = 0; i < strings.Length; i++)
{
if (indexes[i] <= 0)
subStrings[i] = "";
else
{
int[] newIndexes = new int[indexes.Length];
for (int j = 0; j < indexes.Length; j++)
newIndexes[j] = indexes[j];
newIndexes[i]--;
int cachePos = calcCachePos(newIndexes, strings);
if (cache[cachePos] == null)
subStrings[i] = lcsBack(strings, newIndexes, cache);
else
subStrings[i] = cache[cachePos];
}
}
string longestString = "";
int longestLength = 0;
for (int i = 0; i < subStrings.Length; i++)
{
if (subStrings[i].Length > longestLength)
{
longestString = subStrings[i];
longestLength = longestString.Length;
}
}
cache[calcCachePos(indexes, strings)] = longestString;
return longestString;
}
}
int calcCachePos(int[] indexes, string[] strings)
{
int factor = 1;
int pos = 0;
for (int i = 0; i < indexes.Length; i++)
{
pos += indexes[i] * factor;
factor *= strings[i].Length;
}
return pos;
}
Meu exemplo de código pode ser otimizado ainda mais.Muitas das strings armazenadas em cache são duplicadas e algumas são duplicadas com apenas um caractere adicional adicionado.Isso usa mais espaço do que o necessário quando as strings de entrada ficam grandes.
Na entrada:"666222054263314443712", "5432127413542377777", "6664664565464057425"
O LCS retornado é "54442"
Eu só tive que fazer isso como lição de casa, então aqui está minha solução de programação dinâmica em python que é bastante eficiente.É O (nml) onde n, m e l são os comprimentos das três sequências.
A solução funciona criando uma matriz 3D e depois enumerando todas as três sequências para calcular o caminho da subsequência mais longa.Então você pode voltar atrás na matriz para reconstruir a subsequência real de seu caminho.
Portanto, você inicializa o array com zeros e depois enumera as três sequências.Em cada etapa da enumeração, você adiciona um ao comprimento da subsequência mais longa (se houver uma correspondência) ou simplesmente transfere a subsequência mais longa da etapa anterior da enumeração.
Depois que a enumeração for concluída, você poderá rastrear a matriz para reconstruir a subsequência a partir das etapas executadas.ou sejaà medida que você retrocede a partir da última entrada na matriz, cada vez que encontrar uma correspondência, você a procura em qualquer uma das sequências (usando a coordenada da matriz) e a adiciona à subsequência.
def lcs3(a, b, c):
m = len(a)
l = len(b)
n = len(c)
subs = [[[0 for k in range(n+1)] for j in range(l+1)] for i in range(m+1)]
for i, x in enumerate(a):
for j, y in enumerate(b):
for k, z in enumerate(c):
if x == y and y == z:
subs[i+1][j+1][k+1] = subs[i][j][k] + 1
else:
subs[i+1][j+1][k+1] = max(subs[i+1][j+1][k],
subs[i][j+1][k+1],
subs[i+1][j][k+1])
# return subs[-1][-1][-1] #if you only need the length of the lcs
lcs = ""
while m > 0 and l > 0 and n > 0:
step = subs[m][l][n]
if step == subs[m-1][l][n]:
m -= 1
elif step == subs[m][l-1][n]:
l -= 1
elif step == subs[m][l][n-1]:
n -= 1
else:
lcs += str(a[m-1])
m -= 1
l -= 1
n -= 1
return lcs[::-1]
O código abaixo pode encontrar a subsequência comum mais longa em N strings.Isso usa itertools para gerar as combinações de índices necessárias e, em seguida, usa esses índices para encontrar substring comum.
Exemplo de execução:
Entrada:
Insira o número de sequências:3
Insira a sequência 1:83217
Insira a sequência 2:8213897
Insira a sequência 3:683147
Saída:
837
from itertools import product
import numpy as np
import pdb
def neighbors(index):
N = len(index)
for relative_index in product((0, -1), repeat=N):
if not all(i == 0 for i in relative_index):
yield tuple(i + i_rel for i, i_rel in zip(index, relative_index))
def longestCommonSubSequenceOfN(sqs):
numberOfSequences = len(sqs);
lengths = np.array([len(sequence) for sequence in sqs]);
incrLengths = lengths + 1;
lengths = tuple(lengths);
inverseDistances = np.zeros(incrLengths);
ranges = [tuple(range(1, length+1)) for length in lengths[::-1]];
for tupleIndex in product(*ranges):
tupleIndex = tupleIndex[::-1];
neighborIndexes = list(neighbors(tupleIndex));
operationsWithMisMatch = np.array([]);
for neighborIndex in neighborIndexes:
operationsWithMisMatch = np.append(operationsWithMisMatch, inverseDistances[neighborIndex]);
operationsWithMatch = np.copy(operationsWithMisMatch);
operationsWithMatch[-1] = operationsWithMatch[-1] + 1;
chars = [sqs[i][neighborIndexes[-1][i]] for i in range(numberOfSequences)];
if(all(elem == chars[0] for elem in chars)):
inverseDistances[tupleIndex] = max(operationsWithMatch);
else:
inverseDistances[tupleIndex] = max(operationsWithMisMatch);
# pdb.set_trace();
subString = "";
mainTupleIndex = lengths;
while(all(ind > 0 for ind in mainTupleIndex)):
neighborsIndexes = list(neighbors(mainTupleIndex));
anyOperation = False;
for tupleIndex in neighborsIndexes:
current = inverseDistances[mainTupleIndex];
if(current == inverseDistances[tupleIndex]):
mainTupleIndex = tupleIndex;
anyOperation = True;
break;
if(not anyOperation):
subString += str(sqs[0][mainTupleIndex[0] - 1]);
mainTupleIndex = neighborsIndexes[-1];
return subString[::-1];
numberOfSequences = int(input("Enter the number of sequences: "));
sequences = [input("Enter sequence {} : ".format(i)) for i in range(1, numberOfSequences + 1)];
print(longestCommonSubSequenceOfN(sequences));