C# 中的 Aho-Corasick 字符串匹配
4.88/5 (37投票s)
Aho-Corasick 关键字匹配算法的高效 C# 实现，支持多关键字。
引言
在本文中，我将介绍一种高效的 Aho-Corasick 模式匹配算法的实现。简单来说，该算法可用于在一个文本中搜索指定的关键字。当您有一组关键字并希望找到关键字在文本中的所有出现位置，或者检查关键字是否存在于文本中时，下面的代码将非常有用。您应该特别使用此算法，因为如果您有大量不经常更改的关键字，在这种情况下，它比使用 .NET 类库可以轻松实现的算法更有效。
Aho-Corasick 算法
在本节中，我将尝试描述此算法的概念。有关更多信息和更精确的解释，请查看本文末尾的链接。该算法包含两个部分。第一部分是从要搜索的关键字构建树，第二部分是使用先前构建的树（状态机）在文本中搜索关键字。搜索关键字非常高效，因为它只在状态机中移动。如果字符匹配，则遵循 goto 函数，否则遵循 fail 函数。
树构建
在树构建的第一阶段，将关键字添加到树中。在我的实现中，我使用了 StringSearch.TreeNode 类，它表示一个字母。根节点仅用作占位符，并包含指向其他字母的链接。在第一步中创建的链接代表 goto 函数，当字符匹配时，该函数返回下一个状态。
在第二阶段，找到 fail 和 output 函数。当字符不匹配时使用 fail 函数，output 函数返回每个到达状态找到的关键字。例如，在文本 "SHIS" 中，在匹配前两个字符后（因为第三个字符不匹配），fail 函数用于从 "SHE" 分支跳转到 "HIS" 分支。在第二阶段，BFS（广度优先搜索）算法用于遍历所有节点。函数按此顺序计算，因为指定节点的 fail 函数是使用父节点的 fail 函数计算的。
关键字树的构建（图 1 - 第一步后，图 2 - 带有 fail 函数的树）
搜索
正如我之前提到的，搜索仅仅意味着遍历先前构建的关键字树（状态机）。为了演示此算法的工作原理，让我们看一下返回所有匹配关键字的注释方法。
// Searches passed text and returns all occurrences of any keyword
// Returns array containing positions of found keywords
public StringSearchResult[] FindAll(string text)
{
ArrayList ret=new ArrayList(); // List containing results
TreeNode ptr=_root; // Current node (state)
int index=0; // Index in text
// Loop through characters
while(index<text.Length)
{
// Find next state (if no transition exists, fail function is used)
// walks through tree until transition is found or root is reached
TreeNode trans=null;
while(trans==null)
{
trans=ptr.GetTransition(text[index]);
if (ptr==_root) break;
if (trans==null) ptr=ptr.Failure;
}
if (trans!=null) ptr=trans;
// Add results from node to output array and move to next character
foreach(string found in ptr.Results)
ret.Add(new StringSearchResult(index-found.Length+1,found));
index++;
}
// Convert results to array
return (StringSearchResult[])ret.ToArray(typeof(StringSearchResult));
}
算法复杂度
第一部分的复杂度不是很重要，因为它只执行一次。第二部分的复杂度是 O(m+z)，其中 m 是文本的长度，z 是找到的关键字的数量（简单来说，它非常快，并且对于更长的文本或更多的关键字，其速度不会快速下降）。
性能对比
为了展示此算法的效率，我创建了一个测试应用程序，将此算法与另外两种可用于此目的的简单方法进行了比较。第一种算法使用 String.IndexOf 方法搜索文本中的所有关键字，第二种算法使用正则表达式 - 例如，对于关键字 he、she 和 his，它会创建一个正则表达式 (he|she|his)。下面的图表显示了两个不同大小文本的测试结果。X 轴显示使用的关键字数量，Y 轴显示搜索时间。
有趣的是，对于少于 70 个关键字，最好使用简单的 String.IndexOf 方法。正则表达式几乎总是比其他算法慢。我还尝试在 .NET 1.1 和 .NET 2.0 下编译测试以查看差异。尽管我的测量方法可能不够精确，但 .NET 2.0 似乎稍快一些（约 5-10%），而正则表达式方法给出的结果要好得多（约快 60%）。
两张图表比较了三种算法的速度 - Aho-Corasick（绿色）、IndexOf（蓝色）和 Regex（黄色）。
如何使用代码
我决定实现此算法，当时我必须在一个社区网页上屏蔽一些词（粗俗语等）。这是一个典型的用例，因为搜索应该非常快，但被阻止的关键字不经常更改（并且关键字树的创建可能会慢一些）。
搜索算法实现在 StringSearch.cs 文件中。我创建了一个接口来表示任何搜索算法（因此可以轻松地将其替换为另一个实现）。该接口名为 IStringSearchAlgorithm，它包含一个 Keywords 属性（获取或设置要搜索的关键字）和用于搜索的方法。FindAll 方法返回传入文本中的所有关键字，FindFirst 方法返回第一个匹配项。匹配项由 StringSearchResult 结构表示，其中包含找到的关键字及其在文本中的位置。最后一个方法是 ContainsAny，当传入的文本包含关键字时，它返回 true。实现 Aho-Corasick 算法的类名为 StringSearch。
初始化
以下示例显示如何从数据库加载关键字并创建 SearchAlgorithm 实例。
// Initialize DB connection
SqlConnection conn = new SqlConnection(connectionString);
SqlCommand cmd = new SqlCommand("SELECT BlockedWord" +
" FROM BlockedWords",conn);
conn.Open();
// Read list of banned words
ArrayList listWords = new ArrayList();
using(SqlDataReader reader =
cmd.ExecuteReader(CommandBehavior.CloseConnection))
{
while(reader.Read())
listWords.Add(myReader.GetString(0));
}
string[] arrayWords = (string[])listWords.ToArray(typeof(string));
// Create search algorithm instance
IStringSearchAlgorithm searchAlg = new StringSearch();
searchAlg.Keywords = arrayWords;
您还可以使用接受关键字数组作为参数的 StringSearch 构造函数。
搜索
搜索传入的文本以查找关键字更加容易。下面的示例显示如何将所有匹配项写入控制台输出。
// Find all matching keywords
StringSearchResult[] results=searchAlg.FindAll(textToSearch);
// Write all results
foreach(StringSearchResult r in results)
{
Console.WriteLine("Keyword='{0}', Index={1}", r.Keyword, r.Index);
}
结论
如果您想在任何长度的文本中查找大量关键字，此 Aho-Corasick 搜索算法的实现非常高效，但如果您只想搜索少量关键字，最好使用 String.IndexOf 等简单方法。代码可以在 .NET 1.1 和 .NET 2.0 中编译，无需任何修改。如果您想了解有关此算法的更多信息，请查看下一部分的链接，它在我实现该算法期间对我非常有帮助，并解释了该算法背后的理论。
链接和参考
- 集合匹配和 Aho-Corasick 算法 [^] - Pekka Kilpeläinen (库奥皮奥大学)
未来工作和历史
- 2005 年 3 月 12 日 - 本文的第一个版本在 CodeProject 发布。