Xử lý chuỗi (String Algorithms)
Trie cho autocomplete/prefix search, và các thuật toán tìm kiếm chuỗi con hiệu quả hơn brute-force.
Xử lý văn bản xuất hiện ở khắp nơi trong hệ thống thực tế: tìm kiếm, autocomplete, kiểm tra trùng lặp, xử lý log. Thuật toán "brute-force" cho tìm kiếm chuỗi thường đủ dùng, nhưng hiểu các kỹ thuật hiệu quả hơn giúp bạn nhận diện đúng khi nào hệ thống thực sự cần chúng.
🎯 Mục tiêu học tập
- Triển khai Trie (Prefix Tree) và ứng dụng cho autocomplete
- Hiểu vấn đề độ phức tạp của tìm kiếm chuỗi con brute-force
- Nắm ý tưởng cốt lõi của thuật toán tìm kiếm chuỗi hiệu quả (KMP) ở mức khái niệm
- Nhận diện đúng bài toán xử lý chuỗi trong hệ thống thực tế và chọn công cụ phù hợp
Trie (Prefix Tree) — cấu trúc chuyên biệt cho tiền tố
Trie là cây trong đó mỗi node đại diện cho 1 ký tự, đường đi từ root đến 1 node đại diện cho 1 tiền tố (prefix) của các từ đã lưu — các từ có chung tiền tố chia sẻ chung đường đi trong cây, giúp tra cứu/tìm theo tiền tố cực kỳ hiệu quả:
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: str):
node = self.root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.is_end_of_word = True
def starts_with(self, prefix: str) -> bool: # nền tảng cho autocomplete
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
Độ phức tạp tra cứu/thêm chỉ phụ thuộc độ dài từ (O(L)), không phụ thuộc số lượng từ đã lưu — nhanh hơn nhiều so với duyệt qua danh sách từ và so sánh prefix từng cái một (O(N×L)). Ứng dụng trực tiếp: autocomplete/gợi ý tìm kiếm, kiểm tra chính tả, và IP routing table (tìm route khớp tiền tố dài nhất — longest prefix match).
Tìm kiếm Chuỗi con — vấn đề của Brute-Force
def tim_brute_force(text: str, pattern: str) -> int:
n, m = len(text), len(pattern)
for i in range(n - m + 1):
if text[i:i+m] == pattern: # so sánh O(m) tại mỗi vị trí
return i
return -1
# Độ phức tạp: O(n × m) trường hợp xấu nhất
Với văn bản dài (n lớn) và pattern dài (m lớn), brute-force có thể chậm đáng kể trong trường hợp xấu (ví dụ text toàn ký tự lặp lại gần giống pattern). Trong thực tế, với hầu hết bài toán tìm kiếm văn bản thông thường (kích thước vừa phải), brute-force vẫn đủ nhanh — chỉ cần quan tâm thuật toán hiệu quả hơn khi xử lý văn bản cực lớn hoặc tìm kiếm lặp lại rất nhiều lần.
KMP (Knuth-Morris-Pratt) — ý tưởng cốt lõi
KMP cải thiện brute-force bằng 1 quan sát quan trọng: khi so khớp thất bại giữa chừng, brute-force "quên hết" và bắt đầu lại từ đầu — nhưng thực ra đã biết một phần thông tin về những ký tự đã so khớp trước đó. KMP tiền xử lý pattern để xây bảng "longest proper prefix which is also suffix" (LPS), cho phép "nhảy" thông minh thay vì lùi lại từ đầu mỗi lần thất bại — đạt độ phức tạp O(n + m), tuyến tính thay vì O(n×m).
Không cần tự cài đặt KMP trong công việc thực tế — hầu hết ngôn ngữ/thư viện (regex engine, hàm tìm kiếm chuỗi built-in) đã tối ưu sẵn bên dưới. Điều quan trọng là hiểu ý tưởng (dùng thông tin đã biết để tránh làm lại từ đầu) — nguyên lý tối ưu hoá xuất hiện lặp đi lặp lại trong nhiều thuật toán khác (bao gồm cả Memoization ở Module 8).
🏋️ Bài tập thực hành
Triển khai đầy đủ Trie hỗ trợ insert và 1 hàm autocomplete: cho 1 tiền tố, trả về tất cả từ trong Trie bắt đầu bằng tiền tố đó (dùng DFS từ node tương ứng với tiền tố — liên hệ Module 9). Nạp vào Trie 1 danh sách vài nghìn từ tiếng Việt/Anh, đo thời gian autocomplete cho 1 tiền tố và so sánh với cách "ngây thơ" duyệt toàn bộ danh sách kiểm tra từng từ có bắt đầu bằng tiền tố không.
📚 Tài nguyên học tập
-
VisuAlgo — TrieTrực quan hoá tương tác TrieTool
-
GeeksforGeeks — KMP AlgorithmGiải thích chi tiết thuật toán KMPBài viết
✅ Tự đánh giá hoàn thành
- Triển khai đúng Trie với insert và tra cứu theo tiền tố
- Giải quyết được bài toán autocomplete bằng Trie, đo được cải thiện hiệu năng
- Giải thích được độ phức tạp O(n×m) của tìm kiếm chuỗi brute-force
- Nắm được ý tưởng cốt lõi của KMP (dù không cần tự triển khai trong thực tế)