5

2 つの非常に大きな文字列があり、それらのLongest Common Substringを見つけようとしています。

1 つはサフィックス ツリーを使用する方法(複雑な実装ですが、非常に複雑であると想定されます) であり、もう 1 つは動的プログラミング方法です(どちらも上記のリンク先の Wikipedia ページで言及されています)。

動的計画法の使用 代替テキスト

問題は、動的計画法の実行時間が非常に長いことです (複雑さはO(n*m)で、nとmは 2 つの文字列の長さです)。

私が知りたいこと (接尾辞ツリーの実装にジャンプする前に):共通部分文字列の長さだけを知りたい場合 (共通部分文字列自体ではなく)、アルゴリズムを高速化することは可能ですか?

4

4 に答える 4

3

これらにより、実行速度は向上しますが、それでも実行されますO(nm)。

最適化の1つはスペースであり（割り当て時間を少し節約できる可能性があります）LCSuff、前の行にのみ依存することに気づいています。したがって、長さだけを気にする場合は、O(nm)スペースをに最適化できますO(min(n,m))。

アイデアは、処理中の現在の行と処理したばかりの前の行の2つの行だけを保持し、残りを破棄することです。

于 2010-04-25T21:29:27.923 に答える
2

実際には速くなりますか？はい。Big-Ohに関しては速くなりますか？いいえ。動的計画法の解は常に O(n*m) です。

サフィックス ツリーで遭遇する可能性のある問題は、サフィックス ツリーの線形タイム スキャンと引き換えにスペースの大きなペナルティが発生することです。通常、サフィックス ツリーは、動的プログラミング バージョンのアルゴリズムに実装する必要があるテーブルよりもはるかに大きくなります。文字列の長さによっては、動的プログラミングが高速になる可能性は十分にあります。

幸運を ：）

于 2010-04-25T21:24:17.467 に答える
0

これは、O((m+n)*log(m+n)) で終了できる単純なアルゴリズムであり、O(m+n) ランタイムであるサフィックス ツリー アルゴリズムと比較して実装がはるかに簡単です。

最小共通長 (minL) = 0、最大共通長 (maxL) = min(m+n)+1 で開始します。

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

残りの問題は、時間 O(n) で長さ L のすべての部分文字列をハッシュする方法です。次のように多項式を使用できます。

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];
于 2015-11-16T05:21:28.743 に答える
-1

Myer のビット ベクトル アルゴリズムが役に立ちます。これはビット操作を使用して機能し、はるかに高速なアプローチです。

于 2015-11-16T04:04:24.347 に答える