[자료구조] 트라이 (Trie)

단어 찾기

사전에서 "Algorithm" 이란 단어를 찾는 상황을 가정해보자.

사전에서 단어를 찾는 방법은 여러 가지가 있을 것이다.

① 단순 탐색 : 사전의 처음부터 Algorithm이 나올 때까지 모든 단어를 확인

가장 확실하고 구현하기 쉬운 방법이지만, 찾고자 하는 단어가 사전의 어느 위치에 있냐에 따라 걸리는 시간이 천차만별일 것이다. 

따라서 모든 경우에 대해 그다지 좋은 효율을 갖고 있다곤 할 수 없을 것이다.

 

② 이분 탐색 : 사전의 절반 지점의 단어를 확인

사전의 처음부터 끝까지 모든 단어들 중 딱 절반 지점의 단어를 확인한다. 이 절반 지점을 mid라 하자.

이 때 확인된 단어가 찾고자 하는 단어보다 사전 순으로 앞서면, 다음 탐색 범위는 mid부터 사전의 끝이 될 것이다. 또한 앞서지 않는다면 다음 탐색 범위는 사전의 처음부터 mid까지가 될 것이다.

이런 식으로 탐색하는 범위를 절반씩 줄여나간다면, 전체 단어의 개수 N에 대해 logN 만에 단어를 찾을 수 있을 것이다.

 

하지만 이 방법은 어디까지나 사전에 대해서만 적용될 수 있다. 이분 탐색을 위해선 단어들이 정렬되있어야 한다는 전제가 필요하기 때문이다.

사전이 아닌 무작위 단어들의 나열들 중 원하는 답을 찾고자 하는 상황에서는 단어들을 정렬하는 추가적인 시간이 소요된다.

 

③ 다른 좋은 방법?

우리가 일반적으로 사전에서 단어를 찾을 때에는 위의 두 방식을 사용하지 않는다. 우리는 단어를 다음과 같은 과정을 통해 찾는다.

사전에서 Algorithm 단어를 찾는 과정

이 과정을 프로그램 내에서 구현할 때, 우리는 트라이(Trie)라는 자료구조를 이용한다.

 

트라이 (Trie)

트라이는 문자열의 정보를 담은 트리 구조이다.

사전에서 "Algorithm"을 찾는 3번 방법을 다음과 같이 나타낼 수 있다.

트리 구조로 나타낸 단어 찾기 과정

트리의 Root에서 단어의 첫 번째 글자인 A에 해당하는 자식 노드를 탐색하고,

A 노드에서 단어의 두 번째 글자인 L에 해당하는 자식 노드를 탐색한다. 이러한 과정을 반복하다 보면 찾고자 하는 문자열과 동일한 문자열을 얻을 수 있을 것이다.

(만약 얻을 수 없다면, 그 문자열은 현재 트라이 내에 존재하지 않는 문자열이다.)

따라서, 트라이를 통해 문자열을 탐색하는 시간은 찾고자 하는 문자열의 길이에 의해 정해진다. 길이가 L인 문자열을 찾기 위해선 최대 L번의 탐색이 필요하기 때문이다. 즉, O(L)이다.

 

트라이의 구현

이 포스팅에서는 트라이를 객체지향 형태로 구현한다. 우선, 위에서 설명한 트라이를 구현하기 위해 객체를 구상해보자.

객체지향으로 표현된 트라이

위와 같이 Trie 객체 내에는 각 알파벳에 해당하는 자식 Trie 객체를 담을(또는 연결할) 배열을 속성으로 갖도록 한다.

즉 실제로는 이 Trie 객체끼리의 트리 구조가 곧 트라이 자료구조가 된다. 예시는 다음과 같다.

구현된 트라이 구조의 예시

위 그림을 통해 알 수 있듯, 트라이의 단점은 공간복잡도이다. 

실제로 한 트라이 객체 내에서 연결된 다른 자식 노드들이 없더라도, 크기가 26인 포인터 배열은 유지해야 하기 때문이다.

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
typedef pair<int, int> p;
 
class Trie {
private:
    Trie* childs[26];        //자식 Trie 객체를 연결해주는 포인터 배열
 
public:
    Trie() {
        //객체 생성자 : 자식 포인터 배열을 NULL로 초기화
        for (int i = 0; i < 26; i++) childs[i] = NULL;
    }
 
    //삽입 메소드
    void insert(string word, int idx) {
        //종료조건
        if (idx == word.size()) return;
 
        //word의 idx번째 문자에 해당하는 자식 Trie 객체가 현재 트라이 객체 내에 존재하는지 확인
        int pos = word[idx] - 'a';
        if (childs[pos] == NULL) {
            //연결된 객체가 없다면, 자식 객체를 새로 생성해준다.
            childs[pos] = new Trie();
        }
        //자식 객체에 대해 재귀실행
        childs[pos]->insert(word, idx + 1);
    }
 
    //탐색 메소드
    bool find(string word, int idx) {
        //word를 모두 탐색했다면, word는 트라이 구조 내에 존재하는 문자열이다.
        if (idx == word.size()) return true;
 
        //word의 idx번째 문자에 해당하는 자식 Trie 객체가 현재 트라이 객체 내에 존재하는지 확인
        int pos = word[idx] - 'a';
 
        //존재하지 않는다면, word는 현재 트라이 구조 내에 존재하지 않는 문자열이다.
        if (childs[pos] == NULL) return false;
 
        //존재한다면, word의 다음 문자에 대해 자식 트라이 객체에서 재귀실행한다.
        return childs[pos]->find(word, idx + 1);
    }
 
};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    Trie root = Trie();
    string input;
    
    input = "apple";
    root.insert(input, 0);
    if (root.find(input, 0)) cout << input << "은 존재하는 문자열입니다." << endl;
    else cout << input << "은 존재하지 않는 문자열입니다." << endl;
 
    input = "airplane";
    root.insert(input, 0);
    if (root.find(input, 0)) cout << input << "은 존재하는 문자열입니다." << endl;
    else cout << input << "은 존재하지 않는 문자열입니다." << endl;
 
    input = "air";
    if (root.find(input, 0)) cout << input << "은 존재하는 문자열입니다." << endl;
    else cout << input << "은 존재하지 않는 문자열입니다." << endl;
 
    input = "algorithm";
    if (root.find(input, 0)) cout << input << "은 존재하는 문자열입니다." << endl;
    else cout << input << "은 존재하지 않는 문자열입니다." << endl;
 
    return 0;
}

 

※ 트라이를 통한 공통 접두사 (Prefix)

위 코드를 실행하면 단어 "airplane"의 부분 문자열 "air"는 별도의 삽입과정 없이도 트라이 내에서 존재하는 것으로 판단한다.

따라서 트라이를 통해 두 문자열의 공통 접두사를 찾을 수 있다. 예컨데 문자열 "algorithm"과 "airplane"의 공통 접두사는 "a"이고, "apple"과 "application"의 공통 접두사는 "appl"이다.