アプリケーションのメモリにおそらく100,000個の文字列のリストがあります。特定のキーワード（大文字と小文字を区別しない）を含む上位20個の文字列を見つける必要があります。これは簡単です。次のLINQを実行するだけです。
from s in stringList
where s.ToLower().Contains(searchWord.ToLower())
select s
しかし、私はこれをはるかに速く行うことができるという明確な感覚を持っており、このリストを1秒間に複数回検索する必要があるため、その方法を見つける必要があります。
サブストリング（完全一致ではない）を見つけるのは驚くほど難しいです。これを支援する組み込みのものはありません。サブストリングを効率的に見つけるために使用できるサフィックスツリーのデータ構造を調べることをお勧めします。
ローカル変数にプルアウトsearchWord.ToLower()して、大量の文字列操作を節約できます。stringListの小文字バージョンを事前に計算することもできます。事前計算できない場合は、少なくともを使用してs.IndexOf(searchWord, StringComparison.InvariantCultureIgnoreCase) != -1ください。これにより、高価なToLower呼び出しを節約できます。
クエリで.AsParallelを叩くこともできます。
別のオプションは、かなりの量のメモリを必要としますが、接尾辞配列（文字列内の位置のリスト、それらが指す文字列でソートされたもの）のようなものを事前計算することです。
http://en.wikipedia.org/wiki/Suffix_array
これは、検索する文字列のリストが比較的静的である場合に最も実行可能です。文字列インデックスのリスト全体をタプルの単一配列（indexOfString、positionInString）に格納し、その上でを使用してバイナリ検索を実行できますString.Compare(keyword, 0, target, targetPos, keyword.Length)。
したがって、平均20の長さの100,000の文字列がある場合、構造体には100,000 * 20 * 2 * sizeof（int）のメモリが必要になります。indexOfStringとpositionInStringの両方を単一の32ビットintにパックすることで、これを半分に減らすことができます。たとえば、下位12ビットにpositionInStringを、残りの上位ビットにindexOfStringを配置します。2つの値を元に戻すには、少し手を加える必要があります。構造自体には文字列や部分文字列が含まれていないことに注意することが重要です。検索する文字列は1回だけ存在します。
これにより、基本的に完全なインデックスが得られ、実際の文字列の比較を最小限に抑えて、サブ文字列を非常にすばやく見つけることができます（接尾辞配列が表すインデックスの二分探索）。
メモリが重要な場合、元のブルートフォースアルゴリズムの単純な最適化は、一意の文字の辞書を事前に計算し、それぞれを表す序数を割り当てることです。次に、文字列内に含まれる一意の文字ごとに設定されたビットを使用して、各文字列のビット配列を事前計算します。文字列は比較的短いため、結果として得られるBitArrayにはかなりのばらつきがあるはずです（文字列が非常に長い場合はうまく機能しません）。次に、BitArrayまたは検索キーワードを計算し、これらの文字列内のキーワードのみを検索します。keywordBits & targetBits == keywordBits。文字列が小文字に事前変換されていて、英語のアルファベットだけである場合、BitArrayは単一のint内に収まる可能性があります。したがって、これには最小限の追加メモリが必要であり、実装が簡単であり、キーワードが確実に見つからない文字列をすばやく除外できます。文字列検索は高速であるため、これは便利な最適化になる可能性がありますが、ブルートフォース検索を使用して行うことが非常に多くあります。
編集興味のある方のために、これが私が提案した最初のソリューションの基本的な実装です。OPによって記述された長さのランダムに生成された100,000の文字列を使用してテストを実行しました。インデックスの作成と並べ替えには約30秒かかりましたが、一度作成すると、キーワードの検索速度はブルートフォースで49,805ミリ秒、インデックス検索で18ミリ秒と、数千倍速くなりました。リストを作成することがめったにない場合は、最初に接尾辞配列を作成するという、単純ですが比較的遅い方法で十分です。より高速に構築するためのよりスマートな方法がありますが、以下の基本的な実装よりも多くのコーディングが必要になります。
// little test console app
static void Main(string[] args) {
var list = new SearchStringList(true);
list.Add("Now is the time");
list.Add("for all good men");
list.Add("Time now for something");
list.Add("something completely different");
while (true) {
string keyword = Console.ReadLine();
if (keyword.Length == 0) break;
foreach (var pos in list.FindAll(keyword)) {
Console.WriteLine(pos.ToString() + " =>" + list[pos.ListIndex]);
}
}
}
~~~~~~~~~~~~~~~~~~
// file for the class that implements a simple suffix array
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1 {
public class SearchStringList {
private List<string> strings = new List<string>();
private List<StringPosition> positions = new List<StringPosition>();
private bool dirty = false;
private readonly bool ignoreCase = true;
public SearchStringList(bool ignoreCase) {
this.ignoreCase = ignoreCase;
}
public void Add(string s) {
if (s.Length > 255) throw new ArgumentOutOfRangeException("string too big.");
this.strings.Add(s);
this.dirty = true;
for (byte i = 0; i < s.Length; i++) this.positions.Add(new StringPosition(strings.Count-1, i));
}
public string this[int index] { get { return this.strings[index]; } }
public void EnsureSorted() {
if (dirty) {
this.positions.Sort(Compare);
this.dirty = false;
}
}
public IEnumerable<StringPosition> FindAll(string keyword) {
var idx = IndexOf(keyword);
while ((idx >= 0) && (idx < this.positions.Count)
&& (Compare(keyword, this.positions[idx]) == 0)) {
yield return this.positions[idx];
idx++;
}
}
private int IndexOf(string keyword) {
EnsureSorted();
// binary search
// When the keyword appears multiple times, this should
// point to the first match in positions. The following
// positions could be examined for additional matches
int minP = 0;
int maxP = this.positions.Count - 1;
while (maxP > minP) {
int midP = minP + ((maxP - minP) / 2);
if (Compare(keyword, this.positions[midP]) > 0) {
minP = midP + 1;
} else {
maxP = midP;
}
}
if ((maxP == minP) && (Compare(keyword, this.positions[minP]) == 0)) {
return minP;
} else {
return -1;
}
}
private int Compare(StringPosition pos1, StringPosition pos2) {
int len = Math.Max(this.strings[pos1.ListIndex].Length - pos1.StringIndex, this.strings[pos2.ListIndex].Length - pos2.StringIndex);
return String.Compare(strings[pos1.ListIndex], pos1.StringIndex, this.strings[pos2.ListIndex], pos2.StringIndex, len, ignoreCase);
}
private int Compare(string keyword, StringPosition pos2) {
return String.Compare(keyword, 0, this.strings[pos2.ListIndex], pos2.StringIndex, keyword.Length, this.ignoreCase);
}
// Packs index of string, and position within string into a single int. This is
// set up for strings no greater than 255 bytes. If longer strings are desired,
// the code for the constructor, and extracting ListIndex and StringIndex would
// need to be modified accordingly, taking bits from ListIndex and using them
// for StringIndex.
public struct StringPosition {
public static StringPosition NotFound = new StringPosition(-1, 0);
private readonly int position;
public StringPosition(int listIndex, byte stringIndex) {
this.position = (listIndex < 0) ? -1 : this.position = (listIndex << 8) | stringIndex;
}
public int ListIndex { get { return (this.position >= 0) ? (this.position >> 8) : -1; } }
public byte StringIndex { get { return (byte) (this.position & 0xFF); } }
public override string ToString() {
return ListIndex.ToString() + ":" + StringIndex;
}
}
}
}
その場合、必要なのは逆インデックスです。
あなたが多額の支払いをしたいのであれば、データベース固有の全文検索インデックスを使用し、単語のすべてのサブセットにインデックスを付けるようにインデックスを調整することができます。
あるいは、同じことを達成できる非常に成功したオープンソースプロジェクトを使用することもできます。
トークナイザーを使用して文字列に事前インデックスを付け、逆インデックスファイルを作成する必要があります。Javaでも同様のユースケースがあり、大量のデータセットで非常に高速なオートコンプリートが必要です。
Apache Lucene（Java）の移植版であるLucene.NETを見ることができます。
LINQを廃止する場合は、NHibernateSearchを使用できます。（ウィンク）。
もう1つのオプションは、メモリに事前インデックスを実装することです。前処理とスキャンのバイパスは不要です。Knuth-Morris-Prattアルゴリズムを見てください。
はるかに高速なアプローチが1つあります。ただし、機能を使用するのではなく、完全に一致する単語を探すことを意味しContainsます。
基本的に、そのためのメモリがある場合は、単語が見つかった文字列のある種のID（または複数のID）を参照する単語の辞書を作成できます。
したがって、ディクショナリはタイプである可能性があり<string, List<int>>ます。もちろん、ここでの利点は、多くの単語をより小さなコレクションに統合していることです。また、辞書はハッシュテーブル上に構築されているため、ルックアップが非常に高速です。
これが探しているものでない場合は、メモリ内の全文検索ライブラリを検索できます。SQL Serverは、インデックスを使用した全文検索をサポートし、従来のワイルドカード検索を超えてプロセスを高速化します。しかし、純粋なメモリ内ソリューションの方が確実に高速です。ただし、これでもワイルドカード検索の正確な機能が得られない場合があります。