スマートフォン用の表示で見る

最長共通部分列

サイエンス

最長共通部分列

さいちょうきょうつうぶぶんれつ

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のこと。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と呼ぶ。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と呼ぶ。

  • X = <A, B, C, B, D, A, B>
  • Y = <B, D, C, A, B, A>

という二つの系列から得られる LCS

  • <B, C, B, A>

で、その長さは 4 である。長さ 2 の<B, D> の長さ 3 の <A, B, A> なども共通部分列だが、最長ではないのでこれらは LCS ではない。LCS は最長であれば位置はどこでも良いので、この場合 <B, D, B, A> も LCS である。

LCS動的計画法 (Dynamic Programmming, DP) を利用すると効率良く求めることができることが知られている。以下は Python によるその実装例である。

#!/usr/bin/env pyton
import sys

def print_lcs (a, b, lcs, i, j):
    if (i == 0 or j == 0):
        return
    if (a[i-1] == b[j-1]):
        print_lcs(a, b, lcs, i - 1, j - 1)
        print a[i - 1],
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(a, b, lcs, i - 1, j)
        else:
            print_lcs(a, b, lcs, i, j - 1)

a = sys.argv[1]
b = sys.argv[2]

lcs = [ [0 for j in range(len(b) + 1)] for i in range(len(a)+1) ]

for i in xrange(1, len(a) + 1):
    for j in xrange(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            x = 1
        else:
            x = 0
        lcs[i][j] = max(lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1])

print_lcs(a, b, lcs, len(a), len(b))

以下は実行例。

% python lcs.py ABCBDAB BDCBA
B C B A