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

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

In this article, 您将了解用于在大量文本中搜索模式的最强大算法之一:Aho-Corasick算法. This algorithm uses a trie data structure (发音为“try”)来跟踪搜索模式，并使用一种简单的方法来有效地查找任何文本中给定模式集的所有出现情况.

Toptal Engineering Blog上的前一篇文章演示了针对相同问题的字符串搜索算法. 本文采用的方法提高了计算复杂度.

Knuth-Morris-Pratt (KMP)算法

了解我们如何在文本中有效地寻找多种模式, 我们需要首先解决一个简单的问题:在给定文本中寻找单一模式.

假设我们有一大块长度相当的文本 N 以及长度为的模式(我们要在文本中查找) M. 我们是否要寻找这种模式的一次出现, or all of the occurrences, 我们可以实现计算复杂度 O(N + M) using the KMP algorithm.

Prefix Function

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

让我们将搜索模式定义为字符串，标记为 S. For each substring S[0..i], where i >= 1，我们将找到这个字符串的最大前缀，它也恰好是这个字符串的后缀. 我们将标记这个前缀的长度 P[i].

对于模式" abracadabra "，前缀函数将产生以下回退位置:

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

让我们以模式的一个特定前缀为例:“abracadab”.该前缀的前缀函数值为2. 这表明对于这个前缀“abracadab”,"存在一个长度为2的后缀，它与长度为2的前缀(i)完全匹配.e.，该模式以“ab”开始，前缀以“ab”结束.)此外，这是该前缀最长的匹配.

Implementation

下面是一个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++)
    {
        //我们通过前缀函数值跳转来尝试更小的前缀
        //当我们找到匹配或达到零时停止跳转
        //如果在零长度前缀处停止，情况2
        // 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 "运行此函数会产生如下结果:

Computational Complexity

尽管存在两个嵌套循环，但前缀函数的复杂性只是 O(M), where M is the length of pattern S.

通过观察循环的工作原理可以很容易地解释这一点.

所有外部循环迭代通过 i can be divided into three cases:

1. Increases k by one. The loop completes one iteration.

2. Doesn’t change the zero value of k. The loop completes one iteration.

3. 的正数不会改变或减少 k.

前两种情况最多只能运行 M times.

For the third case, let’s define P(s, i) = k1 and P(s, i + 1) = k2, k2 <= k1. 每个案例之前都应该加上 k1 - k2 occurences of the first case. 减少的计数不超过 k1 - k2 + 1. 总的来说，我们没有超过 2 * M iterations.

第二个例子的解释

让我们看一下第二个示例模式“abcdabcdabcdab”. 下面是prefix函数如何一步一步地处理它:

1. 对于空子字符串和长度为1的子字符串" a ", prefix函数的值设置为0. (k = 0)

2. Look at the substring “ab.” The current value of k 是0并且字符b不等于字符a.这里是上一节的第二种情况. The value of k 保持为零，子字符串" ab "的前缀函数的值也为零.

3. 对于子字符串“abc”和“abcd”也是同样的情况.没有前缀也是这些子字符串的后缀. The value for them stays at zero.

4. 现在让我们看一个有趣的例子，子字符串“abcda”.” The current value of k 仍然是零，但是子字符串的最后一个字符与其第一个字符匹配. This triggers the condition of s[k] == s[i], where k == 0 and i == 4. The array is zero-indexed, and k 最大长度前缀的下一个字符的索引. 这意味着我们已经找到了子字符串的最大长度前缀，它也是一个后缀. 我们有第一种情况，新值 k 是1，那么前缀函数的值是多少 P(“abcda”) is one.

5. 同样的情况也会发生在接下来的两个子字符串上， P(“abcdab”) = 2 and P(“abcdabc”) = 3. 这里，我们在文本中搜索我们的模式，逐个字符比较字符串. 假设模式的前七个字符与经过处理的文本的七个连续字符匹配, 但是第八个字符不匹配. What should happen next? 在naïve字符串匹配的情况下, 我们应该返回七个字符，并从模式的第一个字符开始再次开始比较过程. 使用前缀函数值(这里) P(“abcdabc”) = 3)，我们知道我们的三个字符后缀已经匹配了三个字符的文本. 如果文本中的下一个字符是“d”,模式匹配的子字符串和文本中的子字符串的长度增加到4 (" abcd "). Otherwise, P(“abc”) = 0 我们将从模式的第一个字符开始比较过程. 但重要的是，我们在处理文本的过程中不会返回.

