349 lines
10 KiB
Python
349 lines
10 KiB
Python
"""
|
|
GIẢI THÍCH: Logic "Gõ không dấu" trong Trie
|
|
============================================
|
|
|
|
Câu hỏi: Làm thế nào để user gõ "lam sach" vẫn tìm ra "làm sạch"?
|
|
"""
|
|
|
|
import sys
|
|
sys.path.append('src')
|
|
|
|
import unicodedata
|
|
from search.trie import Trie
|
|
|
|
|
|
def explain_normalize():
|
|
"""Giải thích chi tiết hàm _normalize()"""
|
|
|
|
print("=" * 80)
|
|
print("LOGIC: GỠ KHÔNG DẤU (NORMALIZE)")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
CÂU HỎI:
|
|
--------
|
|
User gõ: "lam sach" (không dấu)
|
|
Document: "làm sạch" (có dấu)
|
|
|
|
→ Làm sao tìm được?
|
|
|
|
|
|
GIẢI PHÁP: NORMALIZE CẢ 2 BÊN
|
|
------------------------------
|
|
1. Khi INSERT: Bỏ dấu document trước khi lưu vào Trie
|
|
2. Khi SEARCH: Bỏ dấu query trước khi tìm
|
|
|
|
→ Cả 2 đều thành "lam sach" → MATCH!
|
|
|
|
|
|
HÀM _normalize() LÀM GÌ?
|
|
-------------------------
|
|
Input: "Làm sạch WC"
|
|
Output: "lam sach wc"
|
|
|
|
Steps:
|
|
1. NFD Normalization: Tách dấu ra khỏi chữ
|
|
"à" → "a" + "̀" (dấu huyền riêng)
|
|
|
|
2. Loại bỏ dấu: Xóa các ký tự dấu (category = 'Mn')
|
|
"a" + "̀" → "a"
|
|
|
|
3. Lowercase: Chuyển về chữ thường
|
|
"LAM" → "lam"
|
|
""")
|
|
|
|
input("\nNhấn Enter để xem demo code...\n")
|
|
|
|
|
|
def demo_normalize_step_by_step():
|
|
"""Demo từng bước của normalize"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("DEMO: TỪNG BƯỚC NORMALIZE")
|
|
print("=" * 80)
|
|
|
|
text = "Làm sạch WC"
|
|
print(f"\n📝 Text gốc: '{text}'")
|
|
print(f" Unicode: {[f'{c}(U+{ord(c):04X})' for c in text]}")
|
|
|
|
# Bước 1: NFD Normalization
|
|
print("\n" + "-" * 80)
|
|
print("BƯỚC 1: NFD NORMALIZATION (Tách dấu)")
|
|
print("-" * 80)
|
|
|
|
nfd_text = unicodedata.normalize('NFD', text)
|
|
print(f"Kết quả: '{nfd_text}'")
|
|
print(f"Unicode: {[f'{c}(U+{ord(c):04X})' for c in nfd_text]}")
|
|
print("\n💡 Giải thích:")
|
|
print(" - 'à' (U+00E0) → 'a' (U+0061) + '̀' (U+0300)")
|
|
print(" - 'ạ' (U+1EA1) → 'a' (U+0061) + '̣' (U+0323)")
|
|
print(" - Dấu giờ là ký tự RIÊNG, dễ loại bỏ!")
|
|
|
|
# Bước 2: Loại bỏ dấu
|
|
print("\n" + "-" * 80)
|
|
print("BƯỚC 2: LOẠI BỎ DẤU (Remove Marks)")
|
|
print("-" * 80)
|
|
|
|
no_marks = ''.join(
|
|
char for char in nfd_text
|
|
if unicodedata.category(char) != 'Mn' # Mn = Mark, Nonspacing
|
|
)
|
|
print(f"Kết quả: '{no_marks}'")
|
|
print(f"Unicode: {[f'{c}(U+{ord(c):04X})' for c in no_marks]}")
|
|
print("\n💡 Giải thích:")
|
|
print(" - Loại bỏ tất cả ký tự có category = 'Mn'")
|
|
print(" - 'Mn' = Mark, Nonspacing (dấu thanh, dấu sắc, huyền...)")
|
|
print(" - Chỉ giữ lại chữ cái thuần")
|
|
|
|
# Bước 3: Lowercase
|
|
print("\n" + "-" * 80)
|
|
print("BƯỚC 3: LOWERCASE")
|
|
print("-" * 80)
|
|
|
|
final = no_marks.lower()
|
|
print(f"Kết quả: '{final}'")
|
|
print("\n💡 Giải thích:")
|
|
print(" - Chuyển về chữ thường để không phân biệt hoa/thường")
|
|
|
|
print("\n" + "=" * 80)
|
|
print(f"✅ KẾT QUẢ CUỐI: '{text}' → '{final}'")
|
|
print("=" * 80)
|
|
|
|
input("\nNhấn Enter tiếp...\n")
|
|
|
|
|
|
def demo_unicode_categories():
|
|
"""Demo các Unicode categories"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("UNICODE CATEGORIES (Quan trọng!)")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
UNICODE CATEGORY LÀ GÌ?
|
|
------------------------
|
|
Mỗi ký tự Unicode có 1 category (loại):
|
|
- Lu: Letter, Uppercase (A, B, C)
|
|
- Ll: Letter, Lowercase (a, b, c)
|
|
- Mn: Mark, Nonspacing (dấu sắc, huyền, hỏi...)
|
|
- Zs: Separator, Space (khoảng trắng)
|
|
- Po: Punctuation, Other (., !, ?)
|
|
- ...
|
|
|
|
→ Ta chỉ cần loại bỏ 'Mn' để bỏ dấu!
|
|
""")
|
|
|
|
# Demo các ký tự
|
|
test_chars = [
|
|
('a', 'Chữ a thường'),
|
|
('à', 'Chữ à có dấu huyền (1 ký tự)'),
|
|
('̀', 'Dấu huyền riêng (sau NFD)'),
|
|
('ạ', 'Chữ a dấu nặng'),
|
|
('̣', 'Dấu nặng riêng (sau NFD)'),
|
|
(' ', 'Khoảng trắng'),
|
|
('!', 'Dấu chấm than'),
|
|
]
|
|
|
|
print("\n📋 TABLE: Ký tự và Category")
|
|
print("-" * 80)
|
|
print(f"{'Ký tự':<10} {'Unicode':<15} {'Category':<10} {'Mô tả'}")
|
|
print("-" * 80)
|
|
|
|
for char, desc in test_chars:
|
|
if char in ['̀', '̣']: # Dấu cần NFD trước
|
|
display = f"'{char}'"
|
|
else:
|
|
# NFD để xem dấu
|
|
nfd_char = unicodedata.normalize('NFD', char)
|
|
if len(nfd_char) > 1:
|
|
# Có dấu riêng
|
|
base = nfd_char[0]
|
|
mark = nfd_char[1]
|
|
category_base = unicodedata.category(base)
|
|
category_mark = unicodedata.category(mark)
|
|
print(f"'{char}' U+{ord(char):04X} {category_base} {desc}")
|
|
print(f" └─ '{mark}' U+{ord(mark):04X} {category_mark} (dấu riêng)")
|
|
continue
|
|
|
|
code = ord(char)
|
|
category = unicodedata.category(char)
|
|
print(f"'{char}' U+{code:04X} {category} {desc}")
|
|
|
|
print("\n💡 QUAN TRỌNG:")
|
|
print(" - Category 'Mn' = Mark, Nonspacing = DẤU")
|
|
print(" - Loại bỏ 'Mn' = Bỏ dấu!")
|
|
|
|
input("\nNhấn Enter tiếp...\n")
|
|
|
|
|
|
def demo_insert_and_search_flow():
|
|
"""Demo flow INSERT và SEARCH với normalize"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("FLOW: INSERT VÀ SEARCH VỚI NORMALIZE")
|
|
print("=" * 80)
|
|
|
|
trie = Trie(max_results=10)
|
|
|
|
# INSERT
|
|
print("\n📥 INSERT: Thêm 'Làm sạch WC'")
|
|
print("-" * 80)
|
|
|
|
original = "Làm sạch WC"
|
|
print(f"1. Text gốc: '{original}'")
|
|
|
|
# Normalize
|
|
normalized = unicodedata.normalize('NFD', original)
|
|
normalized = ''.join(c for c in normalized if unicodedata.category(c) != 'Mn')
|
|
normalized = normalized.lower()
|
|
|
|
print(f"2. Sau normalize: '{normalized}'")
|
|
print(f"3. Lưu vào Trie: '{normalized}'")
|
|
|
|
# Thực tế insert
|
|
trie.insert(original, doc_id=0, score=1.0, index_word_starts=True, normalize=True)
|
|
print(f"4. ✓ Đã insert vào Trie")
|
|
|
|
# SEARCH
|
|
print("\n\n🔍 SEARCH: User gõ 'lam' (không dấu)")
|
|
print("-" * 80)
|
|
|
|
query = "lam"
|
|
print(f"1. Query gốc: '{query}'")
|
|
print(f"2. Sau normalize: '{query}' (đã không dấu từ đầu)")
|
|
print(f"3. Tìm trong Trie với prefix: '{query}'")
|
|
|
|
results = trie.search_prefix(query, normalize=True)
|
|
|
|
if results:
|
|
print(f"4. ✓ Tìm thấy {len(results)} kết quả:")
|
|
for doc_id, score in results:
|
|
print(f" [{doc_id}] (score: {score})")
|
|
|
|
print("\n💡 TẠI SAO TÌM ĐƯỢC?")
|
|
print("-" * 80)
|
|
print(f" - Document trong Trie: 'lam sach wc'")
|
|
print(f" - Query search: 'lam'")
|
|
print(f" - 'lam sach wc'.startswith('lam') = True")
|
|
print(f" → MATCH!")
|
|
|
|
input("\nNhấn Enter để xem code...\n")
|
|
|
|
|
|
def show_code():
|
|
"""Hiển thị code thực tế"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("CODE THỰC TẾ TRONG trie.py")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
def _normalize(self, text: str) -> str:
|
|
\"\"\"
|
|
Normalize text: Bỏ dấu tiếng Việt
|
|
|
|
Example:
|
|
>>> self._normalize("Làm sạch WC")
|
|
"lam sach wc"
|
|
\"\"\"
|
|
# BƯỚC 1: NFD - Tách dấu ra khỏi chữ
|
|
text = unicodedata.normalize('NFD', text)
|
|
|
|
# BƯỚC 2: Loại bỏ dấu (category = 'Mn')
|
|
text = ''.join(
|
|
char for char in text
|
|
if unicodedata.category(char) != 'Mn' # ← KEY LINE!
|
|
)
|
|
|
|
# BƯỚC 3: Lowercase
|
|
return text.lower()
|
|
|
|
|
|
def insert(self, text, doc_id, normalize=True, ...):
|
|
if normalize:
|
|
text = self._normalize(text) # ← Normalize trước khi insert
|
|
|
|
# ... insert vào Trie
|
|
|
|
|
|
def search_prefix(self, prefix, normalize=True):
|
|
if normalize:
|
|
prefix = self._normalize(prefix) # ← Normalize trước khi search
|
|
|
|
# ... search trong Trie
|
|
""")
|
|
|
|
print("\n💡 KEY POINTS:")
|
|
print("-" * 80)
|
|
print("1. Normalize CẢ INSERT và SEARCH")
|
|
print("2. Dùng NFD để tách dấu")
|
|
print("3. Loại bỏ category 'Mn' (Mark, Nonspacing)")
|
|
print("4. Lowercase để không phân biệt hoa/thường")
|
|
|
|
input("\nNhấn Enter để xem kết luận...\n")
|
|
|
|
|
|
def conclusion():
|
|
"""Kết luận"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("📝 KẾT LUẬN")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
✅ LOGIC "GỠ KHÔNG DẤU":
|
|
-------------------------
|
|
1. INSERT: Normalize text trước khi lưu
|
|
"Làm sạch" → "lam sach"
|
|
|
|
2. SEARCH: Normalize query trước khi tìm
|
|
"lam" → "lam" (đã không dấu)
|
|
|
|
3. MATCH: Prefix matching trên text đã normalize
|
|
"lam sach".startswith("lam") = True
|
|
|
|
|
|
🔑 KEY: unicodedata.category(char) != 'Mn'
|
|
------------------------------------------
|
|
- 'Mn' = Mark, Nonspacing = DẤU thanh
|
|
- Loại bỏ 'Mn' = Bỏ dấu tiếng Việt
|
|
- NFD trước để tách dấu thành ký tự riêng
|
|
|
|
|
|
📊 COMPLEXITY:
|
|
--------------
|
|
- Normalize: O(n) với n = độ dài text
|
|
- Không ảnh hưởng đến performance của Trie
|
|
- Chỉ chạy 1 lần khi insert/search
|
|
|
|
|
|
🎯 LỢI ÍCH:
|
|
------------
|
|
✓ User gõ linh hoạt: có dấu hoặc không dấu
|
|
✓ Không cần 2 index riêng
|
|
✓ Memory hiệu quả
|
|
✓ UX tốt hơn (user không cần gõ dấu)
|
|
|
|
|
|
⚠️ TRADE-OFF:
|
|
--------------
|
|
- Mất thông tin dấu gốc
|
|
- Cần giữ document gốc riêng (có dấu)
|
|
- "lam" sẽ match cả "làm", "lạm", "lãm"...
|
|
(nhưng OK cho search autocomplete)
|
|
""")
|
|
|
|
print("=" * 80)
|
|
print("\n✅ Hiểu rồi chứ? Logic đơn giản nhưng hiệu quả!")
|
|
print("📂 Code: src/search/trie.py → _normalize()")
|
|
print("🔑 Key: unicodedata.category(char) != 'Mn'\n")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
explain_normalize()
|
|
demo_normalize_step_by_step()
|
|
demo_unicode_categories()
|
|
demo_insert_and_search_flow()
|
|
show_code()
|
|
conclusion()
|