使用 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 算法的教程很有用。