Tokenising and normalising text
Step 3 of 12, and the engine starts answering the questions readers actually
type. Step 2 left the index holding whatever split_whitespace produced:
“Ownership” and “ownership” were two different terms, “valid.” was a word of
its own, and “the” sat in the dictionary next to “borrow”. This step replaces
the body of tokenize — lowercase, split on punctuation, drop stop words,
stem what is left — and the index itself does not change.
The starting state is tag search-ch02, the end of step 2:
one HashMap<String, Vec<u32>> and a tokeniser that splits on whitespace. The
end state of this step is tagged search-ch03; the whole file is at the end of
this page, and the checkout commands follow it.
What step 2 left broken
Section titled “What step 2 left broken”Step 2’s demo ended with two queries that found nothing:
queries that miss: "ownership" -> no documents "valid" -> no documentsBoth words are in the corpus. “ownership” missed because its only occurrence starts a sentence, so the dictionary holds “Ownership” with a capital O. “valid” missed because the sentence ends “is valid.”, and the full stop was indexed as part of the term. A third failure is quieter: “the” was indexed like any other word, so it occupied a postings list in nearly every document and matched nearly every query. Casing, punctuation and stop words — this step fixes all three.
Case folding, and why the terms are now owned
Section titled “Case folding, and why the terms are now owned”The natural first attempt keeps step 2’s signature and lowercases on the way through:
fn tokenize(text: &str) -> impl Iterator<Item = &str> { let lowered = text.to_lowercase(); lowered.split_whitespace()}
fn main() { for term in tokenize("The borrow checker enforces the borrowing rules") { println!("{term}"); }}error[E0515]: cannot return value referencing local variable `lowered` --> src/main.rs:3:5 |3 | lowered.split_whitespace() | -------^^^^^^^^^^^^^^^^^^^ | | | returns a value referencing data owned by the current function | `lowered` is borrowed here | = help: use `.collect()` to allocate the iterator
For more information about this error, try `rustc --explain E0515`.to_lowercase returns a new String, so the iterator borrows a local that
dies when the function returns. Step 2’s impl Iterator<Item = &str> could
only hand back slices of its input; folding case builds new strings, so the
output has to be owned. The signature widens to impl Iterator<Item = String>,
and two lines of add_document move with it: the collection becomes
let mut terms: Vec<String> = tokenize(text).collect();, and the insertion
becomes self.postings.entry(term).or_default().push(id);. The owned String
that step 2’s entry(term.to_string()) had to build on the way in is now what
the tokeniser hands out — the allocation moved inside tokenize.
Step 2 closed by promising that step 3 would replace the body of tokenize
and nothing else in the file. The seam held — text still becomes terms in
exactly one function — but the signature grew, and those two lines followed
it. A seam that cannot survive the change it exists for is not a seam.
Splitting on anything that is not a letter or a digit
Section titled “Splitting on anything that is not a letter or a digit”Splitting on whitespace left punctuation glued to words. The replacement
splits on everything that is not a letter or a digit:
text.split(|c: char| !c.is_alphanumeric()). The predicate takes a char,
so it is Unicode-aware without a Unicode table: “Ärger” is one word and so is
“Straße”. The .filter(|word| !word.is_empty()) that follows is not optional
— two separators in a row, as in “scope – drops”, would otherwise leave an
empty term between them.
Two costs are worth naming. “C++” becomes “c”, because the plus signs are separators and nothing reattaches them. And digits count as term characters, so “v1.2” indexes as “v1” and “2”; for a folder of notes that is usually what you want, because “http2” and “2024” are words people search for.
Case folding itself is str::to_lowercase, which is Unicode lowercase
mapping rather than an ASCII-only to_ascii_lowercase:
fn main() { for word in ["ÜBER", "STRASSE", "Straße", "Ärger"] { println!("{word} -> {}", word.to_lowercase()); }}ÜBER -> überSTRASSE -> strasseStraße -> straßeÄrger -> ärger“STRASSE” lowercases to “strasse” and “Straße” to “straße”, and the two never meet: Unicode’s full case folding maps ß to “ss”, and the standard library ships lowercase mapping only. German compounds are where that bites; an English corpus never notices.
Stop words
Section titled “Stop words”/// 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)}Seventy-seven words: articles, pronouns, prepositions, conjunctions and the auxiliary verbs. They are on the list because they are in every document, so indexing them costs one postings list each and buys a result set the reader has to scan anyway. The classic short list is a starting point, not a specification — a production engine keeps a longer one and one per language, and “out” is the kind of word that could go either way.
Order matters. The filter runs on the word as written, after lowercasing and before stemming. Stem first and the list stops matching the words on it: the stemmer below strips the trailing “s” from “this” and “does”, and both would slip through as “thi” and “doe”.
The stemmer
Section titled “The stemmer”Four rules, tried in order, first match wins. The table below is the real
stem function from the file, run on its own:
/// 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()}
fn main() { let words = [ "borrow", "borrows", "borrowed", "borrowing", "run", "runs", "running", "dropped", "boxes", "watches", "classes", "buzzes", "causes", "houses", "buses", "uses", "built", "ownership", "ring", "this", "does", ]; for word in words { println!("{word:>12} -> {}", stem(word)); }}borrow -> borrow borrows -> borrow borrowed -> borrow borrowing -> borrow run -> run runs -> run running -> run dropped -> drop boxes -> box watches -> watch classes -> class buzzes -> buzz causes -> cause houses -> house buses -> buse uses -> use built -> built ownership -> ownership ring -> ring this -> thi does -> doeReading the rules off the table:
- “ing”, then collapse a doubled final consonant: “borrowing” → “borrow”, “running” → “runn” → “run”.
- “ed”, same fix: “borrowed” → “borrow”, “dropped” → “dropp” → “drop”.
- “es” after a sibilant that is not a bare “s”: “boxes” → “box”, “watches” → “watch”, “classes” → “class”. The plural’s “es” only detaches where the word already ends in a sibilant.
- “s”: “borrows” → “borrow”, “causes” → “cause”.
Every strip needs a stem of at least three characters left, or “ring” would stem to “r” and “uses” to “us”. The doubling fix keeps the three consonants that double naturally — “class”, “fall” and “buzz” keep both letters — because those were never the suffix’s doing.
The misses are as informative as the hits. “built” does not stem at all: it is
an irregular past tense ending in neither -ed nor -ing, so every rule declines
it, and Porter’s algorithm leaves
it alone for the same reason. “ownership” stays whole too — these rules strip
inflections, not derivations, so “owner” and “ownership” remain separate terms
and a query for one does not find the other. “buses” comes out as “buse”,
because after a bare “s” the “s” alone is treated as the marker. And the
y-plurals are the visible gap: “stories” and “story” stay apart here, where
Porter’s IES → I and (*v*) Y → I rules fold both onto “stori”. The
published algorithm is five steps of conditioned rules, several of them
derivational; this one is four unconditional inflectional rules, and the
difference is the point of naming it.
The whole file
Section titled “The whole file”One function replaced, and the file around it: tokenize is new in full —
body and signature — add_document changed in the two lines shown above,
main’s last three sections are new, and the tests grew from six to twelve.
use std::collections::HashMap;
/// An inverted index: for each term, the documents that contain it.struct Index { /// term -> document ids. Every list is ascending and duplicate-free. postings: HashMap<String, Vec<u32>>, /// document id -> the path the document was indexed under. documents: Vec<String>,}
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 { let id = self.documents.len() as u32; self.documents.push(path.to_string());
// The terms this document contributes, each at most once. let mut terms: Vec<String> = tokenize(text).collect(); terms.sort_unstable(); terms.dedup();
for term in terms { self.postings.entry(term).or_default().push(id); }
id }
/// The ids of the documents containing `term`, in insertion order. /// 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) -> &[u32] { 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] }
fn documents(&self) -> usize { self.documents.len() }
fn terms(&self) -> usize { self.postings.len() }}
/// 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))}
fn main() { let documents = [ ( "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.", ), ];
let mut index = Index::new(); for (path, text) in &documents { index.add_document(path, text); } println!( "{} documents, {} distinct terms", index.documents(), index.terms() );
println!("\npostings for \"borrow\": {:?}", index.search("borrow"));
println!("\nquery \"borrow\":"); for id in index.search("borrow") { println!(" {}", index.path(*id)); }
println!("\nthe same documents from a scan:"); for (path, text) in &documents { if tokenize(text).any(|term| term == "borrow") { println!(" {}", path); } }
println!("\nthe queries that used to miss:"); for query in ["ownership", "valid"] { println!(" query {:?}:", query); for id in index.search(query) { println!(" {}", index.path(*id)); } }
println!("\ninflections fold onto one term:"); for query in ["borrow", "borrowing"] { let terms: Vec<String> = tokenize(query).collect(); println!(" query {query:?} -> terms {terms:?}"); for term in &terms { println!(" {term:?}: {:?}", index.search(term)); } }
println!("\nstop words are not terms:"); for query in ["the", "is"] { println!( " query {:?}: {} documents", query, index.search(query).len() ); }}
#[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 }
#[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!(index.search("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!(index.search("fox"), &[0]); }
#[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!(index.search("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!(index.search("fox"), &[0]); assert_eq!(index.search("dog"), &[1]); }
#[test] fn stop_words_are_not_indexed() { let index = sample(); assert!(index.search("the").is_empty()); assert_eq!(index.search("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!(index.search("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!(index.search("run"), &[0]); assert_eq!(index.search("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!(index.search("class"), &[0]); assert_eq!(index.search("box"), &[1]); assert_eq!(index.search("buzz"), &[2]); }
#[test] fn a_stem_needs_three_characters() { let mut index = Index::new(); index.add_document("a.md", "ring"); assert_eq!(index.search("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!(index.search("ärger"), &[0]); }}See it run
Section titled “See it run”From the haystack directory:
cargo run5 documents, 46 distinct terms
postings for "borrow": [0, 1, 2, 3]
query "borrow": docs/ownership.md docs/borrow-checker.md docs/lifetimes.md docs/iterators.md
the same documents from a scan: docs/ownership.md docs/borrow-checker.md docs/lifetimes.md docs/iterators.md
the queries that used to miss: query "ownership": docs/ownership.md query "valid": docs/lifetimes.md
inflections fold onto one term: query "borrow" -> terms ["borrow"] "borrow": [0, 1, 2, 3] query "borrowing" -> terms ["borrow"] "borrow": [0, 1, 2, 3]
stop words are not terms: query "the": 0 documents query "is": 0 documentsEighty-two terms became forty-six. The postings list for “borrow” grew from
[1, 2] to [0, 1, 2, 3]: docs/ownership.md joined it because its
“borrowing” folded onto “borrow”, and docs/iterators.md joined because of
“map borrows the iterator”. The scan underneath finds the same four documents
the slow way, which is the point of the index — the scan’s cost grows with the
corpus, the lookup’s does not.
Note what the inflection demo had to do: the query went through tokenize
before it reached search. search takes a term exactly as the dictionary
stores it, and nothing on the query side normalises yet — a reader typing
“Borrow” with a capital B still gets nothing back. That is the honest state of
the seam at this step, and the query parser is what closes it.
The tests:
cargo testrunning 12 teststest tests::a_doubled_consonant_from_the_suffix_is_collapsed ... oktest tests::a_stem_needs_three_characters ... oktest tests::a_term_in_two_documents_lists_both ... oktest tests::a_missing_term_is_empty_not_an_error ... oktest tests::add_document_returns_the_id_it_gave ... oktest tests::a_term_repeated_in_one_document_lists_it_once ... oktest tests::case_folding_is_unicode_aware ... oktest tests::casing_and_punctuation_are_folded_away ... oktest tests::doubling_that_is_not_the_suffixs_fault_survives ... oktest tests::ids_are_in_insertion_order ... oktest tests::inflections_share_one_term ... oktest tests::stop_words_are_not_indexed ... ok
test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00sTwelve tests. Three of the old ones are untouched, three changed meaning, and six are new: stop words are not indexed, inflections share one term, the doubled-consonant cases both ways, the minimum stem length, and Unicode case folding. The test order is shuffled on every run, so the names come out in a different order each time and nothing should be read into it.
Where this lands
Section titled “Where this lands”This step’s state is tagged search-ch03 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/search-enginegit checkout search-ch03The 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 4, Persisting the index to disk, writes the dictionary and the postings lists to a file the engine can load back — by hand, with no serialisation crate, which is where the sorted-keys decision from step 2 starts to pay off.