Capstone 3: the inverted index

The tokenizer of the previous lesson turns a document into words with positions. The index turns a folder of documents into a map from a word to every place it appears, which is what makes a query a lookup instead of a scan.

An index is built once and read many times, so the cost of the build is paid in exchange for the speed of the queries. On these three files the build is instant and the map has eight entries; the last lesson of the capstone measures both sides and shows where the time goes when the folder grows.

The map is a BTreeMap rather than a HashMap, so the words come out in order and the output of a program that prints the index is the same on every run. A hit is three numbers: the document, the line and the position, and the document vector holds the file names.

Every section reads the same three files from docs, which the command block creates before the program runs.

A word and its documents

build reads the folder, tokenizes each document and appends a hit to the entry of each word. The entry API creates the vector on the first hit and returns the same one afterwards, so the map grows without a second lookup.

The program asks for three words and prints how many hits each one has and which documents they are in. The third word appears in one file only.

use std::collections::BTreeMap; #[derive(Debug, Clone, PartialEq)] struct Token { line: usize, position: usize, word: String, } fn tokenize(text: &str) -> Vec<Token> { let mut tokens = Vec::new(); for (line_number, line) in text.lines().enumerate() { let mut position = 0; for raw in line.split(|c: char| !c.is_alphanumeric()) { if raw.is_empty() { continue; } tokens.push(Token { line: line_number + 1, position, word: raw.to_lowercase(), }); position += 1; } } tokens } #[derive(Debug, Clone, Copy, PartialEq)] struct Hit { document: usize, line: usize, position: usize, } #[allow(dead_code)] struct Index { documents: Vec<String>, words: BTreeMap<String, Vec<Hit>>, counts: Vec<usize>, } #[allow(dead_code)] impl Index { fn build(folder: &str) -> std::io::Result<Index> { let mut paths: Vec<std::path::PathBuf> = std::fs::read_dir(folder)? .filter_map(|entry| entry.ok()) .map(|entry| entry.path()) .filter(|path| path.extension().map(|extension| extension == "txt").unwrap_or(false)) .collect(); paths.sort(); let mut documents = Vec::new(); let mut words: BTreeMap<String, Vec<Hit>> = BTreeMap::new(); let mut counts = Vec::new(); for path in paths { let text = std::fs::read_to_string(&path)?; let document = documents.len(); documents.push(path.file_name().unwrap().to_string_lossy().to_string()); let tokens = tokenize(&text); counts.push(tokens.len()); for token in tokens { words.entry(token.word).or_default().push(Hit { document, line: token.line, position: token.position, }); } } Ok(Index { documents, words, counts }) } fn hits(&self, word: &str) -> &[Hit] { self.words.get(word).map(|hits| hits.as_slice()).unwrap_or(&[]) } fn documents_with(&self, word: &str) -> Vec<&str> { let mut names: Vec<&str> = self .hits(word) .iter() .map(|hit| self.documents[hit.document].as_str()) .collect(); names.dedup(); names } } fn main() { let index = Index::build("docs").unwrap(); println!("documents {}", index.documents.len()); for word in ["rust", "course", "nothing"] { let names = index.documents_with(word); println!("{} {} hits in {}", word, index.hits(word).len(), names.join(", ")); } }

mkdir -p docs
printf 'the rust book\nthe rust course\n' > docs/rust.txt
printf 'a course in rust\n' > docs/course.txt
printf 'nothing here\n' > docs/other.txt
cargo run -q

documents 3
rust 3 hits in course.txt, rust.txt
course 2 hits in course.txt, rust.txt
nothing 1 hits in other.txt

Three hits for rust in two documents, because the word appears twice in one of them. That difference between hits and documents is the subject of the last section: a count of hits is a count of occurrences and a count of documents is a count of files, and a query has to decide which one it ranks by.

The lesson on maps compares the two map types, and parsing text covers the entry API that builds the vectors.

The positions inside a document

A hit that carried only the document number would answer "which file" and nothing else. The line and the position are already in the token, so the index stores them as they are, and a query can print file:line:position as the format every compiler and every grep uses.

The program prints every hit of one word in the order the documents were read.

