Maior subsequência comum de mais de 3 strings

Question

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

Answer 1

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.

Answer 2

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"

Answer 3

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]

Answer 4

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));