아호코라식 다중 패턴 매칭(Aho-Corasick)

아호 코라식(Aho-chorasick)

  여러 문자열 패턴이 있고, 특정 문자열에 어떤 패턴이 어디에 존재하는지 확인하고 싶을 때 쓰는 알고리즘입니다.
  기술적으로는 prefix와 suffix를 가지고 노는 문자열 탐색 알고리즘이라고 말하고 싶네요. KMP도 마찬가지지만 이 알고리즘 역시 매칭 실패했을 때 지금까지 사용한 데이터를 그대로 활용해서 효율적으로 탐색하고 싶어합니다. 아시다시피 그 동작을 실패 함수(Failure function)라고 합니다.

 

[사전 지식]

* 트라이(trie) - prefix 문자열을 저장하는 자료구조. 만약 검색 대상 문자열이 패턴과 정확히 일치해야만 한다면 적절한 자료구조입니다.     * BFS - 아호코라식 자료구조를 동적으로 건설해나가는데, 여기서 실패함수 구조에 의해 BFS를 통해 완성하는 것이 적절합니다.

 

[Aho-chorasick 노드 데이터]

아호코라식은 트라이 자료구조를 사용합니다. 트라이를 구성할 때 몇 가지 기본적인 데이터를 가집니다.

struct _trie {
    _trie *fail;                   // 실패했을 때 찾아가는 노드 포인터(주소, 인덱스 등) 
    _trie *child[TRIE_CHILD_SIZE]; // 트라이 자식 노드
    vector<int> words;             // 현재 노드를 끝으로 하는 패턴의 집합
};

[실패 함수(다이나믹 프로그래밍)]

  실패 함수는 특정 위치에서 매칭 실패 했을 때, 가장 효율적인 위치를 뜻합니다. 여기서는 그 위치는 노드가 됩니다.
  [효율적?] 아호코라식은 패턴 A의 부분문자열 suffix가 패턴 B의 prefix임을 이용합니다. 트라이 특정 노드 X에서 실패 함수는 루트부터 X까지 사용된 문자를 나열하면 X에 해당하는 문자열 Xs가 나옵니다. Xs의 suffix 중 패턴들의 prefix와 매칭되는 것들 중 가장 긴 것을 가져옵니다. 이 때 이 가장 긴 prefix에 해당하는 노드가 실패 함수가 가리키는 노드가 됩니다.

※ 패턴의 prefix는 트라이 루트부터 탐색을 의미한다.

  간단하게 길이 1짜리를 생각해봅시다. 여기에 해당하는 노드들의 실패함수는 루트가 됩니다. 그 중 한 노드를 A라고 하면, A까지는 매칭이 됐으나, A 이후에 매칭이 없다면 어디로 돌아가야할까요? 한글자에선 suffix나 prefix 모두 같기 때문에 의미가 없습니다.

  길이 2를 생각해봅시다. 현재 노드 C까지 x, y 두 문자를 타고 왔다고 보는 겁니다. 여기서 루트의 y에 해당하는 자식 노드 D가 존재해야 실패 함수를 D로 지정할 수 있습니다. 만약에 존재하지 않는다면 노드 C의 실패 함수는 루트와 연결되어 다시 처음부터 탐색하도록 유도됩니다.

  일반화를 위해 길이 k를 생각해봅시다. 앞에서 말한 것처럼 우린 현재 노드 X까지 왔을 때, 가장 긴 prefix에 해당하는 노드를 가져오고 싶습니다. 가장 긴 prefix라고 함은 이미 앞에서 계산되지 않았을까요? 가령 X까지 abcdef 문자열이 구성될 때 X의 부모노드 Y까지의 문자열은 abcde임이 틀림없습니다. 만약 Y의 실패함수가 루트가 아닌 cde에 해당하는 노드 T를 가리킬 때, T의 자식 중 'f' 문자에 해당하는 노드가 있다면 그 노드가 곧 X의 실패함수임을 알 수 있습니다. 따라서 길이 k에 해당하는 노드의 실패함수는 바로 위 부모 노드의 실패함수를 활용합니다.

  이렇게 진행하면 굳이 루트부터 재탐색하지 않고도 바로 구할 수 있습니다. 저장된 데이터를 재활용하여 사용하기 때문에 다이나믹이라고 말할 수 있겠습니다.

 

