문자열 알고리즘 (5) - 트라이 (Trie)

1. 알고리즘 개요

Trie(트라이)는 알고리즘보다는 자료구조에 가깝다. Trie(트라이)는 문자열 검색을 위한 자료구조로 트리 노드 하나에 문자 하나를 담는다. 트라이는 N진 트리인데, N은 문자의 총 종류가 된다. 만약 알파벳 처럼 문자의 종류가 26개라면 26진 트리의 형태를 띄게 된다.

 

 

2. 소스코드 

public class Trie {
    private TrieNode root = new TrieNode();

    private void insert(String key) {
        root.insert(key + '\0');
    }

    private void find(String key) {
        Boolean result = root.find(key + '\0');

        if (result == null)
            System.out.println("값이 없음");
        else if (result)
            System.out.println("값이 있음");
        else
            System.out.println("값이 있으나 끝이 아님");
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("Hello");
        trie.insert("House");

        trie.find("House"); // 값이 있음
        trie.find("Hell"); // 값이 있으나 끝이 아님
        trie.find("Horse"); // 값이 없음
    }
}

class TrieNode {

    private TrieNode[] next = new TrieNode[26];
    private boolean leaf;

    void insert(String string) {
        char[] s = string.toCharArray();
        char curr = s[0];

        if (curr == '\0')
            leaf = true;

        else {
            int idx = char2idx(curr);

            if (next[idx] == null) 
                next[idx] = new TrieNode();

            if (string.length() > 1) 
                string = string.substring(1);

            next[idx].insert(string);
        }
    }

    Boolean find(String string) {
        char[] s = string.toCharArray();
        char curr = s[0];

        if (curr == '\0')
            return leaf;

        else {
            int idx = char2idx(curr);

            if (next[idx] == null)
                return null;

            if (string.length() > 1)
                string = string.substring(1);

            return next[idx].find(string);
        }
    }

    private int char2idx(char c) {
        // make lowercase
        if (c < 'a') {
            c += ('a' - 'A');
        }

        return c - 'a';
    }
}

 

위 소스코드는 자바로 구현한 Trie로 인터넷에 C++ 구현이 많아서 직접 자바로 구현해봤다. 다른 구현은 보지 않아서 이보다 더 효율적인 구현이 존재할 수도 있다. C++에서는 String이 아니라 문자포인터(char*)를 입력받고, next[idx].find()나 next[idx].insert()를 수행할 때, 포인터 연산(pointer + 1 : 다음 주소)을 사용하는데 이는 처음보는 사람으로 하여금 가독성이 좋지 못하기 때문에 자바에서 String.substring(begin)으로 구현했다. substring(1)은 가장 앞문자(0번 인덱스)를 떼고 1번 인덱스를 시작으로 재구성한 스트링을 의미한다.

 

그리고 자바 String에서는 문자열 끝에 null문자(\0)가 포함되지 않기 때문에 (정확히 말하면 내부 버퍼에는 포함이 되어 있지만 String 클래스로 포장되어 있을 땐 null문자를 떼고 출력한다) 인위적으로 Trie 클래스에서 null문자를 포함해서 입력했다.