6. The next substring is “abcdabca."在前一个子字符串中，前缀函数等于3. This means that k = 3 is greater than zero, 与此同时，前缀中的下一个字符(s[k] = s[3] = "d")和下一个后缀字符(s[i] = s[7] = "a"). 这意味着我们触发了 s[k] != s[i]，前缀“abcd”不能作为字符串的后缀. We should decrease the value of k 在可能的情况下，使用前面的前缀进行比较. 如上所述，该数组的索引为零，并且 k 是否从前缀中检查下一个字符的索引. 当前匹配的前缀的最后一个索引是 k - 1. 取当前匹配的前缀的prefix函数的值 k = result[k - 1]. 在我们的例子中(第三种情况)，最大前缀的长度将减少到0，然后在下一行将增加到1, 因为" a "是子字符串的最大前缀，也是子字符串的后缀.

7. (这里我们继续我们的计算过程，直到我们到达一个更有趣的情况.)

8. 我们开始处理以下子字符串:" abcdabcabcdabcd.” The current value of k is seven. As with “abcdabca” above, 我们遇到了不匹配:因为字符“a”(第七个字符)不等于字符“d”," substring " abcdabca "不能是字符串的后缀. 现在我们得到了“abcdabc”(三个)的前缀函数已经计算的值，现在我们有了一个匹配:前缀“abcd”也是字符串的后缀. 它的最大前缀和子字符串的前缀函数的值都是4, 因为这是当前的值 k became.

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

简而言之:两个周期都不超过3 M次迭代，这证明了复杂度为0 (M)。. Memory use is also O(M).

KMP Algorithm Implementation

public int KMP(字符串文本，字符串s)
{
	int[] p = CalcPrefixFunction(s); // Calculate prefix function for a pattern string

	//思路与前面描述的prefix函数相同，但是现在
	//我们正在比较文本和模式的前缀.

    //找到的模式字符串的最大长度前缀的值
    // in the text:
	int maxPrefixLength = 0;
	for (int i = 0; i < text.Length; i++)
	{
        //和前缀函数一样，我们按前缀跳转，直到k为
        //大于0，否则在文本中找到匹配的前缀.
		while (maxPrefixLength > 0 && text[i] != s[maxPrefixLength])
            maxPrefixLength = p[maxPrefixLength - 1]; 

        //如果匹配，则增加maximum-length的长度
        // prefix.
		if (s[maxPrefixLength] == text[i]) maxprefixlength++;

        //如果前缀长度与模式字符串长度相同，则
        //表示我们在文本中找到了匹配的子字符串.
		if (maxPrefixLength == s.Length)
		{
			//我们可以返回这个值或者执行这个操作.
			int idx = i - s.Length + 1;
            
            //获取前一个最大长度前缀并继续搜索.
			maxPrefixLength = p[maxPrefixLength - 1];
		}
	}

	return -1;
}

上面的算法遍历文本, character by character, 并尝试增加我们的模式和文本中某些连续字符序列的最大前缀. 在失败的情况下，我们将不会回到我们的位置在前面的案文. We know the maximum prefix of the found substring of the pattern; this prefix is also the suffix of this found substring and we can simply continue the search.

该函数的复杂度与前缀函数相同, 使整体计算变得复杂 O(N + M) with O(M) memory.

Trivia: The methods String.IndexOf() and String.Contains() in the .. NET框架下有一个具有相同复杂性的算法.

The Aho-Corasick Algorithm

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

Suppose there are M patterns of lengths L1, L2, …, Lm. 我们需要在一个长度为1的文本中从字典中找到所有匹配的模式 N.

一个简单的解决方案就是从第一部分中选取任意算法并运行它 M times. We have complexity of O(N + L1 + N + L2 + … + N + Lm), i.e. O(M * N + L).

任何严肃的测试都会破坏这个算法.

Taking a dictionary with the 1,用它来搜索托尔斯泰的《欧博体育app下载》的英文版需要相当长的时间. 这本书有三百多万字.

如果我们取1万个最常见的英语单词，算法的速度会慢10倍左右. 显然，如果输入值大于这个值，执行时间也会增加.

这就是阿霍-科拉西克算法发挥其魔力的地方.

