File Indexing System & Search Engine

A simplified in-memory file indexing and search system implemented in C. This project simulates the core mechanics of a search engine, mapping keywords to documents using a highly efficient Trie (Prefix Tree) data structure and ranking results using a Max-Heap.

Overview

The system manages a collection of files, each characterized by a unique identifier (name), a relevance score, and a list of associated keywords. The primary goal is to provide fast text-based search capabilities (exact match and prefix match) while dynamically handling metadata updates (adding/removing files or keywords).

Data Architecture

To achieve optimal performance for both text search and metadata management, the project relies on three interconnected data structures:

1. Trie (Prefix Tree): Acts as the inverted index. It stores all keywords present in the system character by character. The leaf nodes (or marked nodes) hold references to the files containing that specific keyword.
2. Doubly Linked List: Stores the actual files (ID and relevance score) in the order they were added to the system. This allows for constant $O(1)$ updates when modifying a file's base properties.
3. Max-Heap: Used exclusively for querying top results (TOPK operation). When a search query matches multiple files, the heap organizes them based on their relevance score, allowing for the extraction of the $k$-most relevant results efficiently.

Features & Supported Operations

• ADD <id> <score> <t> <kw1>...<kwt>: Registers a new file in the linked list and indexes its keywords in the Trie.
• DEL <id>: Removes a file from the system. Crucially, it traverses the Trie to remove all dangling references to this file, effectively pruning unused keywords to save memory.
• ADDKW <id> <kw> / DELKW <id> <kw>: Incrementally updates metadata by associating or dissociating a keyword from an existing file.
• FIND <kw>: Searches the Trie and returns all files containing the exact keyword, sorted lexicographically by file ID.
• TOPK <kw> <k>: Retrieves the top $k$ most relevant files for a given keyword, utilizing the Max-Heap.
• PREFIX <prefix> (Bonus Feature): Extends the search capabilities by finding all files that contain at least one keyword starting with the given prefix. It relies on a deep traversal (DFS) of the Trie subtree originating from the prefix's last character.