どのC＃データ構造によって、部分文字列に対して最も効率的に文字列のペアを検索できますか？

Question

Iは整数であり、（数字で開始することができる）、英数字の文字列となっている第二である第一その値の対からなるデータ構造を有する：

+--------+-----------------+ 
| Number | Name   | 
+--------+-----------------+ 
| 15  | APPLES   | 
| 16  | APPLE COMPUTER | 
| 17  | ORANGE   | 
| 21  | TWENTY-1  | 
| 291 | 156TH ELEMENT | 
+--------+-----------------+ 

これらのテーブルだろう100,000行までを構成します。

私は、数字（文字列のように）または文字列の一部のいずれかをユーザーが検索できるルックアップ機能を提供したいと考えています。理想的には、ユーザのタイプに応じてルックアップが「ライブ」になります。各キーストロークの後（または、わずかに遅れて〜250-500ms後）、最も可能性の高い候補を見つけるために新しい検索が行われる。そのため、例えば、理想的（291 156TH ELEMENT

APが15 APPLESと16 APPLE COMPUTER

を返し、15 APPLESに検索を絞り込むます15 APPLES、16 APPLE COMPUTER、17 ORANGE、および291 156TH ELEMENT

15 を返します

• 1で検索、必須ではありません）ELEMは291 156TH ELEMENTを返します。

Iは、最終的int sはstring sと比較されているから2つのDictionary<string, string> Sを使用して考えていた - 文字列の一部ずつ意志の整数部分によってインデックスおよびその他。

しかし、実際に部分文字列で検索するとハッシュ関数を使用すべきではありません。必要と思われるメモリを2倍使用するのは無駄です。

最終的には、サブストリングのために2つの大きなリストを同時にテキスト検索することはうまくいくのですか？

これが失敗すると、SortedDictionaryはどうですか？パフォーマンスは向上しますが、ハッシュの問題は解決されません。

オンザフライで正規表現を作成することについて考えましたが、それはひどく実行すると思います。

私はLINQをまだ見ていないので、私はC＃（Javaの世界から来たもの）が新です。それは答えですか？

EDIT 18:21 EST：潜在的な解決方法に影響する場合、「名前」フィールドの文字列は12-15文字より長くなりません。

Answer 1

私はTrieデータ構造の使用を検討したいと思います。

これを達成する方法は？リーフはあなたの「行」を表しますが、「行」の各メモリインスタンスには「2つのパス」があります（数字用と名前用の2つのパス）。

次に、あなたの条件を犠牲にすることができます

(ideally, but not required) ELEM will return 291 156TH ELEMENT. 

またはあなたの行インスタンスにも、複数のパスを提供します。

Answer 2

可能であれば、すべての100,000エントリをメモリに読み込まないようにします。私はデータベースまたはLucene.Netのいずれかを使用して値を索引付けします。次に、適切なクエリ構文を使用して、結果を効率的に検索します。

Answer 3

"a"、 "ap"、 "app"、 "appl"、 "apple"などの単語のすべての部分を保存しない限り、単語の先頭を検索しているので、キーベースのコレクションは機能しません"

私の提案は、System.Collections.Generic.List<T>とバイナリ検索を併用することです。あなた自身もIComparer<T>を提供しなければならないでしょう。これはまた単語の始まりを見つけます。 2つのデータ構造を使用します。

List<KeyValuePair<string,int>>は、単一の単語または数字をキーとして、数値を値として保持します。

名前全体を保持するDictionary<int,string>。

あなたは次のように進行する：

1. 単一の単語にあなたの文章（全体の名前）を分割します。

2. 単語をキーとして、数字をKeyValuePairの値としてリストに追加します。

3. 数字をKeyValuePairのキーと値としてリストに追加します。

4. リストがいっぱいになると、バイナリ検索を可能にするためにリストをソートします。

単語の先頭を検索：

1. 検索リストであなたのIComparer<T>と一緒にBinarySearchを使用します。

2. 検索から得られるインデックスが最初に適用されるインデックスでない可能性があるので、最初に一致するエントリが見つかるまでリストに戻ってください。

3. リストに値として格納されている番号を使用して、この番号をキーとして使用して辞書内の名​​前全体を検索します。