254 lines
7.6 KiB
Python
254 lines
7.6 KiB
Python
"""
|
|
TEST: Production-ready Trie với Word-Start Indexing
|
|
====================================================
|
|
|
|
Demo các tính năng mới:
|
|
1. Word-start indexing: Tìm keyword ở giữa câu
|
|
2. Top-K limiting: Performance ổn định
|
|
3. Normalize: Bỏ dấu tiếng Việt
|
|
"""
|
|
|
|
import sys
|
|
sys.path.append('src')
|
|
|
|
from search.trie import Trie
|
|
|
|
|
|
def demo_word_start_indexing():
|
|
"""Demo tính năng chính: Word-start indexing"""
|
|
|
|
print("=" * 80)
|
|
print("DEMO: WORD-START INDEXING")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
WORD-START INDEXING LÀ GÌ?
|
|
---------------------------
|
|
Thay vì chỉ index nguyên câu, ta index TẤT CẢ các phrase bắt đầu từ mỗi từ.
|
|
|
|
Ví dụ: "làm sạch nhà vệ sinh"
|
|
|
|
Index thành:
|
|
✓ "làm sạch nhà vệ sinh" ← Prefix: làm
|
|
✓ "sạch nhà vệ sinh" ← Prefix: sạch
|
|
✓ "nhà vệ sinh" ← Prefix: nhà
|
|
✓ "vệ sinh" ← Prefix: vệ
|
|
|
|
→ User gõ "nhà" hoặc "vệ" vẫn tìm được câu gốc!
|
|
""")
|
|
|
|
input("Nhấn Enter để xem demo...\n")
|
|
|
|
# Tạo Trie với max_results=10
|
|
trie = Trie(max_results=10)
|
|
|
|
# Dữ liệu test
|
|
documents = [
|
|
("làm sạch nhà vệ sinh", 0, 1.0),
|
|
("làm sạch văn phòng", 1, 0.9),
|
|
("lau kính cửa sổ", 2, 0.8),
|
|
("vệ sinh toilet", 3, 0.85),
|
|
]
|
|
|
|
print("📥 BƯỚC 1: THÊM DOCUMENTS VỚI WORD-START INDEXING")
|
|
print("-" * 80)
|
|
|
|
for text, doc_id, score in documents:
|
|
trie.insert(text, doc_id, score=score, index_word_starts=True)
|
|
print(f"✓ [{doc_id}] {text} (score: {score})")
|
|
|
|
print("\n🔍 BƯỚC 2: TEST TÌM KIẾM")
|
|
print("-" * 80)
|
|
|
|
test_cases = [
|
|
("làm", "Prefix match - bình thường"),
|
|
("sạch", "Word-start match - tìm ở GIỮA câu!"),
|
|
("nhà", "Word-start match - tìm ở GIỮA câu!"),
|
|
("vệ", "Word-start match - tìm 2 documents!"),
|
|
("vệ s", "Chính xác hơn"),
|
|
]
|
|
|
|
for query, description in test_cases:
|
|
print(f"\n🔎 Query: '{query}'")
|
|
print(f" ({description})")
|
|
|
|
results = trie.search_prefix(query)
|
|
|
|
if results:
|
|
print(f" ✓ Tìm thấy {len(results)} kết quả:")
|
|
for doc_id, score in results:
|
|
print(f" [{doc_id}] {documents[doc_id][0]} (score: {score:.2f})")
|
|
else:
|
|
print(f" ✗ Không tìm thấy")
|
|
|
|
input("\n\nNhấn Enter tiếp...\n")
|
|
|
|
|
|
def demo_normalize():
|
|
"""Demo normalize tiếng Việt"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("DEMO: NORMALIZE - BỎ DẤU TIẾNG VIỆT")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
NORMALIZE LÀ GÌ?
|
|
----------------
|
|
Chuyển text về dạng không dấu để user có thể gõ linh hoạt.
|
|
|
|
Ví dụ:
|
|
- User gõ: "lam sach" (không dấu)
|
|
- Vẫn tìm ra: "làm sạch" (có dấu)
|
|
""")
|
|
|
|
trie = Trie(max_results=10)
|
|
|
|
# Thêm documents với normalize=True (mặc định)
|
|
trie.insert("làm sạch nhà vệ sinh", 0, score=1.0, index_word_starts=True, normalize=True)
|
|
trie.insert("lau kính cửa sổ", 1, score=0.9, index_word_starts=True, normalize=True)
|
|
|
|
print("\n📥 Đã thêm documents (với normalize)")
|
|
print("-" * 80)
|
|
print("[0] làm sạch nhà vệ sinh")
|
|
print("[1] lau kính cửa sổ")
|
|
|
|
print("\n🔍 TEST: Gõ KHÔNG DẤU")
|
|
print("-" * 80)
|
|
|
|
test_queries = [
|
|
("lam", "Gõ không dấu 'lam'"),
|
|
("lam sach", "Gõ không dấu 'lam sach'"),
|
|
("ve sinh", "Gõ không dấu 've sinh'"),
|
|
("kinh", "Gõ không dấu 'kinh'"),
|
|
]
|
|
|
|
for query, description in test_queries:
|
|
print(f"\n🔎 Query: '{query}' ({description})")
|
|
results = trie.search_prefix(query, normalize=True)
|
|
|
|
if results:
|
|
print(f" ✓ Tìm thấy {len(results)} kết quả:")
|
|
for doc_id, score in results:
|
|
doc_text = ["làm sạch nhà vệ sinh", "lau kính cửa sổ"][doc_id]
|
|
print(f" [{doc_id}] {doc_text}")
|
|
else:
|
|
print(f" ✗ Không tìm thấy")
|
|
|
|
input("\n\nNhấn Enter tiếp...\n")
|
|
|
|
|
|
def demo_top_k_performance():
|
|
"""Demo Top-K limiting cho performance"""
|
|
|
|
print("\n" + "=" * 80)
|
|
print("DEMO: TOP-K LIMITING - PERFORMANCE")
|
|
print("=" * 80)
|
|
|
|
print("""
|
|
TOP-K LIMITING LÀ GÌ?
|
|
---------------------
|
|
Mỗi node trong Trie lưu sẵn TOP K documents phổ biến nhất.
|
|
|
|
Lợi ích:
|
|
✓ Search chỉ mất O(m) - độ dài prefix
|
|
✓ KHÔNG cần DFS toàn bộ subtree
|
|
✓ Performance ổn định dù có hàng ngàn kết quả
|
|
|
|
Ví dụ: max_results=3
|
|
- Node sẽ cache 3 documents có score cao nhất
|
|
- Search trả về ngay từ cache
|
|
""")
|
|
|
|
trie = Trie(max_results=3) # Chỉ giữ top 3
|
|
|
|
# Thêm nhiều documents với "làm"
|
|
docs = [
|
|
("làm sạch wc", 0, 1.0),
|
|
("làm sạch phòng", 1, 0.9),
|
|
("làm sạch nhà", 2, 0.8),
|
|
("làm sạch xe", 3, 0.7),
|
|
("làm sạch văn phòng", 4, 0.6),
|
|
]
|
|
|
|
print("\n📥 Thêm 5 documents với prefix 'làm'")
|
|
print("-" * 80)
|
|
for text, doc_id, score in docs:
|
|
trie.insert(text, doc_id, score=score, index_word_starts=False)
|
|
print(f"[{doc_id}] {text} (score: {score})")
|
|
|
|
print("\n🔍 Search 'làm' → Chỉ trả TOP 3")
|
|
print("-" * 80)
|
|
results = trie.search_prefix("làm")
|
|
|
|
print(f"✓ Trả về {len(results)}/5 documents (top 3 có score cao nhất):")
|
|
for doc_id, score in results:
|
|
print(f" [{doc_id}] {docs[doc_id][0]} (score: {score})")
|
|
|
|
print("\n💡 Lợi ích:")
|
|
print(" - Nếu có 1000 documents, vẫn chỉ trả 3")
|
|
print(" - Performance O(m) ổn định")
|
|
print(" - Không bị lag khi có nhiều kết quả")
|
|
|
|
input("\n\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("""
|
|
✅ TRIE MỚI CÓ GÌ?
|
|
-------------------
|
|
1. Word-start indexing
|
|
→ Tìm được keyword ở GIỮA câu
|
|
→ "wc" tìm ra "làm sạch wc"
|
|
|
|
2. Top-K limiting
|
|
→ Performance O(m) ổn định
|
|
→ Không bị chậm dù có hàng ngàn kết quả
|
|
|
|
3. Normalize tiếng Việt
|
|
→ Gõ không dấu vẫn tìm được
|
|
→ "lam sach" → "làm sạch"
|
|
|
|
❌ KHÔNG CẦN INVERTED INDEX NỮA!
|
|
---------------------------------
|
|
- Trie alone đã đủ cho use case autocomplete
|
|
- Tiết kiệm memory
|
|
- Code đơn giản hơn
|
|
|
|
📊 PERFORMANCE:
|
|
---------------
|
|
- Insert: O(n * w) với n = số từ, w = độ dài trung bình
|
|
- Search: O(m) với m = độ dài query
|
|
- Memory: Tăng ~3-5x (do word-start indexing)
|
|
|
|
🎯 KHI NÀO DÙNG?
|
|
-----------------
|
|
✓ Autocomplete / Search suggestions
|
|
✓ Dataset < 100K documents
|
|
✓ Cần realtime search (< 5ms)
|
|
✓ User gõ có/không dấu
|
|
|
|
⏭️ BƯỚC TIẾP THEO:
|
|
-------------------
|
|
→ Test với data thật (unique_work_contents.json)
|
|
→ Tích hợp vào FastAPI
|
|
→ Build UI cho user
|
|
""")
|
|
|
|
print("=" * 80)
|
|
print("\n✅ Hiểu rồi chứ? Giờ test với data thật nhé!")
|
|
print("📂 Code: src/search/trie.py")
|
|
print("⏭️ Next: tests/test_with_real_data.py\n")
|
|
|
|
|
|
if __name__ == "__main__":
|
|
demo_word_start_indexing()
|
|
demo_normalize()
|
|
demo_top_k_performance()
|
|
conclusion()
|