Aho-Corasick 알고리즘으로 문자열 검색 정복

문자열을 조작하고 문자열에서 패턴을 검색하는 것은 데이터 과학의 기본 작업이며 모든 프로그래머의 일반적인 작업입니다.

효율적인 문자열 알고리즘은 많은 데이터 과학 프로세스에서 중요한 역할을 합니다. 종종 그것들은 그러한 프로세스를 실제 사용에 충분히 실현 가능하게 만드는 것입니다.

이 기사에서는 많은 양의 텍스트에서 패턴을 검색하는 가장 강력한 알고리즘 중 하나인 Aho-Corasick 알고리즘에 대해 배웁니다. 이 알고리즘은 trie 데이터 구조("try"로 발음)를 사용하여 검색 패턴을 추적하고 간단한 방법을 사용하여 모든 텍스트 덩어리에서 주어진 패턴 집합의 모든 발생을 효율적으로 찾습니다.

Toptal Engineering Blog의 이전 기사에서는 동일한 문제에 대한 문자열 검색 알고리즘을 시연했습니다. 이 기사에서 취한 접근 방식은 향상된 계산 복잡성을 제공합니다.

Knuth-Morris-Pratt(KMP) 알고리즘

텍스트에서 여러 패턴을 효율적으로 찾는 방법을 이해하려면 먼저 더 쉬운 문제를 해결해야 합니다. 주어진 텍스트에서 단일 패턴을 찾는 것입니다.

길이가 N 인 큰 텍스트 덩어리와 길이가 M 인 패턴(텍스트에서 찾고자 하는)이 있다고 가정합니다. 이 패턴의 단일 발생을 찾든 모든 발생을 찾든 KMP 알고리즘을 사용하여 O(N + M) 의 계산 복잡도를 얻을 수 있습니다.

접두사 기능

KMP 알고리즘은 우리가 찾고 있는 패턴의 접두사 함수를 계산하여 작동합니다. 접두사 함수는 패턴의 모든 접두사에 대한 대체 위치를 미리 계산합니다.

검색 패턴을 S 레이블이 지정된 문자열로 정의해 보겠습니다. i >= 1 인 각 부분 문자열 S[0..i] 에 대해 이 문자열의 접미사이기도 한 이 문자열의 최대 접두사를 찾습니다. 이 접두사의 길이를 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 를 1씩 증가시킵니다. 루프는 한 번의 반복을 완료합니다.

2. k 의 0 값을 변경하지 않습니다. 루프는 한 번의 반복을 완료합니다.

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"의 경우 접두사 함수의 값은 0으로 설정됩니다. ( k = 0 )

2. 하위 문자열 "ab"를 보십시오. k 의 현재 값은 0이고 문자 "b"는 문자 "a"와 같지 않습니다. 여기에 이전 섹션의 두 번째 경우가 있습니다. k 의 값은 0에 머물고 하위 문자열 "ab"에 대한 접두사 함수의 값도 0입니다.

3. 하위 문자열 "abc" 및 "abcd"의 경우도 마찬가지입니다. 이러한 하위 문자열의 접미사이기도 한 접두사는 없습니다. 그들에 대한 가치는 0으로 유지됩니다.

4. 이제 흥미로운 경우인 "abcda" 부분 문자열을 살펴보겠습니다. k 의 현재 값은 여전히 ​​0이지만 부분 문자열의 마지막 문자는 첫 번째 문자와 일치합니다. 이것은 s[k] == s[i] 조건을 트리거합니다. 여기서 k == 0 및 i == 4 입니다. 배열은 0으로 인덱싱되고 k 는 최대 길이 접두사에 대한 다음 문자의 인덱스입니다. 이것은 접미사이기도 한 부분 문자열의 최대 길이 접두사를 찾았음을 의미합니다. k 의 새로운 값이 1이고 접두사 함수 P("abcda") 의 값이 1인 첫 번째 경우가 있습니다.

