TRIE 자료구조
트라이(Trie)는 컴퓨터 과학에서 탐색 트리의 일종이다.
Trie란?
Trie는 문자열을 저장하고 효율적으로 탐색을 수행하기 위한 탐색 트리의 일종입니다. 검색엔진, 자연어 처리와 같은 빠른 문자열 탐색이 필요할 때 주로 쓰이는 자료구조입니다.
트라이는 문자열을 저장할 때 위 그래프처럼 문자 단위로 쪼개어 저장합니다. 위에 보이는 TRIE는 현재 CAT, CUT, CUTE, TO, B를 저장하고 있는데요, CUT과 CUTE의 경우를 보면 두 문자열이 접두사를 공유하고 있음을 알 수 있습니다. 따라서 TRIE는 접두사와 연관된 단어를 띄워주는 연관 검색어 기능에 활용할 수도 있습니다.
TRIE의 시간 복잡도
만약 가장 긴 문자열의 길이가 m이라고 한다면 삽입에는 총 O(m)의 시간이 소요됩니다. 그리고 모든 문자열의 개수가 n 개라면 모든 문자열 삽입의 시간 복잡도는 O(mn)이라고 할 수 있습니다.
탐색 시간 복잡도도 동일합니다. TRIE에 저장된 가장 긴 문자열의 길이가 M이라고 했을 때 최악의 경우 탐색에도 O(M)의 시간이 소요됩니다.
TRIE의 약점
대표적으로 문자열을 저장할 때 공간 낭비가 심하다는 약점이 있습니다. 보통 문자열을 저장하기 위해서는 알파벳 개수인 26 * _type 크기의 배열을 가진 노드가 연속되는 형태로 TRIE가 구성됩니다. 그런데 만약 "aaaaa"를 저장하는 경우 각 노드에서 25 * _type 크기의 공간이 낭비될 수 있습니다.
또한 "aaaaaaaa..."와 같은 문자열을 저장할 때 트라이 그래프가 비효율적인 공간 깊이를 가질 수 있습니다.
TRIE 구현
소문자로 이루어진 문자열을 다루는 TRIE 자료구조를 구현해 보겠습니다.
struct TRIE {
TRIE* arr[ALPHABET];
bool end;
TRIE() {
memset(arr, 0, sizeof(arr));
end = false;
}
~TRIE() {
for(int i = 0; i < ALPHABET; i++)
if(arr[i])
delete arr[i];
}
void insert(const char* key) {
if(*key == '\0') {
end = true;
}
else {
int idx = *key - 'a';
if(arr[idx] == NULL)
arr[idx] = new TRIE();
arr[idx]->insert(key + 1);
}
}
TRIE* find(const char* key) {
if(*key == '\0') return this;
else {
int idx = *key - 'a';
if(arr[idx] == NULL) return NULL;
return arr[idx]->find(key + 1);
}
}
};가장 기본적인 구현 형태입니다. insert와 find의 경우 재귀 방식으로 수행됩니다. 코드 만으로는 와닿지 않는다면 시각화 사이트에서 직접 트라이를 이용해 보는 것을 추천합니다.
https://www.cs.usfca.edu/~galles/visualization/Trie.html
Trie Visualization
www.cs.usfca.edu
혹시 문자열의 길이가 10만 정도라면 재귀의 깊이가 부담스러워질 수 있습니다. 그럴 때는 아래처럼 단순 for문으로 재귀 호출에 소요되는 시간을 줄여 볼 수 있습니다.
void nonRecursiveInsert(string& key) {
auto* now = this;
for(int i = 0; i < key.size(); i++) {
int idx = key[i] - 'a';
if(now->arr[idx] == NULL)
now->arr[idx] = new TRIE();
now = now->arr[idx];
}
now->end = true;
}
TRIE* nonRecursiveFind(string& key) {
auto* now = this;
for(int i = 0; i < key.size(); i++) {
int idx = key[i] - 'a';
if(now->arr[idx] == NULL)
return NULL;
now = now->arr[idx];
}
return now;
}
TRIE 응용
응용-1
TRIE는 여러 문제에 응용되어서 나오는데요, 그 중에서 [프로그래머스 Level4] 2020년도 카카오 기출 4번 가사_검색 문제를 예시로 들어보겠습니다. 문제는 생각보다 간단한데 효율성 테스트가 굉장히 까다로운 문제입니다. 요구사항은 words가 주어지고 queries가 주어지는데 query에 일치하는 word가 몇 개인지 모두 조사하여 반환하는 것입니다.
words는 ["front", "frodo", "frost",...] 처럼 온전한 형태의 단어들이 포함된 배열입니다. 그리고 queries는 쿼리가 포함된 배열입니다. 쿼리는 "fro??"와 같은 형태를 가지고 있으며 물음표에는 모든 문자를 매칭 할 수 있습니다. 즉 이 쿼리에 일치하는 단어는 "front", "frodo", "frost"가 될 수 있습니다. 반면에 "frame"은 일치하지 않습니다.
그런데 한 가지 골치 아픈 것은 쿼리가 "???st"와 같은 형태도 지닌다는 점입니다. 이러한 경우 물음표가 앞에 오기 때문에 시작부터 많은 탐색 루트를 가지게 되는데요, 이를 최적화하는 방법은 reverse Trie를 이용하는 것입니다. 즉 기존에 "front"를 그대로 저장했다면 reverse Trie에는 "tnorf"를 저장하고 "??orf"라는 쿼리가 주어졌을 때 이를 뒤집어서 ("fro??") find를 수행하는 방법입니다.
응용-2
각 문자열의 길이가 매우 상이하다면 문자열의 길이에 따라서 TRIE를 따로 구성하는 방법도 있습니다. 예를 들어 "front"라는 단어는 길이가 5인 단어만 저장되는 TRIE에 저장하고 "memory"는 길이가 6인 단어만 저장되는 TRIE에 저장하는 방식입니다. 이 방식은 TRIE 자료구조에서 특정 길이의 단어를 조회할 때 공간 및 시간 복잡도를 최적화하는데 도움을 줄 수 있습니다.
Reference
위키백과: 트라이