문자열 - 아호-코라식

아호-코라식(Aho-Corasick) 알고리즘은 다중 문자열 서칭, 즉 하나의 문자열 $T$ 내에서 여러 개의 패턴 문자열 $P_1, P_2, \cdots, P_k$를 찾아야 하는 과제에서 사용 가능한 강력한 알고리즘이다. 아이디어는 매우 직관적이며 단순한데, 찾아야 하는 패턴 문자열들로 트라이(trie)를 만들고, 트라이 내에서 KMP를 수행하는 것이다. 다만 트라이와 kmp 둘 다 다소 복잡한 구조의 알고리즘이다 보니 구현이 간단한 편은 아니다. KMP의 핵심인 실패 함수가 트라이 위에서 어떻게 동작하는지를 이해하는 것이 아호-코라식의 핵심이라고 할 수 있다.

 

 

실패 함수의 구성

KMP의 작동 원리를 다시 떠올려 보자. $j-1$까지 일치하다가 $j$에서 불일치하는 경우, $j := fail[j-1]$로 돌아가서 일치 여부를 검사하도록 하는 것이 kmp의 아이디어였다. 비슷하게, 트라이 내에서 일치가 보장된 직전의 노드(부모 노드)를 $u$, 일치 여부를 확인해야 하는 현재 노드(자식 노드)를 $v$라 하면, 다음과 같이 실패 함수 $fail[v]$의 값을 구할 수 있다.

 

• $f$의 초깃값은 부모 노드의 실패 함숫값 $fail[u]$에서부터 시작한다.
• 현재 문자 char이 $trie[f]$에 존재하는지 확인하고, 존재하지 않으면 $f := fail[f]$로 돌아가서 다시 확인한다.
• 다만 $fail[v]$는 $v$까지 일치했을 경우의 실패 함숫값을 담고 있어야 하므로, 구한 $f$에서 한 단계 더 진행해 $f := trie[f][char]$로 한다.

 

결과적으로 $fail[v]$는 트라이 내에서 $v$보다 깊이가 얕으면서, $v$까지의 부분 문자열과 suffix가 최대로 일치하는 노드를 가리키게 된다. 따라서 트라이 내에서 bfs를 수행하면서 위 과정을 반복함으로써 실패 함수를 build하는 것이 가능하다.

 

 

출력 함수의 구성

단순 일치 여부뿐만 아니라, 실제로 찾은 패턴 문자열과 그 위치까지 구해야 하는 경우에는 별도의 출력 함수도 함께 구성해 줄 필요가 있다. 문자열을 한 번만 훑으면서 선형적으로 동작하는 아호-코라식의 특성상, 'abcde' 내에서 ['bcd', 'cd']를 찾는 문제의 경우 문자 'd'를 처리할 때 'bcd'와 'cd'를 모두 찾아 주어야 하기 때문이다. 그러나 출력 함수 $output$의 구성은 별도로 진행할 필요는 없고 실패 함수를 구성할 때 함께 처리할 수 있다. 예시에서 봤듯이, 같이 찾아 주어야 하는 문자열들은 공통의 suffix를 가지기 때문이다. 따라서, 트라이를 만들 때 각 패턴 문자열의 끝에 해당하는 노드에 출력 값을 넣어 두고, 실패 함수를 구성할 때 $output[fail[v]]$에 있는 출력 값을 가져와서 $output[v]$에 합쳐 주면 된다. 이렇게 하면 bfs를 수행하면서 공통의 suffix를 가진 패턴 문자열들끼리 (마치 분할 정복처럼) 합쳐지면서 목표하는 패턴 문자열들을 모두 찾을 수 있게 된다.

 

class AhoCorasick:
    def __init__(self):
        self.trie = [{}]
        self.fail = [0]
        self.output = [[]]

    def insert(self, word):
        node = 0
        for char in word:
            if char not in self.trie[node]:
                self.trie[node][char] = len(self.trie)
                self.trie.append({})
                self.fail.append(0)
                self.output.append([])
            node = self.trie[node][char]
        self.output[node].append(word)
    
    def build(self):
        q = deque(self.trie[0].values())
        while q:
            u = q.popleft()
            for char, v in self.trie[u].items():
                f = self.fail[u]
                while f > 0 and char not in self.trie[f]:
                    f = self.fail[f]
                
                self.fail[v] = self.trie[f][char] if char in self.trie[f] else 0
                self.output[v].extend(self.output[self.fail[v]])
                q.append(v)
    
    def search(self, text):
        node = 0
        res = []
        for i, char in enumerate(text):
            while node > 0 and char not in self.trie[node]:
                node = self.fail[node]
            
            if char in self.trie[node]: node = self.trie[node][char]
            for word in self.output[node]:
                res.append((i-len(word)+1, word))
        return res

 

 

탐색 대상인 문자열의 길이를 $N$, 패턴 문자열 길이의 총합을 $M$이라고 하자. 트라이를 만들고 실패 함수를 구성하는 데 $O(M)$이 소요되고, 서칭을 수행하는 데 $O(N)$이 걸린다. $T$ 내에 일치하는 패턴의 총 갯수를 $K$라 하면 output 함수에 저장해 놓은 매칭 결과를 반환하는 데에는 $O(K)$가 소요될 것이다. 따라서 아호-코라식의 시간복잡도는 $O(N+M+K)$라 할 수 있다.