32

Boyer-Moore 可能是已知最快的非索引文本搜索算法。所以我在 C# 中为我的Black Belt Coder网站实现它。

我让它工作了，与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# 代码实现的任何测试都快。

如果有人感兴趣，我已经写了我发现的所有内容，并在http://www.blackbeltcoder.com/Articles/algorithms/fast-text-search-with-上发布了 C# 中 Boyer-Moore 算法的几种变体博耶-摩尔。

于 2011-02-06T21:43:52.193 回答
4

我敢打赌，设置该标志允许 String.IndexOf 使用 Boyer-Moore 本身。它的实现比你的要好。

如果没有该标志，则必须小心使用 Boyer-Moore（可能不会），因为 Unicode 存在潜在问题。特别是 Unicode 的可能性会导致 Boyer-Moore 使用的转换表崩溃。

于 2011-02-05T02:27:06.087 回答
0

我对你的代码做了一些小的改动，并对 Boyer-Moore 算法做了不同的实现，得到了更好的结果。我从这里得到了这个实现的想法

但老实说，与IndexOf.

在此处输入图像描述

class SearchResults
{
    public int Matches { get; set; }
    public long Ticks { get; set; }
}

abstract class SearchBase
{
    public const int InvalidIndex = -1;
    protected string _pattern;
    protected string _text;
    public SearchBase(string text, string pattern) { _text = text; _pattern = pattern; }
    public abstract int Search(int startIndex);
}

internal class BoyerMoore3 : SearchBase
{
    readonly byte[] textBytes;
    readonly byte[] patternBytes;
    readonly int valueLength;
    readonly int patternLength;
    private readonly int[] badCharacters = new int[256];
    private readonly int lastPatternByte;

    public BoyerMoore3(string text, string pattern) : base(text, pattern)
    {
        textBytes = Encoding.UTF8.GetBytes(text);
        patternBytes = Encoding.UTF8.GetBytes(pattern);
        valueLength = textBytes.Length;
        patternLength = patternBytes.Length;

        for (int i = 0; i < 256; ++i)
            badCharacters[i] = patternLength;

        lastPatternByte = patternLength - 1;

        for (int i = 0; i < lastPatternByte; ++i)
            badCharacters[patternBytes[i]] = lastPatternByte - i;
    }

    public override int Search(int startIndex)
    {
        int index = startIndex;

        while (index <= (valueLength - patternLength))
        {
            for (int i = lastPatternByte; textBytes[index + i] == patternBytes[i]; --i)
            {
                if (i == 0)
                    return index;
            }

            index += badCharacters[textBytes[index + lastPatternByte]];
        }

        // Text not found
        return InvalidIndex;
    }
}

更改代码Form1：

    private void RunSearch(string pattern, SearchBase search, SearchResults results)
    {
        var timer = new Stopwatch();

        // Start timer
        timer.Start();

        // Find all matches
        int pos = search.Search(0);
        while (pos != -1)
        {
            results.Matches++;
            pos = search.Search(pos + pattern.Length);
        }

        // Stop timer
        timer.Stop();

        // Add to total Ticks
        results.Ticks += timer.ElapsedTicks;
    }
于 2020-12-20T12:39:11.343 回答