아호 코라식(Aho-Corasick) 알고리즘(1)

우아한형제 기술블로그를 보던 중, 이목을 끄는 제목을 발견하고 글을 읽게 되었습니다.

고르곤졸라는 되지만 고르곤 졸라는 안 돼! 배달의민족에서 금칙어를 관리하는 방법 | 우아한형

블로그를 통해 아호 코라식 알고리즘에 대해 알게 되었고, 이번 기회에 정리해보고자 합니다.

 

서론

---

텍스트에서 단일 패턴을 탐색하는 알고리즘은 KMP를 통해 선형 시간(N + M)에 패턴을 찾을 수 있음을 증명하였습니다.

하지만 텍스트에서 여러 개의 패턴을 동시에 탐색해야 한다면 어떻게 해야 할까요?

먼저, 다음과 같은 방법이 있습니다.

 

텍스트의 길이를 n, 각 패턴의 길이를 m, 패턴의 개수를 k라 하겠습니다.

• 브루트 포스
  • 모든 패턴을 텍스트와 일일이 전부 비교
  • 시간복잡도: O(nm₁ + nm₂ + nm₃ + ... + nmₖ)  
• KMP
  
  • 각 패턴을 KMP 알고리즘을 사용해 텍스트와 비교
  • 시간복잡도: O(n + m₁ + n + m₂ + n + m₃ + ... + n + mₖ) = O(kn + m₁ + m₂ + m₃ + ... + mₖ)

KMP 알고리즘도 효율적이지만, 아호 코라식 알고리즘은 이보다 더욱 뛰어난 성능을 보여줍니다.

 

아호 코라식(Aho-Corasick)

---

아호 코라식 알고리즘(Aho–Corasick string matching algorithm)은  Alfred V.Aho와 Margaret J.Corasick이 고안한 문자열 검색 알고리즘(매칭 알고리즘)입니다.

아호 코라식 알고리즘은 일대다 패턴 매칭 알고리즘으로, 시간 복잡도가 O(n + m + k)로 최적화되어 있습니다. 이는 이론적으로 더 이상의 개선 여지가 없을 정도로 완벽한 성능을 자랑한다고 알려져 있습니다.

 

아호 코라식 알고리즘은 여러 문자열을 동시에 찾아야 하는 검색 엔진에서 유용하게 사용되는 알고리즘이며, 우아한형제들의 기술블로그를 보면 통합 금칙어 시스템에서 금칙어 중 허용 단어에 속하는 단어를 찾을 때 이 알고리즘을 사용하였습니다.

 

https://www.acmicpc.net/problem/9250

아래의 예시는 백준 문제를 참고하여 설명하겠습니다.

• 텍스트 = "myungwoo"
• 패턴: { "www", "woo", "jun" }

아호 코라식 알고리즘은 다음과 같은 과정을 가지고 있습니다.

1. 패턴들을 트라이에 저장
2. 실패 링크 생성
3. 탐색

패턴들을 트라이에 저장

---

트라이는 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조로, 자동완성 기능이나 사전 검색 등 문자열 탐색에 특화되어 있습니다.

 

트라이 특징

• 루트 노드는 항상 비어있습니다.
• 문자열 탐색 속도가 O(N)으로 시간 복잡도 측면에서 효율적입니다.
• 각 검색 패턴의 문자마다 메모리가 할당되므로 메모리 사용 측면에서 비효율적일 수 있습니다.

패턴 { 'www', 'woo', 'jun' }을 트라이에 저장하면 아래 그림과 같이 저장됩니다.

'woo'라는 단어를 검색하면, 가장 먼저 'w'를 찾고, 'o', 'o' 순서대로 찾습니다. 
따라서 제일 긴 단어의 길이를 N이라고 할 때, 탐색 시간 복잡도는 O(N)이 됩니다.

 

트라이 구현 코드

public class Main {
    static Node rootNode = new Node();
        
    static class Node {
        Node[] childs; // 자식 노드 저장 배열
        ArrayList<String> outPuts; // 해당 노드에서 끝나는 패턴들을 저장
        Node failLink;
        
        public Node() {
            childs = new Node[26]; // 알파벳 소문자에 대한 자식 노드 배열 생성
            outPuts = new ArrayList<>();
            failLink = null;
        }
    }
    
    static void makeTrie (String pattern) {  
        Node node = rootNode;
        
        for (char c : pattern.toCharArray()) {
            int t = c - 'a'; // 문자를 인덱스로 변환
            if(node.childs[t]==null) { // 자식 노드가 없으면 생성
                node.childs[t] = new Node();
            }
            
            node = node.childs[t]; // 현재 노드를 자식 노드로 이동
        }
        node.outPuts.add(pattern); // 패턴이 끝나는 노드의 리스트에 패턴을 저장
    }
   
    public static void main(String[] args) {    
        String[] patterns = new String[] {"www", "woo","jun"};
        
        for (int i = 0; i<patterns.length; i++) {
            makeTrie(patterns[i],i);
        }
    }
    
}

 

위의  코드를 그림으로 표현하면 다음과 같습니다.

 

참고자료

---

아호 코라식 알고리즘 - 위키백과, 우리 모두의 백과사전

(C++) 문자열 검색 알고리즘 : 아호-코라식(Aho-Corasick) 알고리즘