문자열 수백 개를 한 번에 찾는 법 — Aho-Corasick 알고리듬 완전 정복
한 줄 요약
Aho-Corasick은 여러 개의 패턴 문자열을 트라이(trie)에 저장한 뒤, 여기에 두 종류의 링크를 덧붙여 입력을 단 한 번만 훑으면서 모든 패턴을 동시에 찾아내는 오토마톤입니다. 스팸 필터, 침입 탐지 시스템, 금칙어 검사처럼 "찾아야 할 단어 목록"이 긴 상황에서 특히 빛을 발하죠.
검색어가 100개라면 문자열 검색을 100번 돌려야 할까요? Aho-Corasick은 "아니오"라고 답합니다.
1단계: 트라이로 패턴 집합 저장하기
트라이는 문자열 집합을 담는 n진 트리입니다.
- 각 간선에는 문자가 하나씩 붙습니다
- 각 노드는 루트부터 그 노드까지 간선 문자를 이어 붙인 문자열을 의미합니다
- 공통 접두사를 가진 문자열은 같은 경로를 공유해 중복을 줄입니다
예를 들어 suit, suited, suitable을 저장하면 세 단어가 모두 suit 경로를 함께 씁니다. 그리고 완전한 패턴에 해당하는 노드는 "여기서 패턴 하나가 끝난다"는 표시를 따로 달아 둡니다.
여기까지는 평범한 트라이입니다. 진짜 마법은 다음 단계부터입니다.
2단계: 접미사 링크 — 실패해도 되돌아가지 않기
트라이만으로 매칭하면 문제가 생깁니다. 중간까지 잘 따라가다가 다음 문자에 해당하는 간선이 없으면? 지금까지 읽은 걸 버리고 입력 포인터를 되돌려야 할까요?
접미사 링크(suffix link) 가 이 문제를 해결합니다. 접미사 링크는 현재 노드가 나타내는 문자열의 접미사 중에서, 트라이에 있는 패턴의 접두사와 일치하는 가장 긴 문자열을 가리킵니다.
전이에 실패하면 이 링크를 따라 이동한 뒤, 실패했던 그 문자부터 다시 매칭을 이어갑니다.
예시로 보기
패턴이 item, suits이고 입력이 suitems라고 해봅시다.
suit까지 잘 읽었는데, 다음 문자e를 처리할 간선이 없습니다suit상태의 접미사 링크는it상태를 가리킵니다- 그 상태에서
e부터 계속 읽으면 →su[item]s처럼item을 찾아냅니다
입력을 되감지 않고도 패턴을 놓치지 않았죠. 참고로 루트에서조차 전이할 수 없는 문자는 어떤 패턴의 시작도 될 수 없으므로, 루트에 머문 채 입력 위치만 한 칸 옮깁니다.
3단계: BFS로 접미사 링크 계산하기
링크 계산은 너비 우선 탐색(BFS) 순서로 진행합니다. 짧은 문자열을 먼저 처리해 두면, 더 긴 문자열의 링크를 만들 때 그 결과를 그대로 재활용할 수 있기 때문입니다.
규칙은 이렇습니다.
- 루트와 루트의 직계 자식: 접미사 링크가 루트를 가리킵니다
- 나머지 노드:
- 부모의 접미사 링크가 가리키는 상태에서 시작합니다
- 현재 노드로 들어오는 문자와 같은 이름의 간선을 찾습니다
- 있으면 그 목적지가 접미사 링크
- 없으면 접미사 링크를 계속 타고 올라갑니다
- 루트까지 와도 없으면 루트를 사용합니다 (루트의 자기 링크를 무한히 따라가지 않도록 여기서 멈춥니다)
cadence, facade 예시
노드 번호는 BFS 방문 순서입니다.
- 큐가
[(c, 5), (d, 6)]일 때 → 노드 5의 부모 접미사 링크는 루트, 루트에c간선이 있으므로 그 목적지가 노드 5의 접미사 링크가 됩니다 - 다음 큐
[(d, 6), (a, 7)]→ 노드 6은 부모 접미사 링크가 루트인데 루트에d간선이 없으므로 루트를 씁니다. 즉cad를 읽은 노드 6에서 다음 문자가e가 아니면, 읽었던cad를 버리고 실패한 문자를 루트에서 다시 처리합니다 - 노드 7은 부모의 접미사 링크가 루트가 아닌 노드 2를 가리키고, 그곳의
a간선을 따라 노드 4를 접미사 링크로 삼습니다. 이건faca의 접미사ca가cadence의 유효한 접두사라는 정보를 보존하는 것이죠
흥미로운 점은 같은 패턴을 따라가다가도 자기 패턴의 접두사로 복귀할 수 있다는 것입니다. 완성된 예시에서 노드 12는 노드 2를 가리켜, cadence를 매칭하던 경로 안에서도 다시 cadence를 찾는 데 필요한 접두사 문맥을 남겨 둡니다.
4단계: 출력 링크 — 겹치는 패턴도 놓치지 않기
패턴을 트라이에 넣을 때 마지막 노드는 출력 노드로 표시하고, 보통 해당 패턴 자체를 저장해 둡니다. 그 상태에 도달하면 패턴을 출력하면 되죠.
그런데 문제가 하나 더 있습니다. 현재 패턴의 접미사도 등록된 패턴이라면? 그것도 같은 시점에 함께 출력해야 합니다.
출력 링크(output link) 는 이렇게 함께 출력해야 할 노드끼리 연결합니다. 접미사 링크처럼 더 짧은 문자열을 나타내는 노드를 가리키죠.
예를 들어 spin, pin, in을 저장한 트라이에서 spin 상태인 노드 9에 도달하면 → 노드 8의 pin, 노드 6의 in도 함께 출력합니다. 직접 매처를 돌릴 때는 출력 링크를 연결 리스트처럼 순회하며 패턴을 차례로 뽑아내면 됩니다.
출력 링크를 정하는 규칙
각 노드의 접미사 링크를 계산한 직후 바로 결정할 수 있습니다.
- 접미사 링크의 목적지가 출력 노드이면 → 그 노드를 출력 링크로 사용
- 그렇지 않으면 → 접미사 링크가 가리키는 노드의 출력 링크를 그대로 이어받음
짧은 문자열이 BFS에서 먼저 처리되므로, 필요한 정보는 이미 계산되어 있습니다.
5단계: 링크가 달린 트라이를 DFA로 굳히기
접미사 링크와 출력 링크 계산은 핵심 단계지만, 오토마톤 구성의 중간 단계입니다.
링크가 달린 트라이를 그대로 실행해도 동작은 합니다. 다만 다음 상태를 찾느라 접미사 링크를 여러 번 따라갈 수 있어, 전이 한 번의 작업량이 상수가 아닙니다.
그래서 링크 구성이 끝나면 전이와 출력을 정적으로 확정해 결정적 유한 오토마톤(DFA) 으로 만들 수 있습니다. 이를 위해 마지막 BFS를 한 번 더 돕니다.
루트의 전이부터 모든 입력 기호에 대해 계산합니다.
- 해당 기호의 간선이 있으면 → 그 목적지로 이동
- 간선이 없으면 → 루트로 자기 전이해 그 기호를 건너뜀
- 이 과정에서 루트의 간선으로 도달하는 상태들을 탐색 큐에 넣습니다
나머지 노드도 BFS 순서로 각 입력 기호의 다음 상태를 확정합니다.
- 해당 기호의 직접 간선이 있으면 → 그 목적지 사용
- 없으면 → 현재 노드의 접미사 링크가 가리키는 상태에서 같은 기호로 전이할 때의 목적지 사용
두 번째 규칙이 바로 "현재 경로에서 더 진행할 수 없을 때, 다른 패턴의 접두사이기도 한 가장 긴 접미사를 보존한다"는 동작을 전이 테이블 자체에 녹여 넣은 것입니다. 실행 시점에는 링크를 따라갈 필요가 없어집니다.
💡 구현 팁: 많은 전이가 빈 문자열
ε를 보존하는 루트로 향합니다. 그래서 미리 구성하는 Aho-Corasick 오토마톤에는 희소 행렬(sparse matrix) 저장 방식이 권장됩니다.
he, she, her 예시에서는 접미사 링크와 출력 링크가 있는 트라이의 전이를 확정하고, 출력을 집합으로 합쳐 DFA를 구성합니다.
정리하면
| 구성 요소 | 역할 | |---|---| | 트라이 | 패턴 집합을 공통 접두사 공유로 압축 저장 | | 접미사 링크 | 전이 실패 시 되감기 없이 가장 긴 유효 접미사로 복구 | | 출력 링크 | 접미사 관계의 겹치는 패턴을 함께 출력 | | DFA 변환 | 전이를 정적으로 확정해 전이당 상수 시간 보장 |
세 가지 링크 구조가 각각의 역할을 나눠 맡은 덕분에, 입력을 한 번만 읽고도 모든 패턴을 빠짐없이 찾아낼 수 있습니다.
더 읽어보기
- 문자열 집합으로 Aho-Corasick 트라이를 구성해 볼 수 있는 인터랙티브 데모가 제공됩니다
- 원 논문: Efficient String Matching: An Aid to Bibliographic Search — 전체 알고리듬을 설명한 오리지널 문헌입니다
출처: GeekNews - 개발/기술/스타트업 뉴스 서비스