Boyer-Moore ¿Práctico en C#?

Question

Boyer-Moore es probablemente el algoritmo de búsqueda de texto no indexado más rápido conocido. Así que lo estoy implementando en C# para mi sitio web Black Belt Coder.

Lo tenía funcionando y mostraba aproximadamente las mejoras de rendimiento esperadas en comparación con String.IndexOf(). Sin embargo, cuando agregué el argumento StringComparison.Ordinal al IndexOf, comenzó a superar mi implementación de Boyer-Moore. Algunas veces, en una cantidad considerable.

Me pregunto si alguien puede ayudarme a descubrir por qué. Entiendo por qué StringComparision.Ordinal puede acelerar las cosas, pero ¿cómo podría ser más rápido que Boyer-Moore? ¿Se debe a la sobrecarga de la plataforma .NET, tal vez porque los índices de matriz deben validarse para garantizar que estén dentro del alcance, o algo completamente distinto? ¿Algunos algoritmos simplemente no son prácticos en C# .NET?

A continuación se muestra el código de la llave.

// 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: He publicado todo mi código de prueba y conclusiones sobre el asunto en http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore.

Answer 1

En base a mis propias pruebas y los comentarios realizados aquí, he llegado a la conclusión de que String.IndexOf() funciona tan bien con StringComparision.Ordinal porque el método llama a código no administrado que probablemente emplea lenguaje ensamblador optimizado a mano.

He realizado una serie de pruebas diferentes y String.IndexOf() parece ser más rápido que cualquier cosa que pueda implementar utilizando el código de C# administrado.

Si alguien está interesado, he escrito todo lo que he descubierto sobre esto y he publicado varias variaciones del algoritmo de Boyer-Moore en C# en http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore.

Answer 2

Mi apuesta es que establecer esa bandera permite a String.IndexOf usar Boyer-Moore. Y su implementación es mejor que la tuya.

Sin esa bandera, tiene que tener cuidado al usar Boyer-Moore (y probablemente no) debido a posibles problemas con Unicode. En particular, la posibilidad de que Unicode cause que las tablas de transición que usa Boyer-Moore exploten.