Bygg en liten sökmotor

En sökmotor gör två saker: hittar dokument som innehåller orden, och rangordnar dem.

Steg 1 — inverterat index. I stället för «dokument → ord» bygger man «ord → dokument»:

"katt"  → {1, 4, 7}
"hund"  → {2, 4}
"mat"   → {1, 2, 3, 4, 5, 6, 7}

Söker du «katt hund» tar du snittet: dokument 4. Det går på ett ögonblick även med miljontals dokument, eftersom du aldrig läser något dokument.

Steg 2 — rangordning. Att bara räkna ord fungerar dåligt. Ordet «mat» finns i alla dokument och säger ingenting; «katt» finns i tre och säger mycket.

TF-IDF fångar det med två faktorer:

• TF (term frequency): ju oftare ordet finns i dokumentet, desto mer relevant.
• IDF (inverse document frequency): ju färre dokument ordet finns i, desto mer särskiljande.

Produkten gör att sällsynta ord som faktiskt förekommer väger tyngst — precis som intuitionen säger.

Formeln:

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

där $f_{t,d}$ är antalet förekomster, $|d|$ dokumentets längd, $N$ totala antalet dokument och $n_t$ antalet dokument som innehåller termen.

Situation	IDF	Tolkning
Ordet finns i alla dokument	$\log(N/N) = 0$	säger ingenting
Ordet finns i hälften	$\log 2 \approx 0{,}69$	måttligt
Ordet finns i 1 av 1 000	$\log 1000 \approx 6{,}9$	mycket särskiljande

Normaliseringen med dokumentlängd behövs för att långa dokument annars alltid skulle vinna — de innehåller fler av allt.

Förbehandlingen spelar större roll än formeln. Fyra steg, i ordning:

1. Gemener — «Katt» och «katt» ska vara samma ord.
2. Ta bort skiljetecken — «katt.» och «katt» likaså.
3. Stoppord — «och», «att», «en» finns överallt och bär ingen information. (IDF hanterar dem delvis automatiskt.)
4. Stamning eller lemmatisering — «katter», «katten», «katts» till samma grundform.

För svenska är steg 4 viktigare än för engelska, eftersom morfologin är rikare. Och sammansättningar är det verkligt svåra: «kattmat» matchar inte sökningen «mat» med ordbaserad matchning, hur du än förbehandlar.

Detta är samma grund som RAG bygger på. Skillnaden är att RAG jämför betydelse via embeddingar i stället för ord. Bäst blir nästan alltid att kombinera båda — ordmatchning hittar exakta termer och namn, vektorsökning hittar omskrivningar.

import math, re
from collections import defaultdict, Counter

STOPPORD = {"och", "att", "en", "ett", "som", "det", "i", "på", "är", "för", "med", "av", "den"}

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

class Sokmotor:
    def __init__(self, dokument):
        self.dok = dokument
        self.tokens = [tokenisera(d) for d in dokument]
        self.index = defaultdict(set)                 # ord -> mängd dokument-id
        for i, toks in enumerate(self.tokens):
            for t in set(toks):
                self.index[t].add(i)
        self.N = len(dokument)

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

    def sok(self, fraga, k=3):
        termer = tokenisera(fraga)
        poang = Counter()
        for i, toks in enumerate(self.tokens):
            if not toks:
                continue
            antal = Counter(toks)
            p = sum((antal[t] / len(toks)) * self.idf(t) for t in termer)
            if p > 0:
                poang[i] = p
        return [(self.dok[i], round(p, 4)) for i, p in poang.most_common(k)]

dokument = [
    "Katten sover på mattan och äter mat",
    "Hunden äter mat i köket",
    "Mat är viktigt för alla djur",
    "Katten och hunden leker tillsammans",
]
s = Sokmotor(dokument)

for traff, p in s.sok("katt mat"):
    print(f"{p:.4f}  {traff}")
# 0.1219  Katten sover på mattan och äter mat
# 0.1386  ...

print("idf('mat') =", round(s.idf("mat"), 3))       # 0.0   — finns i alla
print("idf('köket') =", round(s.idf("köket"), 3))   # 1.386 — finns i ett

# Sammansättningsproblemet
print(s.sok("kattmat"))     # [] — inget dokument innehåller det ordet

Sista raden är den svenska fällan i ett nötskal: «kattmat» är ett ord, och ordbaserad matchning hittar varken «katt» eller «mat» i det.