Trie (Prefix Tree) - The Autocomplete Engine

"Trie là nền tảng của mọi hệ thống gợi ý." - HPN

Định nghĩa

Trie (đọc là "try", từ reTRIEval) là cấu trúc dữ liệu dạng cây, trong đó:

Mỗi node đại diện cho một ký tự
Mỗi path từ root đến node đại diện cho một prefix
Các từ có chung prefix sẽ chia sẻ đường đi

📘 Automaton Theory

Trie thực chất là một Deterministic Finite Automaton (DFA) cho bài toán prefix matching. Mỗi state (node) chuyển sang state khác dựa trên input character.

Tại sao cần Trie? (The Why)

So sánh với HashMap

Thao tác	HashMap	Trie
Insert	$O (L)$ hash	$O (L)$
Search exact	$O (L)$ hash	$O (L)$
Prefix search	$O (N \times L)$ ❌	$O (L + K)$ ✅
Autocomplete	Không hỗ trợ	Native
Memory	Tốt hơn	Kém hơn

Với $L$ = độ dài từ, $N$ = số từ trong dictionary, $K$ = số kết quả.

🎯 INSIGHT QUAN TRỌNG

HashMap KHÔNG THỂ tìm kiếm prefix hiệu quả. Bạn phải duyệt TẤT CẢ keys để tìm những từ bắt đầu bằng "hel". Trie chỉ cần đi theo path h → e → l, sau đó DFS từ đó.

Mô hình hóa

Cấu trúc Trie với words: ["HPN", "HPC", "HERO"]

Quan sát:

HPN và HPC chia sẻ prefix HP
Dấu ✓ đánh dấu end of word
Tổng cộng 7 nodes thay vì 9 ký tự (tiết kiệm nhờ shared prefix)

Cơ chế Hoạt động

Insert Operation

Insert "HPN":
1. Start at ROOT
2. 'H' không tồn tại → Tạo node 'H'
3. 'P' không tồn tại → Tạo node 'P' dưới 'H'
4. 'N' không tồn tại → Tạo node 'N' dưới 'P'
5. Đánh dấu 'N' là end_of_word = True

Search Operation

Search "HPC":
1. Start at ROOT
2. 'H' tồn tại → Di chuyển đến 'H'
3. 'P' tồn tại → Di chuyển đến 'P'  
4. 'C' tồn tại → Di chuyển đến 'C'
5. Check end_of_word → True → FOUND!

Prefix Search (Autocomplete)

Autocomplete "HP":
1. Navigate to node 'P' (sau "HP")
2. DFS từ 'P' để thu thập tất cả words
3. Return: ["HPN", "HPC"]

Production Implementation

python

# HPN Engineering Standard
# Implementation: Trie với Autocomplete Support

from typing import List, Optional, Dict
from collections import deque


class TrieNode:
    """
    Node trong Trie structure.
    
    Memory Optimization: Sử dụng __slots__ để giảm 40% memory overhead
    so với dict-based attributes.
    """
    __slots__ = ('children', 'is_end_of_word', 'frequency')
    
    def __init__(self) -> None:
        self.children: Dict[str, 'TrieNode'] = {}
        self.is_end_of_word: bool = False
        # Frequency tracking cho ranking autocomplete results
        self.frequency: int = 0


