最長共通部分列

Sの接頭辞S _{n は}、 Sの最初のn文字として定義されます。^{[ 5 ]} 例えば、S = (AGCA) の接頭辞は次のようになります。

S ₀ = ()

S ₁ = (A)

S ₂ = (AG)

S ₃ = (AGC)

S ₄ = (AGCA)。

LCS ( X , Y ) を、 XとYに共通する最長部分列を計算する関数とする。このような関数には、2 つの興味深い性質がある。

LCS ( X ^ A , Y ^ A ) = LCS ( X , Y )^ A は、すべての文字列X、Yおよびすべての記号Aに対して成り立ちます。ここで、^ は文字列の連結を表します。これにより、同じ記号で終わる 2 つのシーケンスのLCS計算を簡略化できます。たとえば、LCS ("BANANA","ATANA") = LCS ("BANAN","ATAN")^"A、残りの共通記号についても同様に、LCS ("BANANA","ATANA") = LCS ("BAN","AT")^"ANA となります。

AとBが異なる記号である場合（ A ≠ B）、LCS (X^A,Y^B)は、すべての文字列X、Yに対して、集合{ LCS ( X ^ A , Y ), LCS ( X , Y ^ B )}内の最大長文字列の1つです。

例えば、 LCS ("ABCDEFG","BCDGK") は、 LCS ("ABCDEFG","BCDG") とLCS ("ABCDEF","BCDGK")の中で最長の文字列です。もし両者の長さが同じであれば、どちらか一方を任意に選択できます。

この性質を実現するために、2つのケースを区別する。

• LCS ("ABCDEFG","BCDGK") が "G" で終わる場合 、最後の "K" は LCS に含まれないため、LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEFG","BCDG") となります。
• LCS ("ABCDEFG","BCDGK") が "G" で終わらない場合 、最後の "G" は LCS に含まれないため、 LCS ("ABCDEFG","BCDGK") = LCS ("ABCDEF","BCDGK") となります。

2つの数列を以下のように定義する。 ${\displaystyle X=(x_{1}x_{2}\cdots x_{m})}$そして${\displaystyle Y=(y_{1}y_{2}\cdots y_{n})}$の接頭辞${\displaystyle X}$は${\displaystyle X_{0},X_{1},X_{2},\dots ,X_{m}}$; の接頭辞${\displaystyle Y}$は${\displaystyle Y_{0},Y_{1},Y_{2},\dots ,Y_{n}}$。 させて${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})}$接頭辞の最長共通部分列の集合を表す${\displaystyle X_{i}}$そして${\displaystyle Y_{j}}$この一連の数列は、以下のように表されます。

${\displaystyle {\mathit {LCS}}(X_{i},Y_{j})={\begin{cases}\epsilon &{\mbox{if }}i=0{\mbox{ or }}j=0\\{\mathit {LCS}}(X_{i-1},Y_{j-1}){\hat {}}x_{i}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}=y_{j}\\\operatorname {\max } \{{\mathit {LCS}}(X_{i},Y_{j-1}),{\mathit {LCS}}(X_{i-1},Y_{j})\}&{\mbox{if }}i,j>0{\mbox{ and }}x_{i}\neq y_{j}.\end{cases}}}$

LCSを見つけるには${\displaystyle X_{i}}$そして${\displaystyle Y_{j}}$、 比較する${\displaystyle x_{i}}$そして$\displaystyle y_j}}$それらが等しい場合、数列は${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j-1})}$その要素によって拡張され、${\displaystyle x_{i}}$等しくない場合は、2 つのシーケンスのうち長い方、${\displaystyle {\mathit {LCS}}(X_{i},Y_{j-1})}$、 そして${\displaystyle {\mathit {LCS}}(X_{i-1},Y_{j})}$、が保持されます。（長さが同じでも同一でない場合は、両方とも保持されます。）基本ケースでは、${\displaystyle X_{i}}$または${\displaystyle Y_{i}}$空です、空文字列です、${\displaystyle \epsilon }$。

R = (GAC) とC = (AGCAT)に共通する最長部分列が見つかります。LCS 関数は「ゼロ番目」の要素を使用するため、これらのシーケンスに対して空のゼロ接頭辞を定義すると便利です。R 0 ₌ ε、C _{0 = ε。すべての接頭辞は、} C を最初の行 (列ヘッダーにする)、R を最初の列 (行ヘッダーにする)に配置したテーブルに格納されます。

この表は、計算の各ステップにおける最長共通部分列（LCS）を格納するために使用されます。2列目と2行目にはεが記入されています。これは、空のシーケンスと空でないシーケンスを比較した場合、最長共通部分列は常に空のシーケンスになるためです。

