Boyer-Moore C＃で実践していますか？

Question

Boyer-Mooreは、おそらく最も知られているインデックスなしのテキスト検索アルゴリズムです。だから、私はBlack Belt Coderウェブサイトの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; 
    } 
} 

EDIT：私はhttp://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-mooreで問題にすべての私のテストコードと結論を掲載しました。

Answer 1

私自身のテストとここでのコメントに基づいて、理由がStringComparision.Ordinalでうまくいくと結論づけました。なぜなら、このメソッドは手作業で最適化されたアセンブリ言語を採用するアンマネージコードを呼び出すからです。

私は多くの異なるテストを実行しました。String.IndexOf()は、マネージC＃コードを使用して実装できるものより速いようです。

興味があれば、これについて私が発見したすべてを書き、Boyer-MooreアルゴリズムのいくつかのバリエーションをC＃でhttp://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-mooreに投稿しました。

Answer 2

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

このフラグがないと、Unicodeに関する潜在的な問題のために、Boyer-Moore（注意してください）を使用することに注意する必要があります。特にUnicodeの可能性は、Boyer-Mooreが使用する遷移テーブルを爆破させる原因となります。