5. 다음 두 하위 문자열 P("abcdab") = 2 및 P("abcdab") = 3 에 대해서도 동일한 경우가 발생합니다. 여기에서 문자열을 문자별로 비교하면서 텍스트에서 패턴을 검색하고 있습니다. 패턴의 처음 7개 문자가 처리된 텍스트의 연속 7개 문자와 일치하지만 8번째 문자에서는 일치하지 않는다고 가정해 보겠습니다. 다음에 무슨 일이 일어나야 합니까? 순진한 문자열 일치의 경우 7개 문자를 다시 반환하고 패턴의 첫 번째 문자부터 비교 프로세스를 다시 시작해야 합니다. 접두사 함수 값(여기서 P("abcdabc") = 3 )을 사용하여 세 글자 접미사가 이미 세 글자의 텍스트와 일치한다는 것을 알고 있습니다. 그리고 텍스트의 다음 문자가 "d"이면 패턴의 일치하는 부분 문자열과 텍스트의 부분 문자열의 길이가 4로 증가합니다("abcd"). 그렇지 않으면 P("abc") = 0 이고 패턴의 첫 번째 문자부터 비교 프로세스를 시작합니다. 그러나 중요한 것은 텍스트를 처리하는 동안 반환하지 않는다는 것입니다.

6. 다음 하위 문자열은 "abcdabca"입니다. 이전 하위 문자열에서 접두사 함수는 3과 같습니다. 이것은 k = 3 이 0보다 크며 동시에 접두사( s[k] = s[3] = "d" )의 다음 문자와 접미사( s[i] = s[7] = "a" ). 이것은 우리가 s[k] != s[i] 조건을 촉발했고 접두사 "abcd"가 우리 문자열의 접미사가 될 수 없다는 것을 의미합니다. 가능한 경우 k 값을 줄이고 비교를 위해 이전 접두사를 사용해야 합니다. 위에서 설명한 것처럼 배열은 인덱스가 0이고 k 는 접두사에서 확인하는 다음 문자의 인덱스입니다. 현재 일치하는 접두사의 마지막 인덱스는 k - 1 입니다. 현재 일치하는 접두사 k = result[k - 1] 에 대한 접두사 함수의 값을 취합니다. 우리의 경우(세 번째 경우) 최대 접두사의 길이는 0으로 줄어들고 다음 줄에서는 최대 1까지 증가합니다. "a"는 하위 문자열의 접미사이기도 한 최대 접두사이기 때문입니다.

7. (여기서 더 흥미로운 경우에 도달할 때까지 계산 프로세스를 계속합니다.)

8. "abcdabcabcdabcd" 하위 문자열 처리를 시작합니다. k 의 현재 값은 7입니다. 위의 "abcdabca"와 마찬가지로 일치하지 않는 항목이 있습니다. 문자 "a"(7번째 문자)가 문자 "d"와 같지 않기 때문에 하위 문자열 "abcdabca"는 문자열의 접미사가 될 수 없습니다. 이제 "abcdabc"(3)에 대한 접두사 함수의 이미 계산된 값을 얻었고 이제 일치 항목이 있습니다. 접두사 "abcd"는 문자열의 접미사이기도 합니다. 그것의 최대 접두사와 부분 문자열에 대한 접두사 함수의 값은 4입니다. 왜냐하면 그것이 k 의 현재 값이 되었기 때문입니다.

9. 패턴이 끝날 때까지 이 과정을 계속합니다.

간단히 말해서, 두 사이클 모두 3M 이하의 반복을 수행하므로 복잡성이 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(M) 메모리로 전체 계산 복잡도를 O(N + M) 으로 만듭니다.

퀴즈: .NET 프레임워크의 String.IndexOf() 및 String.Contains() 메서드에는 내부적으로 동일한 복잡성을 가진 알고리즘이 있습니다.

Aho-Corasick 알고리즘

이제 여러 패턴에 대해 동일한 작업을 수행하려고 합니다.

길이가 L1 , L2 , … , Lm 인 M 패턴이 있다고 가정합니다. 길이가 N 인 텍스트의 사전에서 패턴의 모든 일치 항목을 찾아야 합니다.

