Các thuật toán phía sau Algolia

📘 Chủ đề: Các Thuật Toán Phía Sau Algolia – Toán Học và Tối Ưu Hóa

🧠 Mục tiêu

• Hiểu cách Algolia hoạt động dưới góc nhìn toán học.
• Phân tích các thuật toán tìm kiếm gần đúng (Approximate Nearest Neighbor).
• Khái quát cơ chế tối ưu thời gian truy vấn và độ chính xác trong tìm kiếm.
• Viết code mô phỏng đơn giản bằng Python để minh hoạ.

1. Giới thiệu về Algolia

• Là công cụ tìm kiếm theo thời gian thực (real-time search engine).
• Ưu tiên hiệu năng cao, thời gian phản hồi cực thấp (dưới 20ms).
• Dựa vào mô hình inverted index kết hợp với tối ưu tìm kiếm gần đúng.

2. Indexing: Inverted Index & Trie Optimization

🔹 Inverted Index

• Dạng cấu trúc: {term: [doc_ids]}
• Mô hình set intersection để tìm tài liệu chứa tất cả từ khóa.

🔹 Trie (Prefix Tree)

• Được dùng để tối ưu prefix search, ví dụ: "alg" sẽ tìm "algolia", "algorithm"...
• Toán học: Cây tìm kiếm tiền tố có chi phí tối ưu O(m) với m là độ dài từ khóa.

🔹 Tối ưu không gian

• Dùng Radix Tree để nén các nhánh đơn (Space optimization).
• Dùng Path Compression.

3. Tìm kiếm gần đúng: Approximate Nearest Neighbor (ANN)

Algolia dùng các kỹ thuật để tìm kiếm gần đúng nhanh hơn thay vì tìm chính xác (vì quá chậm cho real-time).

🔹 Edit Distance & Typo Tolerance

• Dùng Levenshtein Distance (LD): Số bước để chuyển từ từ A → B.
• Giới hạn LD ≤ 2 để có khả năng sửa lỗi gõ từ người dùng.

Toán học:

• Dynamic Programming O(m × n)
• Cải tiến: dùng BK-Tree hoặc Automata để giới hạn không gian tìm kiếm.

🔹 Ranking Formula: TF-IDF + Custom Weights

Công thức tổng thể:

Score(q, d) = w_1 * ExactMatch + w_2 * TypoTolerance + w_3 * Proximity + w_4 * AttributePriority + w_5 * CustomRanking

Thành phần:

• Proximity Score: khoảng cách giữa các từ khóa → tối ưu bằng heuristic rules.
• Typo Penalty: dựa vào Levenshtein Distance.
• Attribute Priority: ví dụ title > description.
• Custom Ranking: theo popularity, date, price,...

4. Fast Filtering và Faceted Search

• Dùng Bitmasking / BitSet để nhanh chóng lọc qua các filter dạng AND/OR.

Toán học:

• Mỗi facet là 1 bit vector, filter = AND operation giữa các vector.
• Nhanh hơn so với lọc tuần tự toàn bộ documents.

5. Compression & Memory Optimization

• Delta Encoding và Front Coding để giảm dung lượng index.
• Numeric Bucketing cho các range query.
• Cache-aware Search: tối ưu locality → giảm cache miss.

6. Code minh họa: BK-Tree cho typo-tolerant search

from collections import defaultdict

def levenshtein(a, b):
    dp = [[i + j if i * j == 0 else 0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
    return dp[-1][-1]

class BKTree:
    def __init__(self, word):
        self.word = word
        self.children = {}

    def insert(self, other):
        dist = levenshtein(self.word, other)
        if dist in self.children:
            self.children[dist].insert(other)
        else:
            self.children[dist] = BKTree(other)

    def search(self, target, max_dist):
        results = []
        dist = levenshtein(self.word, target)
        if dist <= max_dist:
            results.append(self.word)
        for d in range(dist - max_dist, dist + max_dist + 1):
            child = self.children.get(d)
            if child:
                results += child.search(target, max_dist)
        return results

tree = BKTree("algolia")
for word in ["algorithm", "algae", "algol", "align", "log"]:
    tree.insert(word)

print(tree.search("algila", 2))  # gần đúng với "algolia"

7. Kết luận & Hướng mở rộng

• Algolia dùng kết hợp nhiều kỹ thuật: trie + ANN + ranking + filter optimization.
• Có thể kết hợp thêm Embedding Search (BERT, SentenceTransformers) nếu muốn semantic search.
• Gợi ý các paper:
  • FastText + Trie-Based Search
  • Typo-Tolerant Prefix Search