cpp-search-engine

A search engine written from scratch in C++ — tokenizer, inverted index, and ranked retrieval — with no external libraries. Originally built as coursework for Experimentación en Informática (B.Sc. Computer Science, University of Alicante) and cleaned up here as a portfolio piece.

The interesting part is that every layer is hand-rolled: there is no Lucene, no std::regex, no tokenizer library. Text goes in as raw files and comes out as a ranked list of documents.

Architecture

The three stages build on each other, each one a separate class:

raw documents ──▶ Tokenizador ──▶ IndexadorHash ──▶ Buscador ──▶ ranked results
                  (text → terms)  (inverted index)  (BM25 / DFR)

1. Tokenizador — text to terms

A hand-written state machine over a bitset<256> delimiter table, rather than regular expressions, so a character class lookup is O(1). Beyond splitting on delimiters it special-cases the things that naive tokenizers destroy:

• URLs — https://example.com/a?b=c stays one token instead of fragmenting.
• Email addresses — kept whole.
• Decimal numbers — 3.14 and 1.234,56 survive; a trailing . at a sentence end does not.
• Acronyms — U.S.A. is not split into three letters.
• Hyphenated compounds — emitted both as the compound and as its parts.
• Accent folding and case folding for Spanish, done bytewise over Latin-1.

2. IndexadorHash — the inverted index

An inverted index over unordered_map, mapping each term to its postings:

• Postings carry collection frequency, document frequency, per-document term frequency, and optionally term positions (which is what makes phrase queries possible).
• Stopword removal from a configurable list, and Porter stemming for Spanish or English.
• Incremental indexing — re-indexing a directory only re-processes files whose modification time changed, so an unchanged corpus is nearly free.
• Disk-backed mode — when the index outgrows memory it spills term postings to per-term files under the index directory and keeps a working set in RAM, so the corpus size is not bounded by available memory.
• Persistence — GuardarIndexacion() / RecuperarIndexacion() serialise the whole index so a later search run does not re-index anything.

3. Buscador — ranked retrieval

Two probabilistic ranking models, switchable at runtime:

• BM25, with configurable k1 and b.
• DFR (Divergence From Randomness), with configurable c.

Results come back as a sorted list of ResultadoRI (score, document id, query number), in TREC evaluation format so runs can be scored with trec_eval against a relevance judgement file. There is also an experimental vector-space path that ranks documents by cosine similarity over precomputed embeddings.

Build and run

Requires a C++17 compiler and make.

make
mkdir -p indice
./demo

The demo indexes data/corpus_corto, persists the index, then runs the same query under both ranking models:

Indexed 2 documents, 4 distinct terms, 11 tokens (7 after stopword removal)

--- DFR --- query: "pal1 pal2"
0 DFR fichero1 0 2.474810 pal1 pal2
0 DFR fichero2 1 0.867715 pal1 pal2

Point it at your own corpus with:

./demo path/to/corpus data/StopWordsEspanyol.txt "your query here"

On a corpus this small BM25 scores can be negative — that is expected, since IDF goes negative for a term that appears in most of the collection. It disappears on a realistic corpus.

Layout

Path	Contents
include/, lib/	Tokenizer, index and search implementation
src/demo.cpp	Small driver showing index-then-search
data/	Sample corpus and Spanish/English stopword lists
third_party/stemmer/	Porter stemmer (not mine — see below)

Attribution and scope

third_party/stemmer/ is not my code: it is the Porter stemmer C implementation (Stuart J. Barr, c. 1986) distributed with the course, vendored here because the indexer needs it to compile. The class interfaces in include/ were specified by the course; the implementations in lib/ are mine.

Excluded from this repository: the instructor-supplied test harness, expected-output fixtures, the trec_eval binary, and the evaluation corpora.

Known limitations

Kept as written rather than modernised, since this is a record of a university project:

• IndexarDirectorio shells out via system() to list files, so it is POSIX-only and would not be safe on untrusted directory names.
• Accent folding assumes Latin-1 input rather than UTF-8.
• Error handling is largely return codes and cerr, not exceptions.

Three changes were needed to make it build and run on a modern toolchain: a missing <sstream> include, replacing a GNU-only sed -i '1d' with a portable tail -n +2, and a fix to Tokenizador::Tokenizar(const string&, vector<string>&), which cleared its output vector once per input line and so returned only the last line's tokens.

Licence

My code is MIT licensed — see LICENSE. The vendored stemmer is not covered by it; see NOTICE.