Aho-Corasick算法的复杂度是 O(N + L + Z), where Z is the count of matches. This algorithm was invented by Alfred V. Aho and Margaret J. Corasick in 1975.

Implementation

Here, we need a trie, 我们在我们的算法中加入了一个类似于上面描述的前缀函数的想法. 我们将计算整个字典的前缀函数值.

树中的每个顶点将存储以下信息:

public class Vertex
{
	public Vertex()
	{
		Children = new Hashtable();            
		Leaf = false;
		Parent = -1;
		SuffixLink = -1;
		WordID = -1;
		EndWordLink= -1;
	}

    //链接到树中的子顶点:
    // Key: A single character
    // Value: The ID of vertex
	public Hashtable Children;

    //标记字典中的某个单词在这个顶点结束
	public bool Leaf;

    // Link to the parent vertex
	public int Parent;

    //从父顶点移动到当前顶点的Char类型
	public char ParentChar;

    //当前顶点的后缀链接(相当于KMP算法中的P[i])
	public int SuffixLink;

    //链接到当前前缀中最大长度单词的叶子顶点
	public int EndWordLink;

    //如果顶点是叶节点，则存储单词的ID
	public int WordID;
}

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

If we use some structure with O(log(q)) 访问它的元素，我们有额外的内存需求 O(L)，但整个算法的复杂度将是 O((N + L) * log(q) + Z).

对于哈希表，我们有 O(L) 额外的内存，和整个算法的复杂性将 O(N + L + Z).

本教程使用哈希表，因为它还可以处理不同的字符集，例如.g., Chinese characters.

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

public class Aho
{
	List Trie;
	List WordsLength;
	int size = 0;
	int root = 0;

	public Aho()
	{
		Trie = new List();
		WordsLength = new List();
		Init();
	}

	private void Init()
	{
		Trie.Add(new Vertex())            
		size++;
	}
}

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

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];

		//检查这个边是否存在于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
	}
	//标记单词的结尾并存储其ID
	Trie[curVertex].Leaf = true;
	Trie[curVertex].WordID = wordID;
	WordsLength.Add(s.Length);
}

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

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

使它清晰易懂, 我将遍历我们的树，从根结点到叶结点进行类似于KMP算法的计算, 但与KMP算法相比, 我们在哪里找到最大长度的前缀同时也是同一子字符串的后缀, 现在我们将找到当前子字符串的最大长度后缀，它也是trie中某个模式的前缀. The value of this function will be not the length of the found suffix; it will be the link to the last character of the maximum suffix of the current substring. 这就是我所说的顶点的后缀链接.

我将按级别处理顶点. For that, I will use a breadth-first search (BFS) algorithm:

下面是这个遍历的实现:

public void PrepareAho()
{
	Queue vertexQueue = new Queue();
	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]);
		}
	}
}

And below is the CalcSuffLink 计算每个顶点的后缀链接的方法(i.e. trie中每个子字符串的前缀函数值:

公共无效CalcSuffLink(int顶点)
{
	//处理根(空字符串)
	if (vertex == root)
	{ 
		Trie[vertex].SuffixLink = root;
		Trie[vertex].EndWordLink = root;
		return;
	}
	//处理根节点的子节点(一个字符的子字符串)
	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始终为0，并链接到根顶点.

	//为了计算当前顶点的后缀链接，我们需要后缀
	//链接顶点的父节点和将我们移动到的字符
	// current vertex.
	int curBetterVertex = Trie[Trie[顶点]].Parent].SuffixLink;
	char chVertex = Trie[vertex].ParentChar; 
	//从这个顶点和它的子串开始查找最大值
	//当前顶点及其子字符串的前缀.
	
	while (true)
	{
		//如果有一条边包含所需的字符，则更新后缀链接
		// and leave the cycle
		if (Trie[curBetterVertex].Children.ContainsKey(chVertex))
		{
				Trie[vertex].SuffixLink = (int)Trie[curBetterVertex].Children[chVertex];
				break;
		}
		//否则，我们将通过后缀链接跳转，直到到达根目录
		//(相当于前缀函数计算中的k == 0)或者我们找到a
		//当前子字符串更好的前缀.
		if (curBetterVertex == root)
		{ 
				Trie[vertex].SuffixLink = root;
				break;
		}
		curBetterVertex = Trie[curBetterVertex].SuffixLink; // Go back by sufflink
	}
	//当我们完成当前的后缀链接的计算
	//顶点，我们应该更新链接到最大长度字的末尾
	//可以从当前子字符串产生.
	if (Trie[vertex].Leaf) Trie[vertex].EndWordLink = vertex; 
	else Trie[vertex].EndWordLink = Trie[Trie[vertex].SuffixLink].EndWordLink;
}

