この記事では、サフィックス ツリーを利用してマッチング時間を改善する近似部分文字列マッチング手法について説明します。各回答は、異なるアルゴリズムに対応しています。
P部分文字列の近似一致では、文字列内の部分文字列 (パターン) を見つけようとしますが、不一致はT許容されます。k新しいアルゴリズムを追加し (不完全であっても)、回答を改善するように人々を招待します。
これは、このスレッドを開始した最初の質問でした。
Esko Ukkonen 教授は次の論文を発表しました。彼は、異なる一致時間を持つ 3 つの異なるアルゴリズムについて説明します。
O(mq + n)O(mq log(q) + size of the output)O(m^2q + size of the output)mは部分文字列のn長さ、 は検索文字列の長さ、 はq編集距離です。
アルゴリズム B を理解しようとしていますが、手順を実行するのに問題があります。誰もこのアルゴリズムの経験がありますか? 例または疑似アルゴリズムは大歓迎です。
特に：
size of the output接尾辞ツリーまたは入力文字列に関しては何を参照していますか? 最後の出力フェーズでは、出力用にマークされたすべての状態について、 inのすべての出現がリストされます。Key(r)Triindex が何を表しているのかわかりません。初期化されておらず、増加していないようです。これが私が信じていることです（私は修正されるつもりです）：
rootは初期状態を示します。g(a, c) = bここでa、 およびbはツリー内のノードであり、 はツリー内cの文字または部分文字列です。したがって、これは遷移を表します。からa、 で表されるエッジをたどって、cノード に移動しますb。これは、go-to トランジションと呼ばれます。したがって、以下の接尾辞ツリーについては、g(root, 'ccb') = red node
Key(a) = edge sequencewhereaはツリー内のノードを表します。たとえば、Key(red node) = 'ccb'. だからg(root, Key(red node)) = red node。Keys(Subset of node S) = { Key(node) | node ∈ S}aノードandbのサフィックス関数がありますf(a) = b: すべて (または存在する可能性があります) a≠に対して、文字 、部分文字列、および および のようなノードrootが存在します。これは、上記の接尾辞ツリーの例では、whereと.cxbg(root, cx) = ag(root, x) = bf(pink node) = green nodec = 'a'x = 'bccb'Hサフィックス ツリーのノードと値のペアを含むマッピングがあります。値は次の式で与えられloc(w)ます。関数を評価する方法はまだわかりません。このディクショナリには、削除されていないノードが含まれています。extract-min(H)(node, loc(w))からのペアで最小値を持つエントリを取得することを意味しHます。アルゴリズムの核心は、 がどのようloc(w)に評価されるかに関係しているようです。ここで組み合わせた回答を使用して、サフィックスツリーを作成しました。ただし、アルゴリズムはサフィックス トライ (圧縮されていないサフィックス ツリー) で動作します。したがって、深さなどの概念は、異なる方法で維持および処理する必要があります。サフィックス trie では、深さはサフィックスの長さを表します。サフィックス ツリーでは、深さは単にツリー内のノードの深さを表します。
あなたは良くやっている。私はアルゴリズムに精通していませんが、今日論文を読みました。あなたが書いていることはすべて正しいです。説明のいくつかの部分が多くのことを想定していることは正しいです。
あなたの質問
1.サフィックスツリーまたは入力文字列に関して、出力のサイズは何を指しますか? 最終的な出力フェーズでは、出力用にマークされたすべての状態 r について、T 内の Key(r) のすべての出現がリストされます。
出力は、T 内の P の最大 k 距離の一致で構成されます。特に、それぞれの最終的なインデックスと長さを取得します。したがって、明らかにこれも O(n) (big-O は上限であることを思い出してください) ですが、これよりも小さい場合があります。これは、O(p) 時間未満で p 個の一致を生成することは不可能であるという事実への同意です。制限された残りの時間は、パターンの長さと実行可能なプレフィックスの数のみに関係し、どちらも任意に小さくすることができるため、出力サイズが支配的になります。k=0 で、入力がパターン「a」で n 回繰り返される「a」であるとします。
2. アルゴリズム C を見ると、関数 dp が定義されています (4 ページ)。i が表すインデックスがわかりません。初期化されておらず、増加していないようです。
あなたが正しい。エラーです。ループ インデックスは である必要がありますi。どうjですか？これは、動的プログラムで処理されている入力文字に対応する列のインデックスです。これは実際には入力パラメーターである必要があります。
一歩後退しましょう。6 ページの例の表は、前述の式 (1 ～ 4) を使用して、左から右に列ごとに計算されます。これらは、次の列を取得するために D と L の前の列のみが必要であることを示しています。Functionは、からdp列を計算するというこのアイデアの単なる実装です。D と L の列は、それぞれ と と呼ばれます。列D と L は と、関数の入力パラメーターです。jj-1jdlj-1d'l'
よく理解できるまで動的プログラムを実行することをお勧めします。このアルゴリズムは、列の計算の重複を避けるためのものです。ここでの「重複」とは、「重要な部分で同じ値を持つ」ことを意味します。それだけが重要だからです。重要でない部分は答えに影響を与えることはできません。
圧縮されていないトライは、文字ごとに 1 つのエッジを持つように明白な方法で展開された圧縮トライです。「深さ」の考え方を除けば、これは重要ではありません。圧縮されたツリーでは、depth(s) は、ルート ノード s から取得するために必要な文字列 (彼はこれを Key(s) と呼びます) の長さにすぎません。
アルゴリズムA
アルゴリズム A は、巧妙なキャッシング スキームです。
彼のすべての定理と補題は、1) 列の本質的な部分だけを気にする必要があること、2) 列 j の本質的な部分は実行可能なプレフィックス Q_j によって完全に決定されることを示しています。これは、パターンの接頭辞 (編集距離 k 内) に一致する、j で終わる入力の最長の接尾辞です。言い換えれば、Q_j は、これまでに考慮された入力の最後にある k-edit 一致の最大開始点です。
これで、アルゴリズム A の疑似コードは次のようになります。
Let r = root of (uncompressed) suffix trie
Set r's cached d,l with formulas at end page 7 (0'th dp table columns)
// Invariant: r contains cached d,l
for each character t_j from input text T in sequence
Let s = g(r, t_j) // make the go-to transition from r on t_j
if visited(s)
r = s
while no cached d,l on node r
r = f(r) // traverse suffix edge
end while
else
Use cached d',l' on r to find new columns (d,l) = dp(d',l')
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s
while depth(r) != |Q_j|
mark r visited
r = f(r) // traverse suffix edge
end while
mark r visited
set cached d,l on node r
end if
end for
簡単にするために、出力ステップを省略しました。
サフィックスエッジのトラバースとは何ですか? Key(r) = aX (a の後に文字列 X が続く) ノード r からこれを行うと、キー X を持つノードに移動します。結果: 実行可能なプレフィックス Q_h に対応する各列を格納しています。プレフィックス Q_h を持つ入力のサフィックスのトライ ノード。関数 f(s) = r は接尾辞遷移関数です。
それだけの価値はありますが、サフィックス ツリーのウィキペディアの写真は、これをかなりよく示しています。たとえば、"NA" のノードからサフィックス エッジをたどると、"A" のノードに到達し、そこから "" に到達します。私たちはいつも主役を切り捨てています。したがって、状態 s に Key(s) のラベルを付けると、f("NA") = "A" および f("A") = "" になります。(なぜ彼が論文でこのように州にラベルを付けないのか私にはわかりません。多くの説明を単純化するでしょう。)
実行可能なプレフィックスごとに 1 つの列のみを計算しているため、これは非常にクールです。ただし、各文字を検査し、各文字のサフィックス エッジをトラバースする可能性があるため、依然としてコストがかかります。
アルゴリズム B
アルゴリズム B の意図は、入力をスキップして、新しい列を生成する可能性が高い文字、つまり、パターンの以前には見られなかった実行可能なプレフィックスに一致する入力の末尾にある文字のみに触れることで、高速化することです。
ご想像のとおり、アルゴリズムの鍵はloc関数です。大まかに言えば、次の「可能性の高い」入力文字がどこにあるかがわかります。このアルゴリズムは、A* 検索にかなり似ています。論文のセット S_i に対応する最小ヒープ (削除操作が必要) を維持します。(彼はそれを辞書と呼んでいますが、これはこの用語のあまり慣習的な使用法ではありません。) 最小ヒープには、前述のように、次の「可能性の高い文字」の位置に基づいた潜在的な「次の状態」が含まれています。1 文字を処理すると、新しいエントリが生成されます。ヒープが空になるまで続けます。
ここで彼が大雑把になるのはあなたが絶対に正しいです。定理と補題は、正しさについて議論するために結び付けられていません。彼はあなたが彼の仕事をやり直すと思っています。私はこの手を振ることに完全には納得していません。しかし、彼が考えているアルゴリズムを「解読」するには十分なようです。
もう 1 つの核となる概念は、集合 S_i であり、特に除去されない部分集合です。これらの削除されていない状態を最小ヒープ H に保持します。
表記が S_i の意図を覆い隠していると言うのは正しいです。入力を左から右に処理して位置 i に到達すると、これまでに見た実行可能なプレフィックスのセットが蓄積されました。新しい列が見つかるたびに、新しい dp 列が計算されます。著者の表記法では、これらの接頭辞はすべての h<=i またはより正式には { Q_h | h <= i }。これらにはそれぞれ、ルートから一意のノードへのパスがあります。セット S_i は、トライの go-to エッジに沿ってこれらすべてのノードからもう 1 ステップ取得することによって得られるすべての状態で構成されます。これは、Q_h と次の文字 a の出現ごとにテキスト全体を検索し、Q_h a に対応する状態を S_i に追加するのと同じ結果になりますが、その方が高速です。
適切な候補者を選ぶにはどうすればよいでしょうか。入力の位置 i の次に発生するものを選択します。ここで loc(s) の出番です。状態 s の loc 値は、まさに上で述べたとおりです。つまり、その状態に関連付けられた実行可能なプレフィックスが次に発生する i から始まる入力内の位置です。
重要な点は、新しく見つかった (H から min loc 値をプルすることによって) 「次の」実行可能なプレフィックスを Q_{i+1} (dp 列 i+1 の実行可能なプレフィックス) として割り当てるだけではいけないということです。次の文字 (i+2) に進みます。ここで、 Q_k = Q_{i+1}のように、可能な限り最後の文字 k (dp 列 k) までスキップするようにステージを設定する必要があります。アルゴリズム A のように接尾辞のエッジをたどって先にスキップします。今回のみ、H を変更して将来の使用のためにステップを記録します。つまり、S_i から要素を削除するのと同じように要素を削除し、loc 値を変更します。
関数 loc(s) の定義はむき出しであり、彼はそれを計算する方法を決して言いません。また、loc(s) も i の関数であり、現在の入力位置が処理されていることも言及されていません (現在の入力位置について、論文の前の部分の j から i にジャンプすることは役に立ちません)。 (s)入力処理が進むにつれて変化します。
削除された状態に適用される定義の部分は、フォーム H の削除時に状態が削除されたとマークされるため、「ちょうど起こる」ことがわかります。したがって、この場合、マークを確認するだけで済みます。
もう 1 つのケース (削除されていない状態) では、入力を前方に検索して、他の文字列でカバーされていないテキスト内の次の出現を探す必要があります。このカバーの概念は、「可能な限り長い」実行可能なプレフィックスのみを常に処理することを保証するためのものです。最大一致以外の出力を避けるために、短いものは無視する必要があります。さて、順方向検索はコストがかかるように聞こえますが、幸いなことに、O(|Key(s)|) 時間で実行できる接尾辞 trie が既に構築されています。トライは、関連する入力位置を返し、カバーされたキーの発生を回避するために注意深く注釈を付ける必要がありますが、それほど難しくはありません。彼は、検索が失敗したときに何をすべきかについては決して言及しません。ここで loc(s) = \infty です。つまり、これは消去されており、H から削除する必要があります。
おそらく、アルゴリズムの最も厄介な部分は、すでに H にあった w の Key(w) をカバーする実行可能なプレフィックスの新しい状態 s を追加する場合に対処するために H を更新することです。これは、(loc を外科的に更新する必要があることを意味します。 (w) => w) H の要素。接尾辞 trie が、接尾辞 edge でこれを効率的にサポートしていることがわかります。
これらすべてを頭の中で考えて、疑似コードを試してみましょう。
H = { (0 => root) } // we use (loc => state) for min heap elements
until H is empty
(j => s_j) = H.delete_min // remove the min loc mapping from
(d, l) = dp(d', l', j) where (d',l') are cached at paraent(s_j)
Compute |Q_j| = l[h], h = argmax(i).d[i]<=k as in the paper
r = s_j
while depth(r) > |Q_j|
mark r eliminated
H.delete (_ => r) // loc value doesn't matter
end while
set cached d,l on node r
// Add all the "next states" reachable from r by go-tos
for all s = g(r, a) for some character a
unless s.eliminated?
H.insert (loc(s) => s) // here is where we use the trie to find loc
// Update H elements that might be newly covered
w = f(s) // suffix transition
while w != null
unless w.eliminated?
H.increase_key(loc(w) => w) // using explanation in Lemma 9.
w = f(w) // suffix transition
end unless
end while
end unless
end for
end until
ここでも、簡単にするために出力を省略しました。これが正しいとは言いませんが、大まかです。1 つのことは、「訪問済み」の前ではないノードの Q_j のみを処理する必要があると彼が述べていることですが、このコンテキストで「訪問済み」が何を意味するのかわかりません。アルゴリズム A の定義による訪問状態は、H から削除されているため発生しないと思います。パズルです...
補題 9のincrease_key操作は、証明なしで急いで記述されています。min 操作が O(log |alphabet|) 時間で可能であるという彼の主張は、多くのことを想像に任せています。
癖の多さから、これが論文の最終草案ではないのではないかと思います。これは Springer の出版物でもあり、オンラインのこのコピーがまったく同じである場合、著作権の制限に違反する可能性があります。ライブラリを調べたり、最終版にお金を払って、最終レビュー中にラフなエッジの一部が削除されていないかどうかを確認する価値があるかもしれません.
これは私が得ることができる限りです。具体的な質問がある場合は、明確にしようとします。