TRIE 자료구조

트라이(Trie)는 컴퓨터 과학에서 탐색 트리의 일종이다.

---

Trie란?

Trie는 문자열을 저장하고 효율적으로 탐색을 수행하기 위한 탐색 트리의 일종입니다. 검색엔진, 자연어 처리와 같은 빠른 문자열 탐색이 필요할 때 주로 쓰이는 자료구조입니다.

https://koenig-media.raywenderlich.com/uploads/2016/10/SwiftAlgClub_TrieData-trie-1.png

트라이는 문자열을 저장할 때 위 그래프처럼 문자 단위로 쪼개어 저장합니다. 위에 보이는 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

 

혹시 문자열의 길이가 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

위키백과: 트라이