すべての最大共通部分列を見つけるためのアルゴリズムの実装

1. LCS分析

まず、サブシーケンスとは何でしょうか?定義は書きませんが、一目でわかるように例を挙げます。たとえば、文字列「student」の場合、su、sud、sudt などはすべてその部分文字列になります。連続している場合も不連続の場合もあります。スタッドのように連続して現れる場合は、一般にサブシーケンス文字列と呼ばれます。ここではサブシーケンスについてのみ説明します。

共通部分列とは何ですか?とても簡単です。共通の部分列を含む 2 つの文字列がある場合、この部分列は共通部分列と呼ばれます。たとえば、「student」や「shade」の一般的なサブシーケンスには、「s」や「sd」や「sde」などが含まれます。最も長い部分列は、いわゆる最長共通部分列 (LCS) です。もちろん、最長共通部分列が複数存在する場合もあります。たとえば、「ABCBDAB」と「BDCABA」の場合、それらの LCS は「BCBA」、「BCAB」、「BDAB」です。これらの概念を理解した後、次の質問は LCS をどのように計算するかです。

通常のアルゴリズムは動的計画法 (DP) です。 2 つの文字列シーケンス X={x1,x2,...xi...xm}、Y={y1,y2,...yj...yn} があるとします。 X={x1,x2,...xi-1} と Y={y1,y2,...yj-1} の共通部分列 L がわかっている場合は、これを再帰的に解くことができます。

1) xi==yjの場合、{L、xi(またはyj)}が新しいLCSとなり、その長さもlen(L)+1になります。これは簡単に理解できます。つまり、シーケンス {Xi,Yj} の最適解は {Xi-1,Yj-1} によって得られます。

2) xiyj の場合、それを変換して 2 つのケースで LCS を見つけることができます。

A: X={x1,x2,...xi}お​​よびY={y1,y2,...yj-1}のLCS、L1を仮定

B: X={x1,x2,...xi-1}およびY={y1,y2,...yj}のLCS（L2を仮定）

次に、LCSはxiyj=max{L1,L2}、つまり最大値になります。同様に、実際には、シーケンス {Xi,Yj-1} と {Xi-1,Yj} は両方とも {Xi-1,Yj-1} の *** ソリューションによって取得できます。

どうですか、この方法はあなたにとって馴染み深いものだと思いますか?現在の問題に対する最善の解決策には、常に最善の解決策を持つサブ問題が含まれます。これは典型的な DP 解決方法です。さて、上記のテキスト記述ソリューションで LCS の長さを見つけるための式を直接示しましょう。

ここでは、LCSの長さ情報を格納するために2次元配列が使用され、iとjはそれぞれ2つの文字列シーケンスの添え字値を表します。これは、*** 共通部分列の長さを調べる方法です。*** 共通部分列を印刷したい場合はどうすればよいでしょうか。また、*** がパスを遡って LCS を見つけられるように、解決プロセス中にパス情報を保存する別の 2 次元配列も必要です。これが曖昧に思われる場合は、以下でその方法を説明します。

2. DPの実装

これについては多くのブログ投稿があります。基本的には、2 つの 2 次元配列 c[m][n] と b[m][n] が使用されます。1 つは部分文字列の LCS 長さを格納し、もう 1 つはパスの方向を格納してから、バックトラックします。

2次元配列b[i][j]の値は1、2、3のいずれかです。値が1の場合、xi=yj、c[i][j]=c[i-1][j-1]+1であることを意味します。 2 次元配列を行列として見ると、左上隅から右下隅へのパスを表します。値が 2 の場合、xi≠yj であり、c[i][j]=c[i-1][j] であることを意味し、これは上から下へのパスを表します。同様に、値 3 は左から右へのパスを表します。

*** c[m][n]の値に基づいて共通部分列の長さを知ることができます。次に、 b[i][j]に基づいてバックトラックすることで、 LCSを印刷できます。座標点b [i][j]=1に対応する文字は両方のシーケンスに出現するため、 2次元配列を遡ってLCSを見つけることができます。実装コードは次のとおりです。

テストを実施します:

 1文字str1[MAX_LEN] = " BADCDCBA " ; 2文字str2[MAX_LEN] = " ABCDCDAB " ; 3 
