使用 Aho-Corasick 算法征服字符串搜索

操作字符串并在其中搜索模式是数据科学中的基本任务，也是任何程序员的典型任务。

高效的字符串算法在许多数据科学过程中发挥着重要作用。 通常，它们是使此类过程足够可行以供实际使用的原因。

在本文中，您将了解在大量文本中搜索模式的最强大算法之一：Aho-Corasick 算法。 该算法使用 trie 数据结构（发音为“try”）来跟踪搜索模式，并使用一种简单的方法有效地在任何文本块中找到给定模式集的所有出现。

Toptal 工程博客上的前一篇文章演示了针对同一问题的字符串搜索算法。 本文中采用的方法提供了改进的计算复杂性。

Knuth-Morris-Pratt (KMP) 算法

要了解如何有效地在文本中查找多个模式，我们需要首先解决一个更简单的问题：在给定文本中查找单个模式。

假设我们有一个长度为N的大文本块和一个长度为M的模式（我们想在文本中查找）。 无论我们是想寻找这种模式的单个出现，还是所有出现，我们都可以使用 KMP 算法实现O(N + M)的计算复杂度。

前缀功能

KMP 算法通过计算我们正在搜索的模式的前缀函数来工作。 prefix 函数为模式的每个前缀预先计算一个后备位置。

让我们将搜索模式定义为一个字符串，标记为S 。 对于每个子字符串S[0..i] ，其中i >= 1 ，我们将找到该字符串的最大前缀，该前缀也恰好是该字符串的后缀。 我们将标记此前缀P[i]的长度。

对于“abracadabra”模式，前缀函数将产生以下后备位置：

前缀函数标识了模式的一个有趣特征。

让我们以模式的特定前缀为例：“abracadab”。 此前缀的前缀函数值为 2。 这表明对于这个前缀“abracadab”，存在一个长度为 2 的后缀与长度为 2 的前缀完全匹配（即，模式以“ab”开头，前缀以“ab”结尾）。此外，这是此前缀的最长匹配。

执行

