動的計画法３　最長共通部分列

動的計画法シリーズ，３個目の例題です．前回のエントリの最後で説明したステップ通りに問題を解いていきたいと思います．今回の問題も有名な問題で，”最長共通部分列問題”と呼ばれるものです．問題の定義は，，，

問題定義

二つの与えられた文字列に対して，最長共通部分列の長さを出力しなさい．

※部分列とは，与えられた文字列を Z = {z₁, z₂, ... z_n} とすると，
z_i1, z_i2, ... z_im (i1 < i2 < ... < im) を表すことのできる文字列であり，
二つの文字列の最長共通部分列とは，例えば "abcd", "becd" という文字列を考えた場合， "bcd"が最長共通部分列となる．

ということで，動的計画法で問題を解決する下記３ステップを通して，問題を解いていきたいと思います．

１．再帰的に求める方法を考える．
２．再帰関数の分岐から漸化式を作る．
３．漸化式を使って，ボトムアップで表を埋めていく

まず”１．再帰的に求める方法を考える”で問題を解いていきたいと思います．

１．再帰的に求める方法を考える

参考書を何冊か読んでみたんですが，なかなかピンとくるまで時間がかかりました．どの本を読んでも
”より小さい文字列の最長共通部分列を求める問題が，大きい文字列の問題の部分問題になっているので，再帰的に解ける”
とかって書いてあるんですが，ここがどうしてもピンとこず．．．自分なりに解釈してみました．

下記のように二つの文字列があったとします．この時，比較している文字の添え字をそれぞれ i, j とします．
比較文字列A：abcd
比較文字列B：becd

今，比較している文字列が (i, j) = (2, 2) だとすると，A[2] = 'c', B[2] = 'c' となるのでこのペアは共通文字列の一部になれることがわかります．よって次は (i-1, j-1) = (1, 1) を調べます．今度は A[1] = 'b', B[1] = 'e' となるため，このペアは共通文字列の一部にはなれません．ここの再帰関数の分岐のさせ方がキモで，次の調査候補は (i-1, j), (i, j-1) の二つのパターンになります．一致しなかった場合，片方の文字列を一文字捨てて，もう一度他方の文字列と比較します．文字列が二つあるので，結局分岐は二つになります．

関数を次のように定義すると

get_common_longest_subseq(a_idx, b_idx, seq_a, seq_b)
a_idx : 関数コールで比較対象となっている，文字列Aの文字のインデックス．
b_idx : 関数コールで比較対象となっている，文字列Bの文字のインデックス．
seq_a : 文字列A
seq_b : 文字列B

で，関数のコールイメージは下記のようになります．

比較対象文字列が一致した場合：get_common_longest_subseq(a_idx - 1, b_idx - 1, seq_a, seq_b) + 1
比較対象文字列が一致しなかった場合：max(get_common_longest_subseq(a_idx, b_idx - 1, seq_a, seq_b), get_common_longest_subseq(a_idx - 1, b_idx, seq_a, seq_b))

上記をコードに落とすと，下記のようになります．

def longest_common_subsequences(seq1, seq2):
  return longest_common_subsequences_int(len(seq1)-1, len(seq2)-1, seq1, seq2)

def longest_common_subsequences_int(i, j, seq1, seq2):

  if (i == -1 or j == -1):
    return 0

  if (seq1[i] ==  seq2[j]):
    val = longest_common_subsequences_int(i-1, j-1, seq1, seq2) + 1
  else:
    val1 = longest_common_subsequences_int(i-1, j, seq1, seq2)
    val2 = longest_common_subsequences_int(i, j-1, seq1, seq2)
    val = max(val1, val2)

  return val


if __name__ == '__main__':

  seq1 = "abcdbab"
  seq2 = "bdcaba"
  print(longest_common_subsequences(seq1, seq2))

２．再帰関数の分岐から漸化式を作る

ということで，ここまでくればあとは機械的に行けそうです．漸化式は，下記のようになります．

length_tbl[0][:] = 0, length_tbl[:][0] = 0
length_tbl[i][j] = length_tbl[i-1][j-1] + 1 (比較文字列が一致したとき)
length_tbl[i][j] = max(length_tbl[i-1][j], length_tbl[i][j-1]) (比較文字列が不一致の時)

３．漸化式を使って，ボトムアップで表を埋めていく

あとは２の漸化式を使って，(i, j) に関する二次元表を末端から埋めていくだけです．

def longest_common_subsequences_dp(seq1, seq2):

  tbl = np.zeros((len(seq1)+1, len(seq2)+1), dtype=int)
  tbl.fill(-sys.maxsize)
  tbl[:, 0] = 0
  tbl[0, :] = 0

  for i in range(1, len(seq1)+1):
    for j in range(1, len(seq2)+1):
      if (seq1[i-1] == seq2[j-1]):
        tbl[i,j] = tbl[i-1, j-1]+1
      else:
        tbl[i,j] = max(tbl[i-1, j], tbl[i, j-1])

  return tbl[len(seq1), len(seq2)]

if __name__ == '__main__':

  seq1 = "abcdbab"
  seq2 = "bdcaba"
  print(longest_common_subsequences_dp(seq1, seq2))

完成したテーブルは下記のようになります．
[[0 0 0 0 0 0 0]
[0 0 0 0 1 1 1]
[0 1 1 1 1 2 2]
[0 1 1 2 2 2 2]
[0 1 2 2 2 2 2]
[0 1 2 2 2 3 3]
[0 1 2 2 3 3 4]
[0 1 2 2 3 4 4]]