Chỉ mục đảo ngược

Chỉ mục đảo ngược ánh xạ mỗi thuật ngữ trong một tập hợp đến một danh sách bài đăng của các tài liệu chứa thuật ngữ đó, cho phép hệ thống tìm kiếm tìm các tài liệu phù hợp mà không cần quét từng tài liệu.

Definition

Chỉ mục đảo ngược là một cấu trúc dữ liệu bao gồm một từ điển các thuật ngữ được lập chỉ mục, mỗi thuật ngữ trỏ đến một danh sách bài đăng liệt kê các tài liệu chứa thuật ngữ đó, thường được chú thích bằng tần suất và vị trí thuật ngữ, để việc truy xuất có thể được thực hiện bằng cách giao hoặc hợp các danh sách bài đăng.

Scope

Chủ đề này bao gồm cấu trúc và cách xây dựng chỉ mục đảo ngược: từ điển thuật ngữ, danh sách bài đăng ghi lại các định danh tài liệu, tần suất thuật ngữ và vị trí, cũng như các thuật toán xây dựng và cập nhật chỉ mục trên các tập hợp lớn, bao gồm lập chỉ mục dựa trên sắp xếp khối và lập chỉ mục trong bộ nhớ một lần. Nó đề cập đến thông tin vị trí cho các truy vấn cụm từ và kỹ thuật bảo trì chỉ mục, trong khi để nén và chiến lược đánh giá truy vấn cho các chủ đề liền kề.

Core questions

• Một mục từ điển và danh sách bài đăng của nó chứa gì?
• Vị trí được lưu trữ như thế nào để hỗ trợ các truy vấn cụm từ và lân cận?
• Chỉ mục đảo ngược được xây dựng như thế nào khi tập hợp quá lớn so với bộ nhớ?
• Chỉ mục được cập nhật như thế nào khi các tài liệu được thêm, thay đổi hoặc xóa?
• Các danh sách bài đăng hỗ trợ giao cắt hiệu quả cho các truy vấn liên hợp như thế nào?

Key concepts

• từ điển thuật ngữ
• danh sách bài đăng
• định danh tài liệu
• chỉ mục vị trí
• lưu trữ tần suất thuật ngữ
• lập chỉ mục dựa trên sắp xếp khối (BSBI)
• lập chỉ mục trong bộ nhớ một lần (SPIMI)
• hợp nhất và cập nhật chỉ mục

Key theories

Tổ chức từ điển và bài đăng

Việc tách một từ điển thuật ngữ nhỏ gọn khỏi các danh sách bài đăng có độ dài thay đổi cho phép hệ thống tra cứu một thuật ngữ nhanh chóng và sau đó chỉ truyền các tài liệu liên quan, đây là cơ sở cấu trúc của tất cả các truy xuất chỉ mục đảo ngược.

Xây dựng chỉ mục có khả năng mở rộng

Các phương pháp dựa trên đĩa như lập chỉ mục dựa trên sắp xếp khối và lập chỉ mục trong bộ nhớ một lần xây dựng các tệp đảo ngược cho các tập hợp lớn hơn nhiều so với bộ nhớ bằng cách tích lũy và hợp nhất các chỉ mục một phần.

Clinical relevance

Chỉ mục đảo ngược là cấu trúc dữ liệu trung tâm của hầu hết các hệ thống tìm kiếm văn bản, bao gồm các công cụ tìm kiếm web, các nền tảng tìm kiếm mã nguồn mở như Lucene và các dẫn xuất của nó, và tìm kiếm toàn văn cơ sở dữ liệu. Thiết kế của nó quyết định các loại truy vấn nào được hỗ trợ và chúng có thể được trả lời nhanh chóng và tiết kiệm như thế nào.

History

Các tệp đảo ngược đã được sử dụng trong các hệ thống truy xuất thư mục ban đầu và trở thành cấu trúc tiêu chuẩn cho tìm kiếm toàn văn khi các tập hợp dữ liệu tăng lên. Nghiên cứu trong những năm 1990 và 2000, bao gồm các phương pháp xây dựng có khả năng mở rộng như lập chỉ mục trong bộ nhớ một lần, đã giúp việc lập chỉ mục các kho ngữ liệu quy mô web trở nên khả thi, và cấu trúc này hiện là nền tảng của các thư viện tìm kiếm mã nguồn mở được sử dụng rộng rãi.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

Tại sao nó được gọi là chỉ mục 'đảo ngược'?

Một chỉ mục thông thường (thuận) liệt kê, đối với mỗi tài liệu, các thuật ngữ mà nó chứa. Chỉ mục đảo ngược đảo ngược ánh xạ này để liệt kê, đối với mỗi thuật ngữ, các tài liệu chứa thuật ngữ đó. Sự đảo ngược này chính xác là điều làm cho việc tra cứu dựa trên thuật ngữ trở nên nhanh chóng.

Chỉ mục vị trí được sử dụng để làm gì?

Một chỉ mục vị trí lưu trữ các vị trí mà mỗi thuật ngữ xuất hiện trong mỗi tài liệu. Điều này cho phép hệ thống trả lời các truy vấn cụm từ và truy vấn lân cận, nơi thứ tự hoặc sự gần gũi của các thuật ngữ quan trọng, thay vì chỉ đơn thuần là các thuật ngữ có xuất hiện ở đâu đó trong tài liệu hay không.