C＃での文字列比較のためのより高速なアルゴリズム＃

Question

私は2つの文を比較する必要があります。 最後の結果は、1つの文がもう一方の文にどれだけ含まれているかです。私の問題は、比較が必要な100.000レコードがあり、別の10を言うことができるということです。 私のアルゴリズムでは非常に遅い1.000.000ループです。

private double BreakStringsAndCheck(string s1, string s2) 
{ 
    if (s1 == null || s2 == null || s1.Length == 0 || s2.Length == 0) 
     return (double)0; 
    string[] firstArray = s1.Split(' '); 
    string[] secondArray = s2.Split(' '); 
    if (firstArray.Length > secondArray.Length) 
    { 
     string[] tempArray = firstArray; 
     firstArray = secondArray; 
     secondArray = tempArray; 
    } 
    double value = 0; 
    for (int i = 0; i < firstArray.Length; i++) 
     for (int j = 0; j < secondArray.Length; j++) 
      value += firstArray[i] == secondArray[j] ? (double)100 : (double)0; 
    return findLongest ? value : value/firstArray.Length; 
} 

をそれは小さな方法だが、それは非常に高速ではありません。

これは、私が使用していたアルゴリズムです。私のテストでは、1秒間に40-60回の比較を行うことができます.1000.000回のループではほぼ5時間です。

これよりもはるかに高速な別の方法やロジックが考えられますか？

更新：

私は詳細に問題を説明しようとします。 私は100.000以上のレコードを持つデータベースを持ち、毎日私はこのデータベースに10-20個のレコードを挿入し、比較します。 このレコードは2〜10ワードのセンテンスで、この新しいレコードとデータベース内のレコードとを比較する高速メソッドを作成する必要があります。結果は、1つのセンテンスに他のセンテンスの単語がどれくらい含まれているかの割合になります。

単語の一致率が70％を超えるレコードが必要です。

私は今はっきりしていることを願っています。

Answer 1

最初に10個のレコードを分割すると、多数の大きな文字列に少数の文字列が含まれています。これはhttp://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_finite_set_of_patterns

を合わせているようだとAho-Corasick algorithmはあなたのためによく働くかもしれない

どのくらいのレコードがありますか？

EDIT：

これは不要switcharoundである - あなたの比較は対称WRT firstArrayとし、secondArrayある

if (firstArray.Length > secondArray.Length) 
    { 
     string[] tempArray = firstArray; 
     firstArray = secondArray; 
     secondArray = tempArray; 
    } 

代わりに、

リターンfindLongestとリターンを置き換えますか？値：（firstArray.Length> secondArray.Length）？値/ secondArray.length：値/ firstArray.Length）;

のみ

UPDATE質問を更新した後:)より読みやすい何かで

ですから、前処理ができ10万（例えば単語をハッシュしますか）？ 1日あたり10-20回の変更しかないので、前処理されたデータを最新の状態に保つことは簡単です。

100,000の比較的静的な性質を使用するものを間違いなく実行する必要があります。 1日に1回だけ前処理を行ったとしても、前回のレコードのすべてとの比較を行い、前回の前処理の実行以降に追加された他のレコードに対しては、現在の低速なアプローチを使用できます。あなたの言うことから、それらのうち最大10-20があります

私はハッシングアイデア、またはコーパスからAho-Comisack trieを作成すると、はるかに高速な検索ができると思います。

Answer 2

代替方法としてIntersectの方法を検討しましたか。私は、その性能については考えているが、それは、私はC＃のプログラマーないんだけど、ここではいくつかの一般的なヒントです

Answer 3

を働くことのように見えます：

は、ループの外に浮動小数点演算を移動
1. 。あなたは、一致する文字を数え、後で分割しなければなりません。
2. データが静的であるため、それぞれの「長い」ループを別々の実行スレッドで実行できるはずです。私はあなたの "10"の文章ごとに別々のスレッドを生成し、それらを並行して実行します。
3. 可能であれば、splitへの呼び出しを削除したい場合があります。基本的に、余分なメモリ割り当てを削除します。

最終的な考えは、テキスト処理アルゴリズムのアルゴリズムブックまたはグーグルをつかむことです。この問題は何度も何度も解決されたようなものです。おそらくAOCP v3にはこの問題を解決するものがあります。コードをプロファイリングすることもできます（利用可能なプロファイラーの種類は不明ですが）、おそらく実質的な改善は得られません。

Answer 4

交差例

private double BreakStringsAndCheck(string s1, string s2) 
{ 
    var split1 = s1.Split(' '); 
    return (double)split1.Intersect(s2.Split(' ')).Count()/split1.Count() * 100.0; 
} 

