Capstone 3: queries and ranking
The index of the previous lesson answers one word at a time. A query is a few words with a rule between them, and the rules are small: AND keeps the documents that contain every word, OR keeps the ones that contain any, and a phrase keeps the places where the words sit next to each other.
Each query is a function on the index and nothing else, which is what makes the four sections independent: the same index answers all of them, and a new query is a new function rather than a change to the build.
The last piece is the order of the answer. A search that returns the right documents in an arbitrary order is technically correct and practically useless, so the ranking counts the hits and sorts by them, with the document number as the tie-breaker that keeps the output stable.
The three files of the previous lesson are recreated by every command block, so each section starts from the same folder.
AND is an intersection
The first word gives a list of documents, and each following word removes the documents that do not contain it. The lists are short and in order, so a retain with a contains is the whole intersection; a sorted merge would be faster on a folder of thousands of files and is the same idea.
The program asks for the two words that both appear in two of the three files and prints the 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)]
#[allow(dead_code)]
#[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<usize> {
let mut documents: Vec<usize> = self.hits(word).iter().map(|hit| hit.document).collect();
documents.dedup();
documents
}
}
#[allow(dead_code)]
impl Index {
fn query_and(&self, words: &[&str]) -> Vec<usize> {
let mut result = self.documents_with(words[0])
.iter()
.map(|document| *document)
.collect::<Vec<usize>>();
for word in &words[1..] {
let next = self.documents_with(word);
result.retain(|document| next.contains(document));
}
result
}
fn query_or(&self, words: &[&str]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
for word in words {
for document in self.documents_with(word) {
if !result.contains(&document) {
result.push(document);
}
}
}
result.sort();
result
}
fn rank(&self, words: &[&str]) -> Vec<(usize, usize)> {
let mut scores: Vec<(usize, usize)> = self
.query_or(words)
.into_iter()
.map(|document| {
let score = words
.iter()
.map(|word| self.hits(word).iter().filter(|hit| hit.document == document).count())
.sum();
(document, score)
})
.collect();
scores.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
scores
}
fn phrase(&self, words: &[&str]) -> Vec<Hit> {
let mut found = Vec::new();
for first in self.hits(words[0]) {
let mut matches = true;
for (offset, word) in words.iter().enumerate().skip(1) {
let target = Hit {
document: first.document,
line: first.line,
position: first.position + offset,
};
if !self.hits(word).contains(&target) {
matches = false;
break;
}
}
if matches {
found.push(*first);
}
}
found
}
}
fn main() {
let index = Index::build("docs").unwrap();
for document in index.query_and(&["rust", "course"]) {
println!("{}", index.documents[document]);
}
println!("{} documents", index.query_and(&["rust", "course"]).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
course.txt
rust.txt
2 documents
The order of the words in the query does not change the result of an intersection, and it does change the work: the shortest list should come first so that the later retain calls have less to walk. That is an optimization the last lesson measures rather than a rule the reader has to trust. The third file contains neither word and never enters the first list, so the intersection skips it without a check. The order is the order of the documents vector, which the sort of the paths fixed in the previous lesson.
An empty query has no first word, and the function would panic on words[0]. The command line of a real tool checks for it before the call, and the lesson on Option shows the first that makes the check part of the function.
OR is a union
The union visits each word, takes its document list and adds the documents that are not there yet. The result is sorted at the end, because the words of a query arrive in an order that has nothing to do with the order of the files.
The program asks for a word in one file and a word in another, and the answer is those two files.
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)]
#[allow(dead_code)]
#[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<usize> {
let mut documents: Vec<usize> = self.hits(word).iter().map(|hit| hit.document).collect();
documents.dedup();
documents
}
}
#[allow(dead_code)]
impl Index {
fn query_and(&self, words: &[&str]) -> Vec<usize> {
let mut result = self.documents_with(words[0])
.iter()
.map(|document| *document)
.collect::<Vec<usize>>();
for word in &words[1..] {
let next = self.documents_with(word);
result.retain(|document| next.contains(document));
}
result
}
fn query_or(&self, words: &[&str]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
for word in words {
for document in self.documents_with(word) {
if !result.contains(&document) {
result.push(document);
}
}
}
result.sort();
result
}
fn rank(&self, words: &[&str]) -> Vec<(usize, usize)> {
let mut scores: Vec<(usize, usize)> = self
.query_or(words)
.into_iter()
.map(|document| {
let score = words
.iter()
.map(|word| self.hits(word).iter().filter(|hit| hit.document == document).count())
.sum();
(document, score)
})
.collect();
scores.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
scores
}
fn phrase(&self, words: &[&str]) -> Vec<Hit> {
let mut found = Vec::new();
for first in self.hits(words[0]) {
let mut matches = true;
for (offset, word) in words.iter().enumerate().skip(1) {
let target = Hit {
document: first.document,
line: first.line,
position: first.position + offset,
};
if !self.hits(word).contains(&target) {
matches = false;
break;
}
}
if matches {
found.push(*first);
}
}
found
}
}
fn main() {
let index = Index::build("docs").unwrap();
for document in index.query_or(&["nothing", "book"]) {
println!("{}", index.documents[document]);
}
}
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
other.txt
rust.txt
A document that contains both words appears once, because the check runs before the push. That single line is the difference between a result list and a list of lists, and it is also where a bug of this kind usually hides: a union that appends without the check returns the same file twice and doubles its score. The union is the query a search box runs when the user types several words without quotes, and the intersection is what the user usually means. A real engine ranks the union and lets the documents that contain more of the words float to the top, which is the subject of the next section.
The contains on a vector makes the union quadratic in the number of documents, which is invisible on three files and visible on ten thousand. The lesson on sets covers the structure that makes the check constant, and the last lesson of the capstone measures the difference.
Ranking by occurrences
The score of a document is the number of hits it has for the words of the query, so a document that uses a word three times beats one that uses it once. The sort is by score and then by document number, which makes two documents with the same score come out in a fixed order.
The program ranks two words over the three files and prints the file and its score.
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)]
#[allow(dead_code)]
#[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<usize> {
let mut documents: Vec<usize> = self.hits(word).iter().map(|hit| hit.document).collect();
documents.dedup();
documents
}
}
#[allow(dead_code)]
impl Index {
fn query_and(&self, words: &[&str]) -> Vec<usize> {
let mut result = self.documents_with(words[0])
.iter()
.map(|document| *document)
.collect::<Vec<usize>>();
for word in &words[1..] {
let next = self.documents_with(word);
result.retain(|document| next.contains(document));
}
result
}
fn query_or(&self, words: &[&str]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
for word in words {
for document in self.documents_with(word) {
if !result.contains(&document) {
result.push(document);
}
}
}
result.sort();
result
}
fn rank(&self, words: &[&str]) -> Vec<(usize, usize)> {
let mut scores: Vec<(usize, usize)> = self
.query_or(words)
.into_iter()
.map(|document| {
let score = words
.iter()
.map(|word| self.hits(word).iter().filter(|hit| hit.document == document).count())
.sum();
(document, score)
})
.collect();
scores.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
scores
}
fn phrase(&self, words: &[&str]) -> Vec<Hit> {
let mut found = Vec::new();
for first in self.hits(words[0]) {
let mut matches = true;
for (offset, word) in words.iter().enumerate().skip(1) {
let target = Hit {
document: first.document,
line: first.line,
position: first.position + offset,
};
if !self.hits(word).contains(&target) {
matches = false;
break;
}
}
if matches {
found.push(*first);
}
}
found
}
}
fn main() {
let index = Index::build("docs").unwrap();
for (document, score) in index.rank(&["the", "course"]) {
println!("{} {}", index.documents[document], score);
}
}
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
rust.txt 3
course.txt 1
Three hits for the two words in the file that uses one of them twice, and one hit in the file that uses the other once. The score is a count and not a probability, and a real engine divides it by the length of the document to stop a long file from winning by repetition alone; the count is the version that fits on a page and the shape is the same.
The tie-breaker is the part that makes the output stable and the tests possible. Without it two documents with the same score would come out in the order the sort happened to produce, which for a stable sort is the order of the input and for an unstable one is a detail of the implementation. The lesson on sorting covers sort_by and the comparison that this one uses.
A phrase needs positions
Two words that both appear in a document are not a phrase. The phrase check takes every hit of the first word and asks whether the next word has a hit on the same line at the next position, and so on for the rest of the phrase.
The program searches for the rust and finds it at the start of both lines of the file that repeats the pair.
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)]
#[allow(dead_code)]
#[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<usize> {
let mut documents: Vec<usize> = self.hits(word).iter().map(|hit| hit.document).collect();
documents.dedup();
documents
}
}
#[allow(dead_code)]
impl Index {
fn query_and(&self, words: &[&str]) -> Vec<usize> {
let mut result = self.documents_with(words[0])
.iter()
.map(|document| *document)
.collect::<Vec<usize>>();
for word in &words[1..] {
let next = self.documents_with(word);
result.retain(|document| next.contains(document));
}
result
}
fn query_or(&self, words: &[&str]) -> Vec<usize> {
let mut result: Vec<usize> = Vec::new();
for word in words {
for document in self.documents_with(word) {
if !result.contains(&document) {
result.push(document);
}
}
}
result.sort();
result
}
fn rank(&self, words: &[&str]) -> Vec<(usize, usize)> {
let mut scores: Vec<(usize, usize)> = self
.query_or(words)
.into_iter()
.map(|document| {
let score = words
.iter()
.map(|word| self.hits(word).iter().filter(|hit| hit.document == document).count())
.sum();
(document, score)
})
.collect();
scores.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0)));
scores
}
fn phrase(&self, words: &[&str]) -> Vec<Hit> {
let mut found = Vec::new();
for first in self.hits(words[0]) {
let mut matches = true;
for (offset, word) in words.iter().enumerate().skip(1) {
let target = Hit {
document: first.document,
line: first.line,
position: first.position + offset,
};
if !self.hits(word).contains(&target) {
matches = false;
break;
}
}
if matches {
found.push(*first);
}
}
found
}
}
fn main() {
let index = Index::build("docs").unwrap();
for hit in index.phrase(&["the", "rust"]) {
println!("{}:{}:{}", index.documents[hit.document], hit.line, hit.position);
}
println!("{} phrase hits", index.phrase(&["the", "rust"]).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
rust.txt:1:0
rust.txt:2:0
2 phrase hits
The third file has rust and no the, and the second has both in the wrong order, so neither is a phrase hit. A check that only compared the sets of words would have returned both files, which is the mistake this section exists to prevent: without the positions, a phrase query is an AND with a better name.
The comparison is a linear search through the hits of each word, which is fine for a phrase of three words and a small folder. A real engine keeps the positions sorted per document and merges them, and the binary search of the sorting lesson is the first step in that direction. The next lesson measures which of these queries is worth optimizing.
Exercises
- Add a NOT that removes the documents of a word from the result of an AND.
- Divide the score by the number of tokens of the document and compare the two rankings.
- Make the phrase search accept a gap of one word and print the hits it adds.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does an AND query keep?
Answer
The documents that contain every word of the query
The intersection removes a document as soon as one word is missing.
-
Why is the result of an OR query sorted at the end?
Answer
The words arrive in an order that has nothing to do with the order of the files
A union built word by word would otherwise follow the query order.
-
What does the score of a document count in this lesson?
Answer
The hits of the query words in that document
The ranking is a count of occurrences, with the document number as a tie-breaker.
-
Why does a phrase query need positions?
Answer
Two words in a document are not necessarily next to each other
Adjacency is a relation between positions on one line.
-
What does the document number as a tie-breaker give the ranking?
Answer
A fixed order for documents with the same score
Without it the order of equal scores would depend on the sort implementation.
-
What does this program print?
fn main() { let left = [1usize, 2, 3]; let right = [2usize, 3, 4]; let mut both = left.to_vec(); both.retain(|document| right.contains(document)); println!("{:?}", both); }Answer
[2, 3]
The retain keeps the elements of the first list that also appear in the second.
-
What does this program print?
fn main() { let mut documents = Vec::new(); for word in ["b", "a"] { for document in if word == "a" { vec![1usize, 2] } else { vec![2usize, 3] } { if !documents.contains(&document) { documents.push(document); } } } documents.sort(); println!("{:?}", documents); }Answer
[1, 2, 3]
The union adds each document once and the sort puts them in order.
-
What does this program print?
fn main() { let scores = [(2usize, 3usize), (0, 3), (1, 5)]; let mut ranked = scores.to_vec(); ranked.sort_by(|left, right| right.1.cmp(&left.1).then(left.0.cmp(&right.0))); println!("{:?}", ranked); }Answer
[(1, 5), (0, 3), (2, 3)]
The highest score comes first and the equal scores fall back to the document number.
-
What does this program print?
#[derive(Debug, PartialEq)] struct Hit { document: usize, line: usize, position: usize, } fn main() { let first = Hit { document: 0, line: 1, position: 2 }; let second = Hit { document: 0, line: 1, position: 3 }; let adjacent = second.line == first.line && second.position == first.position + 1; println!("{} {}", adjacent, first == second); }Answer
true false
The positions differ by one on one line, and the two hits are still different values.
-
What does this program print?
fn phrase(haystack: &[(&str, usize)], needle: &[&str]) -> usize { let mut count = 0; for (index, (word, _)) in haystack.iter().enumerate() { if *word != needle[0] { continue; } let mut matched = true; for (offset, wanted) in needle.iter().enumerate().skip(1) { if haystack.get(index + offset).map(|(word, _)| word) != Some(wanted) { matched = false; break; } } if matched { count += 1; } } count } fn main() { let text = [("the", 0), ("rust", 1), ("course", 2), ("the", 0), ("course", 1)]; println!("{}", phrase(&text, &["the", "rust"])); }Answer
1
Only the first the is followed by rust, and the second is followed by course.
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