問題タブ [boyer-moore]

高速検索、高速検索と置換、および文字列内の部分文字列の高速カウントの 3 つの高速オン大文字列関数が必要です。

私は C++ と Python で Boyer-Moore 文字列検索に出くわしましたが、高速検索と置換を実装するために使用されている唯一の Delphi Boyer-Moore アルゴリズムは、以前は DroopyEyes ソフトウェアの Peter Morris による FastStrings の一部であり、彼の Web サイトでした。および電子メールは機能しなくなりました。

Delphi 2009/2010 では、1 バイトが 1 つの AnsiChar に等しい AnsiString でうまく機能するように、 FastStringsを移植済みですが、Delphi 2010 で文字列 (UnicodeString) でも機能させるのは簡単ではないようです。

この Boyer-Moore アルゴリズムを使用すると、大文字と小文字を区別しない検索、および大文字と小文字を区別しない検索と置換を、一時的な文字列 (StrUpper などを使用) なしで、Boyer- よりも遅い Pos() を呼び出さずに簡単に実行できるはずです。同じテキストを繰り返し検索する必要がある場合の Moore 検索。

(編集: この質問への回答として書かれた部分的な解決策があります。ほぼ 100% 完成しており、高速な文字列置換機能も備えています。バグがあるに違いないと思います。特に、Unicode のふりをしているので、 Unicode の約束が果たされていないために不具合が発生している可能性があります。)

(Edit2: 興味深い予想外の結果。スタック上の Unicode コードポイント テーブルの大きなスタック サイズ - 以下のコードの SkipTable は、ここで Unicode 文字列ボイヤーで実行できる win-win-optimization の量に深刻なダンパーを置きます。 -moore 文字列検索.すぐに気付くべきだったことを指摘してくれた Florent Ouchet に感謝します.)

KMP (Knuth–Morris–Pratt) アルゴリズムは単純化された Boyer-Moore アルゴリズムよりも少ない比較を実行しますか?

Boyer-Moore は、知られているインデックスなしのテキスト検索アルゴリズムの中でおそらく最速です。そのため、 Black Belt Coderの Web サイト用に C# で実装しています。

私はそれを機能させましたString.IndexOf(). しかし、StringComparison.Ordinal引数をに追加するとIndexOf、Boyer-Moore の実装よりも優れたパフォーマンスを発揮し始めました。時には、かなりの量で。

誰かが理由を理解するのを手伝ってくれるのだろうか. 速度が上がる理由は理解StringComparision.Ordinalできますが、Boyer-Moore よりも高速になるのはなぜでしょうか? .NET プラットフォーム自体のオーバーヘッドが原因でしょうか。おそらく、配列インデックスが範囲内にあることを確認するために検証する必要があるためか、それともまったく別の理由によるものでしょうか。一部のアルゴリズムは C#.NET では実用的ではありませんか?

以下はキーコードです。

編集:この問題に関するすべてのテスト コードと結論をhttp://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-mooreに投稿しました。

CでBoyer-Moore文字列検索アルゴリズムの実例はありますか? いくつかのサイトを見てきましたが、ウィキペディアを含め、かなりバグがあるようです。

ありがとう。

ボイヤームーアパターンマッチングアルゴリズム（具体的には日曜日のアルゴリズム）のバリエーションを実装しようとしています。自分自身に問いかけていました。アルファベットのサイズはどれくらいですか。

それはエンコーディング（=可能な文字数）に依存しますか、それとも私のアルファベットが256個の記号（= 1バイトで表すことができる記号の数）で構成されていると仮定できますか？

他の多くの状況では、文字をバイトとして扱うことが問題になります。これは、エンコーディングによっては文字が複数のバイトで構成される場合があるためですが、私の場合、両方の文字列が同じエンコーディングである場合、等しい文字は等しいバイトシーケンスで表されるため、それは問題ではありません。

したがって、エンコーディングを考慮に入れて、実際の文字で構成されるアルファベット（Unicodeの場合は> 90000）を想定する必要がありますか、それともテキストとパターンをバイトのストリームとして処理できますか？

Boyer-Moore 文字列検索アルゴリズムの"Good Suffix Shift"-Tableを理解するのを手伝ってください。

いつ何が起こったのi==3ですか？

パターンに部分文字列「_MAN」はありません。したがって、シフト値は 8 にする必要があります ( のときと同じi==1です)。

なぜ6ですか？

ファイル内の文字列を検索するより速い方法はありますか？

まず、私はアルゴリズムについてほとんど知らないので、我慢してください。

私が理解しているように、ボイヤームーアアルゴリズムは長いキーで最速です。したがって、非常に短いキー（たとえば、10文字）と検索するテキスト（10,000文字以上）がある場合はどうなりますか。ボイヤームーアは、このシナリオに最適な検索アルゴリズムでしょうか？

そうでない場合はどうなりますか？

プログラミングのWebサイトで、1つの不一致がある文字列を比較するためのプログラムを実行しました。それは私に間違った答えを与えます。私はこれに広範囲に取り組んできましたが、コードが失敗するテストケースを見つけることができませんでした。誰かが私のコードが失敗したテストケースを教えてもらえますか？最速の検索アルゴリズムであるBoyerMooreHorspoolk-mismatchesアルゴリズムを使用して比較を行いました

コードはそれ自体です

ボイヤームーア文字c（++）Wikipediaの実装を適応させて、文字列内のパターンのすべての一致を取得しようとしています。そのまま、ウィキペディアの実装は最初の一致を返します。メインコードは次のようになります。

配列/ベクトルにインデックスを追加し、外側のループを続行させた後、ブロックを変更しようとしましたif (j < 0)が、機能していないようです。変更されたコードをテストしても、一致するものは1つだけです。おそらく、この実装はすべての一致を返すように設計されておらず、そうするためにいくつかの迅速な変更が必要ですか？アルゴリズム自体がよくわからないので、どうやってこれを機能させるのかわかりません。誰かが私を正しい方向に向けることができれば、私は感謝するでしょう。

注：関数make_delta1およびmake_delta2は、ソースで以前に定義されており（Wikipediaページを確認してください）、max（）関数呼び出しは、実際にはソースでも以前に定義されたマクロです。