22

3 つ以上の文字列の最長共通部分列を見つけようとしています。ウィキペディアの記事には、2 つの文字列に対してこれを行う方法が詳しく説明されていますが、これを 3 つ以上の文字列に拡張する方法が少しわかりません。

2文字列のLCSを求めるライブラリはたくさんあるので、できればそのうちの1つを使いたいです。3 つの文字列 A、B、C がある場合、A と B の LCS を X として見つけてから、X と C の LCS を見つけることは有効ですか、それとも間違った方法ですか?

次のように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」のはずです。

4

5 に答える 5

32

漸化式を一般化するだけです。

3つのストリングの場合：

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

これからより多くの文字列に一般化するのは簡単なはずです。

于 2011-02-20T13:41:55.710 に答える
4

2 つの文字列 A と B の最長共通部分列 (LCS) を見つけるには、投稿したリンクに示されているように、2 次元配列を斜めにトラバースできます。配列内のすべての要素は、部分文字列 A' および B' の LCS を見つける問題に対応します (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;
}

私のコード例はさらに最適化できます。キャッシュされている文字列の多くは重複しており、一部の文字列は 1 文字だけ追加された重複しています。これは、入力文字列が大きくなると、必要以上のスペースを使用します。

入力時: "666222054263314443712"、"5432127413542377777"、"6664664565464057425"

返された LCS は「54442」です

于 2013-10-23T14:45:27.963 に答える