트라이(Trie): 효율적인 문자열 검색과 자동 완성을 위한 자료구조

 

 

트라이(Trie)는 문자열을 효율적으로 저장하고 검색할 수 있는 트리 기반의 자료구조입니다. 트라이는 특히 자동 완성(Auto-completion), 사전(Dictionary) 구현, 검색 엔진 최적화 등에 유용하게 사용됩니다. 트라이는 각 노드가 하나의 문자를 저장하고, 루트 노드부터 시작하여 문자열을 구성하는 방식으로 데이터를 저장합니다.

 

트라이의 등장 배경

대량의 문자열 데이터를 빠르게 검색하고 관리해야 하는 필요성이 증가하면서, 효율적인 문자열 검색을 지원하는 자료구조가 요구되었습니다. 기존의 이진 탐색 트리나 해시 테이블은 문자열의 공통 접두사를 효과적으로 활용하지 못하는 반면, 트라이는 공통 접두사를 공유함으로써 저장 공간을 절약하고 검색 속도를 향상시킬 수 있습니다.

 

트라이는 텍스트 편집기, 검색 엔진, 자동 완성 시스템, 사전 애플리케이션 등 다양한 실무 분야에서 핵심적으로 사용됩니다. 이 자료구조는 문자열 데이터의 효율적인 저장과 빠른 검색을 가능하게 합니다.

 

 

 

---

 

 

트라이(Trie)의 개념

 

트라이는 전위 트리(Prefix Tree)라고도 불리며, 문자열을 저장하기 위해 고안된 트리 자료구조입니다. 트라이의 각 노드는 하나의 문자를 저장하며, 루트 노드부터 시작하여 문자열을 구성하는 경로를 형성합니다. 트라이의 주요 특징은 공통 접두사 공유와 효율적인 검색입니다.

 

트라이의 특징

• 공통 접두사 공유: 트라이는 공통된 접두사를 공유함으로써 저장 공간을 절약할 수 있습니다.
• 빠른 검색: 문자열 검색이 O(m) 시간 복잡도로 가능하며, m은 검색하려는 문자열의 길이입니다.
• 자동 완성 지원: 트라이는 특정 접두사를 가진 모든 문자열을 쉽게 찾을 수 있어 자동 완성 기능에 적합합니다.
• 알파벳 기반 트리: 트라이는 보통 알파벳이나 문자 집합을 기반으로 노드를 확장합니다.

 

트라이의 구조

트라이는 루트 노드부터 시작하여 각 문자에 해당하는 자식 노드로 확장됩니다. 문자열의 각 문자는 트라이의 노드를 따라가며 저장됩니다. 트라이의 끝 노드는 종료 플래그를 가지고 있어 해당 경로가 완전한 문자열임을 나타냅니다.

 

 

트라이의 응용 분야

• 자동 완성 시스템: 사용자가 입력한 접두사에 따라 가능한 완성 단어를 빠르게 제안합니다.
• 사전(Dictionary) 구현: 단어의 존재 여부를 빠르게 확인하고, 접두사를 기반으로 단어를 검색합니다.
• 패턴 매칭: 문자열 패턴을 효율적으로 매칭하고 검색합니다.
• 압축: 공통 접두사를 공유하여 저장 공간을 절약합니다.

 

 

---

 

 

트라이의 실제 사용 사례

 

자동 완성(Auto-completion)

자동 완성 시스템은 사용자가 입력하는 문자열의 접두사를 기반으로 가능한 완성 단어를 제안합니다. 트라이는 공통 접두사를 공유하여 빠르게 완성 단어를 검색할 수 있어 효율적인 자동 완성 기능을 구현하는 데 적합합니다.

 

사전(Dictionary) 구현

트라이는 단어의 존재 여부를 빠르게 확인하고, 접두사를 기반으로 단어를 검색할 수 있어 사전 애플리케이션에서 널리 사용됩니다. 트라이는 공통 접두사를 공유하여 저장 공간을 절약할 수 있습니다.

 

검색 엔진 최적화

검색 엔진은 사용자 쿼리에 대한 빠른 응답을 제공하기 위해 트라이를 활용할 수 있습니다. 트라이는 접두사를 기반으로 단어를 빠르게 검색하고, 관련된 검색 결과를 효율적으로 제공할 수 있습니다.

 

패턴 매칭

트라이는 문자열 패턴을 효율적으로 매칭할 수 있어, 텍스트 분석 및 데이터 마이닝에서 유용하게 사용됩니다. 트라이는 접두사를 기반으로 패턴을 빠르게 탐색할 수 있습니다.

 

 

 

---

 

 

트라이(Trie) 구현하기

 

Python으로 트라이(Trie) 구현하기

class TrieNode:
    def __init__(self):
        self.children = {}  # 자식 노드를 저장하는 딕셔너리
        self.is_end_of_word = False  # 단어의 끝을 나타내는 플래그

