文字列のリストで文字列を効率的に検索するには？

私は文字列のリストを持っており、与えられた入力値に一致する文字列を見つける必要があります。私はこの文字列のリストを保存してそれを検索できる最も効率的な方法（メモリ対実行速度）は何ですか？文字列のリストの起動と読み込みは重要ではありませんが、検索の応答時間は重要です。文字列のリストで文字列を効率的に検索するには？

リストやHashSet、または基本文字列[]などを使用する必要がありますか？

出典

2011-12-28 MakkyNZ

"big"は文字列のリストです。 –

StringCollectionクラスについて忘れないでください - http://msdn.microsoft.com/en-us/library/system.collections.specialized.stringcollection.aspx –

任意の文字列を複製できますか？単語や文字列全体を一致させる必要がありますか、それとも文字列内に含めることができますか？ –

それは、文字列の性質とコレクションのサイズに大きく依存します。コレクションの特性や予想される検索文字列によっては、検索が非常に高速になるように物事を巧みに整理する方法があります。あなたは私たちにその情報を与えていません。

しかし、ここで私は何をしています。私は合理的なパフォーマンス要件を設定したいと思います。それでは、n-gramインデックスを試してみたいと思います（なぜなら、コメントの中で、部分一致を説明する必要があるので、HashSet<string>はあなたを助けません）。それが自分のパフォーマンス要件を満たしているかどうかを確認してください。もしそうであれば、私は解決策を受け入れて移動します。そうでない場合は、自分のパフォーマンス要件が妥当かどうかについて非常に慎重に考えています。そうであれば、私は入力と収集について特別なものがあるかどうかを考えて、より巧妙な解決法を使うことができるかもしれません。

出典

2011-12-28 15:32:31 jason

HashSetは部分一致のニーズを満たすことができません（文字列を "複製する"ことができます）。重複するので、とにかく、HashSetではなく、辞書になるだろう） – Random832

@ Random832：彼の質問は、部分一致や重複について何も言わない！ – jason

フォローアップのコメントがありました。あなたが何が必要なのか分からずにFGITWであることを急いで、元の言葉がHashSetが解決できる問題を暗示することに近づくことはありません。「どの文字列が与えられた入力値と一致するか」を注意深く読んで、複数が部分一致を意味することを示します（1つの文字列が完全に一致することができます）。 – Random832

Dictionary<string>()またはHashSet<string>を使用してください。

出典

2011-12-28 15:31:46

+1：これは、文字列のリストで検索文字列を最適化することを考えたときに最初に思いつきました。最初の一般的な解決策は辞書を最も一般的な解決策とする「インデックス作成」です。 –

@StephaneRollandはい一番簡単なのは一番良いですが、もう一度価値があるgotafexソリューションです。 –

-1

ディクショナリとハッシュテーブルはO（1）の速度であるため、「検索」で最も高速になります。ディクショナリとハッシュテーブルには、ソートされていないという点でいくつかの落とし穴があります。

バイナリ検索ツリーを使用すると、O（ログN）検索を取得できます。

ソートされていないリストを使用すると、検索の速度がO（N）になります。

ソートされたリストを使用すると、O（ログN）検索が実行されますが、全体の速度に時間を追加するようにリストをソートする必要があることに注意してください。

メモリの使用に関しては、コレクションのサイズを初期化してください。

したがって、辞書またはハッシュテーブルが検索に最も高速です。最高から最低まで

速度分類はある O（1） O（ログn）の O（n）の O（NログN）はO（n^2） O（2^n）の

nは要素数です。

出典

2011-12-28 15:44:11 Odnxe

です。@FelicePollano私はO（1）の意味が正しいとは思いません。 – Random832

@ Random832インサートのO（1）です。検索では、O（1）でリストを検索し、線形検索を実行します。あなたに何が間違っていますか？ –

リニアに検索されなければならない「リスト」（適切な数のバケットがあれば）は、同じハッシュを持つ多数のアイテムがない限り、O（1）はまだ償却されていることを意味しますコード[意図的にこのように構築されている場合を除き]は挿入されません。 – Random832

O（input_len）時間に入力の接尾辞ツリーを作成し、次にO（pattern_length）時間のパターンを照会するのが最善の方法です。あなたのパターンに比べてあなたのテキストが本当に大きければ、これはうまくいくでしょう。

サフィックスツリーを構築するためのUkkonenのアルゴリズムを参照してください。

不正確な照合が必要な場合は... Gonzalo Navarroの作品を参照してください。

出典

2011-12-28 15:46:19

編集のためのtx。 :) –

"トライの各ノードに256文字以上の128文字/バイトの配列を作成するだけです。"配列は、バイトではなく、nodes_の256/128のポインタになります。 – Random832

または...より正確には、オブジェクト参照/ポインタの文字のascii（またはその他の文字セット）コードでインデックス付けされた配列Node node * = new Node [128]。あなたの改善のためにRandom832ありがとうございました。 –

文字列のリストで文字列を効率的に検索するには？

答えて

関連する問題