どの文字列検索アルゴリズムが実際に最速ですか？

実行する検索の種類によって異なります。各アルゴリズムは、特定のタイプの検索で特に優れたパフォーマンスを発揮しますが、検索のコンテキストについては説明していません。

検索タイプに関する一般的な考え方を次に示します。

• Boyer-Moore：パターンを事前に分析し、右から左に比較することで機能します。不一致が発生した場合は、初期分析を使用して、パターンをw.r.tでどれだけシフトできるかを判断します。検索対象のテキスト。これは、長い検索パターンで特に効果的です。特に、テキストのすべての文字を読み取る必要がないため、劣線形になる可能性があります。

• Knuth-Morris-Pratt：パターンも事前分析します、ただし、パターンの最初の部分ですでに一致したものはすべて再利用して、再一致する必要がないようにします。これは、アルファベットが小さい場合（DNA塩基など）、検索パターンに再利用可能なサブパターンが含まれる可能性が高くなるため、非常にうまく機能します。

• Aho-コラシック：多くの前処理が必要ですが、多くのパターンで必要です。同じ検索パターンを何度も検索することがわかっている場合は、検索ごとに1回ではなく、1回だけパターンを分析する必要があるため、これは他のパターンよりもはるかに優れています。

したがって、CSで通常行われているように、全体的に最良のに対する明確な答えはありません。むしろ、目前の仕事に適したツールを選択することです。

最悪の場合の理由に関する別の注意事項：最悪の場合を作成するために必要な検索の種類を検討し、次のことを十分に検討してください。これらはあなたの場合に本当に関係があります。たとえば、ボイヤームーアアルゴリズムのO(mn)の最悪の場合の複雑さは、検索パターンと、それぞれが1文字のみを使用するテキスト（ in aaaaaaaaaaaaaaaaaaaaa）-そのような検索を本当に高速にする必要がありますか？

コメント

• 英語のアルファベット全体を使用できるので、質問を更新しました。最初から始めなかったことをお詫びします。
• はい、次のような検索でも高速である必要があります。それ
• Z 'のアルゴリズムとマナチャーについても詳しく説明していただけますか？

この質問に答えるのは少し遅れていますが、Z-Algorithmは他のどの質問よりもはるかに速いと思います。その最悪の場合の複雑さはO（m + n）であり、パターン/テキストの前処理を必要としません。また、他のアルゴリズムと比較して、コーディングも非常に簡単です。

次のように機能します。

たとえば、文字列S ="abaaba"があります。 i=0 to len(S)-1のz(i)値を検索します。説明に入る前に、最初にいくつかの定義を示しましょう。

z(i) =いいえ。 Sのプレフィックスがs(i)のプレフィックスと一致する文字の数。

s(i) = ithのサフィックスS。

以下はs(i) s = "abaaba"の値。

s(0) = "abaaba" = S s(1) = "baaba" s(2) = "aaba" s(3) = "aba" s(4) = "ba" s(5) = "a" 

z値はそれぞれ

z(0) = 6 = length(S) z(1) = 0 z(2) = 1 z(3) = 3 z(4) = 0 z(5) = 1 

アルゴリズムの詳細については、次のリンクを参照してください。

http://codeforces.com/blog/entry/3107

https://www.youtube.com/watch?v=MFK0WYeVEag

これで、前処理のオーバーヘッドなしですべてのz値を見つけるのにO（N）が必要になります。このロジックを使用して、特定の文字列のパターンを一致させるにはどうすればよいでしょうか？

例を見てみましょう。Pattern（P）：aba、Text（T）：aacbabcabaad。

これをP $ Tの形式で入力します。（$-パターンにもテキストにも表示されない文字。しばらくすると、$の重要性がわかります。）

P$T = aba$aacbabcabaad

len(P) = 3であることがわかっています。

P$Tのすべてのz値は

z(0) = 16 = len(P$T) z(1) = 0 z(2) = 1 z(3) = 0 z(4) = 1 z(5) = 1 z(6) = 0 z(7) = 0 z(8) = 2 z(9) = 0 z(10) = 0 z(11) = 3 z(12) = 0 z(13) = 1 Z(14) = 1 Z(15) = 0 

これでz(i) = len(P)。 Ans = 11.したがって、パターンはAns-len(P)-1 = 7に存在します。 -1は$文字用です。

なぜ$またはそのような特殊文字は重要です。 P = "aaa"とT = "aaaaaaa"を検討してください。特殊文字がない場合、すべてのz(i)には増分値があります。次の式を使用して、テキスト内のパターンの位置を見つけることができます。

条件：z(i)> = len(P)および位置：Ans-len(P)。しかし、この場合の条件は少しトリッキーで混乱します。個人的には特殊文字のテクニックを使うのが好きです。

コメント

• ここで自分で説明してもらえますか？外部サイトへのリンクを使用して詳しく説明することもできますが、回答の核心は、別のサイトへのリンクをたどる必要はなく、回答自体にある必要があります。
• zアルゴリズムは基本的にと同じです。 kmp。はるかに高速だとは思えません。
• @ThomasAhleに同意します。 z の計算は前処理です。ただし、'は良い説明です。この答えのために、KMP前処理からZ前処理に変換するO(n)の方法を提案しました。 ここ

使用連想メモリ、仮想アドレス指定（文字から文字へのポイント）の形式でソフトウェアに実装されます。

これは、平均的な文字列照合アルゴリズムにはやや不必要です。

CAMは、最大約128文字のパターン（ASCIIの場合、Unicodeのみ64の場合）まで、膨大な数のパターンを同時に照合できます。そして、それは、照合したい文字列の文字の長さごとに1回の呼び出しであり、最大パターン長の長さごとにメモリからランダムに1回読み取られます。したがって、最大90,000,000パターンを同時に使用する100,000文字の文字列を分析する場合（これほど大きなパターンの数を格納するには約128 GiBが必要です）、RAMからのランダム読み取りは12,800,000であるため、1ミリ秒で発生します。

仮想アドレス指定の仕組みは次のとおりです。

最初の文字を表す256個の開始アドレスから始めると、これらの文字は次の256個の文字を指します。パターンの場合は存在しないので、保存しません。

つまり、文字を文字にリンクし続けると、仮想アドレスを指す128スライスの仮想アドレスを持つようなものになります。

—で動作しますが、同時に900,000,000のパターンを一致させるには、—に追加する最後のトリックが1つあります。あなたがこれらの文字バッファの多くの再利用から始めたという事実の、しかし後でそれは散らばります。256文字すべてを割り当てるのではなく、内容をリストすると、速度はほとんど低下せず、「基本的に、すべての文字ポインタバッファで使用される文字は1文字だけになるため、容量が100倍に増加します（これを吹き替えました」エスケープ」）。

最近傍文字列の一致を取得する場合は、これらの多くを並行して実行し、階層に収集するため、エラーを偏りなく分散させます。最近傍が1つしかない場合は、「ツリーの先頭に偏っています。

コメント

• @MagnusRobertCarlWoot roucer81としてのgavatarは、ハッシュコードの衝突の天文学的な偶然であるか、同じ電子メールアドレスを持っています。両方のアカウントの背後にいる同じ個人の場合は、"お問い合わせ"フォームを使用してそれらをマージし、適切なクレジットを取得する必要があります。この回答への賛成票を通じて得られた評判。