아호-코라식(Aho-Corasick) 알고리즘은 주어진 키워드 집합 전체에 대한 모든 출현 위치를 텍스트에서 한 번의 탐색으로 찾아내는 데 유용한 알고리즘입니다. 일종의 사전 매칭(Dictionary-matching) 알고리즘으로, 모든 키워드를 트라이(Trie) 트리 구조로 구성한 뒤 이를 오토마타(상태 기계)로 변환하여 선형 시간 내에 검색을 수행할 수 있도록 설계되었습니다.
알고리즘의 세 가지 단계
아호-코라식 알고리즘은 Go-to(전이), Failure(실패), Output(출력)이라는 세 단계로 구성됩니다.
- Go-to 단계: 모든 키워드를 이용해 트라이 트리를 생성합니다.
- Failure 단계: 매칭에 실패했을 때 돌아갈 수 있도록, 어떤 키워드의 적절한 접미사(proper suffix)에 해당하는 후방 전이(backward transition)를 찾습니다.
- Output 단계: 오토마타의 각 상태 's'에 대해, 그 상태에서 종료되는 모든 단어를 찾아냅니다.
이 알고리즘의 시간 복잡도는 O(N + L + Z)입니다. 여기서 N은 텍스트의 길이, L은 키워드들의 총 길이, Z는 매칭된 횟수를 의미합니다.
입력과 출력
입력:
패턴 집합: {their, there, answer, any, bye}
검색 대상 문자열: "isthereanyanswerokgoodbye"
출력:
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22
알고리즘 (의사코드)
buildTree(patternList, size)
입력 − 모든 패턴의 목록과 목록의 크기
출력 − 패턴 검색에 사용할 전이 맵(transition map) 생성
Begin
set all elements of output array to 0
set all elements of fail array to -1
set all elements of goto matrix to -1
state := 1 // 처음에는 상태가 하나뿐이다.
for all patterns 'i' in the patternList, do
word := patternList[i]
present := 0
for all character 'ch' of word, do
if goto[present, ch] = -1 then
goto[present, ch] := state
state := state + 1
present := goto[present, ch]
done
output[present] := output[present] OR (shift left 1 for i times)
done
// 루트와 직접 연결되지 않은 문자는 루트로 되돌린다.
for all types of characters ch, do
if goto[0, ch] = -1 then
goto[0, ch] := 0
for all types of characters ch, do
if goto[0, ch] ≠ 0 then
fail[goto[0, ch]] := 0
insert goto[0, ch] into a Queue q.
done
while q is not empty, do
newState := first element of q
delete from q.
for all possible characters ch, do
if goto[newState, ch] ≠ -1 then
failure := fail[newState]
while goto[failure, ch] = -1, do
failure := fail[failure]
done
failure := goto[failure, ch]
fail[goto[newState, ch]] := failure
output[goto[newState, ch]] := output[goto[newState, ch]] OR output[failure]
insert goto[newState, ch] into q.
done
done
return state
End
getNextState(presentState, nextChar)
입력 − 현재 상태와 다음 문자
출력 − 다음 상태
Begin
answer := presentState
ch := nextChar
while goto[answer, ch] = -1, do
answer := fail[answer]
done
return goto[answer, ch]
End
patternSearch(patternList, size, text)
입력 − 패턴 목록, 목록의 크기, 검색 대상 텍스트
출력 − 패턴이 발견된 텍스트 내 위치(인덱스)
Begin
call buildTree(patternList, size)
presentState := 0
for all indexes i of the text, do
presentState := getNextState(presentState, text[i])
if output[presentState] = 0 then
ignore next part and go for next iteration
for all patterns j in the patternList, do
if output[presentState] AND (shift left 1 for j times) ≠ 0 then
print location: i - length(pattern[j]) + 1
done
done
End
C++ 구현 예제
#include <iostream>
#include <queue>
#define MAXS 500 // 모든 패턴 길이의 합
#define MAXC 26 // 알파벳은 26글자
using namespace std;
int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];
int buildTree(string array[], int size) {
for (int i = 0; i < MAXS; i++)
output[i] = 0; // output 배열을 모두 0으로 초기화
for (int i = 0; i < MAXS; i++)
fail[i] = -1; // fail 배열을 모두 -1로 초기화
for (int i = 0; i < MAXS; i++)
for (int j = 0; j < MAXC; j++)
gotoMat[i][j] = -1; // goto 행렬을 모두 -1로 초기화
int state = 1; // 초기 상태는 하나뿐
// 배열의 모든 패턴에 대해 트라이(trie) 구조 생성
for (int i = 0; i < size; i++) {
string word = array[i];
int presentState = 0;
for (int j = 0; j < word.size(); ++j) { // 패턴의 각 문자를 추가
int ch = word[j] - 'a';
if (gotoMat[presentState][ch] == -1) // 문자가 없으면 새 노드 생성
gotoMat[presentState][ch] = state++; // 상태 번호 증가
presentState = gotoMat[presentState][ch];
}
output[presentState] |= (1 << i); // 현재 단어를 출력 정보에 추가
}
// 루트와 직접 연결되지 않은 문자는 루트로 되돌림
for (int ch = 0; ch < MAXC; ++ch)
if (gotoMat[0][ch] == -1)
gotoMat[0][ch] = 0;
queue<int> q;
// 실패 시 이전 상태로 이동하도록 설정
for (int ch = 0; ch < MAXC; ++ch) {
if (gotoMat[0][ch] != 0) {
fail[gotoMat[0][ch]] = 0;
q.push(gotoMat[0][ch]);
}
}
while (q.size()) {
int state = q.front(); // 큐의 앞 노드 제거
q.pop();
for (int ch = 0; ch < MAXC; ++ch) {
if (gotoMat[state][ch] != -1) { // 전이 상태가 존재하면
int failure = fail[state];
while (gotoMat[failure][ch] == -1) // 적절한 접미사를 갖는 가장 깊은 노드 탐색
failure = fail[failure];
failure = gotoMat[failure][ch];
fail[gotoMat[state][ch]] = failure;
output[gotoMat[state][ch]] |= output[failure]; // 출력 값 병합
q.push(gotoMat[state][ch]); // 다음 레벨 노드를 큐에 추가
}
}
}
return state;
}
int getNextState(int presentState, char nextChar) {
int answer = presentState;
int ch = nextChar - 'a'; // 'a'의 아스키 값 차감
while (gotoMat[answer][ch] == -1) // 전이를 찾지 못하면 fail 함수 사용
answer = fail[answer];
return gotoMat[answer][ch];
}
void patternSearch(string arr[], int size, string text) {
buildTree(arr, size); // 트라이 구조 생성
int presentState = 0; // 현재 상태를 0으로 설정
for (int i = 0; i < text.size(); i++) { // 패턴의 모든 출현 위치 탐색
presentState = getNextState(presentState, text[i]);
if (output[presentState] == 0) // 매칭이 없으면 다음 문자로 진행
continue;
for (int j = 0; j < size; ++j) { // 매칭이 발견되면 단어와 위치 출력
if (output[presentState] & (1 << j)) {
cout << "Word " << arr[j] << " location: " << i - arr[j].size() + 1 << endl;
}
}
}
}
int main() {
string arr[] = {"their", "there", "answer", "any", "bye"};
string text = "isthereanyanswerokgoodbye";
int k = sizeof(arr)/sizeof(arr[0]);
patternSearch(arr, k, text);
return 0;
}
실행 결과
Word there location: 2 Word any location: 7 Word answer location: 10 Word bye location: 22
위 실행 결과에서 확인할 수 있듯이, 아호-코라식 알고리즘은 텍스트를 한 번만 순회하면서 여러 개의 패턴을 동시에 찾아낼 수 있습니다. 이러한 특성 덕분에 바이러스 백신의 시그니처 검사, 침입 탐지 시스템, DNA 서열 분석 등 대량의 패턴을 빠르게 검색해야 하는 분야에서 널리 활용되고 있습니다.