Lập chỉ mục và Xử lý truy vấn
Lập chỉ mục và xử lý truy vấn bao gồm các cấu trúc dữ liệu và thuật toán cho phép hệ thống tìm kiếm trả lời các truy vấn trên các tập hợp văn bản lớn một cách nhanh chóng, chủ yếu thông qua chỉ mục đảo ngược.
Definition
Lập chỉ mục là việc xây dựng các cấu trúc dữ liệu, chủ yếu là chỉ mục đảo ngược ánh xạ các thuật ngữ đến các tài liệu chứa chúng, hỗ trợ tra cứu hiệu quả, trong khi xử lý truy vấn là tập hợp các thuật toán duyệt qua các cấu trúc này để tính toán các tài liệu phù hợp hoặc được xếp hạng tốt nhất cho một truy vấn.
Scope
Lĩnh vực này bao gồm cách các tập hợp văn bản được chuyển đổi thành các cấu trúc có thể tìm kiếm và cách các truy vấn được đánh giá dựa trên chúng: xây dựng chỉ mục đảo ngược, các quyết định về phân tách từ (tokenization) và từ vựng thuật ngữ đằng sau nó, nén danh sách xuất hiện (postings) để tiết kiệm không gian và tăng tốc truy cập, xử lý truy vấn hiệu quả bao gồm truy xuất xếp hạng và kết thúc sớm, và các kỹ thuật truy xuất chịu lỗi như ký tự đại diện (wildcard), sửa lỗi chính tả và khớp âm vị. Nó đề cập đến kỹ thuật hệ thống của việc truy xuất nhanh, khác biệt với các mô hình truy xuất định nghĩa xếp hạng và các phương pháp đánh giá đo lường chất lượng.
Sub-topics
Core questions
- Chỉ mục đảo ngược được xây dựng và cập nhật như thế nào cho một tập hợp lớn, đang thay đổi?
- Làm thế nào để nén danh sách xuất hiện mà không làm chậm quá trình đánh giá truy vấn?
- Các truy vấn được đánh giá hiệu quả như thế nào, đặc biệt là các truy vấn được xếp hạng trên hàng triệu tài liệu?
- Làm thế nào một hệ thống có thể truy xuất kết quả tốt mà không cần chấm điểm mọi tài liệu?
- Một hệ thống xử lý lỗi chính tả, ký tự đại diện và các kết quả khớp gần đúng như thế nào?
Key concepts
- chỉ mục đảo ngược
- danh sách xuất hiện
- phân tách từ và từ vựng thuật ngữ
- xây dựng chỉ mục (BSBI, SPIMI)
- nén chỉ mục
- đánh giá từng tài liệu và từng thuật ngữ
- cắt tỉa động và kết thúc sớm
- truy xuất chịu lỗi
Key theories
- Chỉ mục đảo ngược là cấu trúc dữ liệu cốt lõi
- Việc ánh xạ mỗi thuật ngữ tới một danh sách xuất hiện của các tài liệu (và vị trí) nơi nó xuất hiện cho phép truy xuất chỉ chạm vào các tài liệu chứa các thuật ngữ truy vấn, biến nó thành cấu trúc nền tảng cho tìm kiếm văn bản có thể mở rộng.
- Đánh đổi giữa nén và hiệu quả
- Mã hóa khoảng cách ID tài liệu và tần suất thuật ngữ bằng các mã số nguyên nhỏ gọn giúp thu nhỏ chỉ mục đáng kể và, bằng cách giảm đầu vào/đầu ra và cải thiện hành vi bộ nhớ đệm, cũng có thể tăng tốc xử lý truy vấn.
- Đánh giá truy vấn xếp hạng hiệu quả
- Các chiến lược từng tài liệu và từng thuật ngữ, kết hợp với các kỹ thuật cắt tỉa động và kết thúc sớm, cho phép các hệ thống trả về các kết quả được xếp hạng hàng đầu mà không cần chấm điểm toàn bộ tập hợp.
Clinical relevance
Chỉ mục đảo ngược và xử lý truy vấn hiệu quả là động cơ của mọi hệ thống tìm kiếm sản xuất, từ các công cụ tìm kiếm web và nền tảng tìm kiếm mã nguồn mở đến tìm kiếm toàn văn bản của doanh nghiệp và cơ sở dữ liệu. Hiệu quả của chúng trực tiếp quyết định độ trễ truy vấn, chi phí phần cứng và quy mô của các tập hợp có thể được tìm kiếm tương tác.
History
Các tệp đảo ngược đã được sử dụng để tìm kiếm văn bản từ những hệ thống thông tin sớm nhất, nhưng lý thuyết hiện đại về xây dựng chỉ mục, nén và đánh giá hiệu quả đã được củng cố vào những năm 1990, đáng chú ý là bởi công trình Managing Gigabytes của Witten, Moffat và Bell. Khảo sát năm 2006 của Zobel và Moffat đã tổng hợp hai thập kỷ nghiên cứu chỉ mục đảo ngược khi tìm kiếm quy mô web đặt hiệu quả lên hàng đầu.
Key figures
- Justin Zobel
- Alistair Moffat
- Ian H. Witten
- W. Bruce Croft
Related topics
Seminal works
- zobel2006
- wittenmgb1999
- manning2008
Frequently asked questions
- Tại sao chỉ mục đảo ngược được ưu tiên hơn việc quét tài liệu?
- Việc quét mọi tài liệu cho mỗi truy vấn quá chậm ở quy mô lớn. Chỉ mục đảo ngược cho phép hệ thống nhảy thẳng đến tập hợp nhỏ các tài liệu chứa các thuật ngữ truy vấn, do đó thời gian truy vấn phụ thuộc vào các danh sách xuất hiện liên quan chứ không phải kích thước của toàn bộ tập hợp.
- Việc nén chỉ mục có làm chậm quá trình tìm kiếm không?
- Thông thường thì ngược lại. Một chỉ mục nhỏ hơn làm giảm lưu lượng đĩa và bộ nhớ, và các mã số nguyên hiện đại giải nén rất nhanh, do đó thời gian tiết kiệm được cho đầu vào/đầu ra và hành vi bộ nhớ đệm được cải thiện thường lớn hơn chi phí giải mã, làm cho các chỉ mục được nén vừa nhỏ hơn vừa nhanh hơn.