Nebula · My Village

What is Nebula?

Nebula is a text search engine, written from the ground up in Python with no external search libraries. Given a corpus of books pulled from Project Gutenberg, it builds an inverted index and a trie, then answers free-text queries by ranking documents with TF‑IDF and returning the top-k matches — each with a keyword-centered snippet pulled straight from the source text.

It started as a course project built around a specific set of data structures, and grew into a small case study on how those textbook structures behave once real (messy, unicode-laden, inconsistently-punctuated) text gets thrown at them.

hash maps tries heaps sets strings TF-IDF Python

Pipeline

The pipeline runs in two stages: building the inverted index and processing queries:

Corpus intake→ Tokenize→ Inverted index + trie

Parse query→ TF-IDF score→ Heap top-k→ Snippet extraction

The inverted index

Instead of storing document → words, Nebula stores word → documents that contain it, which is what makes "find every book containing python" fast instead of a linear scan of the whole library. Concretely, it's a dictionary of dictionaries:

self.index = defaultdict(lambda: defaultdict(int)) "treasure" → { ("84", 935): 1, ("84", 3845): 1, ("1342", 210): 2, }

The inner key is a (document, position) tuple — tuples are hashable, so they work as dictionary keys, and bundling doc + position into one key means a single lookup gives both "which book" and "where in the book" at once. The outer defaultdict is built with a lambda so a brand-new word can be inserted with index[word][(doc, pos)] += 1 and never needs an explicit initialization branch.

Query syntax

A query is just words, but two trailing characters change how a word is treated — a small parser (ParseQuery) splits every term into either a filter word, an expansion word, or a plain query/snippet word:

nebula> treasure! bone$ pirates full query: treasure bones bony boney pirates snippet_terms: bones bony boney pirates

word! — a filter term: it narrows which documents match, but is excluded from the returned snippet windows.
word$ — an expansion term: the trie is walked to find every indexed word sharing that stem/prefix, and all of them are folded into the query.
everything else counts toward both scoring and snippet placement.

TF‑IDF ranking

TF = (count of query_term in this document) / (total words in this document) IDF = log( (total documents) / (documents containing query_term) )

TF is the local signal — how much this particular document is "about" the term. IDF is the global signal — how rare, and therefore how discriminating, the term is across the whole corpus. A document's score for a query is the sum of TF × IDF across every query term.

Two constants get pre-computed up front — total document count for IDF, and each document's total word count for TF — so that scoring a query only has to compute the parts that actually depend on the query itself. If a term's TF is zero for a document, its IDF is never even calculated.

Heap-ranked top-k

Once every candidate document has a score, only the top k are needed — so rather than sorting the entire result set, Nebula keeps a size-k min-heap and pushes candidates through it, discarding the lowest score whenever the heap overflows. In theory that's an O(n log k) win over an O(n log n) full sort whenever k ≪ n. Benchmarking it against Python's built-in sort confirmed the crossover:

Bar chart comparing heap and sort runtime at input sizes of 3, 30, and 1000 documents — Heap pulls ahead of a full sort once the corpus reaches ~1000 documents.

At tiny input sizes the constant overhead of maintaining a heap actually loses to a plain sort — it only pays off once n is large enough for the asymptotic gap to matter, which shows up cleanly between the 30-document and 1000-document runs above.

A tokenization bug worth telling

Early on, a query for treasure and Jim against Treasure Island returned a single hit — but grep found the word "treasure" five separate times in the same file. The index was under-counting because words were being stored with their surrounding punctuation still attached ("treasure," and "treasure" hashed to two different keys) and with inconsistent casing.

import string word = word.strip(string.punctuation).lower()

That one-liner alone dropped the index from 24,036 entries to 15,733 — and brought the "treasure" query results in line with grep. A second pass turned up leftover curly quotes (“ ” ‘ ’) that string.punctuation doesn't know about, since they're Unicode, not ASCII:

PUNCTUATION = string.punctuation + "“”‘’" word = word.strip(PUNCTUATION).lower()

The fix also surfaced a performance lesson: Python re-evaluates an expression like that on every loop iteration, so the punctuation set needs to be built once outside the tokenizing loop, not redefined on every word.

Precision & recall

To check whether TF‑IDF was actually earning its keep, each query was also run with TF only and IDF only as an ablation study. Precision/recall@20 was measured against metadata in the Project Gutenberg corpus that defines books as part of "bookshelves" with labels such as "adventure" and "science fiction".

Bar chart of precision and recall at 20 for the adventure query, comparing TF-IDF, TF only, and IDF only — Adventure query (5 terms, 130 relevant docs)

Bar chart of precision and recall at 20 for the science fiction query, comparing TF-IDF, TF only, and IDF only — Sci-fi query (5 terms, 33 relevant docs)

Bar chart of precision and recall at 20 for the Treasure Island query, comparing TF-IDF, TF only, and IDF only — Treasure Island query (4 terms, 1 relevant doc)

Recall and Precision are metrics for testing how well your query engine returns relevant results. Precision tells you the number of relevant results returned out of the total number of results returned by the engine. In these examples, 20 results are always returned, so precision is always some value out of 20. Recall is the number of relevant results returned out of the total number of relevant results in the dataset. In these examples:

The adventure query had 130 possible relevant results in the 964 document dataset.
The science fiction query had 33 possible relevant results in the 964 document dataset.
The treasure island query had 1 possible relevant result in the 964 document dataset.

The adventure query was five terms: “treasure voyage adventure pirates swords”, which are very common words so the term-frequency calculation outperformed the other two metrics. The science fiction query was also five terms: “spaceship future technology alien planet”, which are also very common words, so term frequency was again the best ranking calculation, with TF-IDF only slightly worse. The Treasure Island query was 4 words with less common words: “voyage yo-ho-ho travel weapons”. In particular, "yo-ho-ho" is only found in Treasure Island, and "weapons" is only in Treasure Island one time. In this case, the inverse document frequency was able to find the relevant document, but the term frequency calculation was not. These three queries together show why term frequency multiplied by inverse document frequency is a good calculation in both situations, for common query terms and uncommon query terms.

What's next

Persist the built index to disk — right now it's rebuilt from scratch on every run, which is the main bottleneck at larger corpus sizes (~5–30 minutes to index 1000 books).
Scale from ~1000 books toward the full ~80,000-book Gutenberg catalog, which will need the index-persistence work above to be usable.