LCS ( R ₁ , C ₁ ) は、各シーケンスの最初の要素を比較することによって決定されます。 G と A は同じではないため、この LCS は (「2 番目の性質」を使用して) 2 つのシーケンスLCS ( R ₁ , C ₀ ) と LCS ( R ₀ , C ₁ ) のうち長い方を取得します。 表によると、これらは両方とも空であるため、下の表に示すように、 LCS ( R ₁ , C ₁ ) も空です。 矢印は、シーケンスが上のセルLCS ( R ₀ , C ₁ ) と左側のセルLCS ( R ₁ , C ₀ ) の両方から来ていることを示しています。

LCS ( R ₁ , C ₂ ) は G と G を比較することによって決定されます。これらは一致するため、G は左上のシーケンスLCS ( R ₀ , C ₁ ) (ε) に追加され、(εG) となり、(G) となります。

LCS ( R ₁ , C ₃ )では、G と C は一致しません。上のシーケンスは空です。左側のシーケンスには、要素 G が 1 つ含まれています。これらのうち長い方を選択すると、LCS ( R ₁ , C ₃ ) は (G) になります。矢印は左を向いています。これは、2 つのシーケンスのうち長い方だからです。

LCS ( R ₁ , C ₄ ) も同様に (G) です。

LCS ( R ₁ , C ₅ ) も同様に (G) です。

LCS ( R ₂ , C ₁ )の場合、A は A と比較されます。2 つの要素は一致するため、A が ε に追加され、(A) となります。

LCS ( R ₂ , C ₂ )では、A と G は一致しないため、LCS ( R ₁ , C ₂ ) （G）とLCS ( R ₂ , C ₁ ) （A）のうち長い方が使用されます。この場合、それぞれ 1 つの要素が含まれているため、この LCS には (A) と (G) の 2 つの部分列が与えられます。

LCS ( R ₂ , C ₃ )では、A は C と一致しません。LCS ( R ₂ , C _{2 )}にはシーケンス (A) と (G) が含まれています。LCS ( R ₁ , C ₃ ) は (G) であり、これは既にLCS ( R ₂ , C ₂ ) に含まれています。結果として、LCS ( R ₂ , C ₃ ) にも 2 つのサブシーケンス (A) と (G) が含まれます。

LCS ( R ₂ , C ₄ )の場合、A は A と一致し、左上のセルに追加されて (GA) になります。

LCS ( R ₂ , C ₅ )の場合、A は T と一致しません。2 つの配列 (GA) と (G) を比較すると、最も長いのは (GA) なので、LCS ( R ₂ , C ₅ ) は (GA) です。

LCS ( R ₃ , C ₁ )の場合、C と A は一致しないため、LCS ( R ₃ , C ₁ ) は 2 つのシーケンスのうち長い方 (A) を取得します。

LCS ( R ₃ , C ₂ )では、C と G は一致しません。LCS ( R 3 , C ₁ ) とLCS ( R ₂ , C ₂ ) はどちらも 1 つの要素を持ちます。結果として、LCS ( R ₃ , C _{2 ) には 2 つの部分列 (A) と (G)が}含まれます。

LCS ( R ₃ , C ₃ )の場合、C と C は一致するので、C はLCS ( R ₂ , C ₂ ) に追加され、2 つのサブシーケンス (A) と (G) が含まれるため、(AC) と (GC) が得られます。

LCS ( R ₃ , C ₄ )では、C と A は一致しません。(AC) と (GC) を含むLCS ( R ₃ , C _{3 ) と (GA) を含む}LCS ( R ₂ , C ₄ ) を組み合わせると、合計 3 つの配列 (AC)、(GC)、および (GA) が得られます。

最後に、LCS ( R ₃ , C ₅ ) では、C と T は一致しません。その結果、LCS ( R ₃ , C ₅ ) には、(AC)、(GC)、(GA) の 3 つの配列も含まれます。

最終的な結果として、最後のセルには (AGCAT) と (GAC) に共通する最長のサブシーケンスがすべて含まれています。これらは (AC)、(GC)、および (GA) です。この表には、考えられるすべての接頭辞のペアについて、共通する最長のサブシーケンスも示されています。たとえば、(AGC) と (GA) の場合、共通する最長のサブシーケンスは (A) と (G) です。

LCS表の各行のLCSを計算するには、現在の行と前の行の解のみが必要です。しかし、長いシーケンスの場合、これらのシーケンスは多数かつ長くなり、多くのストレージ容量が必要になります。ストレージ容量を節約するには、以下の表のように、実際のサブシーケンスではなく、サブシーケンスの長さと矢印の方向を保存すればよいのです。

