C/C++で大文字でキーワード検索を行う最速の方法

Question

私は100個のキーワード（空白を含めることができます）があり、大きなテキストに何回出現するかを調べる必要があります。これを速やかに達成するにはどうすればよいでしょうか？

次のように私の現在の考えは次のとおりです。

は、ノード以下のテキストといつでもcharが（すなわちノード - >次== NULLを発生しませんを通じて接尾辞木に
• 徒歩キーワードを回し
• ）接尾辞木に、次の単語をスキップして、接尾辞木の構造体は、このようなものになります

再度検索：

struct node { 
    int count; //number of occurences (only used at leaf node) 
    /* for each lower-case char, have a pointer to either NULL or next node */ 
    struct node *children[26]; 
}; 

を

私はこれを行うより速い方法があると確信していますが、それは何ですか？スペース効率は、このケースではそれほど大きな問題ではありません（したがって、検索の高速化のために子供の配列）が、時間効率は本当にです。助言がありますか？

Answer 1

接尾辞ツリーアプローチの問題は、検索するテキストの各文字の接尾辞検索を開始する必要があることです。私は最良の方法はテキスト内の各キーワードの検索を手配することですが、Boyer-Mooreのような事前計算された値を持ついくつかの高速検索方法を使用することです。

EDIT：

OK、あなたはトライが速いかもしれ必ずあります。 Boyer-Mooreは平均的なケースでは非常に高速です。たとえば、文字列の平均長さがmであるとします。 BMは「通常の」文字列の場合、O（n/m）と同じくらい速くなります。それは100 * O（n/m）になります。トライは平均でO（n * m）になりますが（実際にはもっと速くなることは事実です）、100 >> mならトライが勝つでしょう。

最適化に関するランダムなアイデアがあります。後ろ向きの検索を行う必要のある圧縮アルゴリズムでは、文字列の2文字で索引付けされた部分的なハッシュテーブルを見たことがあります。その上c2とc3、次いで

if (hash_table[c1 * 256 + c2] == true) check_strings_begining with [c1,c2] 

、および：チェック対象の文字列が文字c1、c2、およびc3のシーケンスである場合つまり、あなたは、天気を確認することができます。このハッシュは各100/65536回（0。0）にしか当てはまらないので、この単純なチェックを行うことで回避することができるのは驚くべきことです。1％）。

Answer 2

これは私がやることです。

1. （あなたはそれを推測）キーとして値やキーワードなどのキーワードの出現箇所の数と、キーと値のペアのハッシュテーブル内のすべてのキーワードを入れてください。
2. テキストblobの各単語をハッシュテーブルと照合します。単語がハッシュテーブルにある場合は、その単語に関連付けられたオカレンスカウントをインクリメントします。

これは、ハッシュテーブル参照が償却O（1）時間であるため、良い方法です。全体のアルゴリズムは線形の複雑さを持っています:)。

EDIT：キーワードにスペースが含まれる場合は、DFAのソートを行う必要があります。あなたのキー "フレーズ"の1つが始まる単語を見つけるまで、ファイルをスキャンしてください。第2の（または多くの）次の単語が「キーフレーズ」の一部である場合は、出現回数を増やします。

Answer 3

あなたは引用するhttp://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

に向けて自分の道を模索しているように見える：

アルゴリズムの複雑さは、パターンの長さを加えた検索テキストに加えて、出力一致の数の長さが直線的です。すべての一致が見つかるため、すべての部分文字列（たとえば、辞書= a、aa、aaa、aaaaおよび入力文字列はaaaa）が一致すると、一致の2次数が存在する可能性があることに注意してください。

Answer 4

それは、産業アプリケーションである場合は、

それは、テストされBoost Regexを使用し、迅速かつチャンスは、それはあなたの痛みを大幅に節約することがあります。