class Trie:
    def __init__(self):
        self.root = TrieNode()

    # 단어 삽입
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # 새로운 노드 생성
            node = node.children[char]
        node.is_end_of_word = True  # 단어의 끝을 표시

    # 단어 검색
    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False  # 단어가 존재하지 않음
            node = node.children[char]
        return node.is_end_of_word  # 단어의 끝인지 확인

    # 접두사를 가진 모든 단어 검색
    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []  # 접두사가 존재하지 않음
            node = node.children[char]
        words = []
        self._dfs(node, prefix, words)
        return words

    # 깊이 우선 탐색을 통한 단어 수집
    def _dfs(self, node, prefix, words):
        if node.is_end_of_word:
            words.append(prefix)
        for char, child in node.children.items():
            self._dfs(child, prefix + char, words)

    # 트리 구조 출력 (재귀적)
    def display(self, node=None, word=''):
        if node is None:
            node = self.root
        if node.is_end_of_word:
            print(word)
        for char, child in node.children.items():
            self.display(child, word + char)

# 트라이 사용 예시
if __name__ == "__main__":
    trie = Trie()
    words = ["apple", "app", "application", "apt", "bat", "batch", "baton"]
    for word in words:
        trie.insert(word)

    print("Search 'app':", trie.search("app"))  # 출력: True
    print("Search 'appl':", trie.search("appl"))  # 출력: False
    print("Words starting with 'app':", trie.starts_with("app"))  # 출력: ['app', 'apple', 'application']
    print("Words starting with 'ba':", trie.starts_with("ba"))  # 출력: ['bat', 'batch', 'baton']

    print("\nAll words in Trie:")
    trie.display()
    # 출력:
    # app
    # apple
    # application
    # apt
    # bat
    # batch
    # baton

코드 설명

1. TrieNode 클래스:
   • init 메서드:
     • children: 현재 노드의 자식 노드를 저장하는 딕셔너리입니다. 키는 문자이고, 값은 자식 TrieNode 객체입니다.
     • is_end_of_word: 해당 노드가 단어의 끝을 나타내는지 여부를 표시하는 플래그입니다.
2. Trie 클래스:
   • init 메서드:
     • root: 트라이의 루트 노드로, 초기에는 빈 TrieNode 객체로 설정됩니다.
   • insert 메서드:
     • 주어진 단어를 트라이에 삽입합니다.
     • 단어의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 새로운 TrieNode를 생성합니다.
     • 단어의 마지막 문자에 도달하면 is_end_of_word를 True로 설정하여 단어의 끝을 표시합니다.
   • search 메서드:
     • 주어진 단어가 트라이에 존재하는지 확인합니다.
     • 단어의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 False를 반환합니다.
     • 단어의 마지막 문자에 도달하면 is_end_of_word 플래그를 확인하여 단어의 존재 여부를 반환합니다.
   • starts_with 메서드:
     • 주어진 접두사를 가진 모든 단어를 검색하여 리스트로 반환합니다.
     • 접두사의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 빈 리스트를 반환합니다.
     • 접두사에 도달한 후, 해당 노드부터 깊이 우선 탐색(DFS)을 수행하여 모든 단어를 수집합니다.
   • _dfs 메서드:
     • 깊이 우선 탐색을 통해 단어를 수집합니다.
     • 현재 노드가 단어의 끝이면, 현재까지의 접두사를 리스트에 추가합니다.
     • 자식 노드를 따라가며 재귀적으로 탐색을 계속합니다.
   • display 메서드:
     • 트라이에 저장된 모든 단어를 재귀적으로 출력합니다.
     • 현재 노드가 단어의 끝이면, 현재까지의 단어를 출력합니다.
     • 자식 노드를 따라가며 단어를 완성해갑니다.
3. 사용 예시:
   • 트라이 객체를 생성하고, 여러 단어를 삽입합니다.
   • 특정 단어의 존재 여부를 검색하고, 특정 접두사를 가진 단어들을 검색합니다.
   • 트라이에 저장된 모든 단어를 출력하여 트리의 구조를 확인합니다.

 

JavaScript으로 트라이(Trie) 구현하기

 

class TrieNode {
    constructor() {
        this.children = {}; // 자식 노드를 저장하는 객체
        this.isEndOfWord = false; // 단어의 끝을 나타내는 플래그
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // 단어 삽입
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode(); // 새로운 노드 생성
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // 단어의 끝을 표시
    }

    // 단어 검색
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false; // 단어가 존재하지 않음
            }
            node = node.children[char];
        }
        return node.isEndOfWord; // 단어의 끝인지 확인
    }

    // 접두사를 가진 모든 단어 검색
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return []; // 접두사가 존재하지 않음
            }
            node = node.children[char];
        }
        let words = [];
        this._dfs(node, prefix, words);
        return words;
    }

    // 깊이 우선 탐색을 통한 단어 수집
    _dfs(node, prefix, words) {
        if (node.isEndOfWord) {
            words.push(prefix);
        }
        for (let char in node.children) {
            this._dfs(node.children[char], prefix + char, words);
        }
    }

    // 트리 구조 출력 (재귀적)
    display(node = this.root, word = '') {
        if (node.isEndOfWord) {
            console.log(word);
        }
        for (let char in node.children) {
            this.display(node.children[char], word + char);
        }
    }
}