간단한 솔루션은 첫 번째 부분에서 알고리즘을 가져와 M 번 실행하는 것입니다. 복잡성은 O(N + L1 + N + L2 + … + N + Lm) , 즉 O(M * N + L) 입니다.

충분히 심각한 테스트는 이 알고리즘을 죽입니다.

1,000개의 가장 흔한 영어 단어가 있는 사전을 패턴으로 사용하여 톨스토이의 "전쟁과 평화"의 영어 버전을 검색하는 데 사용하면 꽤 오랜 시간이 걸립니다. 책의 길이는 300만 자를 넘습니다.

가장 일반적인 영어 단어 10,000개를 취하면 알고리즘이 약 10배 느리게 작동합니다. 분명히 이 값보다 큰 입력에서는 실행 시간도 늘어납니다.

여기에서 Aho-Corasick 알고리즘이 마법을 발휘합니다.

Aho-Corasick 알고리즘의 복잡성은 O(N + L + Z) 이며, 여기서 Z 는 일치 횟수입니다. 이 알고리즘은 1975년 Alfred V. Aho와 Margaret J. Corasick에 의해 발명되었습니다.

구현

여기에서 트라이가 필요하고 위에서 설명한 접두사 함수와 유사한 아이디어를 알고리즘에 추가합니다. 전체 사전에 대한 접두사 함수 값을 계산합니다.

트라이의 각 꼭짓점은 다음 정보를 저장합니다.

 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) + 지) .

해시 테이블의 경우 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++; } }

그런 다음 모든 패턴을 트라이에 추가합니다. 이를 위해 트라이에 단어를 추가하는 메서드가 필요합니다.

 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) 의 추가 메모리가 필요합니다.

다음으로 모든 접미사 링크와 사전 항목 링크를 계산해야 합니다.

명확하고 이해하기 쉽게 하기 위해 루트에서 리프까지 트리를 탐색하고 KMP 알고리즘에 대해 수행한 것과 유사한 계산을 수행하지만 KMP 알고리즘과 대조적으로 최대 길이를 찾는 동일한 하위 문자열의 접미사이기도 한 접두사를 사용하여 현재 하위 문자열의 최대 길이 접미사를 찾습니다. 이 접미사는 또한 트라이에 있는 일부 패턴의 접두사이기도 합니다. 이 함수의 값은 찾은 접미사의 길이가 아닙니다. 현재 부분 문자열의 최대 접미사의 마지막 문자에 대한 링크가 됩니다. 이것이 내가 정점의 접미사 링크로 의미하는 바입니다.

정점을 레벨별로 처리하겠습니다. 이를 위해 BFS(Breadth First Search) 알고리즘을 사용합니다.

다음은 이 순회를 구현한 것입니다.

 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 방법입니다(즉, 트라이의 각 부분 문자열에 대한 접두사 함수 값):

 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에서 테스트되었습니다.

테스트를 위해 1,000개의 가장 일반적인 영어 단어와 10,000개의 가장 일반적인 영어 단어의 두 가지 사전을 사용했습니다.

이 모든 단어를 사전에 추가하고 각 사전과 함께 작동하도록 데이터 구조를 준비하려면 알고리즘이 각각 55ms 및 135ms가 필요했습니다.

알고리즘은 300만~400만 자의 실제 책을 1.0~1.3초 이내에 처리한 반면, 약 3천만 자의 책은 9.6초가 걸렸다.

Aho-Corasick 알고리즘 병렬화

Aho-Corasick 알고리즘과 병행하는 것은 전혀 문제가 되지 않습니다.

큰 텍스트는 여러 청크로 나눌 수 있으며 여러 스레드를 사용하여 각 청크를 처리할 수 있습니다. 각 스레드는 사전을 기반으로 생성된 트라이에 액세스할 수 있습니다.

청크 사이의 경계에서 단어가 분할되는 것은 어떻습니까? 이 문제는 쉽게 해결할 수 있습니다.

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 알고리즘에 대한 이 튜토리얼이 유용했기를 바랍니다.