Trie - Prefix Tree

---

트라이 자료구조가 없었을 때

트라이 이전에는 배열, 해시 테이블, BST, Balanced BST, 문자열 검색 전용 알고리즘(KMP, Boyer-Moore), 그리고 정규 표현식 등으로 효과적으로 문자열 검색이 가능했습니다. 그러나 기존에 사용되던 자료구조로는 문자열 검색에 있어 여러 제약 사항과 성능 이슈가 있었기 때문에, 트라이는 이러한 문제를 해결하기 위한 방법으로 개발되었습니다.

예를 들어서, 배열과 해시테이블로 문자열을 검색하는 경우를 생각해 보겠습니다.

• 배열(Array)
  • 배열이나 리스트에 문자열을 저장하고, 검색할 때마다 전체를 순회하면서 검색
  • 이 방법은 효율성이 떨어져 큰 데이터셋에서는 사용하기 어려운 제약이 있습니다.
• 해시 테이블(Hash Table)
  • "apple"이라는 단어의 뜻을 알고 싶다면, 해시 테이블에서 'apple'을 키로 검색하면 $O(1)$ 속도로 빠르게 문자열 검색 가능
  • 하지만, 해시 충돌시 값의 재 비교 필요 & 접두사 검색, 부분 문자열 검색, 사전 순 정렬 등에 제약이 있습니다.
    • 접두사 / 부분 문자열 검색: 'ppl'처럼 단어의 중간 부분만 알고 있을 때, 이 부분을 포함하는 모든 단어('apple', 'people' 등)를 찾는 것도 어렵습니다. → 자동 완성 기능 X
    • 문자열을 알파벳 순서대로 정렬: 해시 테이블은 키를 사전 순으로 정렬하지 않습니다. 따라서, 단어를 사전 순으로 보고 싶다면 별도의 작업이 필요합니다.

Trie

트라이는 1959년에 Edward Fredkin에 의해 처음 소개되었습니다. 그 당시에는 효율적인 문자열 검색, 특히 사전 검색(Dictionary lookup)에 대한 높은 요구가 있었습니다.

트라이(Trie)는 트리의 일종으로 ”문자열의 키”를 효율적으로 저장하고 검색하기 위한 자료구조 입니다. 여기서, 문자열의 키라고 하면 “apple”, “app”, “a”, “application”등이 될 수 있습니다.

다음과 같은 경우에 아주 유용하게 활용할 수 있는 자료구조입니다.

• 접두사 검색(Prefix Search)
  • 사용자가 입력한 접두사를 가진 모든 가능한 단어나 문구를 찾습니다.
  • 사용자가 "app"을 입력하면, "app", "apple", "application" 등이 결과로 나올 수 있습니다.
• 자동 완성(Auto-Completion)
  • 자동 완성 기능은 접두사 검색을 기반으로 동작합니다. 접두사 검색과 같이 사용자가 입력한 부분 문자열(접두사)를 기반으로 가능한 모든 완전한 문자열을 찾아서 제안합니다.
  • 단순 접두사 검색보다 더 다양한 변수(사용 빈도, 사용자 행동 등)를 고려하여 결과를 제공합니다.
• 사전 검색(Dictionary Lookup)
  • 사용자가 완전한 단어나 문구를 입력하여 해당 단어가 사전에 있는지 확인하고, 있다면 관련 정보(뜻, 사용 예 등)를 제공합니다.
  • 사용자가 "apple"을 검색하면, "apple"이라는 단어의 뜻, 발음, 동의어, 반의어, 예문 등이 제공될 수 있습니다.
  • 사전 검색은 완전한 단어에 대한 정확한 정보를 제공하려고 합니다. 여기에는 단어의 정의, 발음, 문법 정보 등이 포함될 수 있습니다.
  • ❓완전한 단어 검색이라면, 해시 테이블을 사용하는 것이 일반적으로 더 효율적입니다. 그러나 만약에 사전 순 정렬 기능이 필요하면 Trie 자료구조가 더 유리합니다.

트라이 자료구조 구현하기

Trie Node

class Node:
	def __init__(self):
    	self.children = {}
        self.isEndOfWord = False

삽입(Insert)

• for문
  

class Trie:
	def __init__(self):
    	self.root = Node()
        def insert(self, word):
        	current = self.root
        	for char in word:
                if char not in current.children:
                    current.children[char] = Node()
                current = current.children[char]
        
            current.isEndOfWord = True

• 재귀

class Trie:
    def __init__(self):
        self.root = Node()
        
    def insert(self, word):
        self._insert_recursive(self.root, word)
        
    def _insert_recursive(self, node, word):
        if not word:
            node.isEndOfWord = True
            return
                
        char = word[0]
        if char not in node.children:
            node.children[char] = Node()
                
        self._insert_recursive(node.children[char], word[1:])

검색(Search)

class Trie:
    def __init__(self):
        self.root = Node()
    
    def search(self, word):
        return self._search_recursive(self.root, word)
    
    def _search_recursive(self, node, word):
        if not word:
            return node.isEndOfWord
    
        char = word[0]
        if char in node.children:
            return self._search_recursive(node.children[char], word[1:])
        else:
            return False

자동 완성

class Trie:
    def __init__(self):
        self.root = Node()
    
    def autocomplete(self, prefix):
        current = self.root
   
        for char in prefix:
            if char in current.children:
                current = current.children[char]
            else:
                return []
    
        return self._search_start_with(current, prefix)
    
    def _search_start_with(self, node, prefix):
        results = []
    
        if node.isEndOfWord:
            results.append(prefix)
    
        for char, child in node.children.items():
            results.extend(self._search_start_with(child, prefix + char))
    
        return results

• autocomplete 함수는 주어진 접두어(prefix)에 해당하는 노드를 찾습니다. 만약 접두어에 해당하는 노드가 트라이 내에 없다면 빈 결과 리스트를 반환합니다.
• _search_start_with 함수는 재귀적으로 동작하며, 현재 노드에서 시작하는 모든 단어를 찾아 결과 리스트에 추가합니다.

트라이의 성능 분석

시간 복잡도

접두어를 탐색하는 부분은 상수 시간 $*O(p)*$이 걸리는데 (여기서 p는 접두어의 길이), 이는 전체 트라이의 크기에 비해 상대적으로 작은 값입니다.

재귀적 탐색 부분(_search_start_with())에서는 트라이의 특정 부분 (접두어가 가리키는 노드부터 시작하여 그 아래에 있는 모든 노드들)을 탐색합니다. 최악의 경우, 이 부분이 트라이의 전체 노드를 탐색할 수도 있습니다.

따라서, 시간복잡도를 계산할 때 가장 중요한 것은 이 재귀적 탐색의 부분입니다. 이 부분의 시간복잡도는 $O(n)$입니다. 여기서 n은 탐색되는 트라이 부분의 노드 수입니다.

공간 복잡도

재귀의 깊이는 트라이의 최대 높이나 깊이에 비례합니다. 트라이의 깊이는 문자열의 최대 길이로 제한됩니다. 이 최대 깊이를 d 라고 할 때, 재귀적 호출로 인한 스택의 공간 복잡도는 $O(d)$입니다.

---

---

트라이 파이썬 딕셔너리로 구현하기

class Trie:
    def __init__(self):
        self.root = {}
        self.isEndOfWord = False

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node[self.isEndOfWord] = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.isEndOfWord in node

    def startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True