// 트라이 사용 예시
const trie = new Trie();
const words = ["apple", "app", "application", "apt", "bat", "batch", "baton"];
for (let word of words) {
    trie.insert(word);
}

console.log("Search 'app':", trie.search("app")); // 출력: true
console.log("Search 'appl':", trie.search("appl")); // 출력: false
console.log("Words starting with 'app':", trie.startsWith("app")); // 출력: ['app', 'apple', 'application']
console.log("Words starting with 'ba':", trie.startsWith("ba")); // 출력: ['bat', 'batch', 'baton']

console.log("\nAll words in Trie:");
trie.display();
// 출력:
// app
// apple
// application
// apt
// bat
// batch
// baton

코드 설명

1. TrieNode 클래스:
   • constructor 메서드:
     • children: 현재 노드의 자식 노드를 저장하는 객체입니다. 키는 문자이고, 값은 자식 TrieNode 객체입니다.
     • isEndOfWord: 해당 노드가 단어의 끝을 나타내는지 여부를 표시하는 플래그입니다.
2. Trie 클래스:
   • constructor 메서드:
     • root: 트라이의 루트 노드로, 초기에는 빈 TrieNode 객체로 설정됩니다.
   • insert 메서드:
     • 주어진 단어를 트라이에 삽입합니다.
     • 단어의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 새로운 TrieNode를 생성합니다.
     • 단어의 마지막 문자에 도달하면 isEndOfWord를 True로 설정하여 단어의 끝을 표시합니다.
   • search 메서드:
     • 주어진 단어가 트라이에 존재하는지 확인합니다.
     • 단어의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 False를 반환합니다.
     • 단어의 마지막 문자에 도달하면 isEndOfWord 플래그를 확인하여 단어의 존재 여부를 반환합니다.
   • startsWith 메서드:
     • 주어진 접두사를 가진 모든 단어를 검색하여 리스트로 반환합니다.
     • 접두사의 각 문자를 따라가며, 해당 문자가 현재 노드의 자식에 없으면 빈 리스트를 반환합니다.
     • 접두사에 도달한 후, 해당 노드부터 깊이 우선 탐색(DFS)을 수행하여 모든 단어를 수집합니다.
   • _dfs 메서드:
     • 깊이 우선 탐색을 통해 단어를 수집합니다.
     • 현재 노드가 단어의 끝이면, 현재까지의 접두사를 리스트에 추가합니다.
     • 자식 노드를 따라가며 재귀적으로 탐색을 계속합니다.
   • display 메서드:
     • 트라이에 저장된 모든 단어를 재귀적으로 출력합니다.
     • 현재 노드가 단어의 끝이면, 현재까지의 단어를 출력합니다.
     • 자식 노드를 따라가며 단어를 완성해갑니다.
3. 사용 예시:
   • 트라이 객체를 생성하고, 여러 단어를 삽입합니다.
   • 특정 단어의 존재 여부를 검색하고, 특정 접두사를 가진 단어들을 검색합니다.
   • 트라이에 저장된 모든 단어를 출력하여 트리의 구조를 확인합니다.

 

 

---

 

 

트라이(Trie)의 장단점

트라이의 장점

• 빠른 검색 속도: 트라이는 문자열의 길이에 비례하는 O(m) 시간 복잡도로 검색이 가능하여 매우 빠릅니다.
• 공통 접두사 공유: 공통된 접두사를 공유하여 저장 공간을 절약할 수 있습니다.
• 자동 완성 지원: 접두사를 기반으로 모든 단어를 효율적으로 검색할 수 있어 자동 완성 기능에 적합합니다.
• 문자열 관련 작업에 최적화: 문자열의 삽입, 삭제, 검색, 접두사 기반 검색 등이 효율적으로 수행됩니다.

 

트라이의 단점

• 높은 메모리 사용: 각 노드가 여러 자식 노드를 가질 수 있어 메모리 사용량이 많아질 수 있습니다.
• 복잡한 구현: 트라이는 기본적인 이진 트리에 비해 구현이 다소 복잡할 수 있습니다.
• 고정된 문자 집합: 트라이는 보통 알파벳이나 특정 문자 집합을 기반으로 설계되므로, 유니코드나 다양한 문자 집합을 지원하기 위해 추가적인 구현이 필요할 수 있습니다.

 

 

---

 

 

트라이는 효율적인 문자열 검색과 자동 완성 기능을 구현할 수 있는 강력한 자료구조입니다. 공통 접두사를 공유하여 저장 공간을 절약하고, 빠른 검색 속도를 제공하여 다양한 실무 문제를 효율적으로 해결하는 데 필수적인 도구로 자리 잡고 있습니다.

 

 

 

참고 자료

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

 

https://www.geeksforgeeks.org/trie-insert-and-search/

Trie Data Structure | Insert and Search - GeeksforGeeks