트라이 (Trie/Prefix Tree) - 1

 

목차

 

트라이 (Trie/Prefix Tree)

데이터(주로 문자열)을 효율적으로 저장하고 탐색하기 위한 자료구조이다.

검색을 뜻하는 단어 Retrieval 에서 유래되었으며, 트리 형태로 이루어져있다.

접두사를 기반으로 동작하기에, Prefix Tree라고도 불린다.

 

 

 

적용 사례

테무의 검색어 자동완성 기능

 

 

"아이"라는 키워드를 검색했을 때, 해당 단어를 접두사로 하는 모든 단어를 표시해준다.

이렇듯 접두사를 활용할 수 있는 자동완성 기능, 자연어 처리(NLP), 맞춤법 검사기(Spell Checker)등에 사용된다.

 

트라이의 특징

1. 접두사(prefix)를 기반으로 문자열을 저장한다.

node라는 문자열을 저장하면, 해당 문자열과 함께 접두사인 n, no, nod또한 저장된다. (node 또한 node의 접두사이다.)

밑에 등장하지만, nod라는 단어가 같이 저장된 것인지, 직접 nod를 저장하고자 했는지 판별이 가능하다.

 

2. 삽입, 삭제, 조회 연산을 O(m)에 수행할 수 있다.

여기서 m은 문자열의 length이다.

O(m)으로 수행할 수 있는 이유는, 문자열 각 인덱스가 하나의 노드가 되며 이를 O(1) *m번 수행하기 때문이다.

또한, 트리의 높이 h는 저장된 가장 긴 문자열의 길이이다.

 

3. 공간의 효율성을 가진다.

문자열 node와 nos는 no라는 공통 부분이 있다. 두 문자열을 각각 저장한다면 공간의 낭비가 생긴다.

트라이는 각 인덱스의 문자를 자식 노드로 저장하기 때문에 이를 효율적으로 다룬다.

 

트라이 구현

전체 코드는 다음과 같다.

delete(), listWithPrefix(), listAll()의 구현은 조금 복잡하므로, 다음 글에서 다루려 한다.

 

import java.util.HashMap;
import java.util.Map;

class Main {

    static class Node {
        Map<Character, Node> childNode;
        
        boolean endOfWord;

        public Node() {
            this.childNode = new HashMap<>();
            this.endOfWord = false;
        }
    }

    static class Trie {

        Node root;

        Trie(Node node) {
            this.root = node;
        }

        void insert(String s) {

            Node current = root;
            
            for (int i = 0; i < s.length(); i++) {
                current = current.childNode.computeIfAbsent(s.charAt(i), key -> new Node());
            }

            current.endOfWord = true;
        }

        boolean search(String s) {
            Node current = root;
            for (int i = 0; i < s.length(); i++) {
                current = current.childNode.getOrDefault(s.charAt(i), null);
                if (null == current) return false;
            }
            return current.endOfWord;
        }
    }

    public static void main(String[] args) {

        Node root = new Node();
        Trie trie = new Trie(root);

        trie.insert("node");

        System.out.println(trie.search("node")); // true
        System.out.println(trie.search("nod")); // false

    }
}

 

1. 노드의 구현

static class Node {
    Map<Character, Node> childNode;
    boolean endOfWord;

    public Node() {
        this.childNode = new HashMap<>();
        this.endOfWord = false;
    }
}

 

일반적으로 Map으로 자식 노드를 표현한다. 이진 트리에 반해, 다수의 노드가 자식이 될 수 있기 때문이다.

추가로, 단어의 끝임을 표시하는 endOfWord라는 변수를 사용한다. 이는 리프 노드가 아닐 수 있다.

 

이후 동작은 Map의 computeIfAbsent(), getOrDefault() 메서드를 통해 간결하게 구현할 수 있다.

뒤에 간단히 메서드의 동작을 기술했지만 사전 지식이 필요하다면 Docs를 참조하자.

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

 

2. 트라이의 구현

static class Trie {

    Node root;

    Trie(Node node) {
        this.root = node;
    }

    // insert(), search()... 구현
}

루트 노드는 진입점의 역할을 한다.

이 외의 필요한 동작을 하는 메서드를 추가한다. 

 

3. insert()의 구현

void insert(String s) {

    Node current = root;

    for (int i = 0; i < s.length(); i++) {
        current = current.childNode.computeIfAbsent(s.charAt(i), key -> new Node());
    }

    current.endOfWord = true;
}

current는 현재 탐색 중인 노드를 의미한다. 처음에는 진입점인 root일 것이다.

이후 파라미터인 문자열을 탐색하며, 다음과 같은 동작을 수행한다.

 

char c = s.charAt(i);

1. key가 c인 노드가 자식에 존재한다면, current를 자식 노드로 갱신한다.

2. 존재하지 않는다면, c를 key로 가지는 노드를 생성하여 자식 노드로 연결하고, current를 해당 노드로 갱신한다.

3. for문 이후, 최종적으로 current는 s.charAt(s.length()-1)의 val을 가질 것이다. 해당 노드를 endOfWord로 표현한다.

 

"node"라는 문자열을 insert 한다면, n-o-d-e(eow)라는 서브 트리가 생겼을 것이다.

이후 "nod"라는 문자열을 insert 한다면, n-o-d(eow)-d(eow)의 형태가 된다.

 

이로서, 우리는 "nod"를 의도적으로 저장했는지, 단순히 "node"를 저장하는 과정에서 생긴 것인지 판별할 수 있다.

 

computeIfAbsent -> 해당 key가 존재한다면 val 반환, 존재하지 않는다면 mappingFunction 실행후 해당 val 반환

 

4. search()의 구현

boolean search(String s) {
    Node current = root;
    for (int i = 0; i < s.length(); i++) {
        current = current.childNode.getOrDefault(s.charAt(i), null);
        if (null == current) return false;
    }
    return current.endOfWord;
}

 

리턴값 boolean은 해당 단어의 존재여부 외에도, 직접 저장되어 있는지를 판별한다.

 

char c = s.charAt(i);

1. key가 c인 노드가 자식에 존재한다면, current를 자식 노드로 갱신한다.

2. 존재하지 않는다면, current를 default값 null로 갱신한다.

3. current가 null이라는 것은, 자식 노드가 존재하지 않음을 의미한다. 해당 문자는 트라이에 없다.

4. for문 이후, 최종적으로 current는 s.charAt(s.length()-1)의 val을 가질  것이다.

current가 eow라면, 해당 단어는 의도적으로 저장되어 있다. eow가 아니라면, 생긴 것이다.

 

getOrDefault -> 해당 key가 존재한다면 val 반환, 존재하지 않는다면 default val 반환

 

3번이 반환하는 false는 문자가 트라이에 존재하지 않는 것이며, 4번이 반환하는 false는 다른 단어의 접두사로서 존재하는 것임을 유의하자. 또한, 노드가 존재하지 않음을 의미하는 Default 값은 null이 아니여도 괜찮다.