4 GetLCSLen(str1, str2, C, B, str1len+ 1 , str2len+ 1 ); 5 TraceBack(str1, B, str1len+ 1 , str2len+ 1 );

詳細なコードについては、記事の最後に記載されているリンクを参照してください。このテスト出力: BDCDB

質問:上記の方法では、 c[i-1][j]==c[i][j-1]の場合を個別に考慮しなかったため、共通部分列が複数ある場合、バックトラック中に印刷された文字は、共通部分列の1つだけになります。どうすれば解決できるでしょうか? 2次元配列b[i][j]の値に可能性を追加します。これは4に等しくなります。これは、前述した複数の状況を表します。その後、バックトラックするときに、この情報に基づいて、より多くの可能な選択肢を出力できます。このプロセスは実際には非常に単純なので、コードを書くことはありません。以下のパス バックトラッキング図を例に挙げます。ポイント (8,8) から開始し、b[i][j] の値で示される方向にバックトラックします。すべてのパスをトラバースします。開始ポイント (0,0) に到達できるパスがある場合、それが LCS です。存在するパスをすべて出力します。しかし、

別の問題が発生します。パスをバックトラックするときに、一般的な完全検索を使用すると、多くの無駄な作業が行われることに気付きましたか。つまり、これは何度も繰り返され、ノード(6,3)、(7,2)、(8,1)などのパスは最終的に終点(0,0)に到達しないため、いくつかの無効なパスが通過します。したがって、アルゴリズムの複雑さと時間の消費が増加します。それで、どうやって解決するのでしょうか?以下の方法を見て、この記事の本題に正式に入りましょう。

パスバックトラッキング図:

状態 4 を追加した後の状態図:

3. アルゴリズムの改善

前述のパスバックトラッキングプロセスでは、一般的な方法はすべての可能なパスをトラバースすることですが、*** 共通サブシーケンスを構成できないいくつかのジャンプポイントも計算します。ここでまずジャンプポイントとは何かを説明します。ジャンプポイントとは共通部分列の長さを変化させるノード、つまりb[i][j]=1に対応するノード(i, j)のことです。さて、次の質問は、これらの無効なジャンプ ポイントを無視して、アルゴリズムの複雑さを軽減するにはどうすればよいかということです。参考文献では、長方形検索という方法を提案しています。

まず、保存と印刷の 2 つのスタック データ構造を構築します。名前が示すように、1 つはノードを保存するために使用され、もう 1 つはノードを印刷するために使用されます。スタックの定義は次のとおりです。

 1 #定義MAX_STACK_SIZE 1024
 2 typedef struct _Element 3 { 4 int nlcslen; 5 int nrow; 6 int ncolumn; 7 }Element; 8 typedef struct _Stack 9 { 10 int top; 11 Element data[MAX_STACK_SIZE]; 12 }Stack;

スタックは配列を使用して実装され、頂点を指すインデックス値 top を持ちます。初期化の目的で、まず仮想ノード virtualnode が構築され、ノード (m,n) の右下隅、つまり (m+1,n+1) を指します。このノードの LCS の長さは、*** 共通サブシーケンスの長さ + 1 であると想定されます。仮想ノードをスタック ストアにプッシュし、次のアルゴリズムを実行します。

1) スタックストアは空ですか?はいの場合は終了します。

2) それ以外の場合は、ストア スタックの一番上からノードをポップします。

3) このノードが境界要素 (行または列の添え字が 1) である場合は、このノードをスタック プリントにプッシュし、スタック プリント内のすべてのノード (仮想ノードを除く) をプリントします。この時点でストア スタックの最上位ノードの LCS 長さを確認し、この長さを基準にして、LCS 長さがこの基準値以下のプリント スタック内のすべてのノードをポップアウトし、手順 1 にジャンプします。

4) 境界要素でない場合は、このノードの左上ノード (i-1、j-1) を開始点として、開始点が示す方向に沿って最初のジャンプ ポイント e1 (つまり、b[i][j]==1 のポイント) を見つけます。途中で分岐ノード（b[i][j]==4の点）に遭遇したら、その上のノードに沿って探索を続けます。

