std.AutoHashMap;std.mem.sort so the best document lands at position zero, the way a real search box behaves;Index, Posting and Tokenizer, and pick the story up precisely where it left off;std.StringHashMap comfort from episode 22, the iterator shape from episode 23, and the std.mem.sort reflex from the sorting run around episode 116;Learn Zig Series):Last episode ended on a deliberate note of dissatisfaction. We built a real boolean search engine -- an inverted index that answers "which documents contain all of these words" with a couple of linear merges instead of re-reading the archive -- and then I pointed at the hole in the middle of it. When "systems language" came back as {0, 1}, the engine handed you two documents and shrugged. It had no opinion about which one you would actualy rather read first. A real search box is not a set-membership test; it is a ranking. It puts the best answer at the top and the also-rans below, and the entire difference between "a pile of matching documents" and "search" lives in that ordering.
So today we teach the engine to rank. And the beautiful part -- the reason I split the project here -- is that we already stored everything we need. Every posting carries a term frequency, and behind documentFrequency sits the count of how many documents hold a word. Those two numbers are the whole raw material of ranking. We are not going to bolt on some new subsystem; we are going to take the two counters we have been quietly filling since last episode and turn them into a score. This is a mini-project episode, so there are no separate exercises -- the build is the exercise, and by the end you will have a search engine that sorts its own results.
Let us make the goal painfully concrete before we write anything, because "rank the results" sounds obvious and hides a genuinely subtle question. Suppose you search for quick fox across a small corpus. Which document deserves the top slot? Your instinct says: the one where "quick" and "fox" show up the most. That instinct -- reward the document that mentions your words a lot -- is called term frequency, and it is half right. A document that says "fox" eight times really is more about foxes than one that says it once.
But term frequency alone ranks the wrong things to the top, and it does so for a reason worth stating precisely. Consider a two-word query like the fox. The word "the" appears in nearly every document, dozens of times each. If we score by raw term frequency, the winner is whichever document happens to be longest and most stuffed with "the" -- a document that might not even mention foxes. The common word drowns out the rare one. Here is that failure written as code, scoring a single document by summing the term frequencies of the query words:
// naive scoring: just add up how often each query word appears -- and it ranks the wrong docs
fn naiveScore(index: *const Index, doc: u32, query: []const u8) u32 {
var score: u32 = 0;
var tok = Tokenizer{ .text = query };
while (tok.next()) |term| {
for (index.postingsFor(term)) |p| {
if (p.doc == doc) score += p.tf;
}
}
return score;
}
The bug is not in the code -- the code does exactly what it says. The bug is in the idea. Every word contributes with equal authority, so "the" (which distinguishes nothing) shouts just as loud as "fox" (which distinguishes almost everything). What we are missing is a way to say: a word that appears in every document is worthless as a discriminator, and a word that appears in few documents is precious. That measure exists, it has a name, and it is the second half of the most famous ranking formula in information retrieval.
The insight is to weight each word by how rare it is across the whole corpus. If a word appears in only a handful of documents, then a document containing it is genuinely distinguished -- the word carries a lot of information. If a word appears everywhere, containing it tells you nothing. We already have the raw quantity: document frequency (df), the number of documents a term appears in, which is exactly the length of its postings list. We just need to turn "small df" into "big weight" and "large df" into "small weight". The classic answer is inverse document frequency:
idf(term) = log( N / df )
where N is the total number of documents. Walk through what it does. A word in every document has df = N, so N/df = 1, and log(1) = 0 -- the word contributes nothing, exactly as we want "the" to. A word in one document out of ten thousand has N/df = 10000, and log of that is large -- a strong, discriminating signal. The logarithm is not decoration; it is there to dampen. Without it, a word twice as rare would count twice as much, and rarity would dominate everything else wildly. The log squashes that into a gentle, diminishing curve -- the same "diminishing returns" shape we kept meeting in the consistent-hashing load curves last episode. Here it is on top of the Index, reusing documentFrequency:
fn idf(self: *const Index, term_raw: []const u8) f64 {
const df = self.documentFrequency(term_raw);
if (df == 0) return 0; // unknown word: no documents, no signal
const n: f64 = @floatFromInt(self.doc_count);
const d: f64 = @floatFromInt(df);
return @log(n / d); // natural log; the base only scales all scores uniformly
}
test "idf is zero for a word in every document and positive for a rare one" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
_ = try index.addDocument("the quick brown fox");
_ = try index.addDocument("the lazy brown dog");
_ = try index.addDocument("the sleepy cat");
try std.testing.expectEqual(@as(f64, 0), index.idf("the")); // in all 3 docs -> log(3/3) = 0
try std.testing.expect(index.idf("fox") > index.idf("brown")); // fox in 1 doc, brown in 2
try std.testing.expectEqual(@as(f64, 0), index.idf("elephant")); // unknown -> 0
}
The base of the logarithm genuinely does not matter for ranking -- switching from natural log to log base 2 multiplies every idf by the same constant, and a constant scale factor never reorders a list. I use @log (natural log) because it is the built-in and the cheapest thing to reach for. Notice the guard on df == 0: an unknown word has no documents, and we must not divide by zero. Returning zero there is not a hack -- it is the correct semantics, since a word we have never indexed contributes nothing to any document's score.
Before we assemble the score, there is one more number we will want, and it is cheapest to record while we are already walking each document: its length in terms. We will need it shortly to stop long documents from cheating. Last episode's Index did not track this, so we extend it with a single new field, doc_lengths, and remember to free it. Here is the extended struct -- the same map, doc_count and ownership discipline from episode 125, plus the one new list:
const std = @import("std");
const Posting = struct { doc: u32, tf: u32 };
const Postings = struct { list: std.ArrayList(Posting) = .empty };
const Index = struct {
gpa: std.mem.Allocator,
map: std.StringHashMap(Postings),
doc_count: u32 = 0,
doc_lengths: std.ArrayList(u32) = .empty, // NEW: how many terms each document had
fn init(gpa: std.mem.Allocator) Index {
return .{ .gpa = gpa, .map = std.StringHashMap(Postings).init(gpa) };
}
fn deinit(self: *Index) void {
var it = self.map.iterator();
while (it.next()) |e| {
e.value_ptr.list.deinit(self.gpa); // free each postings list
self.gpa.free(e.key_ptr.*); // free the duped term string
}
self.map.deinit();
self.doc_lengths.deinit(self.gpa); // NEW: free the lengths list too
}
};
Nothing here should surprise you after last time -- the map still owns its term strings, still frees each postings list, and the only addition is one more owned buffer torn down at the end. Three owners became four, all accounted for, and std.testing.allocator will still slam the door on any leak. That is the whole point of making ownership explicit: adding a field forces exactly one new line in deinit, and the compiler and the leak checker between them guarantee you did not forget it.
The addDocument from last episode is almost unchanged -- we bolt on a len counter that increments once per term and gets recorded at the end. Everything else (the getOrPut, the owned-key dupe, the frequency bump on repeat words, the natural sortedness of postings) is exactly as we left it:
fn isTermChar(c: u8) bool {
return (c >= 'a' and c <= 'z') or (c >= 'A' and c <= 'Z') or (c >= '0' and c <= '9');
}
const Tokenizer = struct {
text: []const u8,
pos: usize = 0,
buf: [64]u8 = undefined,
fn next(self: *Tokenizer) ?[]const u8 {
while (self.pos < self.text.len and !isTermChar(self.text[self.pos])) : (self.pos += 1) {}
if (self.pos >= self.text.len) return null;
const start = self.pos;
while (self.pos < self.text.len and isTermChar(self.text[self.pos])) : (self.pos += 1) {}
const raw = self.text[start..self.pos];
const n = @min(raw.len, self.buf.len);
for (raw[0..n], 0..) |c, i| self.buf[i] = std.ascii.toLower(c);
return self.buf[0..n];
}
};
fn lower(raw: []const u8, buf: []u8) []const u8 {
const n = @min(raw.len, buf.len);
for (raw[0..n], 0..) |c, i| buf[i] = std.ascii.toLower(c);
return buf[0..n];
}
fn addDocument(self: *Index, text: []const u8) !u32 {
const doc_id = self.doc_count;
self.doc_count += 1;
var len: u32 = 0;
var tok = Tokenizer{ .text = text };
while (tok.next()) |term| {
len += 1; // count every term, including repeats
const gop = try self.map.getOrPut(term);
if (!gop.found_existing) {
gop.key_ptr.* = self.gpa.dupe(u8, term) catch |err| {
_ = self.map.remove(term);
return err;
};
gop.value_ptr.* = .{};
}
const p = gop.value_ptr;
const nn = p.list.items.len;
if (nn > 0 and p.list.items[nn - 1].doc == doc_id) {
p.list.items[nn - 1].tf += 1; // same word again in this doc -> bump tf
} else {
try p.list.append(self.gpa, .{ .doc = doc_id, .tf = 1 });
}
}
try self.doc_lengths.append(self.gpa, len); // record this doc's length
return doc_id;
}
fn postingsFor(self: *const Index, term_raw: []const u8) []const Posting {
var buf: [64]u8 = undefined;
const term = lower(term_raw, &buf);
const e = self.map.get(term) orelse return &.{};
return e.list.items;
}
fn documentFrequency(self: *const Index, term_raw: []const u8) usize {
return self.postingsFor(term_raw).len;
}
Because documents are indexed in id order and doc_lengths is appended once per document, doc_lengths.items[doc] is always the term count of document doc -- the array is dense and index-aligned with the doc ids, no map needed. That is a small thing worth savouring: when your ids are a contiguous 0, 1, 2, ... run, a plain array is the fastest possible map from id to value, and Zig's ArrayList gives it to you with zero ceremony.
Now we put the two halves together. The weight of a term in a document is its term frequency times its inverse document frequency -- tf-idf. To score a whole query against a document, we sum the tf-idf weight of each query term. And to score every candidate at once, we do a single pass over the query terms' postings lists, accumulating a running score per document in a std.AutoHashMap(u32, f64) -- doc id to score. This is the natural spelling of the operation: we do not know in advance which documents will match, so we let the hash map grow the candidate set as we discover it.
One refinement over raw tf. A word appearing 100 times is more relevant than a word appearing once, but it is not 100 times more relevant -- relevance saturates. So we use a sublinear term frequency, 1 + log(tf), the same dampening trick we used for idf. Here is the scorer, returning a list of { doc, score } results:
const Result = struct { doc: u32, score: f64 };
fn tfWeight(tf: u32) f64 {
return 1.0 + @log(@as(f64, @floatFromInt(tf))); // sublinear: tf=1 -> 1.0, tf=8 -> ~3.08
}
fn searchRanked(self: *const Index, gpa: std.mem.Allocator, query: []const u8) !std.ArrayList(Result) {
var scores = std.AutoHashMap(u32, f64).init(gpa);
defer scores.deinit();
var tok = Tokenizer{ .text = query };
while (tok.next()) |term| {
const w = self.idf(term);
if (w == 0) continue; // word in every doc (or absent): adds nothing, skip it
for (self.postingsFor(term)) |post| {
const contribution = tfWeight(post.tf) * w;
const gop = try scores.getOrPut(post.doc);
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += contribution; // accumulate across all query terms
}
}
var results: std.ArrayList(Result) = .empty;
var it = scores.iterator();
while (it.next()) |e| {
try results.append(gpa, .{ .doc = e.key_ptr.*, .score = e.value_ptr.* });
}
std.mem.sort(Result, results.items, {}, struct {
fn less(_: void, a: Result, b: Result) bool {
return a.score > b.score; // highest score first -> best result at index 0
}
}.less);
return results;
}
A few decisions are quietly load-bearing here. Scoring is OR semantics: a document is a candidate if it contains at least one query term, unlike last episode's AND intersection which demanded all of them. That is what you want for ranking -- you would rather show a partial match ranked low than nothing at all -- and the score sorts the fully-matching documents above the partial ones automatically, because they collect more contributions. The if (w == 0) continue is both an optimization and a correctness statement: a word in every document has idf zero, so it can neither add to nor break any ranking, and skipping it saves us walking its (enormous) postings list. And the final std.mem.sort with a.score > b.score is the whole payoff -- the comparator that flips a set of matches into a ranked answer, best-first.
Let us watch it order a corpus where the naive scorer would have failed:
test "ranking puts the most relevant document first" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
_ = try index.addDocument("the fox is quick the fox is clever"); // 0: fox x2
_ = try index.addDocument("the the the the the lazy dog"); // 1: all common words
_ = try index.addDocument("a quick brown fox jumps"); // 2: fox x1, quick x1
var results = try index.searchRanked(gpa, "quick fox");
defer results.deinit(gpa);
try std.testing.expect(results.items.len == 2); // doc 1 has neither "quick" nor "fox"
try std.testing.expectEqual(@as(u32, 0), results.items[0].doc); // most fox-and-quick
try std.testing.expectEqual(@as(u32, 2), results.items[1].doc);
try std.testing.expect(results.items[0].score > results.items[1].score);
}
Document 1, which is nothing but "the" repeated and a lazy dog, does not even appear in the results -- it contains no query term with any idf, so it scores nothing and never enters the candidate map. Document 0 wins over document 2 because it holds "fox" twice and "quick", collecting more weight. That is precisely the ordering a human would pick, produced entirely from two counters and a logarithm. No document was re-read; we only ever walked the postings of the two query words.
There is a bias hiding in that scorer, and it is the classic one. A long document has more room to accidentally contain your query words, and more room to repeat them, so it accumulates score simply by being big -- not by being relevant. A thousand-word rambling essay that mentions "fox" three times in passing will out-score a crisp two-line note that is entirely about foxes, even though the note is the better answer. Left unchecked, TF-IDF quietly rewards verbosity.
The fix is length normalization: divide each document's score by a function of its length, so that concentration of relevance matters more than raw volume. Dividing by the length outright over-corrects (it punishes long documents too harshly), so the standard move -- the one cosine normalization approximates -- is to divide by the square root of the length. That is exactly why we recorded doc_lengths. Here is the normalized scorer, one line different from before:
fn searchRankedNorm(self: *const Index, gpa: std.mem.Allocator, query: []const u8) !std.ArrayList(Result) {
var scores = std.AutoHashMap(u32, f64).init(gpa);
defer scores.deinit();
var tok = Tokenizer{ .text = query };
while (tok.next()) |term| {
const w = self.idf(term);
if (w == 0) continue;
for (self.postingsFor(term)) |post| {
const gop = try scores.getOrPut(post.doc);
if (!gop.found_existing) gop.value_ptr.* = 0;
gop.value_ptr.* += tfWeight(post.tf) * w;
}
}
var results: std.ArrayList(Result) = .empty;
var it = scores.iterator();
while (it.next()) |e| {
const len: f64 = @floatFromInt(self.doc_lengths.items[e.key_ptr.*]);
const norm = if (len > 0) @sqrt(len) else 1.0; // divide out document length
try results.append(gpa, .{ .doc = e.key_ptr.*, .score = e.value_ptr.* / norm });
}
std.mem.sort(Result, results.items, {}, struct {
fn less(_: void, a: Result, b: Result) bool {
return a.score > b.score;
}
}.less);
return results;
}
The only change is in the results-building loop: we look up the document's length -- a dense array read, doc_lengths.items[doc], no hashing -- and divide the accumulated score by its square root. Let us prove it changes the outcome, with a short focused document going head to head against a long padded one:
test "length normalization lets a focused short doc beat a padded long one" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
// doc 0: short and entirely on-topic -- "zig" twice in two words
_ = try index.addDocument("zig zig");
// doc 1: "zig" twice too, but drowned in unrelated padding
_ = try index.addDocument("zig appears here and zig again among many other unrelated filler words about cooking and travel");
// doc 2: no "zig" at all -- keeps idf non-zero so the term still carries signal
_ = try index.addDocument("python tutorial for beginners");
var raw = try index.searchRanked(gpa, "zig");
defer raw.deinit(gpa);
// raw tf-idf: both docs have tf 2, so they score identically -- length is invisible
try std.testing.expect(raw.items.len == 2);
var norm = try index.searchRankedNorm(gpa, "zig");
defer norm.deinit(gpa);
try std.testing.expectEqual(@as(u32, 0), norm.items[0].doc); // focused short doc wins
try std.testing.expect(norm.items[0].score > norm.items[1].score);
}
Both documents mention "zig" exactly twice, so raw TF-IDF scores them identically -- length is invisible to it. With normalization, the crisp two-word document that is nothing but "zig" rises decisively above the sprawling one where the same two mentions are buried among cooking and travel words. The short document's relevance is concentrated, and dividing by the square root of length is how we reward that concentration. This is the difference between a search box that feels sharp and one that feels like it is burying the good answer under padding.
Let us drive the whole thing once with a corpus that looks a little more like real documents, so you can see the ranking behave end to end -- indexing several documents, then asking a two-word query and reading back an ordered list of results:
test "end to end: index a small corpus and rank a real query" {
const gpa = std.testing.allocator;
var index = Index.init(gpa);
defer index.deinit();
_ = try index.addDocument("Zig is a systems programming language with no hidden control flow");
_ = try index.addDocument("Rust is a systems programming language focused on memory safety");
_ = try index.addDocument("Python is a scripting language that is easy to learn");
_ = try index.addDocument("systems systems systems language language language"); // keyword-stuffed
var results = try index.searchRankedNorm(gpa, "systems language");
defer results.deinit(gpa);
// every doc except the Python one holds at least one of the two query terms with signal
try std.testing.expect(results.items.len >= 3);
// the top result must actually contain both query words
const top = results.items[0].doc;
try std.testing.expect(top == 0 or top == 1 or top == 3);
// results are sorted strictly by descending score
var i: usize = 1;
while (i < results.items.len) : (i += 1) {
try std.testing.expect(results.items[i - 1].score >= results.items[i].score);
}
}
Run this under zig test and it passes clean, no leaks -- every ArrayList and AutoHashMap we opened is closed on the correct allocator, the same discipline drilled all the way back in episode 7. What you have now is a genuine ranked retrieval engine: feed it text, ask it a question in words, and it returns documents ordered by how well they answer -- not merely whether they match. That is the leap from episode 125's boolean set to something that behaves like a search box.
TF-IDF is not a teaching toy -- it is the historical bedrock of full-text search, and every serious engine is a hardened, extended version of what we just wrote. In C, this is the shape at the bottom of the classic retrieval systems: a term-to-postings hash table exactly like ours, scores accumulated into a flat array indexed by doc id (an "accumulator array", the array-as-map trick we leaned on for lengths), and a partial sort -- a heap that keeps only the top k -- instead of sorting the whole result set, because when you have a million matches you only ever want the first ten. That top-k heap is the single most important optimization we did not write today, and it is worth knowing it is there.
In Rust, the natural spelling is HashMap<u32, f64> for the accumulators and a BinaryHeap for top-k, and the tf-idf arithmetic is identical to ours line for line. The tantivy crate -- Rust's Lucene-class search engine -- computes exactly this family of scores, though its default is BM25, the modern refinement of TF-IDF that adds tunable term-frequency saturation and a smarter length-normalization curve (the same two problems we hit today, solved with two extra parameters). In Go, you would reach for map[uint32]float64 and container/heap, and Bleve is the production engine that does it for real. Java's Lucene -- the machine inside Elasticsearch and Solr -- is the same story wearing decades of optimization: compressed postings, skip lists inside the merge, and BM25 scoring over an inverted index that is, at heart, the one we built across these two episodes. Four ecosystems, one formula, one truth: rank by term frequency, discount by document frequency, normalize by length. Bam, jonguh ;-)
Step back and look at the arc. Episode 125 gave us an index that could find; today gave it the judgement to rank. Between them we have a small but honest search engine -- tokenizer, inverted index, boolean AND, and now TF-IDF scoring with length normalization -- and every gear in it is something we forged earlier in the series: the hash map from episode 22, the iterator from episode 23, the sort from the algorithms run, the ownership discipline from the very start.
But there is still a crack of naivety in how a query reaches the engine. Right now a "query" is just a bare string that we chop into a flat bag of words -- searchRanked treats "quick fox" and "fox quick" identically, and it has no way to express "these two words next to each other", or "this word but not that one", or "this OR that". Real search users type things with structure, and structure needs to be parsed before it can be answered. We have, conveniently, spent whole earlier episodes building exactly the machinery for turning structured text into something a program can act on -- tokenizers, and the parsing techniques from the markdown project. Next time we point that machinery at the search box itself and give our engine a query language of its own. That is where "type some words" turns into "ask a real question" ;-)
Thanks for your time, and until the next one -- go index a folder of your own text files and watch the right document float to the top. De groeten! ;-)
@scipio