Build a small search engine

A search engine does two things: it finds the documents containing the words, and it ranks them.

Step 1 — the inverted index. Instead of «document → words» you build «word → documents»:

"cat"  → {1, 4, 7}
"dog"  → {2, 4}
"food" → {1, 2, 3, 4, 5, 6, 7}

If you search for «cat dog» you take the intersection: document 4. That happens in an instant even with millions of documents, because you never read a document.

Step 2 — the ranking. Just counting words works badly. The word «food» is in every document and says nothing; «cat» is in three and says a lot.

TF-IDF captures that with two factors:

• TF (term frequency): the more often the word is in the document, the more relevant.
• IDF (inverse document frequency): the fewer documents the word is in, the more distinguishing.

The product makes rare words that do occur weigh the heaviest — exactly as intuition says.

The formula:

$\mathrm{tfidf}(t, d) = \underbrace{\frac{f_{t,d}}{|d|}}_{\text{TF}} \cdot \underbrace{\log\frac{N}{n_t}}_{\text{IDF}}$

where $f_{t,d}$ is the number of occurrences, $|d|$ the length of the document, $N$ the total number of documents and $n_t$ the number of documents containing the term.

The situation	IDF	The interpretation
The word is in every document	$\log(N/N) = 0$	says nothing
The word is in half of them	$\log 2 \approx 0.69$	moderate
The word is in 1 of 1 000	$\log 1000 \approx 6.9$	very distinguishing

The normalisation by document length is needed because long documents would otherwise always win — they contain more of everything.

The preprocessing matters more than the formula. Four steps, in order:

1. Lower case — «Cat» and «cat» should be the same word.
2. Remove punctuation — «cat.» and «cat» likewise.
3. Stop words — «and», «that», «a» are everywhere and carry no information. (IDF handles them partly automatically.)
4. Stemming or lemmatisation — «cats», «cat's» to the same base form.

For Swedish, step 4 matters more than for English, because the morphology is richer. And compounds are the genuinely hard part: «kattmat» (cat food, one word in Swedish) does not match the search «mat» (food) with word-based matching, however you preprocess.

This is the same foundation RAG is built on. The difference is that RAG compares meaning through embeddings instead of words. The best is nearly always to combine both — word matching finds exact terms and names, vector search finds paraphrases.

import math, re
from collections import defaultdict, Counter

STOPWORDS = {"and", "that", "a", "an", "as", "it", "in", "on", "is", "for", "with", "of", "the"}

def tokenise(text):
    return [w for w in re.findall(r"\w+", text.lower()) if w not in STOPWORDS]

class SearchEngine:
    def __init__(self, documents):
        self.docs = documents
        self.tokens = [tokenise(d) for d in documents]
        self.index = defaultdict(set)                 # word -> the set of document ids
        for i, toks in enumerate(self.tokens):
            for t in set(toks):
                self.index[t].add(i)
        self.N = len(documents)

    def idf(self, term):
        n = len(self.index.get(term, ()))
        return math.log(self.N / n) if n else 0.0

    def search(self, query, k=3):
        terms = tokenise(query)
        scores = Counter()
        for i, toks in enumerate(self.tokens):
            if not toks:
                continue
            counts = Counter(toks)
            p = sum((counts[t] / len(toks)) * self.idf(t) for t in terms)
            if p > 0:
                scores[i] = p
        return [(self.docs[i], round(p, 4)) for i, p in scores.most_common(k)]

documents = [
    "The cat sleeps on the mat and eats food",
    "The dog eats food in the kitchen",
    "Food is important for all animals",
    "The cat and the dog play together",
]
s = SearchEngine(documents)

for hit, p in s.search("cat food"):
    print(f"{p:.4f}  {hit}")
# 0.1961  The cat sleeps on the mat and eats food
# 0.1733  The cat and the dog play together
# 0.0719  The dog eats food in the kitchen

print("idf('food') =", round(s.idf("food"), 3))       # 0.288 — in three of four
print("idf('kitchen') =", round(s.idf("kitchen"), 3)) # 1.386 — in one

# The compounding problem (in Swedish "kattmat" — cat food — is ONE word)
print(s.search("catfood"))    # [] — no document contains that word

The last line is the Swedish trap in a nutshell: «kattmat» is one word, and word-based matching finds neither «katt» nor «mat» in it.