実際のサブシーケンスは、表の最後のセルから矢印を逆方向にたどる「トレースバック」手順で推測されます。長さが減少する場合、シーケンスには共通の要素があったはずです。セルに2つの矢印が表示されている場合は、複数のパスが考えられます。以下は、長さが減少するセルに色付きの数字を付けた、このような分析の表です。太字の数字はシーケンス(GA)をトレースします。^{[ 6 ]}

以下の関数は、入力シーケンスとを受け取りX[1..m]、すべてのとに対してと間Y[1..n]のLCSを計算し、それをに格納します。には、ととのLCSの長さが格納されます。^{[ 7 ]}X[1..i]Y[1..j]1 ≤ i ≤ m1 ≤ j ≤ nC[i,j]C[m,n]XY

関数LCSLength(X[1..m], Y[1..n]) C = array(0..m, 0..n) i := 0..mについて C[i,0] = 0 j := 0..nについて C[0,j] = 0 i := 1..m、 j := 1..n の場合、 X[i] = Y[j]の場合 C[i,j] := C[i-1,j-1] + 1 それ以外 C[i,j] := max(C[i,j-1], C[i-1,j]) C[m,n]を返す

あるいは、メモ化を用いることもできる。

以下の関数は、テーブルを計算する際に選択された内容を遡って確認しますC。接頭辞の最後の文字が等しい場合、それらはLCSに含まれているはずです。そうでない場合は、保持する文字の中で最大のLCSを生成したものを確認します。${\displaystyle x_{i}}$そして$\displaystyle y_j}}$i=m、そして同じ選択をします。長さが同じ場合は、どちらか一方を選択します。とを指定して関数を呼び出しますj=n。

function backtrack(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i = 0 or j = 0 return "" if X[i] = Y[j] return backtrack(C, X, Y, i-1, j-1) + X[i] if C[i,j-1] > C[i-1,j] return backtrack(C, X, Y, i, j-1) return backtrack(C, X, Y, i-1, j)

選択する場合${\displaystyle x_{i}}$そして$\displaystyle y_j}}$同じ長さの結果が得られるので、結果として得られる両方の部分列を読み出します。この関数はこれをセットとして返します。文字列が似ている場合、ほぼすべてのステップで分岐する可能性があるため、この関数は多項式ではないことに注意してください。

