Marouane.B

in the previous article, we built the first version of lexical retrieval.

we took raw text, processed it into terms, and made search less fragile.

so now a query like:

bear

can match documents like:

doc1: bear
doc2: bear bear bear
doc3: bear forest river
doc4: ocean whale

that is already better than raw string matching.

but we still have a problem.

three documents contain bear.

so which one should appear first?

does doc2 win because it says bear more times?

does doc3 win because it contains extra context like forest and river?

or should all matches be treated the same?

this is the problem TF-IDF tries to solve.

not just:

does this document match?

but:

how strongly does this document match?

before scoring: the inverted index

before scoring documents, we need a way to find matching documents quickly.

the naive approach is to scan every document for every query.

that works for tiny datasets.

it does not work for real search.

instead, search engines build an inverted index.

an inverted index maps each term to the documents where it appears.

roughly:

index = {
    "cyborg": {"doc-123", "doc-456"},
    "bear": {"doc-789"},
}

now, when the user searches for bear, we do not scan every document.

we look up:

index["bear"]

and immediately get the documents that contain it.

the index answers:

which documents contain this term?

we can store the number of occurrences separately:

term_counts = {
    ("doc-123", "cyborg"): 1,
    ("doc-456", "cyborg"): 2,
    ("doc-789", "bear"): 3,
}

the term counts answer:

how many times does this term appear in this document?

this is the foundation of fast keyword search.

first scoring idea: count the term

the simplest scoring idea is:

the more a term appears in a document, the more relevant the document is.

for the query:

bear

we might count how many times bear appears:

doc1: bear              -> 1
doc2: bear bear bear    -> 3
doc3: bear forest river -> 1
doc4: ocean whale       -> 0

with raw counts, doc2 wins.

that is not a stupid idea.

if a document repeats a term many times, that term is probably important inside the document.

but raw counts have a problem.

consider these two documents:

docA: bear bear bear
docB: a 10,000-word novel that mentions bear 3 times

both contain bear three times.

but they are not equally about bears.

in docA, the whole document is basically about bear.

in docB, bear is only a tiny part of the document.

raw counts are biased toward longer documents.

we need to take document length into account.

term frequency

there are several ways to define term frequency.

for this simple implementation, we divide the number of times the term appears by the total number of terms in the document:

tf = term_count_in_doc / total_terms_in_doc

this gives us the proportion of the document occupied by the term.

consider our documents again:

doc1: bear
doc2: bear bear bear
doc3: bear forest river
doc4: ocean whale

for the term bear:

tf(bear, doc1) = 1 / 1 = 1.00
tf(bear, doc2) = 3 / 3 = 1.00
tf(bear, doc3) = 1 / 3 = 0.33
tf(bear, doc4) = 0 / 2 = 0.00

doc1 and doc2 receive the same TF.

even though doc2 contains more occurrences, both documents are entirely composed of bear.

in doc3, bear occupies only one-third of the document.

term frequency gives us a better signal than raw count because it considers the document's length.

but TF still has a weakness.

it only looks inside one document.

it does not ask whether the term is useful across the whole collection.

second scoring idea: rare terms matter more

imagine every document in our corpus contains the word bear.

matching on bear would not tell us much.

it would not help us choose between documents.

but if only one document contains river, then river gives us more information about which document the user might want.

this is the intuition behind inverse document frequency.

a term is usually more useful for distinguishing documents when it appears in fewer documents.

Karen Spärck Jones formalized this idea as term specificity: terms should be weighted based on how they are used across the collection, not only by their meaning in isolation.

we need a score that behaves like this:

common term -> low weight
rare term   -> high weight

a first attempt could be:

total_documents / documents_containing_term

but this value can grow quickly for very rare terms.

we use a logarithm to dampen that growth:

idf = log(total_documents / documents_containing_term)

this is one simple version of inverse document frequency.

real implementations often use slightly modified formulas to handle edge cases such as terms that appear in no documents.

the Stanford IR book defines IDF using this same basic shape: rare terms receive higher weights, while common terms receive lower weights.

inverse document frequency

our corpus contains four documents:

doc1: bear
doc2: bear bear bear
doc3: bear forest river
doc4: ocean whale

therefore:

N = 4

now count how many documents contain each term:

bear   -> appears in 3 documents
forest -> appears in 1 document
river  -> appears in 1 document
ocean  -> appears in 1 document
whale  -> appears in 1 document

so:

idf(bear)   = log(4 / 3) = 0.29
idf(forest) = log(4 / 1) = 1.39
idf(river)  = log(4 / 1) = 1.39
idf(ocean)  = log(4 / 1) = 1.39
idf(whale)  = log(4 / 1) = 1.39

bear receives a lower IDF because it appears in most of the collection.

river receives a higher IDF because it appears in only one document.

this does not mean that rare terms are automatically meaningful.

a typo can also be rare.

it means that rare terms are usually more useful for distinguishing documents from one another.

combining TF and IDF

now we have two signals.

term frequency asks:

how important is this term inside this document?

inverse document frequency asks:

how useful is this term for distinguishing documents in the corpus?

TF-IDF combines them:

tf_idf = tf * idf

multiplication matters.

