아호-코라식(Aho-Corasick) 알고리즘은 여러 패턴을 동시에 텍스트에서 탐색하는 알고리즘이다. KMP의 실패 함수 개념을 트라이(Trie) 구조로 확장해 O(n + m + k) 시간에 모든 매칭을 찾는다(n: 텍스트 길이, m: 패턴 합 길이, k: 매칭 수).
핵심 구조
- 1.트라이(Trie) 구성: 모든 패턴을 트라이에 삽입
- 2.실패 링크(Failure Link): 현재 상태에서 불일치 시 돌아갈 가장 긴 접미사 상태
- 3.출력 링크(Output Link): 접미사로 끝나는 다른 패턴 정보
패턴: ["he", "she", "his", "hers"]
트라이 + 실패 링크로 한 번의 순회에 모두 탐색 가능
구현
python
from collections import deque
class AhoCorasick:
def __init__(self):
self.goto = [{}]
self.fail = [0]
self.output = [[]]
def add_pattern(self, pattern, idx):
state = 0
for ch in pattern:
if ch not in self.goto[state]:
self.goto[state][ch] = len(self.goto)
self.goto.append({})
self.fail.append(0)
self.output.append([])
state = self.goto[state][ch]
self.output[state].append(idx)
def build(self):
q = deque()
for ch, s in self.goto[0].items():
self.fail[s] = 0
q.append(s)
while q:
r = q.popleft()
for ch, s in self.goto[r].items():
f = self.fail[r]
while f and ch not in self.goto[f]:
f = self.fail[f]
self.fail[s] = self.goto[f].get(ch, 0)
if self.fail[s] == s:
self.fail[s] = 0
self.output[s] += self.output[self.fail[s]]
q.append(s)
def search(self, text):
state = 0
results = []
for i, ch in enumerate(text):
while state and ch not in self.goto[state]:
state = self.fail[state]
state = self.goto[state].get(ch, 0)
for pat_idx in self.output[state]:
results.append((i, pat_idx))
return results
활용
- •바이러스/악성코드 시그니처 매칭
- •스팸 필터 키워드 탐색
- •사전 기반 형태소 분석
관련 개념
