文字列に効く動的計画法: 最長共通部分列(LCS)

この記事は「文字列に効く動的計画法」シリーズの最長共通部分列(LCS)に関する記事です。

文字列に効く動的計画法

動的計画法(DP)は複雑な問題をより小さく単純な部分問題に分割し解決する手法です。その中には文字列メトリクスに対して効果的なパターンもいくつかあり、このシリーズはそれらに関する私のまとめノートです。何か追加すべきものがあると思われる場合は、お気軽にお問い合わせください。

最長共通部分列

最長共通部分列(LCS)問題のアルゴリズムは文字列のあいまい検索やdiffコマンド等で使われており、（通常）二つの文字列間で共通している最長の部分列を見つけ出します。この時部分列は連続した共通の文字列である必要はなく、間に他の文字列が入っていてもカウントされますが、比較される文字列の順番は守られる必要があります。例としては、ABCDとACBD間の最長共通部分列は3であり、それはABDかACDのどちらかのカウントとなります。

DP テーブル

以下の表では、「stone」（左側に縦にマップされたもの）と「longest」（上部に水平にマップされたもの）が比較されています。LCS では、基本ケースを文字ではないもの（ε）と定義しますので、最初の行と最初の列の値は全て 0 にします。

[1,1]の位置から 2 つの文字を比較し、左から各セルを各行チェックしていきます。文字が同一である場合、左上のセルから 1 つの数字を増やし、その値でセルを更新します。同一でない場合、この時点までのベストな値を使用します。ベストな値とは上か左のセルのどちらか大きい方になります。そして一番右下の値が結果になります。

実装

def lcs(s, target):
    slen = len(s) + 1  # +1 for empty string
    tlen = len(target) + 1
    dp = [[0 for _ in range(tlen)] for _ in range(slen)]  # DP table creation

    for i in range(1, slen):
        for j in range(1, tlen):
            if s[i-1] == target[j-1]:  # if characters are identical, increment number from left top
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])  # if not, use the best value either from top of left

    return dp[-1][-1]

Notes

LCS は測定値のみを返します。そのため、測定値ではなく共通文字列自体が欲しい場合、それを取得するための別の式が必要になります。これは、LCS 関数で作成された DP テーブルを使用して、右下のセルから最大の数字をトラックして文字を集めることで可能になります。