What TF-IDF actually measures
Step 5 of 12, and the postings lists start answering questions. Every posting gains a term frequency, every document gains a length, and haystack can rank: for a query term it now produces a score per document instead of a list of ids. The scorer is TF-IDF in its classic form, and on this corpus it gets the most obvious query wrong — a long page that mentions “borrow” in passing outranks the page that is about borrowing. That failure is the document length bias, and it is the reason step 6 exists.
The starting state is tag search-ch04, the end of step 4: an index that saves to disk and loads back. The end state of this step is tagged search-ch05; the whole file is at the end of this page, and the checkout commands follow it.
What a posting has to carry
Section titled “What a posting has to carry”Since step 2 a posting has been a bare document id. That answers “which documents contain this term”, and document frequency — how many documents contain it — comes for free, as the length of the postings list. TF-IDF needs two more numbers, and neither is on disk:
- Term frequency. How often the term appears inside one document. A page that says “borrow” four times is more about borrowing than one that says it once.
- Document length. How many terms the document holds. Without it, the extra mentions a long document makes look like enthusiasm rather than length.
Both are counted while the text is in hand, at indexing time; neither can be recovered from the file afterwards. So the file format changes. Version 1 held ids only. Version 2 holds the rest, and refuses a version 1 file rather than guessing.
Counting term frequency
Section titled “Counting term frequency”add_document tokenises the text and sorts the terms. Step 2 sorted them to deduplicate; now the same sorted list is walked in runs, and a run of equal terms is that term’s frequency in the document:
/// Count a sorted term list in runs: each distinct term once, with the/// number of times it occurred. ["dog", "fox", "fox", "fox"] counts/// "dog" once and "fox" three times.fn count_terms(sorted: &[String]) -> Vec<(&str, u32)> { let mut counts = Vec::new(); let mut start = 0; while start < sorted.len() { let mut end = start + 1; while end < sorted.len() && sorted[end] == sorted[start] { end += 1; } counts.push((sorted[start].as_str(), (end - start) as u32)); start = end; } counts}
fn main() { let mut terms = ["fox", "dog", "fox", "fox"] .iter() .map(|word| word.to_string()) .collect::<Vec<_>>(); terms.sort_unstable(); println!("{:?}", count_terms(&terms));}Run this in the Rust Playground
[("dog", 1), ("fox", 3)]Each distinct term becomes one posting, and the run’s length rides along in it as tf. The document’s length is the term count before deduplication — every term the tokeniser kept. Stop words are not in the index, so they are not in the length either: a document’s length is the number of terms that could match something.
Document frequency, and the log
Section titled “Document frequency, and the log”Document frequency is postings.len(), the thing step 4 wrote to disk. The inverse document frequency turns it into a weight:
idf = ln(N / df)where N is the number of documents and df the document frequency. The form dates to Karen Sparck Jones’s 1972 paper on term specificity, and it has outlived every replacement anyone has proposed for it:
/// How much information a term carries: the natural log of the document/// count over the number of documents containing the term.////// A term in every document scores zero — it cannot tell two documents/// apart. A term in one document scores the most. The zero for an empty/// postings list is for callers that pass one: a term in no document is/// not in the dictionary at all.fn idf(df: usize, n: usize) -> f64 { if df == 0 { return 0.0; } (n as f64 / df as f64).ln()}
fn main() { let n = 6; println!("idf = ln({n} / df):"); for df in 1..=n { println!(" df={df} idf={:.4}", idf(df, n)); }}Run this in the Rust Playground
idf = ln(6 / df): df=1 idf=1.7918 df=2 idf=1.0986 df=3 idf=0.6931 df=4 idf=0.4055 df=5 idf=0.1823 df=6 idf=0.0000The curve is the whole idea. A term in every document scores zero — ln(N/N) is ln 1 — because it cannot separate one document from another. A term in one document scores ln N, the most there is. The log is a compression, not a law: without it the ratio is unbounded, and on a million-document corpus a term in one document would be worth a million times a term in all of them, one rare word drowning every other signal in the score. The natural log of a million is about 13.8 — still the top of the range, but a range.
What the log buys in the middle is a fixed step: halving the document frequency adds ln 2 to the weight, whether df goes from 100 to 50 or from 2 to 1.
The score
Section titled “The score”TF-IDF multiplies the two: the term’s frequency in the document, times the inverse of its document frequency. Nothing else enters.
/// One entry in a term's postings list: the document, and how many/// times the term appears in it.#[derive(Debug, PartialEq)]struct Posting { doc: u32, tf: u32,}
/// How much information a term carries: the natural log of the document/// count over the number of documents containing the term.////// A term in every document scores zero — it cannot tell two documents/// apart. A term in one document scores the most. The zero for an empty/// postings list is for callers that pass one: a term in no document is/// not in the dictionary at all.fn idf(df: usize, n: usize) -> f64 { if df == 0 { return 0.0; } (n as f64 / df as f64).ln()}
/// Rank a term's postings by TF-IDF, best first. Each result is/// (document, term frequency, score).////// The score is the term's frequency in the document times the inverse/// of its document frequency — raw counts, with no length/// normalisation, which is what makes step 6 necessary. Equal scores/// keep their input order, and postings arrive in ascending document/// order, so ties come out in document order.fn rank(postings: &[Posting], n: usize) -> Vec<(u32, u32, f64)> { let idf = idf(postings.len(), n); let mut ranked: Vec<(u32, u32, f64)> = postings .iter() .map(|p| (p.doc, p.tf, p.tf as f64 * idf)) .collect(); // f64 is not Ord, because of NaN. total_cmp gives every float a // place in a total order, and sort_by is stable, so equal scores // keep the order they arrived in. ranked.sort_by(|a, b| b.2.total_cmp(&a.2)); ranked}
fn main() { // The "borrow" postings from the demo corpus: five documents, // five frequencies, one term. let postings = [ Posting { doc: 0, tf: 1 }, Posting { doc: 1, tf: 4 }, Posting { doc: 2, tf: 1 }, Posting { doc: 3, tf: 1 }, Posting { doc: 5, tf: 5 }, ]; for (doc, tf, score) in rank(&postings, 6) { println!("doc {doc} tf={tf} score={score:.4}"); }}Run this in the Rust Playground
doc 5 tf=5 score=0.9116doc 1 tf=4 score=0.7293doc 0 tf=1 score=0.1823doc 2 tf=1 score=0.1823doc 3 tf=1 score=0.1823Sorting floats needs a decision. f64 is not Ord, because of NaN; total_cmp gives every float a place in a total order, and sort_by is stable, so documents with equal scores keep the order they arrived in. Postings arrive in ascending document order, so ties come out in document order, and the ranking is a function of the index alone — no hash seed, no run-to-run drift.
The failure
Section titled “The failure”Those five postings are the demo corpus’s real “borrow” postings, and the ranking they produce is wrong in an instructive way. From the full run below:
postings for "borrow" — term frequency, then document length: docs/ownership.md tf=1 len=15 docs/borrow-checker.md tf=4 len=12 docs/lifetimes.md tf=1 len=13 docs/iterators.md tf=1 len=13 docs/style-guide.md tf=5 len=57
query "borrow", ranked by tf * idf: 0.9116 docs/style-guide.md tf=5 len=57 0.7293 docs/borrow-checker.md tf=4 len=12 0.1823 docs/ownership.md tf=1 len=15 0.1823 docs/lifetimes.md tf=1 len=13 0.1823 docs/iterators.md tf=1 len=13The style guide wins. It is 57 terms long and mentions “borrow” five times in passing, in a paragraph of advice about something else. The borrow checker page is 12 terms long and mentions it four times, because both of its sentences are about borrowing. TF-IDF’s discount is across documents — it asks how many documents contain the term, and never how long the document is. Term frequency is a count, and a long document has more room for counts. That is the document length bias: not a bug in the formula, a property of it.
The second query shows the same scorer behaving:
query "owner", ranked by tf * idf: 2.1972 docs/ownership.md tf=2 len=15 1.0986 docs/borrow-checker.md tf=1 len=12“owner” is in two documents; ownership.md mentions it twice and wins. Here term frequency does honest work, because the more frequent document is also the more relevant one. The scorer has no opinion about length. Documents do.
Step 6 replaces the scorer, and the test that pins this ranking changes with it.
The file grew to version 2
Section titled “The file grew to version 2”The format from step 4 gains two fields:
- per document — a u32 term count, straight after the path.
- per posting — a u32 term frequency, straight after the document id.
Everything else is where it was. The version constant moves to 2, and the demo’s last line is the version field earning its keep — the same file with the version patched to 1:
a version 1 file: unsupported index version 1A version 1 file does not hold the numbers the ranker needs, and guessing them is not an option.
One more refusal joins the loader’s. Step 4’s loader accepted a hand-edited file whose postings list ran backwards, and predicted it would confuse the ranker that step 5 was about to build. The ranker itself would have survived it — the scores do not change — but ties would come out in whatever order the file happened to hold, and the ascending, duplicate-free invariant that add_document builds on, and that step 7’s positions will need, would be gone. So the loader checks it now:
the postings list for "x" is not in ascending document orderThe whole file
Section titled “The whole file”One file: Posting, Document, the run-length counter, the scorer, the version 2 format with its new refusal, and a sixth corpus document. The block below is the file at tag search-ch05, byte for byte.
use std::collections::HashMap;use std::error::Error;use std::fmt;use std::fs;use std::io;use std::path::Path;
/// One entry in a term's postings list: the document, and how many/// times the term appears in it.#[derive(Debug, PartialEq)]struct Posting { /// The document this posting refers to. doc: u32, /// How many times the term occurs in that document. At least one: /// a posting exists because the term is there. tf: u32,}
/// One document the index has seen: the path it was indexed under,/// and how many terms the tokeniser took out of it.#[derive(Debug)]struct Document { path: String, /// The document's length in terms, stop words excluded. length: u32,}
/// An inverted index: for each term, the documents that contain it.#[derive(Debug)]struct Index { /// term -> its postings. Each list is ascending in document id, /// with one entry per document that contains the term. postings: HashMap<String, Vec<Posting>>, /// document id -> the document itself. documents: Vec<Document>,}
impl Index { fn new() -> Self { Index { postings: HashMap::new(), documents: Vec::new(), } }
/// Index one document. `path` is its id; `text` is its contents. /// Returns the id the document was given. fn add_document(&mut self, path: &str, text: &str) -> u32 { // The terms this document contributes, sorted so that equal // terms sit next to each other and can be counted in runs. let mut terms: Vec<String> = tokenize(text).collect(); terms.sort_unstable();
let id = self.documents.len() as u32; self.documents.push(Document { path: path.to_string(), length: terms.len() as u32, });
// Each distinct term becomes one posting, carrying the size of // its run as the term frequency. for (term, tf) in count_terms(&terms) { self.postings .entry(term.to_string()) .or_default() .push(Posting { doc: id, tf }); }
id }
/// The postings for `term`. Empty when the index has never seen /// the term. /// /// The term has to be normalised the way the tokeniser normalises /// text: `search("borrowing")` finds nothing, because the dictionary /// holds "borrow". Normalising the query is the caller's job. fn search(&self, term: &str) -> &[Posting] { self.postings.get(term).map(Vec::as_slice).unwrap_or(&[]) }
/// The path a document was indexed under. fn path(&self, id: u32) -> &str { &self.documents[id as usize].path }
/// How many terms a document holds, stop words excluded. They are /// not in the index, so they are not in the length either. fn length(&self, id: u32) -> u32 { self.documents[id as usize].length }
fn documents(&self) -> usize { self.documents.len() }
fn terms(&self) -> usize { self.postings.len() }
/// Every term with its postings, in sorted order — the order `save` /// writes them in. fn postings(&self) -> Vec<(&str, &[Posting])> { let mut entries: Vec<(&str, &[Posting])> = self .postings .iter() .map(|(term, postings)| (term.as_str(), postings.as_slice())) .collect(); entries.sort_unstable_by(|a, b| a.0.cmp(b.0)); entries }
/// Write the index to `path` as one binary file: the magic and the /// version, the documents with their lengths, then the dictionary /// with its postings lists, terms in sorted order. /// /// The file is built in memory and written in one call. At this size /// that is cheaper than a buffered writer, and it makes the whole /// file one value that can be compared, hashed or diffed. fn save(&self, path: impl AsRef<Path>) -> io::Result<()> { let mut out: Vec<u8> = Vec::new(); out.extend_from_slice(MAGIC); out.extend_from_slice(&VERSION.to_le_bytes()); out.extend_from_slice(&(self.documents.len() as u32).to_le_bytes()); for document in &self.documents { put_str(&mut out, &document.path); out.extend_from_slice(&document.length.to_le_bytes()); } out.extend_from_slice(&(self.terms() as u32).to_le_bytes()); for (term, postings) in self.postings() { put_str(&mut out, term); out.extend_from_slice(&(postings.len() as u32).to_le_bytes()); for posting in postings { out.extend_from_slice(&posting.doc.to_le_bytes()); out.extend_from_slice(&posting.tf.to_le_bytes()); } } fs::write(path, out) }
/// Read an index back from `path`. Reading the file and interpreting /// it are two steps that fail differently: the first with an io /// error, the second with a `LoadError`. fn load(path: impl AsRef<Path>) -> Result<Index, LoadError> { let bytes = fs::read(path).map_err(LoadError::Io)?; Index::load_bytes(&bytes) }
/// Parse the bytes of an index file. Every field is length-prefixed, /// so the reader never has to guess where one field ends and the /// next begins — and a file that ends early is a `LoadError`, not a /// panic. fn load_bytes(bytes: &[u8]) -> Result<Index, LoadError> { let mut reader = Reader::new(bytes); if reader.take(MAGIC.len())? != MAGIC { return Err(LoadError::BadMagic); } let version = reader.u32()?; if version != VERSION { return Err(LoadError::BadVersion(version)); }
let mut index = Index::new(); for _ in 0..reader.u32()? { let path = reader.string()?; let length = reader.u32()?; index.documents.push(Document { path, length }); } for _ in 0..reader.u32()? { let term = reader.string()?; let mut postings = Vec::new(); let mut previous: Option<u32> = None; for _ in 0..reader.u32()? { let doc = reader.u32()?; let tf = reader.u32()?; // Step 2 promised ascending, duplicate-free lists, and // the ranker assumes it: a hand-edited file that breaks // the order is refused here rather than trusted. if previous.is_some_and(|last| doc <= last) { return Err(LoadError::BadPostings(term)); } previous = Some(doc); postings.push(Posting { doc, tf }); } index.postings.insert(term, postings); } if reader.pos != reader.data.len() { return Err(LoadError::TrailingBytes); } Ok(index) }}
/// Count a sorted term list in runs: each distinct term once, with the/// number of times it occurred. ["dog", "fox", "fox", "fox"] counts/// "dog" once and "fox" three times.fn count_terms(sorted: &[String]) -> Vec<(&str, u32)> { let mut counts = Vec::new(); let mut start = 0; while start < sorted.len() { let mut end = start + 1; while end < sorted.len() && sorted[end] == sorted[start] { end += 1; } counts.push((sorted[start].as_str(), (end - start) as u32)); start = end; } counts}
/// How much information a term carries: the natural log of the document/// count over the number of documents containing the term.////// A term in every document scores zero — it cannot tell two documents/// apart. A term in one document scores the most. The zero for an empty/// postings list is for callers that pass one: a term in no document is/// not in the dictionary at all.fn idf(df: usize, n: usize) -> f64 { if df == 0 { return 0.0; } (n as f64 / df as f64).ln()}
/// Rank a term's postings by TF-IDF, best first. Each result is/// (document, term frequency, score).////// The score is the term's frequency in the document times the inverse/// of its document frequency — raw counts, with no length/// normalisation, which is what makes step 6 necessary. Equal scores/// keep their input order, and postings arrive in ascending document/// order, so ties come out in document order.fn rank(postings: &[Posting], n: usize) -> Vec<(u32, u32, f64)> { let idf = idf(postings.len(), n); let mut ranked: Vec<(u32, u32, f64)> = postings .iter() .map(|p| (p.doc, p.tf, p.tf as f64 * idf)) .collect(); // f64 is not Ord, because of NaN. total_cmp gives every float a // place in a total order, and sort_by is stable, so equal scores // keep the order they arrived in. ranked.sort_by(|a, b| b.2.total_cmp(&a.2)); ranked}
/// Append a length-prefixed UTF-8 string: a u32 byte count, then the/// bytes. A binary file has no separator to scan for, so the length is/// the separator.fn put_str(out: &mut Vec<u8>, text: &str) { out.extend_from_slice(&(text.len() as u32).to_le_bytes()); out.extend_from_slice(text.as_bytes());}
/// Everything that can be wrong with an index file. The disk it sits on/// is a separate concern, carried along as `Io`.#[derive(Debug)]enum LoadError { /// The file does not start with the magic this engine writes. BadMagic, /// The magic is right, but the version is not one this build reads. BadVersion(u32), /// The file ends where another field was expected. Truncated, /// A length-prefixed field holds bytes that are not UTF-8. BadUtf8, /// Bytes were left over after the last field the format describes. TrailingBytes, /// A postings list whose document ids are not ascending. BadPostings(String), /// The file could not be read at all. Io(io::Error),}
impl fmt::Display for LoadError { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { LoadError::BadMagic => write!(f, "not a haystack index: the magic bytes are wrong"), LoadError::BadVersion(v) => write!(f, "unsupported index version {v}"), LoadError::Truncated => write!(f, "the file ends where another field was expected"), LoadError::BadUtf8 => write!(f, "a length-prefixed field is not valid UTF-8"), LoadError::TrailingBytes => write!(f, "the file has bytes after the last field"), LoadError::BadPostings(term) => { write!(f, "the postings list for {term:?} is not in ascending document order") } LoadError::Io(e) => write!(f, "{e}"), } }}
impl Error for LoadError { fn source(&self) -> Option<&(dyn Error + 'static)> { match self { LoadError::Io(e) => Some(e), _ => None, } }}
/// A cursor over an index file's bytes. Every read checks the end first,/// so a truncated file is a `LoadError` instead of a panic.struct Reader<'a> { data: &'a [u8], pos: usize,}
impl<'a> Reader<'a> { fn new(data: &'a [u8]) -> Self { Reader { data, pos: 0 } }
/// The next `len` bytes, or `Truncated` when the file ends first. fn take(&mut self, len: usize) -> Result<&'a [u8], LoadError> { let end = self.pos.checked_add(len).ok_or(LoadError::Truncated)?; let bytes = self.data.get(self.pos..end).ok_or(LoadError::Truncated)?; self.pos = end; Ok(bytes) }
/// The next four bytes, as a little-endian u32. fn u32(&mut self) -> Result<u32, LoadError> { let bytes: [u8; 4] = self.take(4)?.try_into().unwrap(); Ok(u32::from_le_bytes(bytes)) }
/// The next length-prefixed UTF-8 string. fn string(&mut self) -> Result<String, LoadError> { let len = self.u32()? as usize; let bytes = self.take(len)?; std::str::from_utf8(bytes) .map(str::to_owned) .map_err(|_| LoadError::BadUtf8) }}
/// The first eight bytes of every index file: eight ASCII bytes that no/// file this engine reads by accident starts with.const MAGIC: &[u8] = b"haystack";
/// The format version. A file announcing any other number is refused./// Version 2 adds a length to every document and a term frequency to/// every posting; a version 1 file has neither, and this build will/// not guess them.const VERSION: u32 = 2;
/// Where the demo writes its index. The file is output, not source: it/// is gitignored and rebuilt by every run.const INDEX_PATH: &str = "haystack.idx";
/// The demo corpus: one file is one document, and the path is the id.////// The last entry is deliberately long and mentions "borrow" five times/// in passing. It is the document length bias in one file: more terms/// to say less.fn corpus() -> [(&'static str, &'static str); 6] { [ ( "docs/ownership.md", "Ownership and borrowing are the two ideas Rust is built on. Every value has one owner, and the owner going out of scope drops it.", ), ( "docs/borrow-checker.md", "The borrow checker enforces the borrowing rules at compile time. A borrow must not outlive the owner of the borrowed value.", ), ( "docs/lifetimes.md", "A lifetime is the region of code for which a reference is valid. The borrow checker uses lifetimes to keep every reference in scope.", ), ( "docs/iterators.md", "Iterators are lazy: each call to next advances the iterator by one. An adapter such as map borrows the iterator it wraps.", ), ( "docs/error-handling.md", "Recoverable errors are values of type Result. The question mark operator returns an error to the caller early.", ), ( "docs/style-guide.md", "House style for these pages: prefer short sentences, and name the thing you mean. When a function borrows a value, say what it borrows and for how long. A struct that borrows from its input should say so in its name. Tests borrow fixtures from the module above them, and an example that borrows code from another chapter says where it came from. Prefer the active voice, cut words like simply and just, and keep paragraphs under six lines. One idea per paragraph, a heading every screenful, and the exception to a rule written next to the rule.", ), ]}
fn main() -> Result<(), Box<dyn Error>> { let mut index = Index::new(); for (path, text) in &corpus() { index.add_document(path, text); } println!( "{} documents, {} distinct terms", index.documents(), index.terms() );
index.save(INDEX_PATH)?; let written = fs::read(INDEX_PATH)?; println!("\nsaved to {INDEX_PATH}: {} bytes", written.len());
// The dictionary is written in sorted order, so the same index // always produces the same bytes. index.save(INDEX_PATH)?; let rewritten = fs::read(INDEX_PATH)?; println!( "saved again: {} bytes, byte-identical: {}", rewritten.len(), rewritten == written );
let loaded = Index::load(INDEX_PATH)?; println!( "\nloaded back: {} documents, {} terms", loaded.documents(), loaded.terms() );
// What a posting carries now: the document, how often the term // appears in it, and how long the document is. println!("\npostings for \"borrow\" — term frequency, then document length:"); for posting in loaded.search("borrow") { println!( " {:<26} tf={} len={}", loaded.path(posting.doc), posting.tf, loaded.length(posting.doc) ); }
println!("\nquery \"borrow\", ranked by tf * idf:"); for (doc, tf, score) in rank(loaded.search("borrow"), loaded.documents()) { println!( " {score:>7.4} {:<26} tf={tf} len={}", loaded.path(doc), loaded.length(doc) ); }
println!("\nquery \"owner\", ranked by tf * idf:"); for (doc, tf, score) in rank(loaded.search("owner"), loaded.documents()) { println!( " {score:>7.4} {:<26} tf={tf} len={}", loaded.path(doc), loaded.length(doc) ); }
// The version field, doing its job: the same file with the version // patched to 1 is a file this build does not read. let mut stale = written.clone(); stale[8..12].copy_from_slice(&1u32.to_le_bytes()); if let Err(e) = Index::load_bytes(&stale) { println!("\na version 1 file: {e}"); }
Ok(())}
/// The stop words: terms so common that indexing them costs memory and/// buys nothing. This is the classic short English list; a production/// engine keeps a longer one, and one per language.const STOP_WORDS: &[&str] = &[ "a", "am", "an", "and", "are", "as", "at", "be", "been", "being", "but", "by", "can", "could", "did", "do", "does", "for", "from", "had", "has", "have", "he", "her", "his", "how", "i", "if", "in", "into", "is", "it", "its", "may", "might", "must", "no", "nor", "not", "of", "on", "or", "our", "shall", "she", "should", "so", "such", "than", "that", "the", "their", "them", "then", "there", "these", "they", "this", "those", "through", "to", "us", "was", "we", "were", "what", "when", "where", "which", "while", "who", "whom", "will", "with", "would", "you", "your",];
fn is_stop_word(word: &str) -> bool { STOP_WORDS.contains(&word)}
/// Shortest stem worth keeping. Without the guard "ring" stems to "r".const MIN_STEM: usize = 3;
/// Strip `suffix`, but only when a stem of at least `MIN_STEM`/// characters is left.fn strip_suffix(word: &str, suffix: &str) -> Option<String> { let base = word.strip_suffix(suffix)?; (base.chars().count() >= MIN_STEM).then_some(base.to_string())}
/// "runn" -> "run", "dropp" -> "drop": a doubled final consonant is/// usually the suffix's doing. l, s and z double naturally, so/// "class", "fall" and "buzz" keep both letters.fn undouble(stem: String) -> String { let mut chars: Vec<char> = stem.chars().collect(); if chars.len() >= 2 { let (last, before) = (chars[chars.len() - 1], chars[chars.len() - 2]); if last == before && !matches!(last, 'l' | 's' | 'z') { chars.pop(); } } chars.into_iter().collect()}
/// "boxes" -> "box", "watches" -> "watch", "classes" -> "class":/// after a sibilant that is not a bare "s", the plural's "es" detaches./// Everywhere else the "s" alone is the marker, so "causes" -> "cause"/// and "buses" -> "buse", which is a known miss.fn strip_sibilant_es(word: &str) -> Option<String> { let base = word.strip_suffix("es")?; let sibilant = base.ends_with('x') || base.ends_with('z') || base.ends_with("ss") || base.ends_with("ch") || base.ends_with("sh"); if !sibilant || base.chars().count() < MIN_STEM { return None; } Some(base.to_string())}
/// A small rule-based stemmer: strip one inflectional suffix, then fix/// the doubling it left behind. "borrow", "borrows", "borrowed" and/// "borrowing" all come out as "borrow".////// It produces terms, not lemmas: "built" ends in no suffix it knows/// and stays whole, and "ownership" does not stem at all. Porter's/// algorithm is the full version of this idea; this is its small/// cousin.fn stem(word: &str) -> String { if let Some(base) = strip_suffix(word, "ing") { return undouble(base); } if let Some(base) = strip_suffix(word, "ed") { return undouble(base); } if let Some(base) = strip_sibilant_es(word) { return base; } if let Some(base) = strip_suffix(word, "s") { return base; } word.to_string()}
/// Split text into terms: lowercase, split on anything that is not a/// letter or a digit, drop stop words, and stem what is left.////// The terms are owned. Step 2's version handed back slices of the text/// it was given; lowercasing a word builds a new String, and so does/// stemming one, so the output cannot borrow `text` any more.fn tokenize(text: &str) -> impl Iterator<Item = String> { text.split(|c: char| !c.is_alphanumeric()) .filter(|word| !word.is_empty()) .map(str::to_lowercase) .filter(|word| !is_stop_word(word)) .map(|word| stem(&word))}
#[cfg(test)]mod tests { use super::*;
fn sample() -> Index { let mut index = Index::new(); index.add_document("a.md", "The Quick Brown Fox"); index.add_document("b.md", "the lazy dog, the quick cat"); index }
/// The document ids in a term's postings, for the tests that only /// care which documents matched. fn ids(index: &Index, term: &str) -> Vec<u32> { index.search(term).iter().map(|p| p.doc).collect() }
#[test] fn add_document_returns_the_id_it_gave() { let mut index = Index::new(); assert_eq!(index.add_document("a.md", "fox"), 0); assert_eq!(index.add_document("b.md", "fox"), 1); }
#[test] fn a_term_in_two_documents_lists_both() { let index = sample(); assert_eq!(ids(&index, "quick"), [0, 1]); }
#[test] fn a_term_repeated_in_one_document_lists_it_once() { let mut index = Index::new(); index.add_document("a.md", "fox fox fox"); assert_eq!(ids(&index, "fox"), [0]); }
#[test] fn a_repeated_term_records_how_often_it_repeated() { let mut index = Index::new(); index.add_document("a.md", "fox fox fox"); assert_eq!(index.search("fox"), &[Posting { doc: 0, tf: 3 }]); }
#[test] fn distinct_terms_in_one_document_get_one_posting_each() { let mut index = Index::new(); index.add_document("a.md", "fox dog fox"); assert_eq!(index.search("fox"), &[Posting { doc: 0, tf: 2 }]); assert_eq!(index.search("dog"), &[Posting { doc: 0, tf: 1 }]); }
#[test] fn document_length_counts_the_terms_the_tokeniser_kept() { let mut index = Index::new(); index.add_document("a.md", "The Quick Brown Fox"); assert_eq!(index.length(0), 3); // "the" is a stop word }
#[test] fn ids_are_in_insertion_order() { let index = sample(); assert_eq!(index.path(0), "a.md"); assert_eq!(index.path(1), "b.md"); assert_eq!(ids(&index, "dog"), [1]); }
#[test] fn a_missing_term_is_empty_not_an_error() { let index = sample(); assert!(index.search("wolf").is_empty()); }
#[test] fn casing_and_punctuation_are_folded_away() { let index = sample(); assert_eq!(ids(&index, "fox"), [0]); assert_eq!(ids(&index, "dog"), [1]); }
#[test] fn stop_words_are_not_indexed() { let index = sample(); assert!(index.search("the").is_empty()); assert_eq!(ids(&index, "quick"), [0, 1]); }
#[test] fn inflections_share_one_term() { let mut index = Index::new(); index.add_document("a.md", "borrowing"); index.add_document("b.md", "borrowed"); index.add_document("c.md", "borrows"); assert_eq!(ids(&index, "borrow"), [0, 1, 2]); }
#[test] fn a_doubled_consonant_from_the_suffix_is_collapsed() { let mut index = Index::new(); index.add_document("a.md", "running dropped"); assert_eq!(ids(&index, "run"), [0]); assert_eq!(ids(&index, "drop"), [0]); }
#[test] fn doubling_that_is_not_the_suffixs_fault_survives() { let mut index = Index::new(); index.add_document("a.md", "classes"); index.add_document("b.md", "boxes"); index.add_document("c.md", "buzzes"); assert_eq!(ids(&index, "class"), [0]); assert_eq!(ids(&index, "box"), [1]); assert_eq!(ids(&index, "buzz"), [2]); }
#[test] fn a_stem_needs_three_characters() { let mut index = Index::new(); index.add_document("a.md", "ring"); assert_eq!(ids(&index, "ring"), [0]); assert!(index.search("r").is_empty()); }
#[test] fn case_folding_is_unicode_aware() { let mut index = Index::new(); index.add_document("a.md", "Ärger"); assert_eq!(ids(&index, "ärger"), [0]); }
#[test] fn idf_is_zero_for_a_term_in_every_document() { assert_eq!(idf(2, 2), 0.0); }
#[test] fn idf_falls_as_the_document_frequency_rises() { assert!(idf(1, 6) > idf(2, 6)); assert!(idf(2, 6) > idf(5, 6)); assert_eq!(idf(1, 6), 6.0f64.ln()); }
#[test] fn rank_puts_the_highest_score_first() { let postings = [Posting { doc: 0, tf: 1 }, Posting { doc: 1, tf: 5 }]; let ranked = rank(&postings, 6); assert_eq!(ranked[0].0, 1); assert!(ranked[0].2 > ranked[1].2); }
#[test] fn rank_keeps_the_input_order_of_equal_scores() { let postings = [Posting { doc: 3, tf: 1 }, Posting { doc: 1, tf: 1 }]; let ranked = rank(&postings, 6); assert_eq!(ranked.iter().map(|r| r.0).collect::<Vec<_>>(), [3, 1]); }
/// The length bias, pinned as the behaviour the demo shows: on the /// demo corpus "borrow" ranks the long style guide above the page /// that is actually about borrowing, because it mentions the term /// more often. Step 6 replaces the scorer, and this test with it. #[test] fn raw_term_frequency_lets_the_longer_document_win() { let mut index = Index::new(); for (path, text) in &corpus() { index.add_document(path, text); } let ranked = rank(index.search("borrow"), index.documents()); assert_eq!(index.path(ranked[0].0), "docs/style-guide.md"); assert_eq!(index.path(ranked[1].0), "docs/borrow-checker.md"); }
/// A scratch path in the OS temp directory. Each test picks its own /// name, so the tests can run in parallel. fn scratch(name: &str) -> std::path::PathBuf { std::env::temp_dir().join(format!("haystack-{name}.idx")) }
#[test] fn a_saved_index_loads_back_identical() { let index = sample(); let path = scratch("roundtrip"); index.save(&path).unwrap(); let loaded = Index::load(&path).unwrap(); assert_eq!(loaded.documents(), index.documents()); assert_eq!(loaded.terms(), index.terms()); for (term, postings) in index.postings() { assert_eq!(loaded.search(term), postings, "postings for {term:?}"); } for id in 0..index.documents() as u32 { assert_eq!(loaded.path(id), index.path(id)); assert_eq!(loaded.length(id), index.length(id)); } }
#[test] fn a_terms_frequency_survives_a_reload() { let mut index = Index::new(); index.add_document("a.md", "fox fox fox"); index.add_document("b.md", "fox"); let path = scratch("frequencies"); index.save(&path).unwrap(); let loaded = Index::load(&path).unwrap(); assert_eq!( loaded.search("fox"), &[Posting { doc: 0, tf: 3 }, Posting { doc: 1, tf: 1 }] ); assert_eq!(loaded.length(0), 3); assert_eq!(loaded.length(1), 1); }
#[test] fn saving_twice_writes_the_same_bytes() { let index = sample(); let path = scratch("determinism"); index.save(&path).unwrap(); let first = fs::read(&path).unwrap(); index.save(&path).unwrap(); assert_eq!(fs::read(&path).unwrap(), first); }
#[test] fn the_dictionary_is_written_in_sorted_order() { let index = sample(); let path = scratch("sorted"); index.save(&path).unwrap(); let bytes = fs::read(&path).unwrap();
// Walk the saved file the way the loader does, collecting the // terms as they appear on disk. let mut reader = Reader::new(&bytes); reader.take(MAGIC.len()).unwrap(); reader.u32().unwrap(); for _ in 0..reader.u32().unwrap() { reader.string().unwrap(); reader.u32().unwrap(); // the document's length } let mut terms = Vec::new(); for _ in 0..reader.u32().unwrap() { let term = reader.string().unwrap(); let ids = reader.u32().unwrap(); reader.take(ids as usize * 8).unwrap(); // doc and tf, four bytes each terms.push(term); } assert!( terms.windows(2).all(|pair| pair[0] < pair[1]), "not sorted: {terms:?}" ); }
#[test] fn a_truncated_file_is_refused() { let index = sample(); let path = scratch("truncated"); index.save(&path).unwrap(); let bytes = fs::read(&path).unwrap(); let error = Index::load_bytes(&bytes[..20]).unwrap_err(); assert_eq!( error.to_string(), "the file ends where another field was expected" ); }
#[test] fn a_wrong_magic_is_refused() { let mut bytes = Vec::new(); bytes.extend_from_slice(b"haystacs"); // one letter off bytes.extend_from_slice(&VERSION.to_le_bytes()); let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!( error.to_string(), "not a haystack index: the magic bytes are wrong" ); }
#[test] fn a_newer_version_is_refused() { let mut bytes = Vec::new(); bytes.extend_from_slice(MAGIC); bytes.extend_from_slice(&3u32.to_le_bytes()); let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!(error.to_string(), "unsupported index version 3"); }
#[test] fn a_version_1_file_is_refused() { let mut bytes = Vec::new(); bytes.extend_from_slice(MAGIC); bytes.extend_from_slice(&1u32.to_le_bytes()); let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!(error.to_string(), "unsupported index version 1"); }
#[test] fn a_postings_list_that_is_not_ascending_is_refused() { let mut bytes = Vec::new(); bytes.extend_from_slice(MAGIC); bytes.extend_from_slice(&VERSION.to_le_bytes()); bytes.extend_from_slice(&0u32.to_le_bytes()); // no documents bytes.extend_from_slice(&1u32.to_le_bytes()); // one term bytes.extend_from_slice(&1u32.to_le_bytes()); // one byte long bytes.push(b'x'); bytes.extend_from_slice(&2u32.to_le_bytes()); // two postings bytes.extend_from_slice(&2u32.to_le_bytes()); // document 2 bytes.extend_from_slice(&1u32.to_le_bytes()); // term frequency 1 bytes.extend_from_slice(&1u32.to_le_bytes()); // document 1 — out of order bytes.extend_from_slice(&1u32.to_le_bytes()); // term frequency 1 let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!( error.to_string(), "the postings list for \"x\" is not in ascending document order" ); }
#[test] fn trailing_bytes_are_refused() { let index = sample(); let path = scratch("trailing"); index.save(&path).unwrap(); let mut bytes = fs::read(&path).unwrap(); bytes.push(0); let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!(error.to_string(), "the file has bytes after the last field"); }
#[test] fn a_term_that_is_not_utf8_is_refused() { let mut bytes = Vec::new(); bytes.extend_from_slice(MAGIC); bytes.extend_from_slice(&VERSION.to_le_bytes()); bytes.extend_from_slice(&0u32.to_le_bytes()); // no documents bytes.extend_from_slice(&1u32.to_le_bytes()); // one term bytes.extend_from_slice(&1u32.to_le_bytes()); // one byte long bytes.push(0xFF); // and not UTF-8 let error = Index::load_bytes(&bytes).unwrap_err(); assert_eq!( error.to_string(), "a length-prefixed field is not valid UTF-8" ); }
#[test] fn a_missing_file_is_an_io_error() { let path = scratch("never-written"); assert!(matches!(Index::load(&path), Err(LoadError::Io(_)))); }
#[test] fn an_empty_index_round_trips() { let index = Index::new(); let path = scratch("empty"); index.save(&path).unwrap(); let loaded = Index::load(&path).unwrap(); assert_eq!(loaded.documents(), 0); assert_eq!(loaded.terms(), 0); }}Run this in the Rust Playground
See it run
Section titled “See it run”From the haystack directory:
cargo run6 documents, 84 distinct terms
saved to haystack.idx: 2131 bytessaved again: 2131 bytes, byte-identical: true
loaded back: 6 documents, 84 terms
postings for "borrow" — term frequency, then document length: docs/ownership.md tf=1 len=15 docs/borrow-checker.md tf=4 len=12 docs/lifetimes.md tf=1 len=13 docs/iterators.md tf=1 len=13 docs/style-guide.md tf=5 len=57
query "borrow", ranked by tf * idf: 0.9116 docs/style-guide.md tf=5 len=57 0.7293 docs/borrow-checker.md tf=4 len=12 0.1823 docs/ownership.md tf=1 len=15 0.1823 docs/lifetimes.md tf=1 len=13 0.1823 docs/iterators.md tf=1 len=13
query "owner", ranked by tf * idf: 2.1972 docs/ownership.md tf=2 len=15 1.0986 docs/borrow-checker.md tf=1 len=12
a version 1 file: unsupported index version 1The opening lines are the round trip from step 4, unchanged in shape: the same index, saved twice, byte-identical, loaded back. What is new is everything after it — postings that carry frequencies, two ranked queries, and one refusal. The sixth document is the corpus gaining a deliberately long page; the ranking above is what it costs.
The tests:
cargo testrunning 33 teststest tests::a_doubled_consonant_from_the_suffix_is_collapsed ... oktest tests::a_missing_file_is_an_io_error ... oktest tests::a_missing_term_is_empty_not_an_error ... oktest tests::a_newer_version_is_refused ... oktest tests::a_postings_list_that_is_not_ascending_is_refused ... oktest tests::a_repeated_term_records_how_often_it_repeated ... oktest tests::a_stem_needs_three_characters ... oktest tests::a_term_repeated_in_one_document_lists_it_once ... oktest tests::a_term_that_is_not_utf8_is_refused ... oktest tests::a_term_in_two_documents_lists_both ... oktest tests::a_version_1_file_is_refused ... oktest tests::a_wrong_magic_is_refused ... oktest tests::a_saved_index_loads_back_identical ... oktest tests::add_document_returns_the_id_it_gave ... oktest tests::case_folding_is_unicode_aware ... oktest tests::a_truncated_file_is_refused ... oktest tests::a_terms_frequency_survives_a_reload ... oktest tests::casing_and_punctuation_are_folded_away ... oktest tests::distinct_terms_in_one_document_get_one_posting_each ... oktest tests::an_empty_index_round_trips ... oktest tests::document_length_counts_the_terms_the_tokeniser_kept ... oktest tests::doubling_that_is_not_the_suffixs_fault_survives ... oktest tests::idf_falls_as_the_document_frequency_rises ... oktest tests::idf_is_zero_for_a_term_in_every_document ... oktest tests::ids_are_in_insertion_order ... oktest tests::inflections_share_one_term ... oktest tests::rank_keeps_the_input_order_of_equal_scores ... oktest tests::rank_puts_the_highest_score_first ... oktest tests::stop_words_are_not_indexed ... oktest tests::saving_twice_writes_the_same_bytes ... oktest tests::raw_term_frequency_lets_the_longer_document_win ... oktest tests::trailing_bytes_are_refused ... oktest tests::the_dictionary_is_written_in_sorted_order ... ok
test result: ok. 33 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00sThirty-three tests: the twenty-two from the earlier steps, and eleven around the new numbers — term frequencies, document lengths, the scorer’s ordering, the version 1 refusal, and the ascending check. The order is shuffled on every run, so nothing should be read into it.
Where this lands
Section titled “Where this lands”This step’s state is tagged search-ch05 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/search-enginegit checkout search-ch05The tag contains Cargo.toml, the README and src/main.rs in full. If your
build misbehaves, diff your files against the tag’s — the drifting line is
usually findable that way. The track overview
keeps the step list current.
Step 6, Ranking with BM25, replaces the scorer: two constants, k1 and b, at the values Lucene ships, turn the raw count into a saturating one and divide the length out.