[Algorithm] 트라이

트라이 (Trie)

문자열을 다루는 작업은 정수나 실수를 다르는 것과는 다르다.

정수나 실수는 고정된 크기만큼의 메모리만 이용하지만, 문자열의 경우에는 그 크기가 정해져 있지 않다.

그러므로 최악의 경우 문자열 길이에 비례하는만큼 시간을 소모하게 된다.

그렇기 때문에, 정수나 실수와 같은 타입에 대해서는 훌륭하게 동작하는 이진트리나 해시테이블 같은 자료구조도,

문자열을 저장하는데에 있어서는 취약하다.

이진트리에 일반적인 정수 타입을 검색, 삽입, 삭제 하는데에는 O(logN)의 시간이 걸린다.

하지만 이진트리에 길이 M의 문자열을 N개 저장한다고 했을 때, 이 문자열 타입에 대한 연산은 O(MlogN)이 걸린다.

즉, 문자열이 길어지게 되면 이진트리의 장점도 무용지물이 된다는 의미이다. 해시테이블도 마찬가지이다.

이와 같은 문제를 해결하기 위해 탄생한 문자열 특화 자료구조가 바로 트라이(Trie)이다.

트라이는 문자열 집합을 표현하는 자료구조로, 집합 내에서 원하는 문자열을 찾는 작업을 O(M) 시간만에 할 수 있다.

 

다음 그림은 문자열 집합 S = { "GET", "GO", "GOD", "HA", "HAS", "HATE" } 를 저장하는 트라이이다.

그림에서 볼 수 있듯이 트라이는 문자열의 접두사들에 대응되는 노드들이 연결된 트리이다.

한 접두사 뒤에 문자를 하나 붙여서 다른 접두사를 얻을 수 있다면 두 노드는 부모자식관계로 연결된다.

그림에서 노란색 노드들은 종료 노드들로, 해당 위치에 대응되는 문자열이 실제로 집합에 존재한다는 의미이다.

실제로 "HA", "HATE" 등은 종료 노드지만, "H", "HAT"은 종료 노드가 아니다.

이러한 노드들은 집합에는 포함되어있지 않지만, 트라이의 기본 골격을 잡기 위해 필요한 노드들이다.

(후에, 이 노드에 해당되는 문자열이 들어온다면, 종료노드로 세팅될 수도 있다.)

트라이의 중요한 속성은 루트에서 한 노드까지 내려가는 경로에서 간선에 대응되는 문자들을 모으면, 해당 노드에 대응되는 접두사를 얻을 수 있다. 그러므로, 그림에서 보여지는 것과 같이 모든 문자열들을 저장할 필요가 없다.

트라이의 한 노드는 자식 노드들을 가리키는 포인터들과, 이 노드가 종료 노드인지 체크할 수 있는 플래그 변수만 있으면 충분하다. 이 때 자식 노드들을, 가능한 문자 개수만큼의 포인터 배열로 설계하면, 자식에 대한 문자를 인덱스에 대응시킬 수 있으므로 성능적인 이점을 갖을 수 있다. 반대로 메모리는 훨씬 더 많이 먹게 될 것이다.

// 알파벳 소문자를 저장하는 트라이 노드
struct TrieNode
{
public:
    static const int Alphabets = 26;
    TrieNode() : childs(), has_value(false)
    {}

    ~TrieNode()
    {
        for (int i = 0; i < Alphabets; ++i)
            delete childs[i];
    }

private:
    static int ToIndex(char alphabet)
    {
        return (int)(alphabet - 'a');
    }

    static char ToChar(int index)
    {
        return (char)index + 'a';
    }

public:
    TrieNode* childs[Alphabets];
    bool has_value;
};

 

이제 트라이에 기본적인 연산들을 구현할 차례이다.

트라이에는 문자열을 찾는 연산, 문자열을 삽입하는 연산, 이렇게 두 가지 연산이 필요하다.

 

먼저 문자열을 찾는 Find 연산을 구현한다.

Find연산은 트라이라는 문자열 집합 내에 어떤 문자열이 존재하는지 확인할 수 있어야 한다.

그러므로 문자열을 인풋으로 받도록 설계하고, 추가로 해당 노드가 종료 노드인지까지는 검사하지 않고, 

인풋 문자열과 대응되는 노드를 반환하도록 설계한다. 이는 좀 더 범용적으로 활용하기 위함이다.

대응되는 문자열을 트라이에서 찾는 과정은 문자열의 각 문자들에 대해서 트라이의 루트의 child들부터 대응시켜 본다.

문자열의 각 문자에 대응되는 child로의 포인터가 null이 아니라면, 그 child를 기준으로 다음 문자를 탐색하도록 한다.

그렇게 문자열의 모든 문자를 탐색하도록 하고, 만약 해당되는 문자가 없었다면 중간에 nullptr을 만나게 될 것이다.

// ..
    const TrieNode* Find(const char* text, int size) const
    {
        const TrieNode* cur = this;
        for (int i = 0; i < size; ++i)
        {
            int index = ToIndex(text[i]);
            if (cur->childs[index] == nullptr)
            {
                return nullptr;
            }

            cur = cur->childs[index];
        }

        return cur;
    }
// ..

 

다음으로 문자열을 트라이에 넣는, Insert 함수를 구현한다.

Insert 함수는 트라이에 새로운 문자열을 추가해주는 함수이다. 그러므로 문자열을 인풋으로 받도록 한다.

Insert 함수도 Find 함수와 마찬가지의 방식으로 트라이 노드들을 탐색한다.

대신 문자열의 문자에 대응되는 child가 없어서 null을 만나게 되는 경우마다 새로운 트라이 노드들을 할당한다.

대응되는 child가 있어서 null이 아닌 경우라면, 이미 다른 문자열이 추가되면서 할당된 트라이 노드일 것이다.

그렇게 모든 문자열에 대한 트라이 노드들이 생성되었다면, 마지막 노드에 종료 노드 체크를 해준다.

// ..
    void Insert(const char* text, int size)
    {
        TrieNode* cur = this;
        for (int i = 0; i < size; ++i)
        {
            int index = ToIndex(text[i]);
            if (cur->childs[index] == nullptr)
            {
                cur->childs[index] = new TrieNode();
            }

            cur = cur->childs[index];
        }
        cur->has_value = true;
    }
// ..

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Trie/1-Trie.cpp

insooneelife/AlgorithmTutorial