트라이, 아호 코라식

트라이

문자열 집합을 트리 형태로 저장하는 자료구조다.

각 노드에 26개의 알파벳 노드를 배열로 저장한다.

 

int toNumber(char ch) { return ch - ‘A’; }

struct TrieNode {
    TrieNode* children[26];
    bool terminal;
    TrieNode() : terminal(false) {
    	memset(children, 0, sizeof(children));
    }
    
    ~TrieNode() { //  destructor 소멸자
    	for(int i=0; i<26; i++) {
        	if(children[i]) delete children[i];
        }
    }
    
    void instert(const char* key) { // 문자열 key
        if(*key == 0) { // c언어에서 문자열이 끝나면 /0 널문자로 끝남
            terminal = true;
        }
        else {
            int next = toNumber(*key) {
            if(children[next] == NULL) {
                children[next] = new TrieNode();
            }
            children[next] -> insert(key + 1); // key+1은 내 다음 문자의 포인터 가르킴
		}
    }

    TrieNode* find(const char* key) { // key 문자열이 있는지 탐색
        if(*key == 0) return this; // 널문자 까지 오면 마지막 tire노드 반환
        int next = toNumber(*key);
        if(children[next] == NULL) return NULL;
        return children[next] -> find(key+1);
    }
};

 

 

아호 코라식

어떤 문자열 s에서 특정 패턴 리스트가 일치하는 부분 문자열이 있는지 찾는 알고리즘.

 

핵심은 이미 했던 탐색을 반복하지 않도록 하는 원리다.

 

예를 들어 

문자열 S = “CACACHEF”  패턴 [“CACHE”, “ACHY”] 가 있을 때

문자열 S의 첫문자부터 C -> CA -> CAC 까지 찾고 실패 했을 때

그 다음문자 A -> AC 와 같이 처음부터 찾지 않고 바로 “ACHY”의 접두사인 AC부터 바로 찾겠다는 것.

 

패턴 리스트의 트라이 자료구조가 필요하고

실패 함수는 주어진 문자열을 쭉 탐색하다가 실패했을 때 

현재 노드의 접미사이면서 일치하는 가장 긴 노드로 이동하여 다시 탐색하도록 한다.

 

즉 CAC 노드에서 CACA로 탐색이 실패했을 때 AC 노드로 이동하여 탐색하겠다.

 

반대로 S = “CZXYZXA” 이고 패턴이 앞선 리스트와 같다면

C에서 실패하고 Z,X,Y,Z,X 에서 계속 실패하여 루트로 이동하고 A부터 다시 시작하게 된다.

 

다른 예시를 한번 더 들어보자.

s = “cdhisxy” 이고  patterns = [ “he”, “she”, “his”, “hers” ] 라 하자. 트라이 자료구조는 머릿속에 상상해보자.

 

c와 d는 실패하여 시작 위치에 그대로 존재

his가 성공하여 his 패턴이 존재함 표시.

hisx가 없으니 his의 접미사 중 가장 긴 노드인 s로 이동.

sx 는 없으니 실패 시작위치로 이동. x 없으니 실패. y 없으니 실패.

 

극단적인 예를 한번만 더 들어보자

S = “WXYZABCDEF”  patterns = [“WXYZAB” , “ZABCD”] 이면

 

WXZYZAB에서 성공하고 WXYZABC가 실패 후 접미사이면서 패턴의 트라이 노드 중 가장 긴 노드인 ZAB로 이동

ZAB -> ZABC -> ZABCD 까지 성공하고 패턴 매칭 성공. ZABCDE 에서 실패하면서 접미사이면서 긴 노드가 없으니 시작 위치로 이동.

 

패턴이 다른 패턴 중간에 껴있는 경우는 ? 만약 axyb, xy가 있으면

트라이가 a->x->y->b가 되고 각 노드에 나로 끝나는 패턴 목록을 가지고 있으면 매칭도 체크가 된다.

 

—— 챗 지피티 답변 ——

패턴 리스트: ["axyb", "xy"]

 

트라이 구축 :

1. 먼저 "axyb"와 "xy" 두 패턴을 트라이에 삽입합니다.

2. "axyb"를 삽입할 때, 트라이에는 a -> x -> y -> b 경로가 추가됩니다.

3. "xy"를 삽입할 때, 이미 x -> y가 존재하므로, 그 경로를 그대로 사용하게 됩니다. 이때 "xy"의 끝(y 노드)에도 패턴이 끝났음을 표시합니다.

실패 함수 설정:

1. 실패 함수는 트라이에서 각 노드의 접미사를 찾으면서 설정됩니다.

2. a -> x에서는 실패 함수는 루트로 설정됩니다.

3. x -> y에서는 y 노드가 "xy" 패턴의 끝임을 표시하고, 이 노드의 실패 함수는 트라이의 루트로 설정됩니다. 이는 "xy"가 독립적인 패턴이므로, 다음 비교를 위해 루트로 돌아가도록 합니다.

4. y -> b에서는, "xy"를 찾은 이후 b로 이어지는 경우에 대해 실패 함수가 y로 돌아가도록 설정됩니다.

 

텍스트에서의 검색 예시

텍스트가 "zaxybwxy"라고 가정해보겠습니다. 아호코라식 알고리즘이 텍스트를 어떻게 검색하는지 보겠습니다.

1. "z"를 읽으면, 트라이에 "z"로 시작하는 경로가 없으므로 루트로 돌아갑니다.
2. "a"를 읽으면, 트라이의 "a"로 이동합니다.
3. "x"를 읽으면, "a -> x"로 이동합니다.
4. "y"를 읽으면, "x -> y"로 이동하고, 이 시점에서 "xy" 패턴이 매칭됩니다.
5. "b"를 읽으면, "y -> b"로 이동하여 "axyb" 패턴이 매칭됩니다.

—— ——

 

 

자 그럼 실패 함수는 어떻게 만드나?

 

실패 연결을 따라가는 데 만나는 문자열은 원래 노드의 문자열보다 항상 짧다. 

이를 이용하여 BFS로 짧은 문자열부터 실패 노드를 채워준다.

 

어떤 자식노드의 실패연결을 찾는 방법은 아래와 같다.

1. 부모노드의 실패연결에서 나에게 추가로 붙은 문자의 노드가 있는지 찾는다.
2. 찾는 데에 실패하면 그 실패연결(부모노드의 실패연결의 실패연결)에서 나에게 추가로 붙은 문자의 노드가 있는지 찾는다.
3. 그 실패연결이 루트가 될 때까지 반복한다.

 

왜 그런가?

어떤 A의 실패 연결이 B라고하자

A에 x라는 문자가 추가되어 Ax가 자식노드라 할 때 Bx라는 노드가 있으면 

Ax의 실패연결은 반드시 Bx가 된다.

 

그런데 Bx가 없다면 ?

부모노드의 실패연결의 실패연결로부터 찾아야 한다.

 

예를 들어 부모 “CACH”와 “CACHE”를 보면  (“CH”와 “CHE”가 있다고 가정)

“CACH”의 실패 연결인 “ACH”에 E 가 추가된 노드가 없다.

그러면 실패연결 “ACH”의 실패연결을 한번 더 찾는다. “CH”가 된다. 

“CH”에는 E가 추가된 “CHE” 노드가 자식으로 있다. 그러면 “CHE”가 “CACHE”의 실패연결이 된다. 

 

정리하면 접미사의 시작 위치를 한칸씩 문자열 끝으로 이동시켜서 다시 찾는 작업이라고 보면 된다.

(실패 연결은 접미사 중 가장 긴 노드를 찾는 것이기 때문)

 

void computeFailure(TrieNode* root) {
	queue<TrieNode*> q;
    
    // 루트의 실패 연결은 자기 자신
    root->fail = root;
    q.push(root);
    while(!q.empty()) {
    	TrieNode* here = q.front();
        q.pop();
        
        for(int i=0;i<26;i++) {
        	TrieNode* child = here->children[i];
            if(!child) contnue;
            if(here == root) {
            	child->fail = root; // 1레벨 노드의 실패 연결은 항상 루트
            }
            else {
            	TrieNode* t = here->fail; // 부모의 실패연결
                /*
                	실패 연결에 나에게 추가된 문자의 노드가 없으면 
                    실패연결의 실패연결에서 찾는다.
                    찾을 때까지 반복. 끝까지 없다면 루트
                */
                while(t != root && t->children[i] == NULL) {
                	t = t->fail;
                }
                if(t->children[i]) t = t->children[i]; // 나에게 추가된 문자를 가진 노드. 즉 child의 실패 연결
                child->fail = t;
            }
            
            // 이 위치에서 끝나는 패턴 문자열 목록
            child->output = child->fail->output;
            if(child->terminal != -1) {
            	child->output.push_back(child->terminal);
            }
            q.push(child);
        }
    }
 }

 

실제 탐색은 어떻게 하는가?

KMP와 거의 다를 것이 없다고 한다.

 

주어진 문자열 s를 하나하나 보면서 실패 연결까지 탐색하면서 일치하는 패턴이 있는지 찾는다.

찾는 과정에선 trie 에서 현재 상태(위치)를 state로 기억하며 활용한다.

 

// s내에서 패턴이 출현할 때마다 (마지막 글자, 패턴 번호)의 쌍을 저장한다.
vector<pair<int,int>> ahoCorasick(const string& s, TrieNode* root) {
    vector<int,int> ret;
    TrieNode* state = root;
    
    for(int i=0;i<s.size();i++) {
    	int chr = toNumber(s[i]);
        while(state != root && state->children[chr] == NULL) { // 내 추가된 다음 문자에 해당하는 노드를 찾을 때까지 반복.
        	state = state->fail; // 실패하면 실패 연결의 실패 연결로 이동.
        }
        if(state->children[chr]) state = state->children[chr]; // 찾으면 해당 노드로 이동.
        for(int j=0;j<state.output.size();j++){
        	ret.push_back({i, state->output[j])); // 현재 노드에 해당되는 패턴들 결과에 저장.
        }
    }
    return ret;
}

 

정리하자면 문자열과 찾고자 하는 패턴 리스트가 주어졌을 때 패턴과 매칭되는 부분 문자열들을 찾는 알고리즘이고,

패턴들로 트라이 자료구조를 만들어서 실패 연결로 이동하며 했던 탐색을 줄이며 패턴 매칭을 찾는다.

실패 연결은 현재 노드의 접미사이면서 트라이 노드로 존재하는 가장 긴 노드로 지정한다.

 

KMP는 trie를 사용하지 않고 패턴 하나를 검색하고

아호 코라식은 trie를 사용하고 패턴 여러개를 검색한다는 차이가 있다.