私は40.0の代わりに比0.4を返すことを好むだろう：

var percent = BreakStringsAndCheck("Jan Banan går till GAIS.", "I Torsk på Tallin så var en annan Jan Banan med."); 

私はちょうどあなたのアルゴリズムは常に長いの短い文字列を比較することに気づきました。したがって、入力パラメータがこのように切り替わってもアルゴリズムは40.0を返します。

var percent = BreakStringsAndCheck("I Torsk på Tallin så var en annan Jan Banan med.", "Jan Banan går till GAIS."); 

しかし、私の交差する例は18.18を返します。私はこれがより正確だと思っていますが、あなたが本当にあなたのやり方を望むのであれば、方法の冒頭に

if (s1.Length > s2.Length) 
{ 
    var tmp = s2; 
    s2 = s1; 
    s1 = tmp; 
} 

を追加してください。

var presplits = new List<string[]>() { s1.Split(' '), s2.Split(' '), s3.Split(' ') }; 

をPresplitting

...その後

private static IEnumerable<double> StringsInString(IEnumerable<string[]> strings, string s2) 
{ 
    return strings.Select(h => (double)h.Intersect(s2.Split(' ')).Count()/h.Count()); 
} 

Parallel.For内のすべてのあなたの100.000文字列をループ。

PS。私は、より正確な比率を得るために、文字列から.、,などを削除して削除しなければならないと思います。 DS。

Answer 5

個人的に私は2つの配列の作成を避けるでしょう。メモリ割り当てによってパフォーマンスが低下します。

string.IndexOf関数を見て、次のスペースが両方の文字列のどこにあるかを調べて、前のスペースの場所から減算して単語の長さを計算します。 2つの長さが等しい場合は、string.Compareを使用して、2つのサブストリングが等しいかどうかを確認します。これはメモリの割り当てを避け、文字列を一度しか反復しないので、より速くなければなりません。

また、他の人も触れたように、Parallel拡張機能を使って見てください。

Answer 6

これを試してください。

比較を実行する前に、100,000行を前処理してください。 100,000行のすべての単語がDictionary<>オブジェクトのキーになります。その値はidのリスト（その単語が出現する各行のID）になります。 「一致の検索」、2番目の辞書を維持すると

Dictionary<string, List<int>> allWords 

は、このいずれかを行IDをキーとし、それは価値があなたがインクリメントよ整数ですされています。例えば

Dictionary<int, int> matches 

検索文字列を単語に分割し、各単語の各行IDに対して、その行IDの値を増やします。

var searchWords = search.Split(" "); 
foreach(var word in searchWord) 
{ 
    foreach(var id in allWords[word]) 
     matches[id] += 1; 
} 
var bestRowId = (from m in matches orderby m.Value select m.Key).Last(); 

最大値の行IDが最適です。

辞書を作成するのに時間がかかります（ただし、1回の比較ではそれほど多くはないと思いますが）。その後はすばやく表示されます。

NB：ここでスピードの鍵は、辞書が格納しているキーのHashCodeを使用し、文字列の.netハッシュ関数が優れていることです。

更新

この順に前処理は時間がかかりすぎる場合は、軽量化の前処理を行うことができます。
100,000行のそれぞれを読み上げると、単語に分割され、単語の配列がソートされます。次に、比較する際に、文字列を分割して比較しソートすることもできます。 関数は、各文字列を複数回に分割しないため、時間を節約し、ネストされたループはmin(words1.length, words2.length)のループに置き換えることができます。

Answer 7

これは別のアプローチです。私は、10文を100,000文と比較すると、単語が一致せず％= 0になる数が多いと推測しています。常に100,000の比較を実行するのではなく、100,000少なくとも1つの単語が一致し、それらを比較するだけです。

100,000文のすべての単語の辞書を作成してください。

各エントリは、この単語を含む文のリストLです。

tobetested=empty 
For each s in the 10 sentences 
    for each word in s 
    if dictionary.contains(word) then 
     add members of L that aren't already there to tobetested 
    next 
    for each sentence to tobetested ' hopefully much less than 100'000 
    compare using your algorithm 
    next 
next 

Answer 8

データがデータベースにあるため、データベースでの作業はできませんか？

センテンス行に対する単語にセンテンスを細断します。

細断された言葉にあなたの言葉に参加してください。これにより、どの文に一致する単語があるかを確認することができます。

次に、文idでグループ化して合計すると、指定された文と一致する単語の合計が格納された文と一致する必要があります。

私はあなたのデータを事前に細断することにします。主要な文章表に対する索引としてそれらを使用してください。