Tính phức tạp của tìm kiếm của Lucene

Question

Nếu tôi viết và thuật toán thực hiện tìm kiếm bằng cách sử dụng Lucene, làm thế nào tôi có thể nêu tính phức tạp tính toán của nó? Tôi biết rằng Lucene sử dụng tf * idf ghi bàn nhưng tôi không biết làm thế nào nó được thực hiện. Tôi đã tìm thấy rằng id * tf có độ phức tạp sau:

O(|D|+|T|) 

trong đó D là tập hợp các tài liệu và T tập hợp tất cả các cụm từ.

Tuy nhiên, tôi cần một người có thể kiểm tra xem điều này có đúng hay không và giải thích cho tôi lý do.

Cảm ơn bạn

Answer 1

Lucene cơ bản sử dụng một Vector Space Model (VSM) với một chương trình tf-idf. Vì vậy, trong bối cảnh tiêu chuẩn chúng ta có:

• Một bộ sưu tập các tài liệu từng biểu diễn dưới dạng một vector
• Một truy vấn văn bản cũng thể hiện dưới dạng một vector

Chúng tôi xác định K tài liệu của bộ sưu tập với điểm số không gian vectơ cao nhất trên truy vấn q. Thông thường, chúng tôi tìm kiếm các tài liệu hàng đầu K này được sắp xếp theo điểm theo thứ tự giảm dần; ví dụ: nhiều công cụ tìm kiếm sử dụng K = 10 để truy xuất và xếp thứ tự trang đầu tiên trong số mười kết quả tốt nhất.

Các thuật toán cơ bản để tính điểm không gian vector là:

float Scores[N] = 0 
Initialize Length[N] 
for each query term t 
do calculate w(t,q) and fetch postings list for t (stored in the index) 
    for each pair d,tf(t,d) in postings list 
    do Scores[d] += wf(t,d) X w(t,q) (dot product) 
Read the array Length[d] 
for each d 
do Scored[d] = Scores[d]/Length[d] 
return Top K components of Scores[] 

đâu

• Mảng Length giữ độ dài (yếu tố bình thường) cho mỗi N tài liệu, trong khi mảng Scores giữ điểm cho từng tài liệu.
• tf là tần suất cụm từ của một thuật ngữ trong tài liệu.
• w(t,q) là trọng số của truy vấn được gửi cho một cụm từ nhất định. Lưu ý rằng truy vấn được coi là bag of words và véc tơ của trọng số có thể được xem xét (như thể nó là một tài liệu khác).
• wf(d,q) là trọng số hạn logarit cho truy vấn và tài liệu

Như đã trình bày ở đây: Complexity of vector dot-product, vector dot-sản phẩm là O(n). Ở đây, thứ nguyên là số thuật ngữ trong từ vựng của chúng tôi: |T|, trong đó T là tập hợp các cụm từ.

Vì vậy, mức độ phức tạp thời gian của thuật toán này là:

O(|Q|· |D| · |T|) = O(|D| · |T|) 

chúng ta xem xét | Q | cố định, trong đó Q là tập hợp các từ trong truy vấn (kích thước trung bình thấp, trung bình một truy vấn có từ 2 đến 3 cụm từ) và D là tập hợp tất cả tài liệu.

Tuy nhiên, để tìm kiếm, các bộ này bị chặn và chỉ mục không có xu hướng phát triển thường xuyên.Vì vậy, kết quả là các tìm kiếm bằng cách sử dụng VSM thực sự rất nhanh (khi T và D lớn thì tìm kiếm thực sự chậm và người ta phải tìm cách tiếp cận thay thế).