9

次のような状況があります: 平均的な長さはおそらく 30 の文字列 (250.000+ としましょう) の大きなコレクションがあります。

コレクションは実行時に静的です。つまり、選択したコレクションの最初の読み取りと入力は一度だけ行われます..したがって、データ構造を構築するパフォーマンスはまったく重要ではありません。メモリも問題ではありません。つまり、必要に応じて同じデータを持つ 2 つのコレクションを作成してもかまいません (1 つは startwith 用、もう 1 つは含む場合など)。重要なのは、検索条件に一致するすべての要素を返す必要がある検索のパフォーマンスだけです。

まず、Trie または Radix-tree に出くわしました..しかし、もっと良い選択肢があるのではないでしょうか?

を含む..私にはまだ良い考えがありません（その量のデータでは非常に高速ではないリストでlinqクエリを実行する以外に）。

よろしくお願いします！

更新：重要な部分を忘れていました：Containsを使用すると、コレクションに完全に一致するものがないことを意味します..しかし、指定された検索文字列を含むコレクション内のすべての文字列を見つけたい

4

1 に答える 1

4

接尾辞ツリーを作成すると、すべての文字列に対して部分文字列検索を並行して実行できますO(1)。私のペダンティックは、部分文字列に一致する文字列の数が実際O(n + m)にはどこにあり、クエリされる部分文字列のサイズであることに注意せずにはいられません。nm

では、あなたが尋ねる接尾辞ツリーとは何ですか? 最も基本的な実装では、より手の込んだ挿入メソッドを使用したトライです。文字列を追加するだけでなく、その文字列のすべての可能なサフィックスもトライに追加します。このデータ構造では、部分文字列検索は可能なすべてのサフィックスのプレフィックス検索になります。プレフィックス検索も行いたいので、挿入された各文字列とクエリ部分文字列の前に特殊文字を追加する必要があります。特殊文字を使用すると、サフィックスと完全な文字列を区別できます。

このサフィックス ツリーの実装は非常に単純ですが、非常に非効率的でもあります (O(n^2)スペースとビルド時間)。幸いなことに、空間と時間の境界を大幅に削減できる、より効率的な実装が他にもあります。これらの 1 つである Ukkonen のアルゴリズムは、この SO の回答で非常によく説明されており、スペースの境界を に下げO(n)ます。また、接尾辞ツリーと同等ですが、より効率的な表現である接尾辞配列を調べることもできます。

サフィックスツリーの実装が他にもたくさんあることは知っていますが (そのうちの 1 つがユースケースのスイートスポットにヒットする可能性があります)、それらを知りません。実装を決定する前に、この件について調査することをお勧めします。

于 2013-03-03T23:59:43.457 に答える