use std::collections::BTreeMap; #[derive(Debug, Clone, PartialEq)] struct Token { line: usize, position: usize, word: String, } fn tokenize(text: &str) -> Vec<Token> { let mut tokens = Vec::new(); for (line_number, line) in text.lines().enumerate() { let mut position = 0; for raw in line.split(|c: char| !c.is_alphanumeric()) { if raw.is_empty() { continue; } tokens.push(Token { line: line_number + 1, position, word: raw.to_lowercase(), }); position += 1; } } tokens } #[derive(Debug, Clone, Copy, PartialEq)] struct Hit { document: usize, line: usize, position: usize, } #[allow(dead_code)] struct Index { documents: Vec<String>, words: BTreeMap<String, Vec<Hit>>, counts: Vec<usize>, } #[allow(dead_code)] impl Index { fn build(folder: &str) -> std::io::Result<Index> { let mut paths: Vec<std::path::PathBuf> = std::fs::read_dir(folder)? .filter_map(|entry| entry.ok()) .map(|entry| entry.path()) .filter(|path| path.extension().map(|extension| extension == "txt").unwrap_or(false)) .collect(); paths.sort(); let mut documents = Vec::new(); let mut words: BTreeMap<String, Vec<Hit>> = BTreeMap::new(); let mut counts = Vec::new(); for path in paths { let text = std::fs::read_to_string(&path)?; let document = documents.len(); documents.push(path.file_name().unwrap().to_string_lossy().to_string()); let tokens = tokenize(&text); counts.push(tokens.len()); for token in tokens { words.entry(token.word).or_default().push(Hit { document, line: token.line, position: token.position, }); } } Ok(Index { documents, words, counts }) } fn hits(&self, word: &str) -> &[Hit] { self.words.get(word).map(|hits| hits.as_slice()).unwrap_or(&[]) } fn documents_with(&self, word: &str) -> Vec<&str> { let mut names: Vec<&str> = self .hits(word) .iter() .map(|hit| self.documents[hit.document].as_str()) .collect(); names.dedup(); names } } fn main() { let index = Index::build("docs").unwrap(); for hit in index.hits("rust") { println!( "{}:{}:{}", index.documents[hit.document], hit.line, hit.position ); } }

mkdir -p docs
printf 'the rust book\nthe rust course\n' > docs/rust.txt
printf 'a course in rust\n' > docs/course.txt
printf 'nothing here\n' > docs/other.txt
cargo run -q

course.txt:1:3
rust.txt:1:1
rust.txt:2:1

The first hit is the third word of the first line of course.txt, which is rust in a course in rust. A reader can open the file at that line, and a phrase query of the next lesson compares the positions of two words on the same line.

The order of the hits is the order of the documents and then the order of the tokens, which is stable because the folder is sorted in the next section. A map of vectors keeps insertion order within one word, and the lesson on vectors covers the push that builds it.

A folder of documents

read_dir returns the entries in the order of the file system, which differs between machines and between two runs on one machine. The index sorts the paths before it reads them, so document zero is the same file on every run and a test that expects a name is stable.

The program lists the documents with their token counts and the number of distinct words, which is the size of the index in entries.

use std::collections::BTreeMap; #[derive(Debug, Clone, PartialEq)] struct Token { line: usize, position: usize, word: String, } fn tokenize(text: &str) -> Vec<Token> { let mut tokens = Vec::new(); for (line_number, line) in text.lines().enumerate() { let mut position = 0; for raw in line.split(|c: char| !c.is_alphanumeric()) { if raw.is_empty() { continue; } tokens.push(Token { line: line_number + 1, position, word: raw.to_lowercase(), }); position += 1; } } tokens } #[derive(Debug, Clone, Copy, PartialEq)] struct Hit { document: usize, line: usize, position: usize, } #[allow(dead_code)] struct Index { documents: Vec<String>, words: BTreeMap<String, Vec<Hit>>, counts: Vec<usize>, } #[allow(dead_code)] impl Index { fn build(folder: &str) -> std::io::Result<Index> { let mut paths: Vec<std::path::PathBuf> = std::fs::read_dir(folder)? .filter_map(|entry| entry.ok()) .map(|entry| entry.path()) .filter(|path| path.extension().map(|extension| extension == "txt").unwrap_or(false)) .collect(); paths.sort(); let mut documents = Vec::new(); let mut words: BTreeMap<String, Vec<Hit>> = BTreeMap::new(); let mut counts = Vec::new(); for path in paths { let text = std::fs::read_to_string(&path)?; let document = documents.len(); documents.push(path.file_name().unwrap().to_string_lossy().to_string()); let tokens = tokenize(&text); counts.push(tokens.len()); for token in tokens { words.entry(token.word).or_default().push(Hit { document, line: token.line, position: token.position, }); } } Ok(Index { documents, words, counts }) } fn hits(&self, word: &str) -> &[Hit] { self.words.get(word).map(|hits| hits.as_slice()).unwrap_or(&[]) } fn documents_with(&self, word: &str) -> Vec<&str> { let mut names: Vec<&str> = self .hits(word) .iter() .map(|hit| self.documents[hit.document].as_str()) .collect(); names.dedup(); names } } fn main() { let index = Index::build("docs").unwrap(); for (number, name) in index.documents.iter().enumerate() { println!("{} {} {} tokens", number, name, index.counts[number]); } println!("{} words in the index", index.words.len()); }

