[알고리즘 공부] Trie (트라이) - 1

올해 소프트웨어 마에스트로 11기 활동이 끝나고 활동 중에 못했던 알고리즘, 자료구조 공부를 하고 있다.

몇일 전에 트라이 자료구조를 공부하려고 공부하고 트라이 관련 문제를 쭉 풀었다.

 

이 글은 내가 공부했던 것을 정리하는 글이다.

 

(난 트라이 이론을 정리는 안하고 트라이 구현 및 문제 풀이 위주로 작성한다.)

 

이 글에서는 트라이를 맨 처음에 짠 코드에서 최적화 시킨 코드까지 어떤 과정을 거쳤는지 정리한다.

 

1. 포인터를 이용한 구현 with map

 

처음부터 간단하게 짜기 힘들다. 포인터를 이용해서 먼저 직접 짜보는게 좋다.

나도 트라이 이론만 보고 혼자 포인터를 이용해서 짰었다.

 

빌드 과정은 완전한 O(NL)이 아니라 map을 사용하기 때문에 log 26 (더미노드 없다고 생각하면) 정도가 붙겠지만...

namespace Trie{
    struct Node{
        char data;
        int value;
        map<char, Node*> _next;
        Node() { }
        ~Node() { for(auto &i: _next) delete i.second; }
        Node* insert(char x){ if(_next.count(x) == 0)_next[x] = new Node(); return _next[x]; }
        Node* next(char x){ return _next.count(x) ? _next[x] : NULL; }

        bool find(char x){ return _next.count(x) != 0; }
        bool end(){ return _next.count(0); }
    }*root = new Node();
    int words = 0;

    void insert(const string &word){
        Node *cursor = root;
        for(int i=0;i<(int)word.size();i++)cursor = cursor->insert(word[i]);            
        if(!cursor->find(0))words++;
        cursor->insert(0); // Dummy Node
    }
    
    bool find(string str){
        Node *cursor = root;
        for(int i=0;i<(int)str.size();i++){
            Node *nxt = cursor->insert(str[i]);
            if(nxt == NULL)return false;
        }
        return cursor->end();
    }
}

 

2. map을 배열로 변경

 

map 삽입, 검색이 상수가 아니다. 배열을 이용해서 이를 해결할 수 있다. (하지만 하나의 노드에 저장해야할께 많으면 메모리를 많이 먹으니 상황에 맞게 잘 바꿔야한다.)

 

namespace Trie{
    struct Node{
        char data;
        int value;
        Node* _next[27];
        Node() { for(int i=0;i<27;i++)_next[i] = NULL; }
        ~Node() { for(int i=0;i<27;i++) if(_next[i]) delete _next[i]; }
        Node* insert(char x){ if(_next[x-'A'] == 0)_next[x-'A'] = new Node(); return _next[x-'A']; }
        Node* next(char x){ return _next[x-'A']; }

        bool find(char x){ return _next[x-'A'] != NULL; }
        bool end(){ return _next[26] != NULL; }
    }*root = new Node();
    int words = 0;

    void insert(const string &word){
        Node *cursor = root;
        for(int i=0;i<(int)word.size();i++)cursor = cursor->insert(word[i]);            
        if(!cursor->find(26))words++;
        cursor->insert(26); // Dummy Node
    }
    
    bool find(string str){
        Node *cursor = root;
        for(int i=0;i<(int)str.size();i++){
            Node *nxt = cursor->insert(str[i]);
            if(nxt == NULL)return false;
        }
        return cursor->end();
    }
}

 

3. 포인터를 배열로

 

포인터를 사용하면 장점도 있겠지만 단점도 있다. 그게 바로 메모리를 조금 더 사용(포인터가 8바이트를 차지하는 경우)한다. 배열로 바꾸면 속도도 빨라진다.

 

struct Trie{
    struct Node{
        int _next[27];
        Node() { for(int i=0;i<27;i++)_next[i] = -1; }
        int &operator[](int idx) { return _next[idx]; }
    };
    Node next[1 << 19];
    int node;

    Trie() { node = 1; }

    void insert(const string &word){
        int cur = 0;
        for(int i=0;i<(int)word.size();i++){
            if(next[cur][word[i] - 'A'] == -1)next[cur][word[i] - 'A'] = node++;
            cur = next[cur][word[i] - 'A'];
        }
        next[cur][26] = 0;
    }

    bool find(const string &word){
        int cur = 0;
        for(int i=0;i<(int)word.size();i++){
            if(next[cur][word[i] - 'A'] == -1)return false;
            cur = next[cur][word[i] - 'A'];
        }
        return next[cur][26] != -1;
    }
};

 

4. Node 구조체를 없앨 수 있겠는데?

 

Node 구조체를 없애고 코딩할 수 있는 형태가 보인다. 또한 find 함수는 insert를 이해한다면 쉽게 짤 수 있으니깐 이 다음부터는 지웠다.

 

struct Trie{
    int next[1 << 19][27], node;

    Trie() { 
        node = 1;
        for(int i=0;i<(1<<19);i++)for(int j=0;j<27;j++)next[i][j] = -1;
    }

    void insert(const string &word){
        int cur = 0;
        for(int i=0;i<(int)word.size();i++){
            if(next[cur][word[i] - 'A'] == -1)next[cur][word[i] - 'A'] = node++;
            cur = next[cur][word[i] - 'A'];
        }
        next[cur][26] = 0;
    }
};

 

5. 매우 간단해졌지만 메모리 초과...가 뜬다.

 

메모리를 어떻게 더 효율적으로 쓸 수 있을까?

가변 배열을 쓰면 될꺼 같다.

 

struct Trie{
    vector<pair<int, int>> next[1 << 19];
    int node;

    Trie() { node = 1; }
    
    void insert(const string &word){
        int cur = 0;
        for(int i=0;i<(int)word.size();i++){
            int idx = -1;
            for(int j=0;j<(int)next[cur].size();j++){
                if(next[cur][j].first == word[i]){
                    idx = next[cur][j].second;
                    break;
                }
            }
            if(idx == -1){
                next[cur].emplace_back(word[i], node);
                idx = node++;
            }
            cur = idx;
        }
    }
};