Boyer-Moore Práctico en C#?

.net algorithm

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 de Black Belt Coder .

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

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

A continuación se muestra el código clave.

// 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;
    }
}

EDITAR: He publicado todos mis códigos de prueba y conclusiones sobre el tema en http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-boyer-moore .

Answer 1

Basándome en mis propias pruebas y en los comentarios realizados aquí, he concluido que la razón por la que String.IndexOf() funciona tan bien con StringComparision.Ordinal es porque el método invoca un código no administrado que probablemente emplea lenguaje ensamblador optimizado a mano.

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

Si alguien está interesado, he escrito todo lo que he descubierto sobre esto y publiqué 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 la configuración de esa bandera permite que String.IndexOf use el propio Boyer-Moore. Y su implementación es mejor que la tuya.

Sin esa bandera, debe tener cuidado al usar Boyer-Moore (y probablemente no) debido a posibles problemas en torno a Unicode. En particular, la posibilidad de Unicode hace que las tablas de transición que Boyer-Moore usa para explotar.