Search engine algorithms

Module 6 — Search engine: tổng quan

Cách search engine hoạt động: inverted index, chấm điểm TF-IDF/BM25, PageRank, và vector search HNSW. Nền của Elasticsearch, pgvector.

Inverted index — nền tảng full-text search

Ánh xạ term → danh sách document chứa nó (posting list). Tokenize, normalize, và vì sao tra cứu nhanh hơn quét tuần tự.

TF-IDF — chấm điểm liên quan cổ điển

Trọng số term theo tần suất trong document (TF) và độ hiếm toàn corpus (IDF). Vì sao term hiếm quan trọng hơn term phổ biến.

BM25 — chấm điểm chuẩn công nghiệp

Cải tiến TF-IDF: bão hoà tần suất term và chuẩn hoá độ dài document. Vì sao BM25 là mặc định của Elasticsearch/Lucene.

PageRank — xếp hạng theo liên kết

Trang quan trọng = được nhiều trang quan trọng trỏ tới. Random surfer, power iteration hội tụ, damping factor. Liên hệ đồ thị.

HNSW — vector search xấp xỉ (ANN)

Tìm vector gần nhất trong không gian nhiều chiều bằng đồ thị phân tầng HNSW: nhanh gần đúng thay vì O(n) chính xác. Nền embedding search.

Mini-challenge — mini search engine

Lab: dựng search nhỏ — inverted index + BM25 ranking trên tập document, trả top-K kết quả theo truy vấn.

Case study — Elasticsearch & pgvector

Elasticsearch ghép inverted index + BM25 + sharding thế nào; pgvector + HNSW cho semantic search trong Postgres ra sao.

Module 6 — Tổng kết & cheat sheet

Recap search: bảng index/ranking/vector theo bài toán, glossary, self-assessment. Liên hệ string matching và đồ thị.