class Trie:
    """
    Production-ready Trie với Autocomplete support.
    
    Features:
    - O(L) insert/search/delete
    - Top-N autocomplete với frequency ranking
    - Case-insensitive option
    - Memory-optimized với __slots__
    
    Industry Usage:
    - ElasticSearch (Inverted Index)
    - Mobile keyboard suggestions
    - IDE autocompletion
    """
    
    def __init__(self, case_insensitive: bool = True) -> None:
        self.root = TrieNode()
        self.case_insensitive = case_insensitive
        self._word_count = 0
    
    def _normalize(self, word: str) -> str:
        """Normalize input based on case sensitivity setting."""
        return word.lower() if self.case_insensitive else word
    
    def insert(self, word: str, frequency: int = 1) -> None:
        """
        Insert word vào Trie.
        
        Args:
            word: Từ cần insert
            frequency: Tần suất xuất hiện (cho ranking)
            
        Time: O(L) với L = len(word)
        Space: O(L) worst case (từ mới hoàn toàn)
        
        Edge Cases:
            - Empty string: Bỏ qua, không insert
            - Duplicate: Cộng dồn frequency
        """
        if not word:  # Edge case: empty string
            return
            
        word = self._normalize(word)
        current = self.root
        
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        
        # Nếu là từ mới, tăng word count
        if not current.is_end_of_word:
            self._word_count += 1
            
        current.is_end_of_word = True
        current.frequency += frequency  # Accumulate frequency
    
    def search(self, word: str) -> bool:
        """
        Tìm kiếm exact match.
        
        Time: O(L)
        
        Returns:
            True nếu word tồn tại trong Trie
        """
        if not word:  # Edge case: empty string
            return False
            
        node = self._find_node(word)
        return node is not None and node.is_end_of_word
    
    def starts_with(self, prefix: str) -> bool:
        """
        Kiểm tra có từ nào bắt đầu bằng prefix không.
        
        Time: O(L) với L = len(prefix)
        """
        if not prefix:  # Empty prefix matches everything
            return self._word_count > 0
            
        return self._find_node(prefix) is not None
    
    def autocomplete(self, prefix: str, top_n: int = 10) -> List[str]:
        """
        Trả về top N gợi ý cho prefix, sắp xếp theo frequency.
        
        Args:
            prefix: Prefix cần autocomplete
            top_n: Số lượng kết quả tối đa
            
        Returns:
            List các từ match, sorted by frequency (descending)
            
        Time: O(L + K) với K = số từ có prefix này
        
        Example:
            >>> trie.insert("hello", frequency=100)
            >>> trie.insert("help", frequency=50)
            >>> trie.autocomplete("hel", top_n=2)
            ['hello', 'help']  # Sorted by frequency
        """
        if not prefix:
            # Edge case: empty prefix -> return top frequent words
            prefix = ""
            prefix_node = self.root
        else:
            prefix = self._normalize(prefix)
            prefix_node = self._find_node(prefix)
        
        if prefix_node is None:
            return []
        
        # DFS để thu thập tất cả words từ prefix_node
        results: List[tuple] = []  # (frequency, word)
        self._dfs_collect(prefix_node, prefix, results)
        
        # Sort by frequency (descending), lấy top N
        results.sort(key=lambda x: -x[0])
        return [word for _, word in results[:top_n]]
    
    def delete(self, word: str) -> bool:
        """
        Xóa word khỏi Trie.
        
        Chiến lược: Chỉ unmark is_end_of_word, không xóa nodes
        (tránh phức tạp và vẫn đảm bảo correctness)
        
        Returns:
            True nếu word tồn tại và đã xóa
        """
        if not word:
            return False
            
        node = self._find_node(word)
        if node is None or not node.is_end_of_word:
            return False
        
        node.is_end_of_word = False
        node.frequency = 0
        self._word_count -= 1
        return True
    
    def _find_node(self, prefix: str) -> Optional[TrieNode]:
        """Navigate to node representing prefix."""
        prefix = self._normalize(prefix)
        current = self.root
        
        for char in prefix:
            if char not in current.children:
                return None
            current = current.children[char]
        
        return current
    
    def _dfs_collect(
        self, 
        node: TrieNode, 
        current_word: str, 
        results: List[tuple]
    ) -> None:
        """DFS helper để thu thập tất cả words từ node."""
        if node.is_end_of_word:
            results.append((node.frequency, current_word))
        
        for char, child_node in node.children.items():
            self._dfs_collect(child_node, current_word + char, results)
    
    @property
    def size(self) -> int:
        """Số lượng words trong Trie."""
        return self._word_count


# ============================================
# USAGE EXAMPLE
# ============================================
if __name__ == "__main__":
    # Initialize
    trie = Trie(case_insensitive=True)
    
    # Insert với frequency (từ search logs)
    trie.insert("python", frequency=1000)
    trie.insert("pytorch", frequency=500)
    trie.insert("pandas", frequency=800)
    trie.insert("pip", frequency=200)
    
    # Exact search
    print(trie.search("python"))      # True
    print(trie.search("pythonic"))    # False
    
    # Autocomplete
    suggestions = trie.autocomplete("py", top_n=3)
    print(suggestions)  # ['python', 'pytorch'] - sorted by frequency
    
    # Prefix check
    print(trie.starts_with("pan"))    # True
    print(trie.starts_with("java"))   # False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

Deep Dive: Space Complexity

The Memory Trade-off

Worst Case: Mỗi word không share prefix nào

$N$ words, mỗi word dài $L$
Space: $O (N \times L \times ALPHABET_SIZE)$

Với ALPHABET_SIZE = 26 (lowercase letters):

Mỗi TrieNode chứa:
- Dict với tối đa 26 child pointers: ~26 × 8 bytes = 208 bytes
- is_end_of_word: 1 byte
- frequency: 8 bytes
≈ 220 bytes/node (worst case)

⚠️ MEMORY WARNING