[아호코라식 건설]

  현재 노드까지의 문자열 suffix와 루트부터의 prefix를 봐야하기 때문에 현재 노드의 depth가 prefix의 depth보다 짧을 이유가 없습니다. 따라서 depth를 같게끔 내려가는 구조인 BFS를 쓰면됩니다. 

  일반 트라이에서는 문자열 마지막에 해당하는 노드만 문자열 끝을 뜻합니다. 하지만 아호코라식에서는 문자열 중간에 있는 노드가 문자열 끝을 나타낼 수 있습니다. 이유는 (몇 번 말하는지 모르겠지만ㅠ) 노드까지의 해당하는 문자열의 suffix를 prefix로 재활용하는 구조를 생각해야합니다. 탐색 중 방문 노드가 X이고, X의 실패함수에 해당하는 노드 K가 패턴 그 자체라고 해봅시다. 즉, K까지의 문자열이 X까지의 문자열의 suffix인 경우를 말합니다. 따라서 X 노드를 방문할 때 패턴이 매칭했음을 나타내기 위해 실패함수 노드에서 패턴 정보를 가져옵니다.

void ahocorasick() {
	queue<_trie*> q;
	q.push(root);
	while (!q.empty()) {
		_trie* u = q.front(); q.pop();
		for (int i = 0; i < TRIE_CHILD_SIZE; i++) if (u->child[i]) {
			_trie* nxt = u->child[i];

			if (u == root) nxt->fail = u;
			else {
				_trie* k = u->fail;
				while (k != root && !k->child[i])
					k = k->fail;
				if (k->child[i])
					k = k->child[i];
				nxt->fail = k;
			}
			// 실패함수에 해당하는 노드로부터 패턴 정보를 가져온다.
			nxt->words.insert(nxt->words.end(), nxt->fail->words.begin(), nxt->fail->words.end());

			q.push(nxt);
		}
	}
}

 

[탐색]

  설명을 용이하게 하기 위해 아래처럼 용어 정리를 하겠습니다.

s: 탐색할 문자열   n: s의 길이   m: 패턴들의 길이 합   z: s에서 탐색된 패턴들의 수   s[i]: i번째 인덱스에 해당하는 문자   시간 복잡도: O(n + m + z)

[탐색 - prefix 매칭]
  현재 노드에서 s[i]에 해당하는 문자와 같은 자식 노드가 있다면 문자가 존재한다고 볼 수 있습니다.

[탐색 - 미스 매칭]
  현재 노드에서 s[i]에 해당하는 문자와 같은 자식 노드가 없다면 실패함수로 넘어가야합니다.
  실패함수 구조상 s[i]에 해당하는 자식을 찾을 때까지 여러 차례 depth를 낮추며 접근해야할 필요가 있습니다. 전부 없다면 종착지는 루트가 됩니다.

 

예시 1)

p = "xyxyxy" 패턴이 있을 때, 이를 trie에 넣는 걸 생각해봅시다.

각 인덱스에 대해 실패함수를 적자면 아래 표와 같습니다.

i	0	1	2	3	4	5
fail	(R)	(R)	A	B	?	?

부모 노드로부터 실패 함수를 가져오기 때문에 결과 표는 아래와 같습니다. (A나 B가 아님을 확인)

i	0	1	2	3	4	5
fail	(R)	(R)	A	B	C	D

  4 인덱스에 해당하는 노드 E의 실패함수는 노드 C와 연결됩니다. 이유는 더 범용성이 넓기 때문인데 곧바로 노드 A로 가버리면 노드 C 이후의 노드들을 이용해 탐색할 기회를 잃어버립니다. 반대로 C 이후의 노드들로 탐색했을 때 매칭이 되지 않더라도 실패함수를 이용해서 상위 노드로 올라갈 수 있습니다. 

예시 2)

s = "xyxyxyb"
패턴 = ["xyxyxy", "xyb"]

  위 구조에서 탐색할 때, 노드 F에 문자 'b'에 해당하는 자식 노드가 없기 때문에 실패함수가 동작하는데, D노드로 이동합니다. D 노드에도 'b'에 해당하는 자식 노드가 없기 때문에 B노드로 이동합니다. 여기엔 'b'에 해당하는 노드 G가 존재하니 G로 이동합니다. 여기서 한 번만 실패 함수를 타고 올라가는 게 아니라 여러 번 타고 올라가야 함을 알 수 있습니다.

[탐색 - 패턴 매칭]
  s에 포함된 패턴을 찾기 위해서는 트라이와 s를 동시에 순회하면서 패턴의 끝을 해당하는 데이터가 현재 노드에 존재하는지 확인하면 됩니다.

  상황에 따라 패턴의 존재함을 저장할 수도 있고, 단어 인덱스 리스트를 저장할 수도 있고, 길이만 저장할 수도 있습니다. 문제를 잘 읽고 최적화합시다.

_trie* cur = root;
for (i = 0; s[i]; i++) {
    int idx = getIndex(s[i]);
    while (cur != root && !cur->child[idx])
        cur = cur->fail;
    if (cur->child[idx])
        cur = cur->child[idx];
        
    if(!cur->words.empty())
    	;// do something
}