私の問題は、約 7,000 個の 512 ビット文字列で構成されるデータセットがあり、それらを相互に比較して 30 ビット以上の繰り返しシーケンスを識別する最も効率的な方法を探していることです。
ブルートフォースの使用を検討しましたが、適切な解決策ではないようです。
文字列マッチングを実行するアルゴリズムはたくさんありますが、どれが自分の問題に最も適しているかわかりません
質問する
816 次
1 に答える
3
文字列の大きなコレクションがあり、それらすべての文字列に共通する長い部分文字列を見つけたい場合は、すべての文字列に対して一般化されたサフィックス ツリーを構築することを検討してください。これが完了すると、深さ優先検索でツリーを反復処理し、複数の異なる文字列の終了マーカーを持つ部分文字列を探すことで、文字列の任意のサブセットに共通するすべての部分文字列を見つけることができます。
一般化されたサフィックス ツリーのサイズは O(N) であり、N はすべての異なる部分文字列にわたる文字の総数であり、サフィックス ツリーは O(N) の時間で構築できるため、この操作の全体的な実行時間は次のようになります。 O（N）になります。
お役に立てれば！
于 2013-08-09T19:47:56.367 に答える