Inverted Search Engine

A keyword-to-document search engine written in C that builds an inverted index from multiple text files using a hash table with two-level linked lists. Given any word, the system instantly reports which files contain it and how many times.

This is the same fundamental data structure used in real-world search engines like Apache Lucene and Elasticsearch.

---

Features

• Index words from multiple .txt files in one run
• Hash-table-based storage for fast keyword lookup
• Per-file word frequency tracking
• Persistent database: save index to file, reload and extend later
• Duplicate file and duplicate word detection
• Menu-driven interface with 5 operations: Create, Display, Search, Update, Save

---

Data Structure

Hash Table (27 slots: a–z + special characters)

arr[0]  →  main_node("are",  fc=2)  →  sub_node("file2.txt", wc=1)
                                    →  sub_node("file3.txt", wc=1)
arr[4]  →  main_node("Emertxe", fc=1) → sub_node("file1.txt", wc=1)
arr[7]  →  main_node("hi", fc=1)   →  sub_node("file2.txt", wc=1)
        →  main_node("how", fc=2)  →  sub_node("file2.txt", wc=1)
                                    →  sub_node("file3.txt", wc=1)
...
arr[26] →  (non-alpha words)

• Hash function: index = tolower(word[0]) - 'a' (0–25 for letters, 26 for symbols)
• Collision handling: chaining — each bucket holds a linked list of main nodes
• main_node: stores the word, file_count, and a pointer to its sub-node list
• sub_node: stores a filename and the frequency of the word in that file

---

Project Structure

inverted-search/
├── invert.h          # All struct definitions (hash_t, main_node_t, sub_node_t, filename_t) + prototypes
├── main.c            # Entry point: file validation, hash table init, menu loop with state flags
├── create_search.c   # create_database() — word indexing logic; search_word() — hash + list lookup
├── operations.c      # Helpers: hash_function, file_validation, check_txt_ext, check_duplicate,
│                     #          create_main_node, create_sub_node, remove_duplicate_files
├── display_save.c    # display_database() — tabular print; save_database() — serialise to .txt
├── update.c          # update_database() — deserialise saved .txt back into hash table
└── Makefile

---

Build & Run

Compile

make

Usage

./inverted_search <file1.txt> <file2.txt> ...

Example

./inverted_search file1.txt file2.txt file3.txt

---

Menu Operations

--------- INVERTED SEARCH MENU ---------
1. Create Database    — index all loaded .txt files
2. Display Database   — print full index as a formatted table
3. Search Database    — enter a word; see which files contain it
4. Update Database    — load a saved .txt database, then create on new files
5. Save Database      — serialise in-memory index to a .txt file
6. Exit

State Rules

Operation	Requires
Create	At least one valid file loaded; not already created (unless after Update)
Display	Create or Update done
Search	Create or Update done
Update	Not already updated
Save	Create or Update done

---

Sample Session

Input files

file1.txt : Hi Emertxe to welcome
file2.txt : hi are how hello you
file3.txt : am are fine how i you

Create → Display output

HashIdx    | Word                 | FileCount | FileName             | WordCount
-------------------------------------------------------------------------------
0          | are                  | 2         | file2.txt            | 1
           |                      |           | file3.txt            | 1
4          | Emertxe              | 1         | file1.txt            | 1
7          | hi                   | 1         | file2.txt            | 1
7          | Hi                   | 1         | file1.txt            | 1
7          | how                  | 2         | file2.txt            | 1
           |                      |           | file3.txt            | 1
19         | to                   | 1         | file1.txt            | 1
22         | welcome              | 1         | file1.txt            | 1
24         | you                  | 2         | file2.txt            | 1
           |                      |           | file3.txt            | 1

Search output

Enter word to search: how
Word "how" is present in 2 files.
In file2.txt : 1 time(s)
In file3.txt : 1 time(s)

---

Saved Database Format

Each record is written as one line:

#<hash_index>;<word>;<file_count>;<filename1>;<wordcount1>;<filename2>;<wordcount2>;#

Example:

#0;are;2;file2.txt;1;file3.txt;1;#
#7;how;2;file2.txt;1;file3.txt;1;#

update_database() parses this format to restore the full index from disk.

---

How It Works — Step by Step

create_database()

1. Open each validated .txt file
2. Read words one by one with fscanf(fp, "%s", word)
3. Compute hash_index = hash_function(word) → maps to bucket 0–26
4. Walk arr[hash_index].link (main node chain) looking for a matching word via strcmp
5. Word found: walk its sub-node chain for the current filename
   • File found → stemp->word_count++
   • File not found → create new sub_node, append to chain, mtemp->file_count++
6. Word not found: create new main_node (with its first sub_node), append to bucket chain

search_word()

1. Hash the query word to get bucket index
2. Walk the main node chain at that index with strcmp
3. If found: print file_count and iterate sub-nodes to print each (filename, word_count)
4. If not found: print "not found" message

save_database() / update_database()

• Save: iterate all 27 buckets → all main nodes → all sub-nodes → write in #idx;word;fc;fn;wc;#\n format
• Update: parse each #...# record back into malloc'd main + sub nodes, insert into hash table

---

File Validation Rules

Check	Result on Failure
.txt extension	Skipped with INFO message
Duplicate filename	Skipped with INFO message
File not found	Skipped with INFO message
Empty file	Skipped with INFO message

---

Clean Build

make clean

---

Author

Suchithra S
B.E. ECE — Gopalan College of Engineering & Management, VTU (2025)
Advanced Embedded Systems Training — Emertxe Information Technologies, Bengaluru