- vừa được xem lúc

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

#Algolia
#Approximate Search

0 0 4

Người đăng: Phan Ngoc

Theo Viblo Asia

📘 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:

Bình luận