한양과기고 에듀테크 수업도구 대시보드

아호–코라식 (Aho–Corasick)

KMP·보이어–무어는 패턴 하나를 텍스트에서 찾는다. 그런데 금칙어 필터, 바이러스 시그니처, 침입 탐지처럼 수천 개의 패턴을 동시에 찾아야 한다면? 패턴마다 따로 KMP를 돌리면 O(패턴 수 × n)이다. 아호–코라식은 모든 패턴을 하나의 트라이(trie)로 합치고, KMP의 실패 함수를 트리로 확장한 실패 링크(failure link)를 붙여 텍스트를 딱 한 번 훑으면서 겹치는 패턴까지 전부 찾는다 — 총 O(패턴 길이 합 + n + 매칭 수). grep -F(fgrep)와 여러 백신 엔진이 이 구조를 쓴다.

1. 패턴들 → 트라이 → 실패 링크

패턴들을 트라이에 넣는다(검은 실선 = goto 간선, 글자로 라벨). 그다음 너비 우선(BFS)으로 각 노드의 실패 링크(빨간 점선)를 계산한다: 지금 노드가 나타내는 문자열의 가장 긴 진짜 접미사이면서 동시에 트라이 안의 어떤 접두사이기도 한 노드로 이어진다. 루트로 가는 실패 링크는 그림에서 생략했다.

패턴 목록 (쉼표로 구분)

패턴이 끝나는 노드 현재 노드 실패 링크

2. 텍스트를 한 번만 훑으며 모든 패턴 찾기

텍스트 (text)

패턴을 만든 뒤 ▶ 한 글자를 눌러 시작하세요.

읽은 글자 수 (아호–코라식)

비교 횟수 (패턴마다 단순 탐색)

찾은 매칭 수

지금 읽는 글자 패턴 1 매칭 패턴 2 패턴 3+

3. 핵심 아이디어 4가지

트라이 = 여러 KMP 합치기

패턴들이 공통 접두사를 공유하면 트라이에서 노드 하나로 합쳐진다. he와 hers는 h→e 경로를 같이 쓴다.

실패 링크 = KMP 실패 함수

글자가 안 맞으면 루트로 되돌아가지 않는다. 이미 읽은 접미사 중 다시 패턴 접두사가 되는 가장 긴 지점으로 점프한다. KMP의 π 배열과 같은 발상.

출력(dict) 링크

hers를 읽는 도중 접미사 his… 가 아니라 ...he가 숨어 있을 수 있다. 실패 링크를 타고 올라가며 만나는 모든 종료 노드도 매칭으로 보고한다.

한 번의 스캔

텍스트 포인터는 절대 뒤로 가지 않는다. 각 글자마다 goto 아니면 실패 링크를 따르고, 전체가 O(n + 매칭 수). 패턴이 몇 개든 스캔은 한 번뿐.

4. 파이썬 구현 (BFS로 실패 링크 만들기)

from collections import deque

class Aho:
    def __init__(self):
        self.go   = [{}]          # go[node][ch] -> 자식 노드
        self.fail = [0]           # 실패 링크
        self.out  = [[]]          # 이 노드에서 끝나는 패턴들

    def add(self, word):
        cur = 0
        for ch in word:
            if ch not in self.go[cur]:
                self.go.append({}); self.fail.append(0); self.out.append([])
                self.go[cur][ch] = len(self.go) - 1
            cur = self.go[cur][ch]
        self.out[cur].append(word)

    def build(self):
        q = deque()
        for ch, nxt in self.go[0].items():
            self.fail[nxt] = 0; q.append(nxt)
        while q:
            u = q.popleft()
            for ch, v in self.go[u].items():
                f = self.fail[u]
                while f and ch not in self.go[f]:
                    f = self.fail[f]                 # 접미사를 따라 점프
                self.fail[v] = self.go[f].get(ch, 0) if self.go[f].get(ch) != v else 0
                self.out[v] += self.out[self.fail[v]] # 출력 링크 병합
                q.append(v)

    def search(self, text):
        cur = 0
        for i, ch in enumerate(text):
            while cur and ch not in self.go[cur]:
                cur = self.fail[cur]                 # 안 맞으면 실패 링크로
            cur = self.go[cur].get(ch, 0)
            for w in self.out[cur]:
                yield (i - len(w) + 1, w)      # (시작 위치, 패턴)

핵심 두 줄: while cur and ch not in go[cur]: cur = fail[cur] (안 맞으면 접미사로 점프), cur = go[cur].get(ch, 0) (맞으면 한 칸 전진). 텍스트 인덱스 i는 되돌아가지 않는다.