Thuật toán Tìm Kiếm Từ Khóa BM25 (Okapi BM25) từ Gốc

Mục tiêu kiến thức

• Hiểu tại sao BM25 là tiêu chuẩn vàng của tìm kiếm từ khóa (Lexical Search) trong Elasticsearch và Hybrid RAG.
• Công thức tính điểm tương đồng giữa tài liệu D và câu truy vấn Q:

BM25(D, Q) = ∑_{q ∈ Q} IDF(q) · f(q, D) · (k₁ + 1)f(q, D) + k₁ · (1 - b + b · |D|avgdl) Trong đó:

• f(q, D): Tần suất từ truy vấn q xuất hiện trong tài liệu D.
• |D|: Độ dài (tổng số từ) của tài liệu D.
• avgdl: Độ dài trung bình của toàn bộ tài liệu trong tập dữ liệu.
• k₁: Tham số bão hòa tần suất từ (mặc định 1.5).
• b: Tham số phạt độ dài tài liệu (mặc định 0.75).
• Công thức Robertson-Spärck Jones IDF:

IDF(q) = ln(N - n(q) + 0.5n(q) + 0.5 + 1) (với N là tổng số tài liệu, n(q) là số tài liệu chứa từ q).

Yêu cầu

Xây dựng lớp BM25Okapi:

class BM25Okapi:
    def __init__(self, corpus: list[list[str]], k1: float = 1.5, b: float = 0.75):
        pass

    def get_scores(self, query: list[str]) -> list[float]:
        pass

    def top_k(self, query: list[str], k: int = 3) -> list[tuple[int, float]]:
        pass

• corpus: Danh sách các tài liệu đã được tách từ (tokenized), ví dụ [["apple", "pie"], ["banana", "bread"]].
• get_scores(query): Trả về danh sách điểm BM25 của tất cả tài liệu đối với query.
• top_k(query, k): Trả về top k cặp (doc_index, score) có điểm cao nhất giảm dần.

Ràng buộc

• Thời gian chạy tối đa: 2000ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào hợp lệ theo đúng kiểu dữ liệu và miền giá trị được mô tả.