Самая длинная общая подпоследовательность из 3+ строк

Question

Я пытаюсь найти самую длинную общую подпоследовательность из 3 или более строк. В статье Википедии есть отличное описание , как это сделать для 2 строк , но я немного не уверен, как расширить это до 3 или более строк.

Существует множество библиотек для поиска LCS из 2 строк, поэтому я хотел бы использовать одну из них, если это возможно. Если у меня есть 3 строки A, B и C, допустимо ли найти LCS для A и B как X, а затем найти LCS для X и C, или это неправильный способ сделать это?

Я реализовал это в Python следующим образом:

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'])

Это выводит "ba", однако это должно быть "baa".

Answer 1

Просто обобщите рекуррентное соотношение.

Для трех строк:

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

Должно быть легко обобщить несколько строк из этого.

Answer 2

Чтобы найти самую длинную общую подпоследовательность (LCS) из 2 строк A и B, вы можете пройти по 2-мерному массиву по диагонали, как показано в размещенной вами ссылке.Каждый элемент в массиве соответствует задаче нахождения LCS подстрок A 'и B' (A вырезано по номеру строки, B вырезано по номеру столбца).Эта проблема может быть решена путем вычисления значения всех элементов в массиве.Вы должны быть уверены, что при вычислении значения элемента массива все подзадачи, необходимые для вычисления данного значения, уже решены.Вот почему вы пересекаете 2-мерный массив по диагонали.

Это решение можно масштабировать, чтобы найти самую длинную общую подпоследовательность между N строками, но для этого требуется общий способ итерации массива из N измерений, чтобы любой элементдостигается только тогда, когда все подзадачи, решение которых требует элемент, были решены.

Вместо итерации N-мерного массива в специальном порядке, вы также можете решить задачу рекурсивно.При рекурсии важно сохранить промежуточные решения, поскольку многим ветвям потребуются одинаковые промежуточные решения.Я написал небольшой пример на C #, который делает это:

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

Мой пример кода может быть оптимизирован в дальнейшем.Многие из кэшируемых строк являются дубликатами, а некоторые являются дубликатами с добавлением только одного дополнительного символа.Это занимает больше места, чем необходимо, когда входные строки становятся большими.

На входе: "666222054263314443712", "5432127413542377777", "6664664565464057425"

Возвращено значение LCS "54442"

Answer 3

Мне просто нужно было сделать это для домашней работы, так что вот мое решение для динамического программирования на python, которое довольно эффективно. Это O (nml), где n, m и l - длины трех последовательностей.

Решение работает путем создания трехмерного массива, а затем перечисления всех трех последовательностей для расчета пути самой длинной подпоследовательности. Затем вы можете вернуться через массив, чтобы восстановить фактическую подпоследовательность по ее пути.

Итак, вы инициализируете массив всеми нулями, а затем перечислите три последовательности. На каждом шаге перечисления вы либо добавляете единицу к длине самой длинной подпоследовательности (если есть совпадение), либо просто переносите самую длинную подпоследовательность из предыдущего шага перечисления.

Как только перечисление завершено, вы можете проследить обратно через массив, чтобы восстановить подпоследовательность из шагов, которые вы сделали. т.е. когда вы перемещаетесь назад от последней записи в массиве, каждый раз, когда вы встречаете совпадение, вы просматриваете его в любой из последовательностей (используя координату из массива) и добавляете его в подпоследовательность.

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

Этот код ниже может найти самую длинную общую подпоследовательность в N строках.При этом используются itertools для создания требуемых комбинаций индексов, а затем используются эти индексы для поиска общей подстроки.

Пример выполнения:
Ввод:
Введите число последовательностей: 3
Введите последовательность 1: 83217
Введите последовательность 2: 8213897
Введите последовательность 3: 683147

Выход:
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));