[자.알.인] CH16. 트라이

1. 트라이(Tire)란?

트라이 이미지

 

• 트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조입니다.
• 특히 실무에 매우 유용하게 쓰이는 자료구조로서, 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰입니다.
• 래딕스 트리(radix tree) / 접두사 트리(prefix tree) / 탐색 트리(retrieval tree)라고도 불린다. 여기서 트라이는 retrieval tree의 'trie'를 따온 단어입니다.
• 해당 자료구조는 예를 들어서 'Datastructure'라는 단어를 검색하기 위해서 제일 먼저 'D'를 찾고, 다음 단어 순서로 찾는 방식입니다.

 

2. 트라이 구현(Java)

자.알.인의 문제 62번 '트라이 구현'에서 표현된 2개의 객체를 생성하였습니다.

 

[TrieNode.java]

public class TrieNode {

    boolean word;
    TrieNode[] children;

    TrieNode() {
        children = new TrieNode[26]; // 알파벳 총 개수
        word = false;
    }
}

 

[Trie.java]

public class Trie {

    TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode cur = root;
        for(char c : word.toCharArray()) {
            if(cur.children[c - 'a'] == null)
                cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
        }
        cur.word = true;
    }

    public boolean search(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if(cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }

        return cur.word;
    }

    public boolean startsWith(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            if(cur.children[c - 'a'] == null) {
                return false;
            }
            cur = cur.children[c - 'a'];
        }

        return true;
    }
}

 

예를 들어 "apple"이라는 단어를  Trie에 넣는다고 가정하면,

Trie 형태

 

첫번째 TrieNode에 'a'가 활성화되고, 이 후 단어 순서대로 'p', 'p', 'l', 'e'가 활성화 된 TrieNode가 children으로 반복적으로 들어가고 'e'의 TrieNode가 들어감을 확인 후 단어 형태의 참,거짓 값을 구분 짓는 word를 true로 변경시킵니다.

 

그렇게 "apple"의 Trie 객체는 완료가 되었습니다. 이 후, 확인을 위해 search(검색), startWith(앞에서 일치한 단어 형태)를 진행할 시

 

Trie trie = new Trie();

trie.insert("apple"); // apple 삽입
trie.search("apple"); // apple 검색, true 반환
trie.search("app"); // app 검색, false 반환
trie.startsWith("app"); // app 시작값 확인, true 반환

trie.insert("app"); // app 삽입
trie.search("app"); // app 검색, true 반환

 

이러한 결과를 나타냅니다. "app" 검색시 false가 나오는 것은 "apple"만 단어가 들어있는 Trie에서 'a', 'p', 'p' 까지 확인이 가능하고 'p'에서 word가 false이기 때문에 이를 반환하게 됩니다.

 

 

3. 트라이 장단점

• 장점
  문자열을 빠르게 찾을 수 있습니다.
  문자열을 추가하는 경우에도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에 문자열의 추가와 탐색이 모두 O(n)만에 가능합니다.
• 단점
  필요한 메모리의 크기가 너무 큽니다.
  위의 Trie 형태 사진처럼 문자열이 모두 알파벳 소문자로만 이루어진 경우라고 해도, 1 depth에 a~z까지 26개의 공간이 필요하게 됩니다.