Tiny Search Engine

A search engine written in plain C: three small programs — a crawler, an indexer, and a querier — connected by nothing but files on disk. Each one does a single job, validates its inputs defensively, and writes an artifact the next stage reads. They share two libraries: a common module (index, pagedir, word) and libcs50, which supplies the generic containers the pipeline is built on: a bag, a hashtable, a set, a counters set, and a webpage fetcher.

Crawling the web is graph traversal: the web is a directed graph whose vertices are pages and whose edges are links, and the crawler runs breadth-first search over it from a seed URL, bounded by a maximum depth and restricted to a configurable domain, so the crawl stays inside its assigned subset of the web. The frontier is a bag_t of pages still to visit and the seen-set a hashtable_t of URLs already queued:

pageScan pulls the links off each fetched page, normalizes them, and adds the internal, unseen ones to the bag. pagedir_save writes every fetched page to a file named by an integer document ID (URL on the first line, crawl depth on the second, raw HTML below) inside a directory pagedir_init stamps with a .crawler sentinel so the later stages can confirm they were handed a real crawl.

The indexer inverts those pages into a map. It walks that directory and, for each word normalizeWord lowercases out of a page, updates an index_t, a hashtable_t mapping each word to a counters_t that tallies $(docID\to count)$. index_print serializes it to a plain text file, one word per line followed by its docID count pairs; index_load reconstructs the same structure, so the querier reads back exactly what the indexer wrote. Looking up a query term is $O(1)$ per word rather than a scan over every document.

The querier answers ranked boolean queries. It parses them with implicit and conjunctions and explicit or disjunctions, honoring precedence (and binds tighter). Scores follow the operators: a conjunction takes the minimum over its terms, a disjunction the sum,

where $c_w(d)$ counts occurrences of $w$ in document $d$. Those two rules fall straight out of the counters module: query_build looks each word up in the index, query_intersection walks two counter sets keeping the minimum shared count, and query_union sums them. query_print then sorts the surviving documents by score before printing. Everything is valgrind-clean C, checked against the memcheck and indextest harnesses in each module, with every container hand-rolled on the shared libcs50 primitives.