Boyer-Moore 及相关精确字符串匹配算法

• 下载演示项目 - 3.94 KB
• 下载源代码 - 2.04 KB

引言

本文介绍了 Boyer-Moore 字符串匹配算法和一些相关算法的直接实现。

背景

当在另一个字符串中搜索一个字符串时，.NET 程序员通常会使用 String.IndexOf。对于绝大多数应用程序来说，这已经足够好了。然而，当搜索非常长的字符串时，还有其他算法比 .NET 提供的基本算法提供更多的性能。本文提供了其中几种算法的简单实现。

值得注意的是，String.IndexOf 执行的比较比这些算法提供的比较复杂得多，因为 String.IndexOf 执行的是区分文化的比较 - 当需要不区分大小写的匹配时，这是一个非常复杂的问题！ 如果你需要区分文化的匹配，请坚持使用 String.IndexOf。

本文未涵盖的内容

本文没有尝试教你如何编写高性能的字符串匹配算法，也没有试图解释所呈现的算法。 如果您正在寻找这种信息，请查阅算法书籍，例如 Knuth 或 Cormen, et al. 字符串匹配算法的一个很好的在线参考是 精确字符串匹配算法手册。

使用代码

BoyerMooreSearch 类提供了原始 Boyer-Moore 算法以及许多相关算法的实现。 还提供了一个使用 String.IndexOf 的实现，用于比较。

要查找的文本被传递给 BoyerMooreSearch 构造函数。 每个搜索算法都使用一个通用的 IEnumerable<int> 模型呈现。

namespace StringMatch
{
  public class BoyerMoore
  {
    /// <summary>
    /// Constructor
    /// </summary>
    /// <param name="pattern">Pattern for search</param>
    public BoyerMoore(string pattern) { ... }

    /// <summary>
    /// Return all matched of the pattern
    /// in the specified text using algorithm name
    /// </summary>
    /// <param name="text">text to be searched</param>
    /// <param name="startingIndex">Index at 
    ///       which search begins</param>
    /// <returns>IEnumerable which returns
    /// the indexes of pattern matches</returns>
    public IEnumerable<int> AlgorithmNameMatch(string text, 
                                 int startingIndex) { ... }

    /// <summary>
    /// Return all matched of the pattern in the
    /// specified text using algorithm name
    /// </summary>
    /// <param name="text">text to be searched</param>
    /// <returns>IEnumerable which returns the indexes of pattern matches</returns>
    public IEnumerable<int> AlgorithmNameMatch(string text) { ... }
  }
}

每个算法都返回一个 IEnumerable<int>，它产生模式（传递给构造函数）在文本（传递给算法）中找到的所有索引。 这种设计允许 Boyer-Moore 相关算法使用的预计算在任意数量的特定模式搜索之间共享。

BoyerMoore bm = new BoyerMoore("abcd");
foreach (int index in bm.BoyerMooreMatch("abcdsflkjwertabc" + 
         "dfglkjdfgcdjweertopabjsdvacbwer" + 
         "kjhsdfkljhacbsdflkjsdflkjabcd"))
  Console.WriteLine("Matched at index {0}", index);

这个例子将在 0、13 和 72 处列出匹配项。

算法

BoyerMoore 类实现了以下算法

• BCLMatch - 使用 String.IndexOf 进行搜索。
• HorspoolMatch - 使用 Horspool 算法进行搜索。 这在功能上与 "快速搜索" 算法相同，并在一些算法书中被呈现为 Boyer-Moore 算法。 由于其简单性，即使其他算法具有更好的理论性能，这通常也是 Boyer-Moore 类算法中性能最高的算法。
• BoyerMooreMatch - 使用 Boyer-Moore 算法进行搜索。
• TurboBoyerMooreMatch - 使用 Turbo Boyer-Moore 算法进行搜索。
• ApostolicoGiancarloMatch - 使用 Apostolico-Giancarlo 算法进行搜索。 尽管该算法具有最佳的理论性能（当仅考虑字符比较时，正如评估匹配算法时传统的那样），但由于代码的复杂性，它在实践中通常是最慢的。

演示程序

提供的演示程序是一个简单的控制台应用程序，它搜索指定文件中所有出现的字符串，并报告每个算法所花费的时间。 在我的机器（3Ghz P4）上运行演示应用程序，搜索一个大型文本文件以查找一个频繁出现的字符串，得到了以下时间

Finding all occurrences of pattern 
         in path (7324800 characters in length)
String.indexOf found 87473 matches in 0.0579839 seconds
Horspool found 21832 matches in 0.0180492 seconds
Boyer-Moore found 87473 matches in 0.0196312 seconds
Turbo Boyer-Moore found 87473 matches in 0.0282827 seconds
Apostolico-GiancarloMatch found 87473 matches in 0.0563225 seconds

根据我的经验，此处显示的比率是典型的，但您的结果可能会有所不同，具体取决于您要查找的内容以及在搜索文本中存在多少部分匹配。

历史

• 2006 年 1 月 17 日 - 初始版本。