[Algorithm] 트라이 (TRIE)

단어 검색 알고리즘 

단어 검색 알고리즘은 대규모 문자열 데이터에서 특정 단어나 문장을 효율적으로 찾기 위해 필요합니다. 작은 데이터셋에서는 각 문자열을 순차적으로 검사하는 브루트 포스 방법으로 충분할 수 있으나, 수만 또는 수백만 개의 데이터가 있는 경우 이 방법은 비효율적입니다. 이런 상황에서 단어 검색 알고리즘은 필수적으로, 이는 문자열 데이터 처리의 효율성을 크게 향상시키는 데 중요한 역할을 합니다.

---

트라이(Trie) 알고리즘

트라이는 문자열 집합을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 트라이의 주요 특징은 다음과 같습니다.

• 효율적인 검색: 대규모 데이터셋에서도 문자열의 길이에 비례하여 빠른 검색이 가능합니다.
• 공간 최적화: 공통 접두사를 공유하는 문자열들이 경로를 공유함으로써 메모리 사용을 줄입니다.
• 접두사 탐색: 특정 접두사로 시작하는 모든 문자열을 빠르게 찾는 데 유용합니다.

트라이(Trie) 구조

위 이미지는 트라이 자료구조를 이용해 특정 문자열들을 저장한 예를 보여줍니다. 구체적으로는 "deed", "ed", "eed"라는 세 개의 문자열을 트라이에 저장하고 있는데, 이 구조는 접두사를 공유하는 문자열들을 효율적으로 처리할 수 있도록 설계되었습니다. 각 문자는 트리의 노드로 표현되고, 문자열의 마지막을 나타내는 노드는 사각형으로 도식화되어 있습니다. 이는 문자열의 종료 지점을 나타내며, 문자열의 전체적인 끝을 의미합니다.

이 트라이를 탐색함으로써, 우리는 "deed"라는 단어를 찾고자 할 때, 'd'에서 시작하여 연속된 'e'를 거쳐 다시 'd'로 이동하는 경로를 추적함으로써 원하는 단어를 찾을 수 있습니다. 각 경로를 따라가면서 끝을 나타내는 사각형에 도달하면, 해당 문자열이 트라이 안에 존재한다는 것을 알 수 있습니다.

또한, 트라이의 중요한 특징 중 하나는 루트 노드부터 시작하여 특정 노드까지 내려가는 동안 만나는 모든 문자들을 결합하면 해당 노드에 이르기까지의 접두사를 형성한다는 점입니다. 이 예에서 "deed"의 접두사인 "d", "de", "dee"는 각각 트라이의 경로를 따라 추적할 수 있습니다. 이처럼, 각 노드에는 접두사를 별도로 저장하지 않고도, 해당 노드에 이르는 경로에 따라 자연스럽게 접두사가 형성됩니다.

---

장단점

장점

문자열을 빠르게 찾을 수 있다.
문자열을 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색이 모두 O(M)만에 가능하다.

단점

필요한 메모리의 크기가 너무 크다.
문자열이 모두 알파벳 소문자로만 이루어진 경우라고 해도, 1 depth에 a~z까지 26개의 공간이 필요하게 된다.
이 단점을 해결하기 위해 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용하는데, 문제에 따라서 메모리 제한이 적은 경우에는 최적화가 까다롭다.

---

트라이 알고리즘의 구조

트라이는 각 노드가 문자를 나타내는 트리 형태로 이루어진 자료구조입니다. 루트 노드부터 시작하여 각 문자에 해당하는 노드를 따라가면서 전체 문자열을 구성합니다. 마지막 문자를 나타내는 노드에는 문자열의 종결을 표시하는 플래그가 있습니다. 트라이는 문자열의 삽입, 검색 등의 기능을 제공하며, 이를 통해 접두사가 같은 문자열을 효율적으로 저장하고 검색할 수 있습니다.이 코드는 트라이의 기본적인 구현을 보여줍니다. 여기서 TrieNode는 각 문자와 그 문자의 자식 노드들을, Trie는 전체 트리 구조를 관리합니다.

#include <iostream>
#include <unordered_map>

// 트라이의 노드를 나타내는 클래스
class TrieNode {
public:
    // 자식 노드를 담는 맵, 끝을 나타내는 플래그
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    // 생성자
    TrieNode() : isEndOfWord(false) {}

    // 소멸자
    ~TrieNode() {
        for (auto child : children) {
            delete child.second;
        }
    }
};

// 트라이 자료구조를 나타내는 클래스
class Trie {
private:
    TrieNode* root;

public:
    // 생성자
    Trie() {
        root = new TrieNode();
    }

    // 소멸자
    ~Trie() {
        delete root;
    }

    // 단어 삽입 함수
    void insert(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            // 현재 문자에 해당하는 자식 노드가 없으면 새로 생성
            if (node->children.find(ch) == node->children.end()) {
                node->children[ch] = new TrieNode();
            }
            // 다음 문자로 이동
            node = node->children[ch];
        }
        // 단어의 끝 표시
        node->isEndOfWord = true;
    }

    // 단어 검색 함수
    bool search(const std::string& word) {
        TrieNode* node = root;
        for (char ch : word) {
            // 현재 문자에 해당하는 자식 노드가 없으면 단어가 없음
            if (node->children.find(ch) == node->children.end()) {
                return false;
            }
            // 다음 문자로 이동
            node = node->children[ch];
        }
        // 끝까지 탐색했을 때 isEndOfWord가 true라면 단어가 존재함
        return node->isEndOfWord;
    }
};

---

예제

1.  전화번호 목록 (Baekjoon 5052) - Link

