私は、再発する文字シーケンスを識別するための効率的なアルゴリズムを見つけようとしています。シーケンスが3文字以上であり、最大長シーケンスだけを返すとします。データセットは、潜在的に何千もの文字になる可能性があります。また、私は、それが繰り返されるならば、シーケンスについて知りたいだけです、言い換えれば、3回。例として繰り返しのイベントシーケンスを見つける方法
： ASHEKBSHEKCSHEDSHEK
"蒋介石" は3回発生し、同定されるであろう。 「SHE」は4回生じるが、「SHEK」はその配列を含む最大長配列であるため、同定されない。
また、「シード」シーケンスはアルゴリズムに供給されず、自律的にそれらを見つける必要があります。あなたは合計（N）/ 2可能な出発文字列が\存在することを考える場合には、事前に
おかげで、 J
このアルゴリズムを使用して実際に私の実装のために働いた。 – tunneling
のように見える、とあなたはそうではありません単純にを探して、が一致しますが、最も一致する部分文字列が正しいとすれば、あなたのアルゴリズムはひどく理論的に複雑になります。
しかし、Trieを使用すると、実用的な速度が得られる場合があります。トライにそれを挿入...それぞれの長さの部分文字列の場合は
あなたはビルドアップしたらトライをいくつかの最適化のしきい値（あなたのケースでは3）下記の根でトライからすべてのサブツリーを削除し、あなたのデータをモデル化します。
これらの残りのパスは、必要なものを効率的にソートアンドピックするために十分な数でなければなりません。
Trieは共通プレフィックスを操作するために作成され、副作用としてデータセットを圧縮するため、これを出発点としてお勧めします。
自分が望むものを特定した後に、サブストリングの場所を別のプロセスとして識別することを個人的に選択します。それ以外の場合は、すべての部分文字列の場所を格納することになり、それがメモリを爆発させます。あなたの計算はすでにかなり複雑です。
これはいくつかの意味がありますように！がんばろう！
は、以下のアルゴリズムを、考えてみ一致する接尾辞配列に連続した行の先頭をチェックサブストリングstr(0..i)のsuffix tree
T(i+1)を迅速に、入力文字列str内の各文字位置iについてthis algorithm
を使用して、例えば、T(i)から得られたエッジに沿って、T(i)のルートから始まる パスを横切る、より 連続文字で標識されています入力は、位置i + 1から始まります。
このパスは、繰り返し文字列を決定します。パスがすでに見つかったパスが より長い場合は、新しい最大長と位置 i + 1を記録します。
接尾辞ツリーをstr [i+1]で更新し、次の位置で繰り返します。この擬似コードのような
何か：k番目の反復で
max.len = 0
max.off = -1
T = update_suffix_tree (nil, str [0])
for i = 1 to len (str)
r = root (T)
j = i + 1
while j < len (str) and r.child (str [j]) != nil
r = r.child (str [j])
++j
if j - i - 1 > max.len
max.len = j - i - 1
max.off = i + 1
T = update_suffix_tree (T, str [i+1])
、インナーwhileは最大n - k回の反復のために実行され、接尾辞木構造は、O(k)あるので、 ループ本体の複雑さがO(n)であり、それはですn-1回、 を実行します。したがってアルゴリズム全体の複雑さはO(n^2)です。
私の答えの一部ではありませんが、SWIGを見て、あなたの内部ループの仕事をC++にコンパイルすることをお勧めしますか？私は以前はNLP/Machine Learningに取り組んできましたが、もし私がコアアルゴリズムをC++に入れて、計算サーバ/ Hadoopクラスタ上のJVMにそれらをリンクさせるのであれば、しかし、ちょっと考えましたが... – Sam