Hợp Nhất Thứ Hạng Tương Hỗ (Reciprocal Rank Fusion - RRF) Cho Hybrid Search

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

• Hiểu bài toán Hybrid Search: Điểm số của BM25 (thường từ 0 đến 50+) và Cosine Similarity (từ -1 đến 1) nằm trên hai thang đo hoàn toàn khác nhau. Cộng trực tiếp điểm số sẽ gây méo mó kết quả.
• Thuật toán RRF (Cormack et al., 2009): Thay vì cộng điểm số thô, ta chỉ dựa trên vị trí thứ hạng (rank r ≥ 1):

RRF_Score(d) = ∑_{m ∈ M} 1k + r_m(d) Trong đó:

• M là tập hợp các hệ thống xếp hạng (ví dụ: [BM25, Dense Vector]).
• r_m(d) ∈ {1, 2, …} là thứ hạng của tài liệu d trong danh sách m (1-indexed).
• k là hằng số làm mượt (mặc định k = 60).

Yêu cầu

Viết hàm reciprocal_rank_fusion(ranked_lists: list[list[str]], k: int = 60, top_n: int = 5) -> list[tuple[str, float]]:

• ranked_lists: Danh sách các bảng xếp hạng doc_id (mỗi bảng là list[str] xếp theo thứ tự giảm dần của hệ thống đó).
• k: Hằng số làm mượt k ≥ 1.
• top_n: Số lượng tài liệu hợp nhất cần lấy.
• Trả về: Danh sách top top_n cặp (doc_id, rrf_score) sắp xếp giảm dần theo điểm RRF (nếu hòa điểm, sắp xếp theo thứ tự từ điển tăng dần của doc_id).

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ả.