文字列のセットで未知の繰り返しパターンを見つける方法はありますか？

Question

ここに問題の説明があります。文字列のセット（最大100億の文字列、各文字列の長さは最大10k文字、1000個のユニークなシンボル文字列が構築できる）があるとします。長さが2から長さNまでのパターンを見つけるにはどうすればよいですか（簡略化のために10と言うことができます）。また、私はすべての文字列の少なくとも1％（ある閾値）で発生するパターンだけを見たいと思います。

私はこの問題を解決するのに役立つアルゴリズムを見つけたいと思います。数字は正確ではありませんが、私たちがプロジェクトで持っているのと同じオーダーです。

はあなたに接尾辞木（link）で

Answer 1

すべてのインデックスの文字列をありがとうございました。これはO（文字数）にすることができ、開始する前に一度だけ行う必要があります。

接尾辞ツリーを使用すると、索引付けした文字列のいずれかにパターンが表示されているかどうか、また何回表示されるかを簡単に（O（パターン長））知ることができます。

構造をもう1つパスして、各サブツリー（O（N）のリーフの数をもう一度カウントすることができます）と、そのノードのルートから部分文字列を見つけることができる頻度がわかります。それらがどれほど共通しているかに基づいて、あなたが望むものを何でもします。

今では、ラムに収まらない2バイト文字（1000個のユニークな記号に合う）を持つ10億本の文字列がかなり大きい（私の数学が正しい場合は18TB）。だから、しばらく待つか、コンピュータを増やして、分散されたソリューションをセットアップする必要があります。上記のソリューションを利用可能なメモリに収まるようにバッチの文字列に適用することができますが、構造内の参照には実行中のバッチの数を掛ける必要があります。

すべてがバッチであれば、最も効率的な方法はできるだけ大きなバッチを作成することです。その後、バッチのサフィックスツリーを作成してすべてのクエリを実行したら、結果を保存して次のバッチの入力文字列のためにメモリを解放します。