5) 最初のジャンプ ポイントを見つけたら、手順 4 の開始点に戻り、ノードが示す方向に沿って 2 番目のジャンプ ポイント e2 を見つけます。途中で分岐ノード（b[i][j]==4の点）に遭遇したら、その左のノードに沿って探索を続けます。

6) e1 ノードと e2 ノードが同じノードである場合は、そのノードをストア スタックにプッシュし、手順 1) に戻ります。

7) 同じノードでない場合は、e1 と e2 によって形成される長方形の範囲内のすべてのジャンプ ポイントを検索し、それらすべてをストア スタックにプッシュして、手順 1) に戻ります。

分からない？それは問題ではありません。上のマトリックス図に基づいてアルゴリズムを段階的に実行し、計算方法を確認してみましょう。

***ステップ: 仮想ノード 6(9,9) をスタック ストアにプッシュします。ここで、6 はこのノードの LCS 長さを表し、(9,9) は座標値を表します。

ステップ 2: ストア スタックが空でない場合は、ストア スタックの上部がポップされ、プリント スタックに押し込まれます。このときの 2 つのスタックの状態は、次の図の左側のようになります。分岐ノードである開始点 (8,8) から開始します。b[8][8]==4 なので、上へ進んで e1 ジャンプ ポイント (7,8) を検索します。検索パスは (8,8)->(7,8) です。次に (8,8) に戻り、ポイント e2 を見つけます。次に左に移動して、e2 ジャンプ ポイント (8,7) を見つけます。これら 2 つのジャンプ ポイントは異なるため、e1 と e2 で囲まれた四角形内のすべてのジャンプ ポイントを対角方向として検索します。ここには e1 と e2 自体の 2 つのノードのみがあり、それらをスタック ストアにプッシュします。この時点での 2 つのスタックの状態を下図に示します。青色の底のノードは、ストア スタックからポップされてプリント スタックにプッシュされたノードを表し、緑色の底のノードは、ストア スタックに新しくプッシュされたノードを表します。これは、次のすべての図の表現方法です。

ステップ3: 5(7,8)をプリントスタックにポップし、新しい2ホップノードを検索します。

ステップ4:

ステップ5:

ステップ6:

ステップ 7: ここで重要なステップが来ます。この時点でストア スタックからポップされたノードは境界要素 1 (1,2) であるため、印刷スタックのすべての要素 (赤いフォントのノード) を印刷します。これらの要素は、最長共通部分列を構成します (自分で考えてください)。印刷後、印刷スタックをクリーンアップし、不要なノードを削除する必要があります。ステップ 2 によると、ストア スタックの最上位ノードの LCS は 1 なので、印刷スタックから取り出されるノードは 1 (1, 2) のみです。ポップアップ後、印刷スタックの状態は図のようになります。点線のボックスノードはポップアップされていることを示しており、以下でも同様です。

ステップ 8: ストア スタックの最上部をポップし続け、それが再び境界要素であることを確認します。それを印刷スタックにプッシュし続け、印刷スタックを印刷します。印刷スタックをクリーンアップします。

ステップ 9: クリーニング後、ステップ 2 に進みます。

さて、次の工程は上記の手順を繰り返すことです。自分で描いてみれば一目瞭然です。

4: コードの実装

C言語でキーコードを実装する:

同じテストを使用して、このアルゴリズムはすべての最長共通サブシーケンスを出力できます。

5: まとめ

このアルゴリズムは、従来のアルゴリズムの指数関数的な複雑さを max{O(mn),O(ck)} まで削減できます。ここで、k は最大共通部分列の数です。詳細な証明については論文を参照してください。すべての有効なジャンプ ポイントを格納するために 2 つのスタックが使用されるため、多くの繰り返し比較は無視されます。スタックの秩序性により、任意の *** 共通サブシーケンスを巧みに取得することもできます。

このアルゴリズムの完全な実装コードのダウンロード パス: http://pan.baidu.com/share/link?shareid=125428&uk=285541510

議論を歓迎します。

参考文献:

「行列検索を使用してすべての最長共通部分列を見つけるアルゴリズム」、Gong Jieqing、安徽省理工大学学報、第 23 巻、第 4 号、2008 年 12 月