mkdir -p docs
printf 'the rust book\nthe rust course\n' > docs/rust.txt
printf 'a course in rust\n' > docs/course.txt
printf 'nothing here\n' > docs/other.txt
cargo run -q

0 course.txt 4 tokens
1 other.txt 2 tokens
2 rust.txt 6 tokens
8 words in the index

A file that is not UTF-8 stops the build with an error from read_to_string, which is the right behaviour for a folder of text: a file that cannot be read as text is not a document. A folder with a binary file in it needs the filter to check the extension, which this one already does.

Eight entries for twelve tokens, because four of the tokens are repeats of words the map already had. The numbers also show the small duplication that an index pays for: the file name is stored once and the hits point at it by number, while the words themselves are stored once per distinct word and not once per occurrence.

The sort of the paths is the line that makes everything repeatable, and it is the kind of line that is easy to delete and hard to debug later, because the program keeps working and the numbers move. The lesson on paths covers read_dir, PathBuf and the extension check.

The duplicate a vector keeps

A vector of hits keeps one entry per occurrence, so a word on two lines of the same file appears twice. That is right for a phrase query and wrong for a count of documents, and the index answers both with two calls: the length of the hit vector and the length of the deduplicated document list.

The program asks for the, which appears twice in one file, and prints the two counts and the file names.

use std::collections::BTreeMap; #[derive(Debug, Clone, PartialEq)] struct Token { line: usize, position: usize, word: String, } fn tokenize(text: &str) -> Vec<Token> { let mut tokens = Vec::new(); for (line_number, line) in text.lines().enumerate() { let mut position = 0; for raw in line.split(|c: char| !c.is_alphanumeric()) { if raw.is_empty() { continue; } tokens.push(Token { line: line_number + 1, position, word: raw.to_lowercase(), }); position += 1; } } tokens } #[derive(Debug, Clone, Copy, PartialEq)] struct Hit { document: usize, line: usize, position: usize, } #[allow(dead_code)] struct Index { documents: Vec<String>, words: BTreeMap<String, Vec<Hit>>, counts: Vec<usize>, } #[allow(dead_code)] impl Index { fn build(folder: &str) -> std::io::Result<Index> { let mut paths: Vec<std::path::PathBuf> = std::fs::read_dir(folder)? .filter_map(|entry| entry.ok()) .map(|entry| entry.path()) .filter(|path| path.extension().map(|extension| extension == "txt").unwrap_or(false)) .collect(); paths.sort(); let mut documents = Vec::new(); let mut words: BTreeMap<String, Vec<Hit>> = BTreeMap::new(); let mut counts = Vec::new(); for path in paths { let text = std::fs::read_to_string(&path)?; let document = documents.len(); documents.push(path.file_name().unwrap().to_string_lossy().to_string()); let tokens = tokenize(&text); counts.push(tokens.len()); for token in tokens { words.entry(token.word).or_default().push(Hit { document, line: token.line, position: token.position, }); } } Ok(Index { documents, words, counts }) } fn hits(&self, word: &str) -> &[Hit] { self.words.get(word).map(|hits| hits.as_slice()).unwrap_or(&[]) } fn documents_with(&self, word: &str) -> Vec<&str> { let mut names: Vec<&str> = self .hits(word) .iter() .map(|hit| self.documents[hit.document].as_str()) .collect(); names.dedup(); names } } fn main() { let index = Index::build("docs").unwrap(); let hits = index.hits("the"); println!("{} hits", hits.len()); println!("{} documents", index.documents_with("the").len()); for name in index.documents_with("the") { println!("{}", name); } }

