이 문제에서는 입력 문자열과 배열 arr[]가 주어지며, 우리의 과제는 문자열 내에서 배열에 포함된 모든 단어의 등장 위치를 찾아내는 것입니다. 이를 위해 패턴 검색을 위한 아호-코라식(Aho-Corasick) 알고리즘을 활용합니다.
문자열과 패턴 검색은 프로그래밍에서 매우 중요한 주제입니다. 그리고 프로그래밍에서는 더 나은 알고리즘일수록 더 폭넓은 실용적 활용이 가능합니다. 아호-코라식 알고리즘은 문자열 검색을 손쉽게 만들어주는 매우 중요하고 강력한 알고리즘입니다. 일종의 사전 매칭(dictionary matching) 알고리즘으로, 여러 문자열을 동시에 매칭할 수 있다는 점이 특징입니다. 이 알고리즘은 트라이(Trie) 자료구조를 기반으로 구현됩니다.
트라이(Trie) 자료구조란?
트라이는 접두사 트리(prefix tree) 또는 디지털 탐색 트리(digital search tree)라고도 불리며, 각 간선이 특정 문자로 라벨링되고(각 노드에서 나가는 간선들은 서로 다른 문자를 가짐), 루트에서 노드까지의 경로가 하나의 접두사를 표현하는 트리 구조입니다.
예제를 통해 아호-코라식 알고리즘을 이해해 보겠습니다.
입력
string = "bheythisghisanexample"
arr[] = {"hey", "this", "is", "an", "example"}출력
Word hey starts from 2 Word this starts from 5 Word is starts from 11 Word an starts from 13 Word example starts from 15
이 알고리즘의 시간 복잡도는 O(N+L+Z)이며, 각 변수의 의미는 다음과 같습니다.
- N = 입력 문자열(텍스트)의 길이
- L = 키워드(배열에 포함된 단어들)의 총 길이
- Z = 매칭된 결과의 개수
즉, 텍스트 길이에 선형적으로 비례하는 시간 안에 여러 패턴을 한 번에 검색할 수 있어, 단순 반복 검색 방식보다 훨씬 효율적입니다.
구현 방법
아호-코라식 알고리즘은 다음의 간단한 단계들로 구성할 수 있습니다.
큐(queue)를 활용해 트라이를 구축합니다. 큐에서 각 문자를 노드로 꺼내면서 '트라이'를 구성할 수 있습니다.
실패 링크(failure link, 서픽스 링크)를 배열로 구축하여 다음 문자와 현재 문자 정보를 저장합니다.
출력 링크(output link)를 배열로 구축하여 매칭된 단어들을 저장합니다.
모든 문자를 확인하기 위한 순회 함수(FindNextState)를 작성합니다.
실패 링크(Failure Link, 서픽스 링크) − 문자열을 읽다가 더 이상 진행할 수 없는 지점에 도달했을 때, 가능한 한 많은 문맥(context)을 유지하기 위해 서픽스 링크를 따라 되돌아갑니다. 요약하자면, 현재 문자에 해당하는 간선이 트라이에 존재하지 않을 때 따라가야 할 모든 간선 정보를 저장하는 역할을 합니다.
출력 링크(Output Link) − 항상 현재 상태(state)에 존재하는 가장 긴 단어에 해당하는 노드를 가리킵니다. 출력 링크를 통해 모든 패턴들을 사슬처럼 연결함으로써, 겹치는 패턴도 놓치지 않고 찾아낼 수 있습니다.
예제 코드
#include<iostream>
#include <string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MaxStates = 6 * 50 + 10;
const int MaxChars = 26;
int OccurenceOfWords[MaxStates];
int FF[MaxStates];
int GotoFunction[MaxStates][MaxChars];
int BuildMatchingMachine(const vector<string> &words, char lowestChar = 'a', char highestChar = 'z'){
memset(OccurenceOfWords, 0, sizeof OccurenceOfWords);
memset(FF, -1, sizeof FF);
memset(GotoFunction, -1, sizeof GotoFunction);
int states = 1;
for (int i = 0; i < words.size(); ++i){
const string &keyword = words[i];
int currentState = 0;
for (int j = 0; j < keyword.size(); ++j){
int c = keyword[j] - lowestChar;
if (GotoFunction[currentState][c] == -1){
GotoFunction[currentState][c] = states++;
}
currentState = GotoFunction[currentState][c];
}
OccurenceOfWords[currentState] |= (1 << i);
}
for (int c = 0; c < MaxChars; ++c){
if (GotoFunction[0][c] == -1){
GotoFunction[0][c] = 0;
}
}
queue<int> q;
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[0][c] != -1 && GotoFunction[0][c] != 0){
FF[GotoFunction[0][c]] = 0;
q.push(GotoFunction[0][c]);
}
}
while (q.size()){
int state = q.front();
q.pop();
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[state][c] != -1){
int failure = FF[state];
while (GotoFunction[failure][c] == -1){
failure = FF[failure];
}
failure = GotoFunction[failure][c];
FF[GotoFunction[state][c]] = failure;
OccurenceOfWords[GotoFunction[state][c]] |= OccurenceOfWords[failure];
q.push(GotoFunction[state][c]);
}
}
}
return states;
}
int FindNextState(int currentState, char nextInput, char lowestChar = 'a'){
int answer = currentState;
int c = nextInput - lowestChar;
while (GotoFunction[answer][c] == -1){
answer = FF[answer];
}
return GotoFunction[answer][c];
}
vector<int> FindWordCount(string str, vector<string> keywords, char lowestChar = 'a', char highestChar = 'z') {
BuildMatchingMachine(keywords, lowestChar, highestChar);
int currentState = 0;
vector<int> retVal;
for (int i = 0; i < str.size(); ++i){
currentState = FindNextState(currentState, str[i], lowestChar);
if (OccurenceOfWords[currentState] == 0)
continue;
for (int j = 0; j < keywords.size(); ++j){
if (OccurenceOfWords[currentState] & (1 << j)){
retVal.insert(retVal.begin(), i - keywords[j].size() + 1);
}
}
}
return retVal;
}
int main(){
vector<string> keywords;
keywords.push_back("All");
keywords.push_back("she");
keywords.push_back("is");
string str = "Allisheall";
cout<<"The occurrences of all words in the string ' "<<str<<" ' are \n";
vector<int> states = FindWordCount(str, keywords);
for(int i=0; i < keywords.size(); i++){
cout<<"Word "<<keywords.at(i)<<' ';
cout<<"starts at "<<states.at(i)+1<<' ';
cout<<"And ends at "<<states.at(i)+keywords.at(i).size()+1<<endl;
}
}실행 결과
The occurrences of all words in the string ' Allisheall ' are Word All starts at 5 And ends at 8 Word she starts at 4 And ends at 7 Word is starts at 1 And ends at 3
위 코드는 먼저 키워드 목록으로 매칭 머신(matching machine)을 구축한 뒤, 입력 문자열을 한 번만 순회하면서 모든 단어의 시작 위치와 끝 위치를 찾아냅니다. 이처럼 아호-코라식 알고리즘은 여러 패턴을 동시에 검색해야 하는 상황, 예를 들어 민감어 필터링, 바이러스 시그니처 검사, DNA 서열 분석 등에 널리 활용됩니다.