私は最近、C＃のインタビューセッション中にこの質問をした

Question

大きな本のように巨大な文字列内の文字列の出現回数を見つける方法：どのように効率的に単語の出現回数内を見つけるだろう

大きな本のような巨大なテキスト（聖書、辞書など）。

この本の内容を格納する最も効率的なデータ構造は何でしょうか。私が考えることができるもっとも汚いのは、StringBuilderに格納して部分文字列の数を調べることでしたが、これを行うにはより良い方法が必要です。

そして、合理的なサイズの文字列の場合、部分文字列、正規表現などを使用してこれを行う方法は複数ありますが、最も効率的な方法は何とかしています。

アップデート：私は何を探していますが、このです：

テキストファイルがあると仮定すると、サイズが20メガバイトの、聖書を言うと、私は回数に単語「イエス」を見つけたい、再びすることができます文字列またはStringBuilderに20 MB全体をロードし、部分文字列または正規表現を使用して一致数を検索する以外に、テキスト内に文字列全体が格納される他のデータ構造があります。実際の検索は複数の方法で行うことができます。私が探しているのは、一時的なストレージのための最も効率的な "データ構造"です。

Answer 1

あなたは完全な単語マッチを行うと仮定します（プレフィックスマッチのために働くこともできます）。

カウント情報を持つ聖書からトライを構成します。

単語を照会する必要がある場合は、トライを歩き、カウントを取得します。

部分文字列一致を行う必要がある場合は、接尾辞ツリー（基本的にはトライですが、接尾辞も含めて）を試してみることができます。

これは言葉が変更を照会すると仮定し、聖書が固定されたまま...

Answer 2

ウィキペディアは、文字列検索に興味深い記事があります http://en.wikipedia.org/wiki/String_searching_algorithm をし、その記事によると、このアルゴリズムは、ベンチマークの一種である： http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm

Answer 3

聖書の大きさは、文字列全体がメモリにキャッシュされないように巨大ではないので、私は前にこの方法を使っていましたが、明らかに雷が速くないでしょう。厳密に言えば、計算の観点から効率的に言えば、これは最速ではありませんが、コーディングのスピードと合理的なスピードから、ナノ秒がカウントされるまでこれが機能すると思います。

 string text = "a set of text to search in. fast to implement."; 
     string key = "to"; 
     MessageBox.Show(text.Split(" ',.".ToCharArray()).Where(a => a == key).Count().ToString()); 

編集：最終バージョンの質問は解決されず、元の質問が誤っている可能性があります。無視する。

Answer 4

部分文字列は気にしないでくださいが、完全な単語であれば、ハッシュテーブルを使用します。線形時間で構築することができ、サイズは異なる単語の数に比例する。特にDictionary<string,int>。私のマシンでは、聖書全体をハッシュテーブルにロードし、単語「神」のすべてのエントリを見つけるのに約450msかかりました。