function backtrackAll(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i = 0 or j = 0 return {""} if X[i] = Y[j] return {Z + X[i] for all Z in backtrackAll(C, X, Y, i-1, j-1)} R := {} C[i,j-1] ≥ C[i-1,j]の場合 R := backtrackAll(C, X, Y, i, j-1) C[i-1,j] ≥ C[i,j-1]の場合 R := R ∪ backtrackAll(C, X, Y, i-1, j) Rを返す

この関数はC行列を逆方向にたどり、 2つのシーケンス間の差分を出力します。なお、 と≥を以下の と に置き換えると、異なる結果が得られることに注意してください。<>≤

function printDiff(C[0..m,0..n], X[1..m], Y[1..n], i, j) if i >= 0 and j >= 0 and X[i] = Y[j] printDiff(C, X, Y, i-1, j-1) print " " + X[i] それ以外の場合、j > 0かつ(i = 0またはC[i,j-1] ≥ C[i-1,j]) printDiff(C, X, Y, i, j-1) print "+ " + Y[j] それ以外の場合、i > 0 かつ(j = 0またはC[i,j-1] < C[i-1,j]) printDiff(C, X, Y, i-1, j) print "- " + X[i] そうでなければ 「」と表示する

させて${\displaystyle X}$「」でありXMJYAUZ、${\displaystyle Y}$は " であるMZJAWXU。 間の最長共通部分列${\displaystyle X}$そして${\displaystyle Y}$は " MJAU" です。以下の表Cは、関数によって生成されたものでLCSLength、の接頭辞間の最長共通部分列の長さを示しています。${\displaystyle X}$そして${\displaystyle Y}$.${\displaystyle i}$行目と${\displaystyle j}$列目はLCS間の長さを示しています${\displaystyle X_{1..i}}$そして${\displaystyle Y_{1..j}}$。

強調表示されたbacktrack数字は、LCS を読み出すときに関数が右下から左上隅までたどる経路を示しています。現在のシンボルが${\displaystyle X}$そして${\displaystyle Y}$が等しい場合、それらは LCS の一部であり、上と左の両方に進みます (太字で示されています)。そうでない場合は、どちらのセルに数値が大きいかに応じて、上または左に進みます。これは、LCS を次のどちらから取得するかに対応します。${\displaystyle X_{1..i-1}}$そして${\displaystyle Y_{1..j}}$、 または${\displaystyle X_{1..i}}$そして${\displaystyle Y_{1..j-1}}$。

単純なアルゴリズムにおけるC行列は、シーケンスの長さに対して2乗に比例して大きくなります。100個の要素からなる2つのシーケンスの場合、10,000個の要素からなる行列が必要となり、10,000回の比較を行う必要があります。実際のほとんどのケース、特にソースコードの差分やパッチでは、ファイルの先頭と末尾が変更されることはほとんどなく、両方が同時に変更されることはまずありません。シーケンスの中間部分で変更された要素がごくわずかであれば、先頭と末尾を削除できます。これにより、行列に必要なメモリ容量だけでなく、必要な比較回数も削減できます。

関数LCS(X[1..m], Y[1..n]) 開始 := 1 m_end := m n_end := n  start ≤ m_endかつstart ≤ n_endかつX[start] = Y[start]である間、先頭の一致する項目を切り取ります。 start := start + 1  start ≤ m_endかつstart ≤ n_endかつX[m_end] = Y[n_end]の間、末尾の一致する項目を切り取ります。 m_end := m_end - 1 n_end := n_end - 1 C = array(start-1..m_end, start-1..n_end) 変更された項目のみをループ処理します。 i := start..m_end の場合、 j := start..n_end の場合、アルゴリズムは以前と同様に続行されます...

最良のシナリオ、つまりシーケンスに変更がない場合、この最適化によってC行列は不要になります。最悪のシナリオ、つまりシーケンスの最初と最後の項目に変更がある場合でも、追加の比較は2回だけ実行されます。

単純なアルゴリズムでは、ほとんどの時間がシーケンス内の項目間の比較に費やされます。ソースコードなどのテキストシーケンスの場合、シーケンスの要素として単一の文字ではなく行を扱います。これは、アルゴリズムの各ステップで比較的長い文字列を比較する必要があることを意味します。これらの比較にかかる時間を短縮するために、2つの最適化を行うことができます。

ハッシュ関数またはチェックサムを使用することで、シーケンス内の文字列のサイズを縮小できます。つまり、平均行長が60文字以上のソースコードの場合、その行のハッシュまたはチェックサムはわずか8～40文字程度になる可能性があります。さらに、ハッシュとチェックサムはランダムな性質を持つため、ソースコードの先頭部分が変更されることはほとんどなく、比較処理がより迅速に行われることが保証されます。

この最適化には主に3つの欠点があります。まず、2つのシーケンスのハッシュ値を事前に計算するために、ある程度の時間が必要になります。次に、ハッシュ化された新しいシーケンス用にメモリを追加で割り当てる必要があります。しかし、ここで使用した単純なアルゴリズムと比較すると、これらの欠点はどちらも比較的軽微です。

3つ目の欠点は、衝突が発生する可能性があることです。チェックサムやハッシュは一意性が保証されていないため、2つの異なる項目が同じハッシュ値になる可能性がわずかにあります。ソースコードではこのような事態は起こりにくいですが、可能性はゼロではありません。そのため、暗号学的ハッシュの方がこの最適化にははるかに適しています。暗号学的ハッシュのエントロピーは、単純なチェックサムのエントロピーよりもはるかに大きくなるからです。ただし、シーケンス長が短い場合、暗号学的ハッシュの設定や計算コストに見合うだけのメリットが得られない可能性があります。

LCSの長さだけが必要な場合は、行列を次のように縮小できます。${\displaystyle 2\times \min(n,m)}$行列、または${\displaystyle \min(m,n)+1}$動的計画法アプローチでは、行列の現在と前の列のみが必要となるため、ベクトルを使用します。ヒルシュベルグのアルゴリズムでは、同じ2次時間と線形空間の範囲内で最適なシーケンス自体を構築できます。^{[ 8 ]}

ChowdhuryとRamachandranは、LCSの長さと最適なシーケンスを見つけるための2次時間線形空間アルゴリズム^{[ 9 ] [ 10 ]を考案しました。このアルゴリズムは、キャッシュ性能が優れているため、実際にはHirschbergのアルゴリズムよりも高速に動作します。 [ 9 ]}このアルゴリズムは、理想的なキャッシュモデルの下で漸近的に最適なキャッシュ複雑度を持ちます。^{[ 11 ]}興味深いことに、このアルゴリズム自体はキャッシュ非依存^{[ 11 ]}であり、マシンのキャッシュパラメータ（キャッシュサイズやキャッシュラインサイズなど）に基づいて選択を行いません。

提示された動的計画法よりも高速に動作するアルゴリズムがいくつか存在する。その1つがハント・シマンスキーアルゴリズムであり、通常は${\displaystyle O((n+r)\log(n))}$時間（${\displaystyle n>m}$）、 どこ${\displaystyle r}$は、2 つのシーケンス間の一致の数です。^{[ 12 ]}アルファベットのサイズが制限されている問題の場合、4 人のロシア人の方法を使用して、動的計画法アルゴリズムの実行時間を対数係数で短縮できます。^{[ 13 ]}