DAA-最長共通サブシーケンス

最も長い共通サブシーケンス問題は、指定された両方の文字列に存在する最も長いシーケンスを見つけることです。

サブシーケンス

シーケンスS = <s〜1〜、s〜2〜、s〜3〜、s〜4〜、…、s〜n〜>を考えてみましょう。

S上のシーケンスZ = <z〜1〜、z〜2〜、z〜3〜、z〜4〜、…、z〜m〜>は、Sのサブシーケンスと呼ばれます。いくつかの要素の削除。

共通サブシーケンス

*_X_* と *_Y_* は、有限要素セット上の2つのシーケンスであるとします。 *_Z_* が *_X_* と *_Y_* の両方のサブシーケンスである場合、 *_ Z_* は *_X_* と *_Y_* の共通サブシーケンスであると言えます。

最長共通部分列

シーケンスのセットが指定されている場合、最長の共通サブシーケンス問題は、最大長のすべてのシーケンスの共通サブシーケンスを見つけることです。

最も長い共通サブシーケンス問題は、diff-utilityなどのデータ比較プログラムの基礎である古典的なコンピューターサイエンスの問題であり、バイオインフォマティクスに応用されています。また、SVNやGitなどのリビジョン管理システムによって、リビジョン管理されたファイルのコレクションに加えられた複数の変更を調整するために広く使用されています。

ナイーブ法

*_X_* を長さ *_m_* のシーケンスとし、 *_ Y_* を長さ *_n_* のシーケンスとします。 *_X_* のすべてのサブシーケンスが *_Y_* のサブシーケンスであるかどうかを確認し、見つかった最長の共通サブシーケンスを返します。

*_X_* には *_2 ^ m ^ _* サブシーケンスがあります。 シーケンスが *_Y_* のサブシーケンスであるかどうかをテストするには、 *_ O（n）_* 時間かかります。 したがって、ナイーブアルゴリズムには *_O（n2 ^ m ^）_* 時間かかります。

動的計画法

_X = <x〜1〜、x〜2〜、x〜3〜、…、x〜m〜> _および_Y = <y〜1〜、y〜2〜、y〜3〜、…、y〜 n〜> _はシーケンスです。要素の長さを計算するには、次のアルゴリズムが使用されます。

この手順では、テーブル _C [m、n] _ が行優先順に計算され、別のテーブル _B [m、n] _ が計算されて最適なソリューションが構築されます。

Algorithm: LCS-Length-Table-Formulation (X, Y)
m := length(X)
n := length(Y)
for i = 1 to m do
   C[i, 0] := 0
for j = 1 to n do
   C[0, j] := 0
for i = 1 to m do
   for j = 1 to n do
      if xi = yj
         C[i, j] := C[i - 1, j - 1] + 1
         B[i, j] := ‘D’
      else
         if C[i -1, j] ≥ C[i, j -1]
            C[i, j] := C[i - 1, j] + 1
            B[i, j] := ‘U’
         else
         C[i, j] := C[i, j - 1]
         B[i, j] := ‘L’
return C and B

Algorithm: Print-LCS (B, X, i, j)
if i = 0 and j = 0
   return
if B[i, j] = ‘D’
   Print-LCS(B, X, i-1, j-1)
   Print(xi)
else if B[i, j] = ‘U’
   Print-LCS(B, X, i-1, j)
else
   Print-LCS(B, X, i, j-1)

このアルゴリズムは、 X および Y の最長共通サブシーケンスを出力します。

分析

テーブルにデータを入力するには、外側の for' ループが m 回繰り返され、内側の for ループが n 回繰り返されます。したがって、アルゴリズムの複雑さは_O（m、n）です。ここで、 ' m_ および n は2つの文字列の長さです。

例

この例では、2つの文字列 X = BACDB および Y = BDCB を使用して、最も長い共通サブシーケンスを見つけます。

アルゴリズムLCS-Length-Table-Formulation（上記）に従って、テーブルC（左側に表示）とテーブルB（右側に表示）を計算しました。

表Bでは、「D」、「L」、「U」の代わりに、それぞれ斜め矢印、左矢印、上矢印を使用しています。テーブルBを生成した後、LCSは関数LCS-Printによって決定されます。結果はBCBです。

LCS

Design-and-analysis-of-algorithms-longest-common-subsequence

目次