http://www.iaeng.org/publication/WCE2010/WCE2010_pp499-504.pdfで説明されている最長共通部分列問題の並列アルゴリズムを実装しようとしています。
しかし、4 ページの式 6 の変数 C に問題があります。
この論文では、3 ページの最後で C を次のように言及しています。
C as C[1 : l] を有限のアルファベットとする
ABCDEFこれが何を意味するのかはわかりませABQXYEFんABCDEFQXY。しかし、私の 2 つの文字列がオブジェクトのリストである場合 (例の一致テストは ですobj1.Name = obj2.Name)、私の C はここにあるでしょうか? 2つの配列の単なるユニオンですか？
この論文を読んで調べたところ、 は文字列のアルファベットを保持する配列であると言えCます。ここで、アルファベットのサイズ (したがって、のサイズC) はlです。
しかし、あなたの質問を見ると、全体像をまだ把握していないように見えるので、これについてさらに深く掘り下げる必要があると感じています。とは 何P[i,j]ですか?なぜそれが必要なのですか? 答えは、実際には必要ないということですが、これは洗練された最適化です。定理 1の少し前の 3 ページに、次のように書かれています。
[...] このプロセスは、k ステップ目で jk = 0、または k ステップ目で a(i) = b(jk) のときに終了します。プロセスが k 番目のステップで停止すると仮定すると、k は a(i) = b(jk) または jk = 0 になる最小の数でなければなりません。 [...]
(3) の再帰関係は (2) と同等ですが、根本的な違いは、(2) は再帰的に展開されるのに対し、(3) では、k を知っていれば、再帰呼び出しが発生しないことです。言い換えれば、(3) 再帰的に展開しないことの背後にある魔法は、(2) の再帰が停止する場所を何らかの方法で知っているため、再帰的にセルに近づくのではなく、すぐにそのセルを見ることです。
わかりましたが、どうやって の値を見つけますkか? k(2) が基本ケースに到達する場所であるため、限界を超えるまで (つまり、0 で埋められた最初の列)、k「戻らなければならない」列の量であることがわかります。 B)またはB、文字 inと文字 in A((2) の基本ケース条件に対応する)の間の一致を見つけます。現在の行a(i-1)である文字 に一致することに注意してください。i
したがって、本当に必要なのは、キャラクターが現れるB前の最後の位置を見つけることです。そのような文字が の前に現れない場合、それは (2)のケースに到達することと同じです。それ以外の場合は、(2) で到達するのと同じです。ja(i-1)Bji = 0 or j-1 = 0a(i) = b(j-1)
例を見てみましょう：
アルゴリズムが i = 2 と j = 3 の値を計算しているとします (行と列は灰色で強調表示されています)。アルゴリズムが黒で強調表示されたセルで機能し、(2) を適用して (黒のセルS[2,2]の左側の位置) の値を決定しているとします。(2) を適用すると、 と を見ることから始まりa(2)ますb(2)。a(2)は C でb(2)あり、G であり、一致するものはありません (これは、元のよく知られたアルゴリズムと同じ手順です)。(どこにいるか)S[2,2]を計算する必要があるため、アルゴリズムは の値を見つけようとしています。はまだわかっていませんが、この論文では、 の行を参照せずにその値を決定できることが示されています。(2) では、3 番目のケースが選択されます。S[2,3]S[2,2]i = 2S[2,2] = max(S[1, 2], S[2, 1]). この式が行っていることは、 の計算に使用されたであろう位置を調べることだけであることに注意してくださいS[2,2]。つまり、言い換えるとS[2,3]、 を計算している、そのためには が必要S[2,2]で、まだわからないので、テーブルに戻って の値を確認します。元の場合とS[2,2]ほとんど同じ方法です。 、非並列アルゴリズム。
これはいつ止まりますか？この例では、文字C(これは私たちのa(i)) がTGTTCGACA2 番目T(現在の列の文字) の前にある場合、または列 0 に達したときに停止します。 CbeforeがないためT、列 0 に到達します。別の例:
ここで、(2) は = 5 で停止します。なぜなら、それがwherej-1の最後の位置だからです。したがって、再帰は のときに基本ケースに到達します。TGTTCGACACa(i) = b(j-1)j-1 = 5
kこれを念頭に置いて、ここでショートカットを見ることができます: (2) の基本ケースである量を何らかの方法で知ることができればj-1-k、基本ケースを見つけるためにスコア テーブルを調べる必要はありません。
それが背後にある全体のアイデアP[i,j]です。Pアルファベット全体を垂直に（左側に）置く表です。弦Bは再び、上側に水平に配置されます。この表は、前処理ステップの一部として計算され、事前に知っておく必要があることを正確に教えjてBくれC[i]ますC。whereが見つかるB前に (は、文字列ではなく、アルファベットのindex に使用されることに注意してください。作成者は、混乱を避けるために別のインデックス変数を使用する必要があったかもしれません)。jC[i]iCA
したがって、エントリのセマンティクスは、P[i,j]次の行に沿ったものと考えることができます: B の最後の位置で、位置 j の前に C[i] を見ました。たとえば、アルファベットがsigma = {A, E, I, O, U}で、B = "AOOIUEI", thenP` が次の場合:
時間をかけてこの表を理解してください。の行に注意してくださいO。覚えておいてください: この行は、 のすべての位置についてB、 が最後に認識された「O」であることを示しています。ゼロ以外の値 (2) になるのは、そのときだけです。j = 3これは、最初の の後の位置だからOですAOOIUEI。このエントリは、前に見られたB場所の最後の位置Oが位置 2 であることを示しています (そして、実際にB[2]は、O次の位置Aです)。同じ行で、 forj = 4の値が 3 になっていることに注意してください。これは、 for の最後の位置Oが の 2 番目の位置に対応するためOですB(これ以上Oが存在しないため、行の残りは 3 になります)。
式 (2) からの再帰を停止させるPの値を簡単に見つけたい場合は、構築が必要な前処理ステップであることを思い出してください。（3）で探しているのは、k今でP[i,j]は意味があるはずです。kを使用すると、その値を時間Pで決定できます。O(1)
したがって、C[i](6) の はアルファベットの文字であり、現在検討している文字です。上記の例でC = [A,E,I,O,U]は、C[1] = A、C[2] = E、 などです。等式 (7) では、 (考慮されている文字列の現在の文字)がc存在する位置です。それは理にかなっています: 結局のところ、スコア テーブル positionを作成するとき、値を見つけるために使用したい -以前に最後に見たのはどこだったのかを知りたいのです。を読むことでそれを行います。Ca(i)AS[i,j]Pka(i)BjP[index_of(a(i)), j]
の使用法を理解したPので、実装で何が起こっているかを見てみましょう。
あなたの特定のケースについて
論文でPは、アルファベット全体をリストした表として示されています。このアルゴリズムの典型的な用途は、アルファベットが文字列よりもはるかに小さいバイオインフォマティクスであるため、アルファベットを反復処理することをお勧めしますA。
文字列はオブジェクトのシーケンスであるため、可能なすべてのオブジェクトのセットになるためC、可能なすべてのオブジェクト インスタンスのセットを含むテーブルを作成する必要がありPます (もちろんナンセンスです)。これは間違いなく、文字列のサイズに比べてアルファベットのサイズが大きい場合です。Pただし、からの文字に対応する行にのみインデックスを作成することに注意してください。 にない文字のA行は役に立たず、決して使用されません。これは、可能なすべてのオブジェクトのアルファベットを使用する代わりに、文字列を使用して構築できることを意味するため、作業が楽になります。PC[i]APA
繰り返しますが、例: アルファベットがAEIOU、AisEEIおよびBisの場合、およびの行でAOOIUEIのみインデックスを作成するため、 で必要なのはそれだけです。PEIP
(7) では、 は文字P[c,j]のエントリであり、は のインデックスであるため、これで十分です。つまり、常に に属しているため、 のサイズが のサイズよりもかなり小さい場合、アルファベット全体を使用する代わりにの文字を作成することは完全に理にかなっています。Pcca(i)C[c]APAAC
あとは、オブジェクトが何であれ、同じ原則を適用するだけです。
私はそれをもっとうまく説明する方法を本当に知りません。これは最初は少し濃いかもしれません。あなたが本当にそれを理解するまで、それを再読してください - そして、私はすべての細部を意味します. 実装を考える前に、これをマスターする必要があります。
注:信頼できる情報源や公式情報源を探しているとおっしゃいました。私は単なる CS の学生なので、公式の情報源ではありませんが、「信頼できる」と見なすことができると思います。私はこれを以前に勉強したことがあり、その主題を知っています。ハッピーコーディング！