Đây thực sự là vấn đề thực sự mà tôi đang thực hiện, nhưng để đơn giản, hãy giả vờ là tôi là Google.Thuật toán tìm kiếm chỉ mục cho nhiều giá trị là gì?
Nói người dùng tìm kiếm "phần mềm tuabin cỡ nano". Không có nhiều trang với cả hai từ ... chỉ khoảng 3k. Nhưng có ~ 2 triệu trang với "nanoscale" và ~ 4 triệu trang với "tupperware". Tuy nhiên, Google tìm thấy 3k cho tôi trong 0,3 giây.
Làm như thế nào?
Thuật toán duy nhất tôi biết là lấy tài liệu cho "nanoscale", lấy tài liệu cho "tupperware" và sau đó thực hiện hợp nhất danh sách. Nhưng đó là O (N + M), hoặc O (5.000.000) có vẻ hơi chậm. Đặc biệt nếu tôi đang chạy nó trên một máy tính để bàn thay vì một cụm uber nhanh.
Vì vậy, đó thực sự là những gì Google đang làm, và tốc độ của họ là do chủ yếu là thực tế là họ đang chạy tính toán đắt tiền này trên cụm phân phối khổng lồ của họ?
Hoặc có một thuật toán tốt hơn mà tôi không biết? Wikipedia và Google không bật lên bất cứ điều gì cho tôi.
Chỉnh sửa:
Vì mọi người dường như đang tập trung vào khía cạnh Google của câu hỏi của tôi, tôi đoán tôi sẽ cố định nó theo thuật ngữ thực tế.
Tôi có một số chỉ mục rất lớn (hàng triệu mục) được triển khai dưới dạng cặp khóa/giá trị. Phím là các từ, giá trị đơn giản là Bộ tài liệu. Một trường hợp sử dụng phổ biến là để có được giao điểm của kết quả trên một số tìm kiếm trên các chỉ mục khác nhau: điểm đau là nhận được giao điểm của bộ tài liệu.
Tôi có thể triển khai lại chỉ mục của mình tuy nhiên tôi muốn - nó chủ yếu là một dự án học thuật tại thời điểm này.
Có thể có rất nhiều bộ nhớ đệm thông minh có liên quan ... –
Tôi chắc chắn có, cùng với một triệu tối ưu hóa thông minh khác. Nhưng tôi thực sự nghi ngờ họ đang lưu vào bộ nhớ đệm * kết quả * của tìm kiếm của tôi, vì vậy tôi vẫn tò mò - thuật toán nào họ đang sử dụng để thực sự có được danh sách kết quả? – levand
Google có các chỉ mục. Rất nhiều chỉ số. Có thể những gì nó làm là lấy chỉ mục được tạo trước cho từ 'nanoscale' và sau đó cho mỗi trang được liệt kê, xem qua danh sách được sắp xếp trước của tất cả các từ trong trang đó để xem liệu 'tupperware' có xảy ra hay không. Phần đó sẽ được phân phối ồ ạt. Nó sẽ lưu vào bộ nhớ cache kết quả, do đó, lần sau khi bạn tìm kiếm các thuật ngữ tương tự, nó sẽ lấy chỉ mục "phần tử tupperware" được tạo trước. Conceivably Google có các chỉ mục được tạo trước cho mọi kết hợp có thể của bất kỳ 2 trong số 10.000 từ tiếng Anh hàng đầu theo tần suất: đó là "chỉ" 100 triệu danh sách các trang. –