The complexity of this method is O(L); depending on the implementation of the child collection, the complexity might be O(L * log(q)).

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

让我们看看下面的图像. 这是字典树的可视化 {abba, cab, baba, cab, ac, abac, bac} with all its calculated info:

三角形边是深蓝色的，后缀链接是浅蓝色的，字典后缀链接是绿色的. 与字典条目对应的节点用蓝色突出显示.

现在我们只需要再多一个方法——处理我们要搜索的文本块:

public int ProcessString(字符串文本)
{
	// Current state value
	int currentState = root;

	// Targeted result value
	int result = 0;

	for (int j = 0; j < text.Length; j++)
	{
		//计算树的新状态
		while (true)
		{
			//如果我们有边缘，那么使用它
			if (Trie[currentState].Children.ContainsKey(text[j]))
			{
				currentState = (int)Trie[currentState].Children[text[j]];
				break;
			}
			//否则，通过后缀链接跳转并尝试找到带有的边
			// this char

            //如果没有任何可能的边，我们最终会上升到
            //根目录，此时停止检查.
			if (currentState == root) break;
			currentState = Trie[当前状态].SuffixLink;
		}
		int checkState = currentState;

		//尝试从这个前缀中找到所有可能的单词
		while (true)
		{ 
			//检查从当前前缀中获取的所有单词
			checkState = Trie[checkState].EndWordLink;

			//如果我们在根顶点，没有更多的匹配
			if (checkState == root) break;
			
			//如果算法到达这一行，就意味着我们找到了a
			// pattern match. 我们可以做额外的计算，比如find
			//在文本中找到匹配项的索引. Or check that the found
			// pattern是一个单独的单词，而不仅仅是，e.g., a substring.
			result++;
			int indexOfMatch = j + 1 - wordlength [Trie[checkState]].WordID];
	
			//尝试找到所有匹配的较小长度的模式
			checkState = Trie[checkState].SuffixLink;
		}
	}

	return result;
}

And, now this is ready for use:

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

List patterns;

And search text:

string text;

下面是如何将它们粘合在一起:

// Init the trie structure. 我们可以把近似值作为一个可选参数
//为所有节点分配一次内存的尝试大小.
Aho ahoAlg = new Aho();

for (int i = 0; i < patterns.Count; i++)
{
    ahoAlg.AddString(patterns[i], i); // Add all patterns to the structure
}
//为work准备算法(计算结构中的所有链接):
ahoAlg.PrepareAho();

// Process the text. Output might be different; in my case, it's a count of
// matches. 我们可以返回一个包含更详细信息的结构.
int countOfMatches = ahoAlg.ProcessString(text);

And that’s it! 现在您知道了这个简单但功能强大的算法是如何工作的!

Aho-Corasick is really flexible. 搜索模式不必仅仅是单词, 但我们可以使用整个句子或随机的字符链.

Performance

该算法在Intel酷睿i7-4702MQ上进行了测试.

For tests, I took two dictionaries: The 1,000 most common English words, and the 10,000 most common English words.

将所有这些单词添加到字典中，并准备与每个字典一起工作的数据结构, 算法耗时分别为55ms和135ms.

该算法处理长度在1以内的3-4百万字符的真实书籍.0-1.3 seconds, while it took 9.一本3000万字的书需要6秒.

并行化Aho-Corasick算法

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

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

如果单词在块之间的边界被分割呢? 这个问题很容易解决.

Let N be the length of our large text, S be the size of a chunk, and L 是字典中最大模式的长度.

Now we can use a simple trick. 我们把最后有重叠的块分开，比如 [S * (i - 1), S * i + L - 1], where i is index of the chunk. When we get a pattern match, 我们可以很容易地获得当前匹配的起始索引，并检查该索引是否在块范围内，没有重叠, [S * (i - 1), S * i - 1].

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

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

该算法常用于各种系统中, such as spell checkers, spam filters, search engines, 生物信息学/DNA序列检索, etc. In fact, 您可能每天都在使用的一些流行工具在幕后使用了这种算法.

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

我希望这篇关于Aho-Corasick算法的教程对您有所帮助.