32

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

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

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

以下はキーコードです。

// Base for search classes
abstract class SearchBase
{
    public const int InvalidIndex = -1;
    protected string _pattern;
    public SearchBase(string pattern) { _pattern = pattern; }
    public abstract int Search(string text, int startIndex);
    public int Search(string text) { return Search(text, 0); }
}

/// <summary>
/// A simplified Boyer-Moore implementation.
/// 
/// Note: Uses a single skip array, which uses more memory than needed and
/// may not be large enough. Will be replaced with multi-stage table.
/// </summary>
class BoyerMoore2 : SearchBase
{
    private byte[] _skipArray;

    public BoyerMoore2(string pattern)
        : base(pattern)
    {
        // TODO: To be replaced with multi-stage table
        _skipArray = new byte[0x10000];

        for (int i = 0; i < _skipArray.Length; i++)
            _skipArray[i] = (byte)_pattern.Length;
        for (int i = 0; i < _pattern.Length - 1; i++)
            _skipArray[_pattern[i]] = (byte)(_pattern.Length - i - 1);
    }

    public override int Search(string text, int startIndex)
    {
        int i = startIndex;

        // Loop while there's still room for search term
        while (i <= (text.Length - _pattern.Length))
        {
            // Look if we have a match at this position
            int j = _pattern.Length - 1;
            while (j >= 0 && _pattern[j] == text[i + j])
                j--;

            if (j < 0)
            {
                // Match found
                return i;
            }

            // Advance to next comparision
            i += Math.Max(_skipArray[text[i + j]] - _pattern.Length + 1 + j, 1);
        }
        // No match found
        return InvalidIndex;
    }
}

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

4

3 に答える 3

21

私自身のテストとここで行われたコメントに基づいて、このメソッドが手動で最適化されたアセンブリ言語を使用している可能性が高いアンマネージ コードを呼び出すため、String.IndexOf()パフォーマンスが非常に優れていると結論付けました。StringComparision.Ordinal

さまざまなテストを多数実行しましたが、String.IndexOf()マネージ C# コードを使用して実装できるものよりも高速に思えます。

誰かが興味を持っている場合は、私がこれについて発見したことをすべて書き、C# の Boyer-Moore アルゴリズムのいくつかのバリエーションをhttp://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-に投稿しました。ボイヤームーア。

于 2011-02-06T21:43:52.193 に答える
4

私の賭けは、そのフラグを設定すると、String.IndexOfがBoyer-Moore自体を使用できるようになるということです。そして、その実装はあなたのものよりも優れています。

そのフラグがないと、Unicodeに関する潜在的な問題があるため、Boyer-Mooreを使用する場合は注意が必要です（おそらくそうではありません）。特にUnicodeの可能性は、Boyer-Mooreが爆発させるために使用する遷移表を引き起こします。

于 2011-02-05T02:27:06.087 に答える