금칙어, 토큰, 명령어처럼 사전에 있는 여러 패턴을 긴 텍스트에서 찾을 때 패턴마다 문자열 검색을 반복하면 텍스트를 여러 번 읽게 됩니다. Aho-Corasick은 모든 패턴을 trie에 넣고, trie 경로가 끊길 때도 지금까지 읽은 텍스트의 유효한 suffix를 상태로 보존합니다. 이때 trie 간선은 “더 긴 패턴의 접두를 계속 읽는 전이”이고, failure 또는 suffix link는 “현재 문자열의 가장 긴 proper suffix이면서 trie 상태인 후보”입니다. terminal 상태와 output/exit link를 함께 사용하면 한 텍스트 위치에서 끝나는 짧은 패턴까지 누락하지 않습니다.
이 문서는 정적 사전을 먼저 구성하고 텍스트를 순회하는 고전적인 자동자를 다룹니다. 운영 중 패턴을 바꾸는 동적 사전은 링크가 전체 trie의 suffix 관계에 의존하므로 별도의 세대 교체나 재구축 정책이 필요합니다.
사전 trie와 terminal 상태
패턴 집합을 he, she, his, hers라고 하겠습니다. trie의 루트에서 문자를 따라가면 각 노드는 사전에 있는 패턴의 접두를 나타냅니다. he 노드는 terminal이고 she 노드도 terminal입니다. 어떤 terminal에 자식이 있어도 그 노드가 완성 패턴이라는 사실은 사라지지 않습니다.
참조 구현은 고정된 소문자 26개에 대해 노드마다 next[26] 배열을 두고, 패턴을 삽입한 뒤 마지막 노드에 output을 표시합니다. 패턴 총 길이를 m, 알파벳 크기를 k라 할 때 이 표현은 노드 수와 k에 비례한 메모리를 사용합니다. 큰 희소 알파벳에서는 실제 간선만 map으로 보관할 수 있지만 lookup·할당 비용이 달라집니다.
실패 링크의 suffix 불변식
trie 상태가 문자열 p를 나타낸다고 할 때 failure link는 p의 가장 긴 proper suffix 중 trie에 존재하는 상태를 가리킵니다. 부모를 가리키는 링크가 아닙니다. 예를 들어 she 상태의 suffix 후보에는 he, e, 빈 문자열이 있고, he가 사전에 있으면 failure는 he 상태를 가리킵니다.
텍스트의 다음 문자가 현재 상태에서 간선으로 이어지지 않으면 root로 무조건 초기화하지 않습니다. failure를 따라 더 짧은 suffix 상태로 이동한 뒤 그 상태에서 같은 문자를 시도합니다. 이것이 이미 읽은 텍스트의 끝부분을 다음 패턴의 접두로 재사용하는 규칙입니다.
그림을 글로 읽기
- 상태 she: 현재까지의 유효 접두
- failure → he: 가장 긴 suffix 상태
- he + r → her: 같은 입력 r 재시도
- 상태 she → failure → he: 직접 간선 없음
- failure → he → he + r → her: r 전이 성공
루트의 failure는 자기 자신으로 두거나, 루트에서 없는 간선을 루트로 닫힌 전이로 둡니다. 루트의 자식 failure는 root입니다. 더 깊은 노드 v가 부모 p에서 문자 c로 왔다면 link[v]는 go(link[p], c)로 계산할 수 있습니다. 부모보다 짧은 상태의 link와 전이가 먼저 준비되어야 하므로 BFS로 깊이 순서대로 만들거나 memoization을 사용합니다.
상태 전이 추적
he와 she를 사전에 넣고 텍스트 she를 읽어 보겠습니다. s를 읽으면 루트에서 s 상태로 갑니다. 다음 h는 sh로, 다음 e는 she terminal로 갑니다. 이 예는 긴 패턴이 끝나는 정상 전이만 보여 줍니다. 핵심은 현재 상태가 항상 “이미 읽은 텍스트의 suffix 중 trie에서 표현할 수 있는 가장 긴 것”이라는 불변식입니다.
더 직접적으로 failure를 확인하려면 현재 상태가 ab이고 다음 문자가 c인데 ab에서 c 간선이 없으며 bc가 사전에 있다고 하겠습니다. 상태 ab의 suffix b로 failure한 뒤 b에서 c 간선을 따라 bc로 갑니다. root로 초기화하면 bc를 놓칩니다. 링크는 과거 입력을 되돌리는 것이 아니라, 같은 텍스트 접미의 다른 접두 해석을 선택하는 것입니다.
검색 루프는 다음 계약을 갖습니다.
state = root
for (position, c) in text:
state = go(state, c) # 필요하면 failure를 따라 계산
report terminal(state)
report terminal states on output-link chain(state)
고정된 전체 전이 go[state][c]를 미리 채우면 텍스트 문자마다 전이가 O(1)입니다. lazy memoization으로 go와 link를 계산하는 구현은 같은 상태·문자 쌍을 다시 계산하지 않도록 해야 합니다.
output과 exit link
현재 상태가 terminal이면 그 상태의 패턴이 현재 텍스트 위치에서 끝납니다. 그러나 현재 상태의 failure 경로에 terminal이 더 있을 수 있습니다. she에서 she가 끝날 때 suffix he도 같은 끝 위치에서 끝납니다. 따라서 현재 노드만 검사하면 짧은 패턴을 누락합니다.
가장 단순한 방법은 매 위치에서 현재 상태에서 root까지 failure link를 따라가며 모든 terminal을 확인하는 것입니다. 하지만 텍스트의 각 위치에서 긴 link 사슬을 반복하면 결과 수가 적어도 불필요한 순회가 커질 수 있습니다. 그래서 현재 상태의 failure 경로에서 가장 가까운 terminal을 가리키는 output link, 흔히 exit link를 저장합니다. 보고할 때 현재 terminal을 먼저 처리하고 exit link를 따라 다음 terminal로 이동합니다.
he와 she를 텍스트 she에서 처리하면 위치 2에서 she를 보고하고, output chain을 한 번 따라 he도 보고합니다. 둘의 종료 위치는 모두 2이고 시작 위치는 각각 2-3+1=0, 2-2+1=1입니다. 패턴 ID가 같은 문자열을 여러 번 등록할 수 있다면 terminal에 ID 하나만 둘지, 중복 ID 목록을 모두 보고할지 정책을 정해야 합니다.
구축 비용과 전이 표현
패턴을 trie에 삽입하는 비용은 총 패턴 길이에 비례합니다. 참조 자료는 고정 alphabet 배열 표현에서 자동자 구축을 O(mk)로 설명하고, map 전이 또는 다른 표현은 메모리와 lookup 비용의 균형이 달라진다고 설명합니다. BFS 기반으로 각 노드와 각 alphabet 전이를 모두 채우면 노드 수 n과 k에 대한 비용을 생각해야 합니다. “항상 O(패턴 총 길이)”라고만 말하면 alphabet 표현과 완성 전이 수를 숨기게 됩니다.
작은 고정 alphabet에서 배열 전이는 next[c]와 go[c]를 직접 인덱싱해 빠르고 예측 가능한 전이를 제공합니다. 예를 들어 노드가 10,000개이고 alphabet이 26이면 전이 슬롯만 260,000개입니다. 루트 포함 노드가 10,000개인 trie의 실제 간선은 9,999개이므로 나머지 슬롯은 저장 방식에 따라 비어 있는 비용이 됩니다. Unicode 문자열처럼 가능한 기호가 크고 실제 간선이 희소하면 map이나 정렬 간선 배열이 실제 간선 수에 가까운 공간을 사용할 수 있지만, hash·비교·캐시 locality를 측정해야 합니다.
고정 alphabet의 문자는 단순한 ch-'a' 같은 매핑을 전제로 합니다. UTF-8 바이트를 26개 알파벳처럼 취급하면 비ASCII 입력을 잃거나 잘못된 인덱스가 생길 수 있습니다. 입력을 code point로 정규화할지 byte로 검색할지, 대소문자와 정규화가 사전과 텍스트에 동일하게 적용되는지 먼저 고정합니다.
출력량과 검색 비용
사전 구축 후 텍스트 길이를 T, 실제로 보고할 출현 수를 Z라고 하면 exit link로 각 출현을 한 번씩 보고하는 검색은 O(T+Z) 형태로 설명할 수 있습니다. 이때 Z가 결과 저장·직렬화 비용을 포함한다는 점이 중요합니다. 패턴 a, aa, aaa, …가 텍스트의 긴 aaaa... 구간에 있으면 한 위치에서 많은 결과가 나옵니다. 자동자가 빠르다고 결과를 무료로 만들 수는 없습니다.
출현 위치가 아니라 각 텍스트 위치의 매치 개수만 필요하면 terminal 경로의 개수를 미리 누적해 출력 목록을 만들지 않고 세는 선택이 가능합니다. 반대로 처음 매치 하나만 필요하면 즉시 중단해 결과 비용을 줄일 수 있습니다. 모든 패턴 ID를 반환하는 API와 금칙어가 하나라도 있는지만 보는 API는 같은 자동자를 써도 출력 계약과 메모리 사용이 다릅니다.
운영 중 사전 변경
정적 Aho-Corasick의 failure link는 전체 trie의 suffix 관계에 의존합니다. 운영 중 새 패턴을 trie의 한 지점에 삽입하면서 기존 링크가 계속 유효하다고 가정하면, 새 노드가 기존 여러 상태의 가장 긴 suffix 후보를 바꿀 수 있습니다. output/exit link도 새 terminal을 가리켜야 합니다. 따라서 일반적인 구현에서는 사전 전체를 새 세대로 재구축하거나, 동적 사전 전용 자료구조를 선택합니다.
읽는 작업과 구축 작업을 분리하면 한 세대의 자동자는 불변으로 유지할 수 있습니다. 예를 들어 기존 자동자로 텍스트를 처리하는 스레드가 있는 동안 새 trie와 링크를 완성하고, 구축이 끝난 뒤 새 포인터를 원자적으로 교체합니다. 교체 시점 전후 요청의 정책이 “요청 시작 시점 세대”인지 “처리 시점 최신 세대”인지 정해야 동일한 텍스트가 세대마다 다른 판정을 받는 문제를 설명할 수 있습니다. 이 세대 교체는 참조 알고리즘의 직접 보장이 아니라 운영 설계상의 선택입니다.
선택·검증·한계
패턴 하나면 KMP 또는 Z 함수가 패턴 상태와 메모리를 더 단순하게 유지합니다. 여러 패턴을 같은 텍스트에 적용하고 사전이 검색 중 고정이면 Aho-Corasick이 한 번의 텍스트 순회와 suffix 상태 재사용을 제공합니다. 사전이 매우 자주 바뀌면 구축 지연, 세대 메모리, 교체 일관성을 비용에 포함해 판단해야 합니다.
검증에는 패턴이 서로 접두·접미 관계인 경우, he와 she처럼 한 위치에서 여러 terminal이 끝나는 경우, failure를 root로 잘못 초기화했을 때 누락되는 경우, 중복 패턴 ID, 빈 패턴, 비ASCII 입력, 희소 alphabet 메모리를 포함합니다. 구축 후 자동자의 각 link가 실제로 가장 긴 proper suffix 상태인지 작은 사전에서 문자열로 검사하고, brute-force 다중 패턴 결과와 텍스트별 결과를 비교할 수 있습니다. 이 문서의 상태 추적과 숫자는 설명용 계산이며 실행 결과가 아닙니다.
참고한 cp-algorithms의 “Aho-Corasick algorithm” 문서는 2025-04-18 갱신본으로, trie terminal 상태, suffix link, 전이 계산, output/exit link를 통한 O(len+ans) 검색을 설명합니다. 같은 문서는 고정 alphabet 배열과 map 표현의 비용 차이를 함께 언급하지만, 특정 언어 런타임이나 운영 중 동적 삽입 계약은 보장하지 않습니다.
참고 경로
위 링크는 개념별 참고 경로이며, 본문에서 명시한 확인 범위와 미확인 구현 조건을 함께 적용합니다.