Với 1 triệu từ, mỗi từ 10 ký tự, worst case: 10 triệu nodes × 220 bytes = 2.2 GB RAM

Đây là lý do Trie thường được dùng với data có high prefix overlap (URLs, IP addresses, dictionary words).

Memory Optimization Techniques

Technique	Description	Savings
`__slots__`	Loại bỏ instance `__dict__`	~40%
Compressed Trie	Gộp nodes có 1 child	Variable
Array thay Dict	Fixed alphabet size	~30%
LOUDS encoding	Succinct data structure	~95%

Độ phức tạp Tổng hợp

Operation	Time	Space (auxiliary)
Insert	$O (L)$	$O (L)$ worst
Search	$O (L)$	$O (1)$
Delete	$O (L)$	$O (1)$
Autocomplete	$O (L + K)$	$O (K)$
Build Trie	$O (N \times L)$	$O (N \times L)$

Với:

$L$ = độ dài từ
$K$ = số kết quả autocomplete
$N$ = số từ trong dictionary

Ứng dụng Thực tế

1. ElasticSearch - Inverted Index

ElasticSearch sử dụng FST (Finite State Transducer) - một dạng compressed Trie - để lưu inverted index:

"python" → [doc1, doc5, doc7]
"pytorch" → [doc2, doc5]

2. Mobile Keyboard Suggestions

Gboard, SwiftKey sử dụng Trie kết hợp với:

Frequency data từ user typing history
Language model để rank suggestions

3. IP Routing Tables

Routers sử dụng Patricia Trie để match longest prefix:

192.168.1.0/24 → Interface 1
192.168.0.0/16 → Interface 2

Anti-patterns (Cạm bẫy)

❌ SAI LẦM PHỔ BIẾN

1. Dùng Trie cho dataset nhỏ

python

# ❌ WRONG: 100 words, dùng Trie làm gì?
trie = Trie()
for word in small_list:  # 100 words
    trie.insert(word)

# ✅ RIGHT: Dùng set + list comprehension
suggestions = [w for w in words if w.startswith(prefix)]

2. Không xem xét memory footprint

python

# ❌ WRONG: Insert 10 triệu random UUIDs
for uuid in generate_random_uuids(10_000_000):
    trie.insert(uuid)  # Mỗi UUID unique → No shared prefix → BOOM

# ✅ RIGHT: Dùng Bloom Filter hoặc Hash-based approach

3. Quên normalize input

python

# ❌ WRONG: Case-sensitive khi không cần
trie.insert("Python")
trie.search("python")  # False! User sẽ confused

# ✅ RIGHT: Normalize trong constructor
trie = Trie(case_insensitive=True)

Khi nào KHÔNG dùng Trie?

Điều kiện	Alternative
Dataset < 1000 items	`list` + `startswith()`
Không cần prefix search	`set` hoặc `dict`
Memory-constrained	Bloom Filter hoặc Hash
Random strings (no shared prefix)	HashMap

💡 HPN's Golden Rule

"Trie sáng giá khi data có PREFIX LOCALITY." Ví dụ: Dictionary words, URLs, IP addresses, file paths.

Trie (Prefix Tree) - The Autocomplete Engine ​

Định nghĩa ​

Tại sao cần Trie? (The Why) ​

So sánh với HashMap ​

Mô hình hóa ​

Cấu trúc Trie với words: ["HPN", "HPC", "HERO"] ​

Cơ chế Hoạt động ​

Insert Operation ​

Search Operation ​

Prefix Search (Autocomplete) ​

Production Implementation ​

Deep Dive: Space Complexity ​

The Memory Trade-off ​

Memory Optimization Techniques ​

Độ phức tạp Tổng hợp ​

Ứng dụng Thực tế ​

1. ElasticSearch - Inverted Index ​

2. Mobile Keyboard Suggestions ​

3. IP Routing Tables ​

Anti-patterns (Cạm bẫy) ​

Khi nào KHÔNG dùng Trie? ​

Trie (Prefix Tree) - The Autocomplete Engine

Định nghĩa

Tại sao cần Trie? (The Why)

So sánh với HashMap

Mô hình hóa

Cấu trúc Trie với words: ["HPN", "HPC", "HERO"]

Cơ chế Hoạt động

Insert Operation

Search Operation

Prefix Search (Autocomplete)

Production Implementation

Deep Dive: Space Complexity

The Memory Trade-off

Memory Optimization Techniques

Độ phức tạp Tổng hợp

Ứng dụng Thực tế

1. ElasticSearch - Inverted Index

2. Mobile Keyboard Suggestions

3. IP Routing Tables

Anti-patterns (Cạm bẫy)

Khi nào KHÔNG dùng Trie?