How genericalexacc/invertedindex works
Project Focus
• This is a Rust-based toy project implementing an inverted index engine.
• The engine enables full-text search with ranked retrieval (via okapi BM25), processes documents by filtering stop words, and maintains an in-memory inverted index.
• Key modules within the engine include document indexing, stop words filtering, and document occurrence handling.
Main Components to Represent (from the “src/in_memory_index” directory)
• Document Index Component:
• File: document_index.rs
• Role: Maintains the core structure mapping terms to document occurrences.
• Document Occurrence Handler:
• File: doc_occurence.rs
• Role: Manages the specific occurrences (e.g., positions or frequency of terms) in documents.
• Stop Words Module:
• File: stop_words.rs
• Role: Provides functionality to remove common, less meaningful words during query processing.
• Module Aggregator:
• File: mod.rs
• Role: Ties together the above subcomponents for the inverted index engine.
Key Interactions and Data Flow
• Document Ingestion/Parsing:
• A document is received (either via indexing a webpage or through a file input).
• Preprocessing/tokenization occurs (this step might be handled elsewhere, but its output feeds into the engine).
• Stop Words Filtering:
• The parsed terms are processed by the stop words module to remove any non-informative words.
• Indexing and Occurrence Recording:
• The filtered terms are sent to the Document Index Component where each term’s occurrence in the document is recorded.
• The Document Occurrence Handler keeps metadata such as term frequency and position details.
• Query Processing and Ranking (BM25):
• While the BM25 ranking is mentioned in the README, its detailed logic might mix with the querying workflow. Still, it’s a critical part to note.
• A query is processed and the engine retrieves the matching documents from the index, ranking them based on the BM25 algorithm.
Architectural Patterns and Technologies
• In-Memory Data Structures: The inverted index is kept entirely in memory for fast retrieval.
• Concurrency: The project leverages mutexes and threading (as mentioned in the README) to allow concurrent access to or modifications of the index.
• Algorithms: Focus on okapi BM25 for ranked retrieval, and a naive document-frequency (df) count process for stop word filtering at query time.