트라이(Trie), 아호코라식

문자열 변수를 비교할땐 문자열의 길이가 있으므로 정수등과 다르게 오래걸린다. 

예로 어떤 한 문자열 a가 있고 문자열 b가 있다고 하자. a가 b문자열 안에 들어있는지 확인하는데는 

너무 오래걸린다. 이를 해결하기 위해 문자열 특화 자료 구조의 대표적인 예가 트라이다.

문제점은 필요로 하는 공간이 너무 크다는 점. 그래서 트라이로 접미사 트리를 만들수 있지만

사용하기가 어렵다고 한다.(접미사가 필요하면 앞에 글중 하나인 접미사 배열 부분을 주로 쓴다.) 

문자열 집함 s={"BE","BET","BUS","TEA","TEN"}; 이 있다고 할때 이걸 트라이에 저장하면 아래처럼 된다.

이처럼 접두사 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을때 두 노드는 부모 자식 관계로 연결된다.

노드의 깊이가 늘어날수록 문자열의 길이도 1씩 늘어난다. 아래는 이를 구현한 트라이 소스코드다.

처음 단어부터 시작하는게 있어야 true를 반환한다.

#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'A'; }

struct LinkedListNode {
	int elem;
	LinkedListNode* next;

	LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) {
	}
};

// 트라이의 한 노드를 나타내는 객체
struct TrieNode {
	TrieNode* children[ALPHABETS];
	// 이 노드가 종료 노드인가?
	bool terminal;

	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}

	~TrieNode() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}

	// 이 노드를 루트로 하는 트라이에 문자열 key 를 추가한다.
	void insert(const char* key) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = true;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieNode();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1);
		}
	}

	// 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다.
	// 없으면 NULL 을 반환한다.
	TrieNode* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) 
			return NULL;
		return children[next]->find(key+1);
	}
};


int main() 
{
	TrieNode* trie = new TrieNode();
	trie->insert("HELLOWORLD");
	while(1)
	{
		char str[100];
		cin>>str;
		if(trie->find(str))
			cout<<str<<" = true"<<endl;
		else
			cout<<str<<" = false"<<endl;
	}
	return 0;
}

위의 트라이가 시작점에서 시작하는 접두사만 찾을수 있는것에 반해 아호코라식 알고리즘은 kmp

처럼 시작점에서 시작하는것과 상관없이 찾을수 있다.

HELLOWORLD에서 -> HELLO를 찾는다. trie = true, 아호코라식 = true

HELLOWORLD에서 -> WORLD를 찾는다. trie = false. 아호코라식 = true

아호 코라식 알고리즘은 긴 문서에서 많은 문자열을 동시에 찾아야 하는 곳에서 유용하다고 한다.

종만북에서 소스를 가져왔다.

main에서 문자열 "HERSHISHE"를 넣고 "SHE"를 0번, HE를 1번, HERS를 2번, HIS를 3번 패턴으로

놓고 검색한 결과이다. 

패턴 1(HE)는 "HERSHISHE"의 인덱스 1에서 끝난다.

패턴 2(HERS)는 "HERSHISHE"의 인덱스 3에서 끝난다.

~~

#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<string>
#include<vector>
using namespace std;

// 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다
const int ALPHABETS = 26;
int toNumber(char ch) { return ch - 'A'; }

struct LinkedListNode {

	int elem;
	LinkedListNode* next;

	LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) {
	}

};

struct TrieDict {
	TrieDict* children[ALPHABETS];
	int terminal;

	// 이 노드에서 매칭이 실패했을 때 이 곳으로 가서 계속한다.
	// 이 노드에 대응되는 문자열의 접미사이면서 트라이에 포함된 최대 문자열.
	TrieDict* fail;
	// 이 노드가 방문되었을 때 등장하는 문자열들의 번호
	LinkedListNode* output;

	TrieDict() : terminal(-1), output(NULL) {
		memset(children, 0, sizeof(children));
	}

	~TrieDict() {
		for(int i = 0; i < ALPHABETS; i++)
			if(children[i])
				delete children[i];
	}

	// 이 노드를 루트로 하는 트라이에 번호가 id 인 문자열 key 를 추가한다
	void insert(const char* key, int id) {
		// 문자열이 끝나면 terminal 만 참으로 바꾸고 종료
		if(*key == 0)
			terminal = id;
		else {
			int next = toNumber(*key);
			// 해당 자식 노드가 없다면 생성한다
			if(children[next] == NULL)
				children[next] = new TrieDict();
			// 해당 자식 노드로 재귀호출
			children[next]->insert(key + 1, id);
		}
	}

	TrieDict* find(const char* key) {
		if(*key == 0) return this;
		int next = toNumber(*key);
		if(children[next] == NULL) return NULL;
		return children[next]->find(key+1);
	}
};

void calcFailureFunction(TrieDict* root) {
	queue<TrieDict*> q;
	// 루트의 fail 함수는 자기 자신
	root->fail = root;
	q.push(root);
	while(!q.empty()) {
		TrieDict* here = q.front();
		q.pop();
		for(int edge = 0; edge < ALPHABETS; ++edge) {
			if(!here->children[edge]) continue;

			TrieDict* child = here->children[edge];

			// 1레벨 노드의 실패 연결은 항상 루트
			if(here == root)
				child->fail = root;
			else {
				TrieDict* t = here->fail;
				while(t != root && t->children[edge] == NULL)
					t = t->fail;
				if(t->children[edge]) t = t->children[edge];
				child->fail = t;
			}
			if(child->terminal != -1)
				child->output = new LinkedListNode(child->terminal,
						child->fail->output);
			else
				child->output = child->fail->output;

			q.push(child);
		}
	}
}

template<class CALLBACK>
void ahoCorasick(const string& s, TrieDict* trie, CALLBACK callback) {
	TrieDict* state = trie;
	for(int i = 0; i < s.size(); i++) {
		int chr = toNumber(s[i]);
		while(state != trie && state->children[chr] == NULL)
			state = state->fail;
		if(state->children[chr]) state = state->children[chr];
		for(LinkedListNode* t = state->output; t; t = t->next)
			callback(i, t->elem);
	}
}


TrieDict* find(TrieDict* node, const char* key) {
	if(*key == 0) return node;
	int next = toNumber(*key);
	if(node->children[next] == NULL) return NULL;
	return find(node->children[next], key+1);
}

vector<pair<int,int> > accumulated;
void test(int a, int b) {
	printf("pattern %d at pos %d\n", b, a);
	accumulated.push_back(make_pair(a,b));
}

int main() 
{
	TrieDict* trie = new TrieDict();
	trie->insert("SHE", 0);
	trie->insert("HE", 1);
	trie->insert("HERS", 2);
	trie->insert("HIS", 3);

	calcFailureFunction(trie);

	//                  012345678
	ahoCorasick(string("HERSHISHE"), trie, test);
}