文書の過去の版を表示しています。
最長増加部分列・最長共通部分列
ある数列や文字列 $A=\{a_1,a_2,...,a_n\}$ がある時、部分列(Subsequence)とは、$A$ からいくつかの要素を抽出した列。飛び飛びでもよいが、順番は元から変わってはいけない。
$A$の部分列 $B=\{a_i,a_j,...,a_k\}$、ただし $1 \le i \lt j \lt ... \lt k \le n$
元の数列 | $\{5,3,7,4,1,4,6\}$ |
部分列の例 | $\{5,7,4\},\{1,6\}$ |
部分列にまつわる問題では、「最長増加部分列」や「最長共通部分列」を求める問題が出題される。これらは動的計画法により高速に求めることができる。また長さだけなら、なお高速に求める方法がある。
最長増加部分列の長さ
数列の部分列のうち、隣接する2要素を見ると常に右の方が大きいものを増加部分列という。同じ値を許すかは定義によるが、ここでは許さないとする。
そのうち最長のものを最長増加部分列(Longest Increase Subsequence)という。
$A$の増加部分列 $B=\{a_i,a_j,...,a_k\}$、ただし $1 \le i \lt j \lt ... \lt k \le n$ かつ $a_i \lt a_j \lt ... \lt a_k$
元の数列 | $\{5,3,7,4,1,4,6\}$ |
増加部分列の例 | $\{5,7\},\{3,6\}$ |
最長増加部分列 | $\{3,4,6\},\{1,4,6\}$ |
この長さを求めましょう、という問題。(このアルゴリズムでは、最長増加部分列自体は求まらない)
- $A$ の要素を1つずつ順番に処理する。現在処理中の要素を $a_j$ とする。
- $L[i]$ を、「$a_1$~$a_j$ の要素から長さが $i+1$ の増加部分列を作ったとき、末尾要素が取り得る最小値」とし、更新していく。
- 最後まで処理した後の $L$ の値が埋まっている所の長さが、最長増加部分列長となる。
from bisect import bisect_left def lis(A: list): L = [A[0]] for a in A[1:]: if a > L[-1]: # Lの末尾よりaが大きければ増加部分列を延長できる L.append(a) else: # そうでなければ、「aより小さい最大要素の次」をaにする # 該当位置は、二分探索で特定できる L[bisect_left(L, a)] = a return len(L) # ----------------------------------------- print(lis([3, 4, 5, 1, 6, 3, 2, 7])) # => 5
最長共通部分列の長さ
2つの文字列A,Bがある時、「Aの部分列でもあり、Bの部分列でもある」文字列を共通文字列という。
そのうち最長のものを最長共通部分列(Longest Common Subsequence)という。
A | abcbdabc |
B | bdcaba |
LCS | bcba,bdabなど |
この長さを求めましょう、という問題。(このアルゴリズムでは、最長共通部分列自体は求まらない)
- Bの要素を1つずつ順番に処理する。現在処理中の要素を$b_k$とする。
- $L[i]$を、「“$a_1$~$a_j$” と “$b_1$~$b_k$” から長さが $i+1$ の共通部分列が作れるとき、$j$ が取り得る最小値」とし、更新していく。
- Bを最後まで処理した後の $L$ の値が埋まっている所の長さが、最長共通部分列長となる。
def lcs(a: str, b: str): L = [] for bk in b: bgn_idx = 0 # 検索開始位置 for i, cur_idx in enumerate(L): # ※1 chr_idx = a.find(bk, bgn_idx) + 1 if not chr_idx: break L[i] = min(cur_idx, chr_idx) bgn_idx = cur_idx else: # ※2 chr_idx = a.find(bk, bgn_idx) + 1 if chr_idx: L.append(chr_idx) return len(L) # --------------------------------------- print(lcs('>abcbdabc', 'bdcaba')) # => 4
- 以下の解説にあたっての定義
- 文字列Bの先頭 $k$ 文字を抽出した文字列を、$B'_k$ とする
- $AT(S)$ を、「Aの部分文字列$S$ の末尾文字の、Aにおけるindex」とする
- A:abcabc、S:bb だった場合、$AT(S)=4$
- ※1:
- 処理中の文字を $b_k$ とする
- ※1の時点で
bgn_idx
に入っているのは、$L[i-1]$、つまり「$AT(A$と$B'_{k-1}$ の長さ $i$ の共通部分列$)+1$」 - ここで「$A$と$B'_{k-1}$ の長さ $i$ の共通部分列」を $T$ とする(複数ある場合は、$AT(T)$ が最小のもの)
- ループ内でおこなっているのは、以下の確認
- $T$ の末尾に $b_k$ を付け足して長さ $i+1$ の共通部分列を作れるか?
- つまり、$AT(T)$ 以降に、文字 $b_k$ が存在するか?
- 作れたら、$AT(T+b_k)$ の値は?(これ+1が
chr_idx
) - それは、既に発見済みの他の共通部分列$T'$ より短いか?($AT(T+b_k)<AT(T')$ なら更新)
- 以上の繰り返しで、$L$ は更新される
- ※2:
- ループ途中でbreakされないで最後まで進むと、else節に入る
- ここで、$A$と$B'_{k-1}$ の最長共通部分列を $T_{max}$、その長さを $|T_{max}|$とする
- ※2の時点で
bgn_idx
に入っているのは、「$AT(T_{max})+1$」 - Aにおいて、
bgn_idx
より右に文字 $b_k$ が存在する ⇔ 最長共通部分列“$T_{max}+b_k$“が存在し、暫定最長共通部分列長を$|T_{max}|+1$に延長できる - 延長できる場合、$L$ に追加する