알고리즘 문제 해결 전략 2 6장 트리 (9)

26. 트라이

26.1 도입

문자열 특화 자료 구조의 대표적인 것임. 트라이는 문자열의 집합을 표현하는 트리 자료 구조로, 집합 내에서 원하는 원소를 찾는 작업을 O(M) 시간만에 할 수 있음. 트라이는 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리임. 한 접두사의 맨 뒤에 글자를 덧붙여 다른 접두사를 얻을 수 있을 때 두 노드는 부모 자식 관계로 연결됨. 트라이의 루트는 항상 길이 0인 문자열에 대응되며, 노드의 깊이가 깊어질 때마다 대응되는 문자열의 길이는 1씩 늘어남. 트라이의 한 노드를 표현하는 객체는 자손 노드들을 가리키는 포인터 목록과, 이 노드가 종료 노드인지를 나타내는 불린 값 변수로 구성됨. 알파벳 대문자로만 구성된 문자열을 저장하는 트라이의 각 노드는 각 노드가 26개짜리 포인터 배열을 가지고 있으며, 이 배열의 0번 원소는 대응되는 문자열의 맨 뒤에 글자 A를 붙일 경우 얻을 수 있는 문자열 노드의 포인터를 나타냄. 트라이 구조는 이렇게 간단하기 때문에 트라이에 새 문자열을 추가하고 문자열이 존재하는지 확인하는 연산의 구현도 아주 직관적임. 

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) {
			if (children[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);
		}
	}
	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);
	}
};

find()가 종료 노드가 아닌 노드도 상관없이 반환한다는 것은 장점이기도 함. 이와 같은 탐색 속도는 어떤 자료 구조보다도 빠르기 때문에, 트라이는 빠른 속도가 필요한 검색 엔진이나 기타 문자열 처리 프로그램에서 자주 사용됨. 트라이에서 메모리를 절약하기 위한 여러 기법들이 개발되어 있지만, 이들은 프로그래밍 대회에서 사용하기에는 너무 복잡하고 작성하는데 시간이 오래 걸리는 경우가 대부분임. 때문에 대회에서 트라이를 쓸 수 있는 경우는 다루는 문자열의 개수가 그렇게 많지 않은 경우로 제한됨. 

 

접미사 트리

접미사 트라이에서의 검색을 이용하면 어떤 부분 문자열도 빠르게 찾아낼 수 있음. 너무 많은 메모리 사용. 접미사 트리를 사용하면 됨. 접미사 트라이의 많은 부분은 분기 없이 일자로 구성되어 있다는 데 착안함. 낭비를 절약하기 위해 접미사 트리는 각 간선이 문자열의 한 글자가 아니라 여러 글자에 대응되도록 함. 실질적으로 트리 상에서 긴 일자경로를 압축하는 효과가 있음. 접미사 트리를 만드는 단순한 알고리즘은 N^2의 시간이 걸리기 때문에 너무 느리고, 그보다 효율적인 알고리즘들은 너무 복잡함. 

 

26.2 문제: 안녕히, 그리고 물고기는 고마웠어요

여기에 일곱 번의 공백문자까지 입력하면 전체 스물여덟 번 키를 눌러야 함. 가능한 한 적은 타이핑 수로 모든 문장을 입력하고 싶음. 타블렛의 자동 완성 알고리즘이 사용하는 단어들과 각 단어들의 출현 빈도가 주어질 때, 주어지는 긴 문자열을 입력하기 위해 필요한 최소 타이핑 수를 계산하는 프로그램을 작성하시오. 

 

26.3 풀이: 안녕히, 그리고 물고기는 고마웠어요

전처리를 통한 빠른 검색

입력의 크기가 워낙 크기 때문에 언제 어떤 단어가 추천되는지를 가능한 한 빠르게 계산할 수 있는 방법이 필요함. 단어의 첫 몇 글자를 가지고 나머지를 찾는 연산은 문자열의 접두사로 사전을 검색하는 작업이기 떄문에, 트라이를 사용하기에 아주 적합함. 각 노드마다 추천디는 단어들을 문자열로 저장해 둔다거나 해서는 메모리 사용량이 허용 범위를 벗어나게 됨. 한 가지 좋은 방법은 트라이를 만들기 전에 사전에 주어진 문자열들을 출현빈도의 내림차순으로, 출현 빈도가 같은 경우 사전순으로 정렬해 두는 것임. 

struct TrieNode {
	int type(const char* key, int id) {
		if (*key == 0) return 0;
		if (first == id) return 1;
		int next = toNumber(*key);
		return 1 + children[next]->type(key + 1, id);
	}
};

int countKeys(TrieNode* trie, const char* word) {
	TrieNode* node = trie->find(word);
	if (node == NULL || node->terminal == -1) return strlen(word);
	return trie->type(word, node->terminal);
}

사전에 주어진 문자열들을 출현 빈도와 사전순으로 적절히 정렬해서 트라이를 생성하는 함수의 구현을 코드 26.4에서 볼 수 있음. 트라이를 모두 생성한 뒤 루트의 first 멤버를 -1로 바꿔 주는 것을 눈여겨봄. 문제에서는 아무 글자도 입력하지 않을 경우에는 자동 완성이 되지 않는 것으로 되어 있기 때문임.

TrieNode* readInput(int words) {
	vector<pair<int, string>> input;
	for (int i = 0; i < words; ++i) {
		char buf[11];
		int freq;
		scanf("%s %d", buf, &freq);
		input.push_back(make_pair(-freq, buf));
	}
	sort(input.begin(), input.end());
	TrieNode* trie = new TrieNode();
	for (int i = 0; i < input.size(); ++i)
		trie->insert(input[i].second.c_str(), i);
	trie->first = -1;
	return trie;
}