• 이 코드에서 Trie 클래스는 전화번호 목록을 저장하고 관리하기 위한 트라이 자료구조를 구현합니다.
• Insert 메소드는 새로운 전화번호를 트라이에 삽입하고, IsTherePrefix 메소드는 주어진 전화번호가 다른 번호의 접두어로 존재하는지 확인합니다. 이를 통해 전화번호 목록이 일관성을 가지는지 검사할 수 있습니다. 
• 만약 일관성이 없다면(어떤 번호가 다른 번호의 접두어가 된다면), "NO"를 출력합니다.

풀이 코드 (C++)

#include <bits/stdc++.h>

using namespace std;

// Trie 자료구조 클래스
class Trie {
private :
    bool isEnd = false;  // 단어의 끝을 나타내는 플래그
    Trie* child[10]; // 각 숫자에 대응하는 자식 Trie 포인터 배열
    
public :
    Trie() : child() { }
    
    // 전화번호를 트라이에 삽입하는 메소드
    void Insert(string phone_number) {
        Trie* now = this;
        for (int i = 0; i < phone_number.length(); ++i) {
            int index = phone_number[i] - '0';
            if (now->child[index] == nullptr) 
                now->child[index] = new Trie(); 
            now = now->child[index];
            if (i == phone_number.length() - 1) now->isEnd = true;
        }
    }
    
    // 특정 전화번호가 트라이에 접두어로 존재하는지 확인하는 메소드
    bool IsTherePrefix(string phone_number) {
        Trie* now = this;
        for (int i = 0; i < phone_number.length(); ++i) {
            int index = phone_number[i] - '0';
            if (now->child[index] != nullptr) {
                now = now->child[index];
                if (now->isEnd) return true;
            }
            else return false;
        }
        return false;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // 테스트 케이스 수 입력
    int t, n;
    cin >> t;
    
    // 테스트 케이스를 반복 처리
    while (t--) {
        // 전화번호 목록 수 입력
        cin >> n;
        vector<string> phone_number_list(n);
        for (int i = 0; i < n; ++i) {
            cin >> phone_number_list[i];
        }
        
        sort(phone_number_list.begin(), phone_number_list.end());
        
        // 트라이 자료구조 인스턴스화
        Trie* trie = new Trie();
        bool ok = true;
        
        // 각 전화번호에 대해 트라이에 삽입 및 접두어 여부 확인
        for(string& phone_number : phone_number_list) {
            if (trie->IsTherePrefix(phone_number)) {
                ok = false;
                break;
            }
            trie->Insert(phone_number);
        }
        
        // 결과 출력
        cout << (ok ? "YES" : "NO") << '\n';
        delete trie;
    }
    return 0;
}

2.  가사 검색 (카카오 블라인드 공채 2020) - Link

• Insert 함수는 트라이에 새로운 단어를 추가하며, Search 함수는 주어진 쿼리 문자열을 바탕으로 일치하는 단어의 수를 찾아 반환합니다. 
• 트라이 자료구조 상 중복되는 접두사는 같은 노드를 지나기 때문에, Search 함수는 '?' 문자를 만날 때까지 탐색을 계속하여, 해당 노드까지 도달하는 모든 단어의 수를 셉니다. 
• 접미사 검색의 경우에는 단어를 뒤집어서 접두사 검색과 동일한 방식으로 처리합니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

// 트라이의 노드를 나타내는 클래스
class Trie {
private:
    Trie* child[26];  // 자식 노드 배열, 알파벳 소문자에 대응
    int count;  // 해당 노드를 접두사로 가지는 단어의 개수

public:
    // 생성자
    Trie() : child{nullptr}, count(0) {}

    // 단어를 트라이에 삽입하는 함수
    void Insert(string str) {
        Trie* now = this; // 현재 노드를 루트로 시작
        for (char ch : str) { // 단어의 각 문자에 대해
            now->count++; // 경로상의 노드마다 count 증가
            int index = ch - 'a'; // 현재 문자의 알파벳 인덱스
            if (now->child[index] == nullptr) // 자식 노드가 없으면 생성
                now->child[index] = new Trie();
            now = now->child[index]; // 자식 노드로 이동
        }
        now->count++; // 단어의 마지막 문자에 대해서도 count 증가
        now->isEnd = true; // 단어의 끝을 표시
    }

    // 단어를 찾는 함수
    int Search(string str) {
        Trie* now = this; // 현재 노드를 루트로 시작
        for (char ch : str) { // 쿼리의 각 문자에 대해
            if (ch == '?')  // '?'를 만나면 검색 종료, 현재까지의 count 반환
                return now->count;
            int index = ch - 'a';
            if (now->child[index] == nullptr) // 경로를 따라갈 노드가 없으면 0 반환
                return 0;
            now = now->child[index]; // 다음 노드로 이동
        }
        return now->count; // 쿼리의 끝까지 탐색한 경우 count 반환
    }
};

// 각 길이별 트라이 배열 선언
Trie TrieRoot[10000];
Trie ReTrieRoot[10000];

// 가사 검색 솔루션 함수
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
    
    // 단어들을 트라이에 삽입
    for (string str : words) {
        TrieRoot[str.length() - 1].Insert(str); // 정방향 트라이에 삽입
        reverse(str.begin(), str.end()); // 단어를 뒤집어서
        ReTrieRoot[str.length() - 1].Insert(str); // 역방향 트라이에 삽입
    }
    
    // 쿼리를 처리하여 결과를 answer에 추가
    for (string query : queries) {
        if (query[0] != '?') // 접두사가 명시된 쿼리 처리
            answer.push_back(TrieRoot[query.length() - 1].Search(query));
        else { // 접미사가 '?'인 쿼리 처리
            reverse(query.begin(), query.end()); // 쿼리를 뒤집어서
            answer.push_back(ReTrieRoot[query.length() - 1].Search(query));
        }
    }
    
    return answer; // 결과 반환
}