if a term does not appear in a document, its TF is 0, so the score is 0.

if a term appears everywhere, its IDF is close to 0, so the score is also pushed down.

a term receives a strong TF-IDF score when it is both:

important inside the document
distinctive across the corpus

not just one of them.

scoring a document

a query can contain multiple terms.

for this simple search engine, we score a document by adding the TF-IDF weights of its matching query terms:

document_score = sum(tf(term, document) * idf(term))

for the query:

bear river

we calculate the TF-IDF weight of bear, calculate the TF-IDF weight of river, then add them together for each document.

only terms that appear in the query contribute to the score.

documents with the highest total score appear first.

worked example

our corpus:

doc1: bear
doc2: bear bear bear
doc3: bear forest river
doc4: ocean whale

our query:

bear river

first, calculate term frequency:

tf(bear, doc1)   = 1 / 1 = 1.00
tf(bear, doc2)   = 3 / 3 = 1.00
tf(bear, doc3)   = 1 / 3 = 0.33
tf(bear, doc4)   = 0 / 2 = 0.00

tf(river, doc1)  = 0 / 1 = 0.00
tf(river, doc2)  = 0 / 3 = 0.00
tf(river, doc3)  = 1 / 3 = 0.33
tf(river, doc4)  = 0 / 2 = 0.00

then calculate inverse document frequency:

idf(bear)  = log(4 / 3) = 0.29
idf(river) = log(4 / 1) = 1.39

now calculate each document's score.

for doc1:

bear  = 1.00 * 0.29 = 0.29
river = 0.00 * 1.39 = 0.00

score(doc1) = 0.29

for doc2:

bear  = 1.00 * 0.29 = 0.29
river = 0.00 * 1.39 = 0.00

score(doc2) = 0.29

for doc3:

bear  = 0.33 * 0.29 = 0.10
river = 0.33 * 1.39 = 0.46

score(doc3) = 0.10 + 0.46 = 0.56

for doc4:

bear  = 0.00 * 0.29 = 0.00
river = 0.00 * 1.39 = 0.00

score(doc4) = 0.00

the final ranking is:

doc3 -> 0.56
doc1 -> 0.29
doc2 -> 0.29
doc4 -> 0.00

doc3 wins because it contains both query terms.

although bear occupies less of doc3, the rare term river provides strong evidence that the document is relevant to the complete query.

doc1 and doc2 tie.

under our normalized TF formula, both documents are entirely composed of bear, so repeating the same word three times does not make doc2 stronger.

that is the core idea.

TF-IDF rewards query terms that are important inside a document and distinctive across the corpus.

code example

a minimal implementation looks like this:

# Preprocessing has already converted each document into terms.
documents = {
    "doc1": ["bear"],
    "doc2": ["bear", "bear", "bear"],
    "doc3": ["bear", "forest", "river"],
    "doc4": ["ocean", "whale"],
}


index = defaultdict(set)
term_counts = Counter()
document_lengths = {}

for document_id, terms in documents.items():
    document_lengths[document_id] = len(terms)

    for term in terms:
        index[term].add(document_id)
        term_counts[(document_id, term)] += 1


def get_tf(document_id, term):
    term_count = term_counts[(document_id, term)]
    document_length = document_lengths[document_id]

    if document_length == 0:
        return 0.0

    return term_count / document_length


def get_idf(term):
    total_documents = len(documents)
    documents_containing_term = len(index.get(term, set()))

    if documents_containing_term == 0:
        return 0.0

    return math.log(
        total_documents / documents_containing_term
    )


def score_document(document_id, query_terms):
    score = 0.0

    for term in query_terms:
        score += get_tf(document_id, term) * get_idf(term)

    return score


query_terms = ["bear", "river"]

ranking = sorted(
    documents,
    key=lambda document_id: score_document(document_id, query_terms),
    reverse=True,
)

for document_id in ranking:
    score = score_document(document_id, query_terms)
    print(document_id, round(score, 2))

output:

doc3 0.56
doc1 0.29
doc2 0.29
doc4 0.0

this is still a tiny search engine.

but it now contains the beginning of ranking.

what TF-IDF gives us

with preprocessing, we decided what counts as a term.

with the inverted index, we found matching documents quickly.

with TF-IDF, we started ranking those matches.

the big idea is simple:

a useful query term is important inside the document, but uncommon across the corpus.

TF-IDF is still lexical.

it does not know that car and automobile are related.

it does not know that ran and running are related unless preprocessing already reduced them to the same form.

it does not understand meaning.

it only works with terms and statistics.

but for lexical search, this is already a major step.

we no longer return documents only because they match.

we can start asking:

which match is probably better?

what is still missing?

our TF definition normalizes the term count using the document's length.

but it still treats repetition in a simplistic way.

the difference between one occurrence and two occurrences can be important.

after a term already appears many times, however, repeating it again should probably provide less additional evidence.

document length is also difficult.

long documents have more opportunities to contain query terms.

very short documents can receive unusually strong TF values when a single term dominates their text.

BM25 handles these problems more carefully through two ideas:

term-frequency saturation
document-length normalization relative to the average document

that is the next step.

One Problem at a Time: Building RAG From Scratch - part 3