这是一个 C# 函数，可用于计算任何字符串的前缀函数：

 public int[] CalcPrefixFunction(String s) { int[] result = new int[s.Length]; // array with prefix function values result[0] = 0; // the prefix function is always zero for the first symbol (its degenerate case) int k = 0; // current prefix function value for (int i = 1; i < s.Length; i++) { // We're jumping by prefix function values to try smaller prefixes // Jumping stops when we find a match, or reach zero // Case 2 if we stop at a zero-length prefix // Case 3 if we stop at a match while (k > 0 && s[i] != s[k]) k = result[k - 1]; if (s[k] == s[i]) k++; // we've found the longest prefix - case 1 result[i] = k; // store this result in the array } return result; }

在稍长的模式“abcdabcabcdabcdab”上运行此函数会产生以下结果：

计算复杂度

尽管存在两个嵌套循环，但前缀函数的复杂度仅为O(M) ，其中M是模式S的长度。

这可以通过观察循环如何工作来轻松解释。

通过i的所有外循环迭代可以分为三种情况：

1. k加一。 循环完成一次迭代。

2. 不改变k的零值。 循环完成一次迭代。

3. 不改变或减少k的正值。

前两种情况最多可以运行M次。

对于第三种情况，让我们定义P(s, i) = k1和P(s, i + 1) = k2, k2 <= k1 。 这些案例中的每一个都应该在第一个案例的k1 - k2次出现之前。 减少的次数不超过k1 - k2 + 1 。 总共我们不超过2 * M次迭代。

第二个例子的解释

让我们看看第二个示例模式“abcdabcabcdabcdab”。 下面是前缀函数如何处理它，一步一步：

1. 对于空子串和长度为 1 的子串“a”，前缀函数的值设置为零。 ( k = 0 )

2. 查看子字符串“ab”。 k的当前值为零，字符“b”不等于字符“a”。 在这里，我们有上一节的第二种情况。 k的值保持为零，子串“ab”的前缀函数的值也为零。

3. 子串“abc”和“abcd”的情况相同。 没有前缀也是这些子字符串的后缀。 他们的价值保持在零。

4. 现在让我们看一个有趣的例子，子字符串“abcda”。 k的当前值仍然为零，但我们的子字符串的最后一个字符与它的第一个字符匹配。 这会触发s[k] == s[i]的条件，其中k == 0和i == 4 。 数组是零索引的， k是最大长度前缀的下一个字符的索引。 这意味着我们找到了子字符串的最大长度前缀，它也是一个后缀。 我们有第一种情况，其中k的新值为 1，因此前缀函数P(“abcda”)的值为 1。

5. 接下来的两个子字符串P(“abcdab”) = 2和P(“abcdabc”) = 3也会发生同样的情况。 在这里，我们在文本中搜索我们的模式，逐个字符地比较字符串。 假设模式的前七个字符与已处理文本的一些七个连续字符匹配，但在第八个字符上它不匹配。 接下来应该发生什么？ 在简单字符串匹配的情况下，我们应该返回七个字符并从模式的第一个字符重新开始比较过程。 使用前缀函数值（此处为P(“abcdabc”) = 3 ）我们知道我们的三字符后缀已经匹配了文本的三个字符。 如果文本中的下一个字符是“d”，则我们的模式和文本中子串的匹配子串的长度增加到四个（“abcd”）。 否则， P(“abc”) = 0 ，我们将从模式的第一个字符开始比较过程。 但重要的是我们在文本处理过程中不返回。

6. 下一个子字符串是“abcdabca”。 在前面的子字符串中，前缀函数等于 3。 这意味着k = 3大于零，同时前缀中的下一个字符 ( s[k] = s[3] = "d" ) 和后缀中的下一个字符 ( s[i] = s[7] = "a" )。 这意味着我们触发了s[k] != s[i]的条件，并且前缀“abcd”不能是我们字符串的后缀。 如果可能，我们应该减小k的值并取之前的前缀进行比较。 如上所述，数组是零索引的， k是我们从前缀中检查的下一个字符的索引。 当前匹配前缀的最后一个索引是k - 1 。 我们为当前匹配的前缀k = result[k - 1]取前缀函数的值。 在我们的例子（第三种情况）中，最大前缀的长度将减少到零，然后在下一行将增加到一，因为“a”是最大前缀，也是我们的子字符串的后缀。

7. （这里我们继续我们的计算过程，直到我们遇到更有趣的情况。）

8. 我们开始处理以下子字符串：“abcdabcabcdabcd”。 k的当前值为7。 与上面的“abcdabca”一样，我们遇到了不匹配：因为字符“a”（第七个字符）不等于字符“d”，所以子字符串“abcdabca”不能是我们字符串的后缀。 现在我们得到“abcdabc”（三）的前缀函数已经计算的值，现在我们有一个匹配：前缀“abcd”也是我们字符串的后缀。 它的最大前缀和我们的子字符串的前缀函数的值是四，因为这就是k的当前值。

9. 我们继续这个过程直到模式结束。

简而言之：两个循环都需要不超过 3 M 次迭代，这证明复杂度为 O(M)。 内存使用也是 O(M)。

KMP算法实现

public int KMP(String text, String s) { int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string // The idea is the same as in the prefix function described above, but now // we're comparing prefixes of text and pattern. // The value of maximum-length prefix of the pattern string that was found // in the text: int maxPrefixLength = 0; for (int i = 0; i < text.Length; i++) { // As in the prefix function, we're jumping by prefixes until k is // greater than 0 or we find a prefix that has matches in the text. while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength]) maxPrefixLength = p[maxPrefixLength - 1]; // If a match happened, increase the length of the maximum-length // prefix. if (s[maxPrefixLength] == text[i]) maxPrefixLength++; // If the prefix length is the same length as the pattern string, it // means that we have found a matching substring in the text. if (maxPrefixLength == s.Length) { // We can return this value or perform this operation. int idx = i - s.Length + 1; // Get the previous maximum-length prefix and continue search. maxPrefixLength = p[maxPrefixLength - 1]; } } return -1; }

上述算法逐个字符地遍历文本，并尝试增加我们的模式和文本中某些连续字符序列的最大前缀。 如果失败，我们将不会将我们的立场返回到文本的前面。 我们知道找到的模式子串的最大前缀； 这个前缀也是这个找到的子字符串的后缀，我们可以简单地继续搜索。

该函数的复杂度与前缀函数的复杂度相同，使得整体计算复杂度为O(N + M) ，内存为O(M) 。

琐事：.NET 框架中的方法String.IndexOf()和String.Contains()具有相同复杂性的算法。

Aho-Corasick 算法

现在我们想对多个模式做同样的事情。

假设有M个长度为L1 、 L2 、...、 Lm的模式。 我们需要在长度为N的文本中从字典中找到所有模式匹配项。

一个简单的解决方案是从第一部分中获取任何算法并运行它M次。 我们的复杂度为O(N + L1 + N + L2 + … + N + Lm) ，即O(M * N + L) 。

任何足够严重的测试都会杀死这个算法。

用1000个最常用的英语单词作为模式的字典，用它来搜索托尔斯泰的《战争与和平》的英文版，需要相当长的时间。 这本书有超过三百万字长。

如果我们选取 10,000 个最常见的英语单词，算法的运行速度会慢 10 倍左右。 显然，在大于这个的输入上，执行时间也会增加。

这就是 Aho-Corasick 算法发挥魔力的地方。

Aho-Corasick 算法的复杂度为O(N + L + Z) ，其中Z是匹配数。 该算法由 Alfred V. Aho 和 Margaret J. Corasick 在 1975 年发明。

执行

在这里，我们需要一个 trie，并在我们的算法中添加与上述前缀函数类似的想法。 我们将为整个字典计算前缀函数值。

trie 中的每个顶点都将存储以下信息：

 public class Vertex { public Vertex() { Children = new Hashtable(); Leaf = false; Parent = -1; SuffixLink = -1; WordID = -1; EndWordLink= -1; } // Links to the child vertexes in the trie: // Key: A single character // Value: The ID of vertex public Hashtable Children; // Flag that some word from the dictionary ends in this vertex public bool Leaf; // Link to the parent vertex public int Parent; // Char which moves us from the parent vertex to the current vertex public char ParentChar; // Suffix link from current vertex (the equivalent of P[i] from the KMP algorithm) public int SuffixLink; // Link to the leaf vertex of the maximum-length word we can make from the current prefix public int EndWordLink; // If the vertex is the leaf, we store the ID of the word public int WordID; }

有多种实现子链接的方法。 在数组的情况下，该算法将具有O(N + L + Z)的复杂度，但这将需要O(L * q)的额外内存需求，其中q是字母表的长度，因为那是一个节点可以拥有的最大子节点数。

如果我们使用一些结构O(log(q))访问其元素，我们有额外的内存需求O(L) ，但整个算法的复杂度将是O((N + L) * log(q) + Z) 。

在哈希表的情况下，我们有O(L)额外的内存，整个算法的复杂度将是O(N + L + Z) 。

本教程使用哈希表，因为它也适用于不同的字符集，例如中文字符。

我们已经有了一个顶点结构。 接下来，我们将定义一个顶点列表并初始化树的根节点。

 public class Aho { List<Vertex> Trie; List<int> WordsLength; int size = 0; int root = 0; public Aho() { Trie = new List<Vertex>(); WordsLength = new List<int>(); Init(); } private void Init() { Trie.Add(new Vertex()) size++; } }

然后我们将所有模式添加到树中。 为此，我们需要一个向 trie 添加单词的方法：

 public void AddString(String s, int wordID) { int curVertex = root; for (int i = 0; i < s.Length; ++i) // Iterating over the string's characters { char c = s[i]; // Checking if a vertex with this edge exists in the trie: if (!Trie[curVertex].Children.ContainsKey(c)) { Trie.Add(new Vertex()); Trie[size].SuffixLink = -1; // If not - add vertex Trie[size].Parent = curVertex; Trie[size].ParentChar = c; Trie[curVertex].Children[c] = size; size++; } curVertex = (int)Trie[curVertex].Children[c]; // Move to the new vertex in the trie } // Mark the end of the word and store its ID Trie[curVertex].Leaf = true; Trie[curVertex].WordID = wordID; WordsLength.Add(s.Length); }

此时，所有的模式词都在数据结构中。 这需要额外的内存O(L) 。

接下来我们需要计算所有的后缀链接和字典条目链接。

为了清楚易懂，我将遍历我们的 trie 从根到叶子并进行类似的计算，就像我们为 KMP 算法所做的那样，但与 KMP 算法相比，我们找到最大长度前缀也是相同子字符串的后缀，现在我们将找到当前子字符串的最大长度后缀，它也是特里树中某些模式的前缀。 这个函数的值不会是找到的后缀的长度； 它将链接到当前子字符串的最大后缀的最后一个字符。 这就是我所说的顶点的后缀链接。

我将按级别处理顶点。 为此，我将使用广度优先搜索 (BFS) 算法：

下面是这个遍历的实现：

 public void PrepareAho() { Queue<int> vertexQueue = new Queue<int>(); vertexQueue.Enqueue(root); while (vertexQueue.Count > 0) { int curVertex = vertexQueue.Dequeue(); CalcSuffLink(curVertex); foreach (char key in Trie[curVertex].Children.Keys) { vertexQueue.Enqueue((int)Trie[curVertex].Children[key]); } } }

下面是计算每个顶点的后缀链接的CalcSuffLink方法（即trie中每个子串的前缀函数值）：

 public void CalcSuffLink(int vertex) { // Processing root (empty string) if (vertex == root) { Trie[vertex].SuffixLink = root; Trie[vertex].EndWordLink = root; return; } // Processing children of the root (one character substrings) if (Trie[vertex].Parent == root) { Trie[vertex].SuffixLink = root; if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; return; } // Cases above are degenerate cases as for prefix function calculation; the // value is always 0 and links to the root vertex. // To calculate the suffix link for the current vertex, we need the suffix // link for the parent of the vertex and the character that moved us to the // current vertex. int curBetterVertex = Trie[Trie[vertex].Parent].SuffixLink; char chVertex = Trie[vertex].ParentChar; // From this vertex and its substring we will start to look for the maximum // prefix for the current vertex and its substring. while (true) { // If there is an edge with the needed char, we update our suffix link // and leave the cycle if (Trie[curBetterVertex].Children.ContainsKey(chVertex)) { Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex]; break; } // Otherwise, we are jumping by suffix links until we reach the root // (equivalent of k == 0 in prefix function calculation) or we find a // better prefix for the current substring. if (curBetterVertex == root) { Trie[vertex].SuffixLink = root; break; } curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink } // When we complete the calculation of the suffix link for the current // vertex, we should update the link to the end of the maximum length word // that can be produced from the current substring. if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink; }

这种方法的复杂度是O(L) ； 根据子集合的实现，复杂度可能是O(L * log(q)) 。

复杂度证明类似于 KMP 算法中的复杂度证明前缀函数。

让我们看看下面的图像。 这是字典{ abba, cab, baba, caab, ac, abac, bac }的特里树及其所有计算信息的可视化：

Trie 边缘为深蓝色，后缀链接为浅蓝色，字典后缀链接为绿色。 对应于字典条目的节点以蓝色突出显示。

现在我们只需要一个方法——处理我们打算搜索的文本块：

 public int ProcessString(String text) { // Current state value int currentState = root; // Targeted result value int result = 0; for (int j = 0; j < text.Length; j++) { // Calculating new state in the trie while (true) { // If we have the edge, then use it if (Trie[currentState].Children.ContainsKey(text[j])) { currentState = (int)Trie[currentState].Children[text[j]]; break; } // Otherwise, jump by suffix links and try to find the edge with // this char // If there aren't any possible edges we will eventually ascend to // the root, and at this point we stop checking. if (currentState == root) break; currentState = Trie[currentState].SuffixLink; } int checkState = currentState; // Trying to find all possible words from this prefix while (true) { // Checking all words that we can get from the current prefix checkState = Trie[checkState].EndWordLink; // If we are in the root vertex, there are no more matches if (checkState == root) break; // If the algorithm arrived at this row, it means we have found a // pattern match. And we can make additional calculations like find // the index of the found match in the text. Or check that the found // pattern is a separate word and not just, eg, a substring. result++; int indexOfMatch = j + 1 - WordsLength[Trie[checkState].WordID]; // Trying to find all matched patterns of smaller length checkState = Trie[checkState].SuffixLink; } } return result; }

而且，现在可以使用了：

在输入时，我们有一个模式列表：

 List<string> patterns;

并搜索文本：

 string text;

以下是如何将它们粘合在一起：

 // Init the trie structure. As an optional parameter we can put the approximate // size of the trie to allocate memory just once for all nodes. Aho ahoAlg = new Aho(); for (int i = 0; i < patterns.Count; i++) { ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure } // Prepare algorithm for work (calculates all links in the structure): ahoAlg.PrepareAho(); // Process the text. Output might be different; in my case, it's a count of // matches. We could instead return a structure with more detailed information. int countOfMatches = ahoAlg.ProcessString(text);

就是这样！ 你现在知道这个简单而强大的算法是如何工作的了！

Aho-Corasick 非常灵活。 搜索模式不必只是单词，但我们可以使用整个句子或随机的字符链。

表现

该算法在 Intel Core i7-4702MQ 上进行了测试。

为了测试，我拿了两本词典：1000 个最常见的英语单词和 10,000 个最常见的英语单词。

要将所有这些单词添加到字典中并准备数据结构以与每个字典一起使用，该算法分别需要 55 毫秒和 135 毫秒。

该算法在 1.0-1.3 秒内处理长度为 3-400 万个字符的真实书籍，而处理一本大约 3000 万个字符的书籍需要 9.6 秒。

并行化 Aho-Corasick 算法

与 Aho-Corasick 算法并行根本不是问题：

一个大文本可以分为多个块，并且可以使用多个线程来处理每个块。 每个线程都可以访问基于字典生成的 trie。

单词在块之间的边界被分割怎么办？ 这个问题很容易解决。

让N是我们的大文本的长度， S是块的大小， L是字典中最大模式的长度。

现在我们可以使用一个简单的技巧。 我们在最后划分有一些重叠的块，例如采用[S * (i - 1), S * i + L - 1] ，其中i是块的索引。 当我们得到一个模式匹配时，我们可以很容易地得到当前匹配的起始索引，并且只需检查这个索引是否在没有重叠的块范围内， [S * (i - 1), S * i - 1] 。

一种通用的字符串搜索算法

Aho-Corasick 算法是一种功能强大的字符串匹配算法，可为任何输入提供最佳复杂性，并且不需要太多额外的内存。

该算法经常用于各种系统，例如拼写检查器、垃圾邮件过滤器、搜索引擎、生物信息学/DNA 序列搜索等。实际上，您可能每天都在使用的一些流行工具在幕后使用该算法。

KMP 算法中的前缀函数本身就是一个有趣的工具，它将单模式匹配的复杂性降低到线性时间。 Aho-Corasick 算法遵循类似的方法，并使用 trie 数据结构对多个模式执行相同的操作。

我希望您发现本关于 Aho-Corasick 算法的教程很有用。