Thuật toán của Lucene

Question

Tôi đọc bài báo của Doug Cutting; "Space optimizations for total ranking".

Kể từ khi nó được viết một thời gian dài trước đây, tôi tự hỏi những gì các thuật toán lucene sử dụng (liên quan đến bài viết danh sách traversal và tính toán điểm số, xếp hạng).

Cụ thể, tổng thuật toán xếp hạng được mô tả có liên quan đến toàn bộ danh sách bài đăng cho mỗi cụm từ truy vấn, trong trường hợp các thuật ngữ truy vấn rất phổ biến như "chó vàng", một trong hai cụm từ có thể có các bài đăng rất dài trong trường hợp tìm kiếm trên web. Tất cả họ có thực sự vượt qua Lucene/Solr hiện tại không? Hoặc có bất kỳ chẩn đoán nào để cắt ngắn danh sách được sử dụng không?

Trong trường hợp chỉ có kết quả k được trả về đầu tiên, tôi có thể hiểu rằng phân phối danh sách bài đăng trên nhiều máy và sau đó kết hợp đầu k từ mỗi máy sẽ hoạt động, nhưng nếu chúng tôi được yêu cầu trả lại "thứ 100 trang kết quả ", tức là kết quả xếp hạng từ 990-1000, sau đó mỗi phân vùng sẽ vẫn phải tìm ra 1000 đầu, do đó, việc phân vùng sẽ không giúp được gì nhiều.

Nhìn chung, có bất kỳ tài liệu chi tiết cập nhật nào về các thuật toán nội bộ được Lucene sử dụng không?

Answer 1

Tôi không biết tài liệu đó, nhưng vì Lucene là nguồn mở, tôi khuyến khích bạn đọc mã nguồn. Đặc biệt, phiên bản thân hiện tại bao gồm flexible indexing, có nghĩa là lưu lượng danh sách lưu trữ và đăng bài đã được tách riêng khỏi phần còn lại của mã, giúp bạn có thể viết các codec tùy chỉnh.

Giả định của bạn là chính xác về việc chuyển danh sách bài đăng, theo mặc định (tùy thuộc vào việc thực hiện Scorer) Lucene duyệt toàn bộ danh sách bài đăng cho mọi cụm từ hiện có trong truy vấn và đặt các tài liệu phù hợp trong một khối kích thước k để tính toán -k tài liệu (xem TopDocsCollector). Vì vậy, kết quả trả về từ 990 đến 1000 làm cho Lucene khởi tạo một đống kích thước 1000. Và nếu bạn phân vùng chỉ mục của bạn theo tài liệu (một cách tiếp cận khác có thể được chia theo thuật ngữ), mỗi phân đoạn sẽ cần gửi 1000 kết quả hàng đầu đến máy chủ chịu trách nhiệm về kết quả hợp nhất (xem Solr QueryComponent ví dụ, dịch một truy vấn từ N thành P> N thành nhiều yêu cầu phân đoạn từ 0 đến P sreq.params.set(CommonParams.START, "0");). Đây là lý do tại sao Solr có thể chậm hơn trong chế độ phân phối hơn ở chế độ độc lập trong trường hợp phân trang cực đoan. Tôi không biết cách Google quản lý để đạt được kết quả một cách hiệu quả, nhưng Twitter đã xuất bản một số paper on their retrieval engine Earlybird nơi họ giải thích cách họ vá Lucene để thực hiện tiến trình theo thứ tự thời gian ngược hiệu quả của danh sách đăng bài, cho phép họ quay trở lại nhiều nhất các tweet gần đây phù hợp với một truy vấn mà không vượt qua toàn bộ danh sách gửi bài cho mọi cụm từ.

Cập nhật: tôi thấy presentation này từ Googler Jeff Dean, điều này giải thích cách Google xây dựng hệ thống tìm kiếm thông tin quy mô lớn của nó. Đặc biệt, nó nói về các chiến lược sharding và mã hóa danh sách gửi bài.