[26] 트라이 (Trie)

트라이(Trie)

문자열 데이터를 집합에 넣었을 때, 원하는 원소를 찾기 위한 트리 자료구조이다.

Untitled

루트는 길이가 0인 문자열이고, 노드이 깊이가 깊어질 때마다 문자열의 길이는 1씩 늘어난다. 트라이는 아래 특징을 가진다.

루트에서 한 노드까지 내려오는 경로에서 만나는 글자들을 모으면, 해당 노드에 대응되는 접두사를 얻을 수 있다.
트라이의 각 노드는 알파벳 갯수만큼 포인터 배열을 가지고 있다.
- TrieNode* children[i]: i번째 알파벳을 현재 문자열의 뒤에 붙였을 때, 그 문자열이 있는 노드로 향하는 TrieNode 포인터 변수를 반환한다.
- terminal: 종료노드 (트라이의 노드 중에서, 문자열 집합에 속하는 문자열에 해당하는 노드들) 인지 확인하는 변수이다.

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

struct TrieNode {
	// 모든 알파벳에 대한 자식의 포인터를 저장한다.
	TrieNode* children[ALPHABETS];
	bool terminal; // 문자열 종료 지점임을 표시 
	TrieNode() : terminal(false) {
		memset(children, 0, sizeof(children));
	}
	~TrieNode() {
		for (int i = 0; i < ALPHABETS; i++)
			delete children[i];
	}
	void insert(const char* key) {
		// 문자열의 끝에 도달하면 종료 노드임을 표시
		if (*key == 0) terminal = true;
		else {
			int next = toNumber(*key);
			if (children[next] == NULL)
				children[next] = new TrieNode(); 
			// 자식 노드로 재귀호출
			children[next]->insert(key + 1);
		}
	}
	// key 문자열을 접두사로 가지는지 확인한다.
	TrieNode* find(const char* key) {
		 // 문자열의 끝에 도달하면, 현재 노드가 종료 노드이므로 그대로 반환한다.
		if (*key == 0) return this; 
		int next = toNumber(*key); 
		// 트라이에 key에 해당하는 문자열이 없으면 NULL을 반환한다.
		if (children[next] == NULL) return NULL;
		return children[next]->find(key + 1);
	}
};

insert시 문자열의 길이 만큼의 O(L) 시간복잡도를 가지고, find시 가장 긴 문자열의 길이 만큼만 탐색하기 때문에 O(L)의 시간 복잡도를 가진다.

접미사 트라이

추가로, 문자열 자체를 트라이에 넣는 것이 아니라 문자열 S의 모든 접미사를 트라이에 집어넣는다. 이는 문자열 S에 존재하는 모든 부분 문자열을 저장하기 위한 방법이고, 많은 메모리를 사용한다는 특징이 있다.

이 낭비를 절약하기 위해 **접미사 트리(suffix tree)**를 사용한다. 각 간선이 문자열 하나가 아닌 여러개에 대응되는 것이다. 접미사 트리의 노드는, 그 문자열의 첫 글자와 마지막 글자의 위치로 표현한다.

문제 : 안녕히, 그리고 물고기는 고마웠어요! (SOLONG)

트라이를 이용한 다중 문자열 검색

탐색공간을 줄이기 위한 방법으로, 트라이에 포함된 문자열이 같은 접두사를 공유하는 경우 같은 노드에 대응된다는 점을 활용할 수 있다.

하나의 짚더미 문자열에서 찾아야하는 바늘 문자열이 여러개일 경우, 아래와 같이 실패 함수를 통해 돌아갈 노드를 찾게 된다.

// 각 노드에 대한 실패 연결과 출력 문자열 목록을 계산
	void computeFailFunc(TrieNode* root) {
		queue<TrieNode* > q; 

		root->fail = root;
		q.push(root);
		while (!q.empty()) {
			TrieNode* here = q.front();
			q.pop();

			for (int edge = 0; edge < ALPHABETS; edge++) {
				TrieNode* child = here->children[edge];
				if (!child) continue; 
				if (here == root)
					child->fail = root;
				else {
					TrieNode* t = here->fail;
					while (t != root && t->children[edge] == NULL)
						t = t->fail; 
					if (t->children[edge]) t = t->children[edge];
					child->fail - t; 

					child->output = child->fail->output; 
					if (child->terminal != -1)
						child->output.push_back(child->terminal);
					q.push(child);
				}

			}
		}