mkdir -p docs
printf 'the rust book\nthe rust course\n' > docs/rust.txt
printf 'a course in rust\n' > docs/course.txt
printf 'nothing here\n' > docs/other.txt
cargo run -q

2 hits
1 documents
rust.txt

A ranking that uses the number of hits rewards a long document that repeats a word, and a ranking that uses the number of documents rewards a word that is spread over the folder. Both are useful and neither is the whole answer, which is why the next lesson prints both numbers next to each result and lets the reader see the evidence.

dedup removes consecutive duplicates, which is why the hit vector has to be in document order for the call to work. A vector that mixed the documents would need a BTreeSet or a sort before the dedup, and the cost of that mistake is a document counted twice in a ranking.

The lesson on sets covers the collection that a mixed vector would need, and the next lesson uses both counts to rank the answers to a query.

Exercises

  1. Skip files larger than a megabyte and print how many were skipped.
  2. Add the number of distinct words of each document to the index and print it in the folder listing.
  3. Remove the sort of the paths, run the program twice and find a run where the order differs.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does the index map?

    Answer

    A word to every hit that contains it

    The inverted index is the lookup from a word to the places it appears.

  2. Why is the map a BTreeMap?

    Answer

    The words come out in order, so the output is the same on every run

    A hash map has no order, and a program that prints it would print a different order each run.

  3. Why are the paths sorted before the files are read?

    Answer

    The document numbers have to be the same on every run

    read_dir order is arbitrary, so sorting is what makes the numbers stable.

  4. What is the difference between the hits and the documents of a word?

    Answer

    Hits count occurrences and documents count files that contain the word

    One file can hold the same word many times, and the two numbers answer different questions.

  5. Why does dedup work on the hit vector?

    Answer

    It removes consecutive duplicates and the hits are in document order

    dedup only looks at neighbours, which is enough once the hits are grouped by document.

  6. What does this program print? use std::collections::BTreeMap; fn main() { let mut index: BTreeMap<&str, Vec<usize>> = BTreeMap::new(); for (word, document) in [("rust", 1), ("go", 0), ("rust", 0)] { index.entry(word).or_default().push(document); } for (word, hits) in &index { println!("{} {:?}", word, hits); } }

    Answer

    go [0] / rust [1, 0]

    The BTreeMap orders the keys and the vectors keep insertion order.

  7. What does this program print? fn main() { let mut hits = vec![1, 1, 2, 2, 2, 3, 1]; hits.dedup(); println!("{} {:?}", hits.len(), hits); }

    Answer

    4 [1, 2, 3, 1]

    dedup removes neighbours only, so the last one survives as a new run.

  8. What does this program print? fn main() { let names = ["b.txt", "a.txt", "c.txt"]; let mut sorted = names.to_vec(); sorted.sort(); println!("{} {}", sorted[0], names[0]); }

    Answer

    a.txt b.txt

    The copy is sorted and the original array keeps its order.

  9. What does this program print? use std::collections::BTreeMap; fn main() { let mut words: BTreeMap<String, usize> = BTreeMap::new(); for word in ["the", "rust", "the", "index"] { *words.entry(word.to_string()).or_insert(0) += 1; } println!("{} {}", words.len(), words["the"]); }

    Answer

    3 2

    Three distinct words and the repeated one counts two.

  10. What does this program print? fn main() { let hits = [(0usize, 1usize), (0, 2), (1, 1)]; let mut names = Vec::new(); for (document, _) in hits { if names.last() != Some(&document) { names.push(document); } } println!("{} {:?}", names.len(), names); }

    Answer

    2 [0, 1]

    The loop keeps one entry per run of documents, so the two runs give two numbers.

The code on this page was built with cargo 1.96.1 and rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev