Làm thế nào để xây dựng một chỉ số đảo ngược đơn giản?

Question

Tôi muốn xây dựng một chức năng lập chỉ mục đơn giản của công cụ tìm kiếm mà không cần bất kỳ API nào, chẳng hạn như Lucene. Trong chỉ mục đảo ngược, tôi chỉ cần ghi lại thông tin cơ bản của từng từ, ví dụ: docID, vị trí và freqence.

Bây giờ, tôi có một vài câu hỏi:

1. Những loại cấu trúc dữ liệu thường được sử dụng để xây dựng chỉ số đảo ngược? Danh sách đa chiều?

2. Sau khi tạo chỉ mục, cách viết chỉ mục vào tệp? Loại định dạng nào trong tệp? Giống như một cái bàn? Giống như vẽ một bảng chỉ mục trên giấy?

Answer 1

Bạn có thể thấy một thực hiện rất đơn giản của chỉ số đảo ngược và tìm kiếm trong TinySearchEngine.

Đối với câu hỏi đầu tiên của bạn, nếu bạn muốn xây dựng một đơn giản (trong bộ nhớ) chỉ số đảo ngược cấu trúc dữ liệu đơn giản là một bản đồ Hash như thế này:

val invertedIndex = new collection.mutable.HashMap[String, List[Posting]] 

hoặc một Java-esque:

HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>(); 

Bản đồ băm mỗi thuật ngữ/từ/mã thông báo vào danh sách Bài đăng. Một Posting chỉ là một đối tượng đại diện cho một sự xuất hiện của một từ trong một tài liệu:

case class Posting(docId:Int, var termFrequency:Int) 

chỉ mục một tài liệu mới được chỉ là vấn đề tokenizing nó (tách trong thẻ/từ) và đối với mỗi thẻ chèn một viết bài mới trong Danh sách chính xác của bản đồ băm. Tất nhiên, nếu một Đăng đã tồn tại cho thuật ngữ đó trong tài liệu cụ thể đó, bạn tăng thuật ngữ Tần suất. Có nhiều cách khác để làm điều này. Đối với các chỉ mục đảo ngược bộ nhớ, điều này là OK, nhưng đối với chỉ mục trên đĩa bạn có thể muốn chèn Postings một lần với đúng termFrequency thay vì cập nhật nó mỗi lần.

Về câu hỏi thứ hai của bạn, thường có hai trường hợp:

(1) bạn có chỉ mục bất biến (hầu như). Bạn lập chỉ mục tất cả dữ liệu của mình một lần và nếu bạn có dữ liệu mới, bạn có thể chỉ reindex. Ví dụ, không cần phải lập thời gian thực hoặc lập chỉ mục nhiều lần trong một giờ.

(2) tài liệu mới đến mọi lúc và bạn cần phải tìm kiếm các tài liệu mới đến càng sớm càng tốt.

Đối với trường hợp (1), bạn có thể có ít nhất 2 tệp:

1 - Tệp chỉ mục đảo ngược. Nó liệt kê cho mỗi thuật ngữ tất cả Postings (cặp docId/termFrequency). Ở đây được thể hiện bằng văn bản thuần túy, nhưng thường được lưu trữ dưới dạng dữ liệu nhị phân.

Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq> 
Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq> 
Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq> 
Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq> 
... 
TermN<docId5,termFreq><docId7,termFreq> 

2- Tập tin bù đắp. Lưu trữ cho mỗi thuật ngữ bù đắp để tìm danh sách ngược của nó trong tệp chỉ mục đảo ngược. Ở đây tôi đại diện cho bù đắp trong các ký tự nhưng bạn thường sẽ lưu trữ dữ liệu nhị phân, do đó bù đắp sẽ bằng byte. Tệp này có thể được tải vào bộ nhớ lúc khởi động. Khi bạn cần tìm kiếm một danh sách đảo ngược, bạn tra cứu giá trị offset của nó và đọc danh sách ngược từ tệp.

Term1 -> 0 
Term2 -> 126 
Term3 -> 222 
.... 

Cùng với 2 tệp này, bạn có thể (và thường sẽ) có (các) tệp để lưu trữ mỗi tiêu chuẩn của từng tài liệu IDF và mỗi tài liệu.

Đối với trường hợp (2), tôi sẽ cố gắng giải thích ngắn gọn cách Lucene (và do đó Solr và ElasticSearch) làm điều đó.

Định dạng tệp có thể giống như được giải thích ở trên. Sự khác biệt chính là khi bạn lập chỉ mục các tài liệu mới trong các hệ thống như Lucene thay vì xây dựng lại chỉ mục từ đầu, chúng chỉ tạo một tài liệu mới chỉ với các tài liệu mới. Vì vậy, mỗi khi bạn phải lập chỉ mục một cái gì đó, bạn làm điều đó trong một chỉ mục mới được tách ra.

Để thực hiện truy vấn trong chỉ mục "được chia nhỏ" này, bạn có thể chạy truy vấn đối với từng chỉ mục khác nhau (song song) và hợp nhất kết quả với nhau trước khi quay lại người dùng.

Lucene gọi chỉ mục "ít" này segments.

Mối quan tâm rõ ràng ở đây là bạn sẽ nhận được rất nhiều phân đoạn nhỏ rất nhanh. Để tránh điều này, bạn cần có chính sách để hợp nhất phân đoạn và tạo phân đoạn lớn hơn. Ví dụ: nếu bạn có nhiều hơn N segments, bạn có thể quyết định hợp nhất tất cả các phân đoạn nhỏ hơn 10 KBs với nhau.