Capstone 3: a tokenizer
The third capstone is a search index over a folder of text files, in four lessons: the tokenizer, the index, the queries and a measurement. The tokenizer is the layer that decides what a word is, and every later answer is only as good as that decision.
A token carries four things: the document it came from, the line, the position in the line and the word itself. The position is what makes a phrase query possible later, and the line is what a search result shows next to the file name. The word is lower case, so the index answers the same way for Rust and rust.
The project is a cargo package with one file, src/main.rs, and the sections below show it in full at each step.
Words, case and positions
An index is a cache of a decision: it stores what the tokenizer thought the words were, so the queries never read the documents again. That makes the decision hard to change later, which is why it belongs in the first lesson rather than in the last. The tokenizer splits each line on everything that is not a letter or a digit, skips the empty pieces and pushes a token for the rest. The position counts the words of the line and not the characters of the text, which is what a phrase query compares.
The program tokenizes two lines and prints each token as document, line and position followed by the word. The same two words appear on both lines, with the positions starting again at zero.
#[derive(Debug, Clone, PartialEq)]
struct Token {
document: usize,
line: usize,
position: usize,
word: String,
}
fn tokenize(document: usize, 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 {
document,
line: line_number + 1,
position,
word: raw.to_lowercase(),
});
position += 1;
}
}
tokens
}
fn main() {
let text = "Rust is fast\nRust is safe\n";
for token in tokenize(0, text) {
println!("{}:{}:{} {}", token.document, token.line, token.position, token.word);
}
}
cargo run -q
0:1:0 rust
0:1:1 is
0:1:2 fast
0:2:0 rust
0:2:1 is
0:2:2 safe
The pair of positions in the third column is the whole promise of a phrase query: fast at 2 and safe at 2 are not adjacent, while rust is at 0 and 1 is. The document number is zero here because there is one document; the next lesson fills it from a folder.
The lesson on UTF-8 explains why the split is on characters and not bytes, and the lesson on strings covers the to_lowercase that makes the case disappear.
Punctuation falls away
A comma, a semicolon and an exclamation mark are separators like a space, because the split takes every character that is not alphanumeric. A hyphen is a separator too, so state-of-the-art becomes four words, which is a decision and not a law: a search engine that wants the compound adds a rule before the split.
The program tokenizes a sentence with all of that punctuation and prints the count and the words.
#[derive(Debug, Clone, PartialEq)]
struct Token {
document: usize,
line: usize,
position: usize,
word: String,
}
fn tokenize(document: usize, 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 {
document,
line: line_number + 1,
position,
word: raw.to_lowercase(),
});
position += 1;
}
}
tokens
}
fn main() {
let text = "The quick, brown fox; jumps over the lazy dog!";
let tokens = tokenize(0, text);
let words: Vec<&str> = tokens.iter().map(|token| token.word.as_str()).collect();
println!("{} words", tokens.len());
println!("{}", words.join(" "));
}
cargo run -q
9 words
the quick brown fox jumps over the lazy dog
The apostrophe is a separator under this rule, so don't becomes don and t. A real index for English keeps the apostrophe inside a word, and the lesson leaves the rule simple on purpose: the list of exceptions is the part that takes a week. Nine words from a sentence with a comma, a semicolon and an exclamation mark, and every one of them in lower case. The word The at the start became the, so a query for either spelling finds this line.
Stop words are the next decision, and this index keeps them: the is a word like any other, and a query for it returns every line that uses it. Removing stop words makes the index smaller and makes a phrase query harder, which is why the choice belongs to the user of the index and not to the tokenizer. The lesson on sets covers the collection that a stop word list would use.
The line a word came from
A result that names a file and nothing else makes the reader open it and search. A result that names the line is one jump away, and the token already carries the number, so the only work is to keep it.
The program tokenizes three lines and filters the tokens for one word. Five of them match, at two positions on each of the first two lines and one on the third.
#[derive(Debug, Clone, PartialEq)]
struct Token {
document: usize,
line: usize,
position: usize,
word: String,
}
fn tokenize(document: usize, 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 {
document,
line: line_number + 1,
position,
word: raw.to_lowercase(),
});
position += 1;
}
}
tokens
}
fn main() {
let text = "the index keeps the line\nthe position and the word\nthe end";
let tokens = tokenize(7, text);
let hits: Vec<&Token> = tokens.iter().filter(|token| token.word == "the").collect();
println!("{} hits", hits.len());
for token in hits {
println!("line {} position {}", token.line, token.position);
}
}
cargo run -q
5 hits
line 1 position 0
line 1 position 3
line 2 position 0
line 2 position 3
line 3 position 0
The document number is seven here, which shows that the tokenizer does not care where the number comes from; the next lesson passes the position of the file in the folder. The line and the position are one-based and zero-based respectively, which is the convention of an editor: a line is counted from one and a column from zero.
Filtering a vector of tokens is the slowest way to answer a query and the clearest way to check the tokenizer. The index of the next lesson turns the same filter into a lookup, and the lesson on iterators covers the filter and map used here.
The file that will not open
The tokenizer is done, and the first thing the program does with it is read a file. The read returns a Result, and the caller decides whether a missing document is a warning or the end of the run.
The program asks for a file in a folder that does not exist and prints the comparison and the kind, the same pair the tracker printed in its storage lesson.
#[derive(Debug, Clone, PartialEq)]
struct Token {
document: usize,
line: usize,
position: usize,
word: String,
}
#[allow(dead_code)]
fn tokenize(document: usize, 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 {
document,
line: line_number + 1,
position,
word: raw.to_lowercase(),
});
position += 1;
}
}
tokens
}
fn main() {
match std::fs::read_to_string("docs/missing.txt") {
Ok(text) => println!("{} bytes", text.len()),
Err(error) => println!("{} {:?}", error.kind() == std::io::ErrorKind::NotFound, error.kind()),
}
}
cargo run -q
true NotFound
The index of the next lesson walks a folder and reads every file in it, so a missing file is only possible between the listing and the read, and the run continues with the rest. Printing the kind instead of the message keeps the output the same on every platform, which a test can rely on.
The lesson on text files covers the read and the buffer, and the next lesson builds the index from a folder of documents.
Exercises
- Keep a hyphen inside a word and check that state-of-the-art becomes one token.
- Add a column that counts characters rather than words and explain which queries it would serve.
- Drop the words of a small stop list and print how many tokens the filter removed.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
Why is every word stored in lower case?
Answer
A query finds rust and Rust with one entry
Normalising the case is what makes the index case-insensitive.
-
What does the position of a token count?
Answer
The words of its line, which is what a phrase query compares
Two words are adjacent when their positions differ by one on the same line.
-
What happens to a comma in the tokenizer?
Answer
It is a separator, so it produces no token
The split breaks on every character that is not alphanumeric.
-
Why does a token keep the line number?
Answer
A search result can name the line instead of only the file
The line is the useful part of a hit and it costs one number.
-
Why does the tokenizer keep stop words?
Answer
Removing them makes a phrase query harder, so the choice belongs to the index
The tokenizer reports what it read and leaves the filtering policy above it.
-
What does this program print?
fn tokenize(text: &str) -> Vec<String> { text.split(|c: char| !c.is_alphanumeric()) .filter(|word| !word.is_empty()) .map(|word| word.to_lowercase()) .collect() } fn main() { let tokens = tokenize("Rust, Rust! rust?"); println!("{} {}", tokens.len(), tokens[2]); }Answer
3 rust
Three words survive the split and all of them are lower case.
-
What does this program print?
fn main() { let text = "one two\nthree four five"; let mut count = 0; for line in text.lines() { count += line.split_whitespace().count(); } println!("{count}"); }Answer
5
Two words on the first line and three on the second make five.
-
What does this program print?
#[derive(Debug, PartialEq)] struct Token { line: usize, position: usize, word: String, } fn main() { let tokens = vec![ Token { line: 1, position: 0, word: "a".to_string() }, Token { line: 1, position: 1, word: "b".to_string() }, Token { line: 2, position: 0, word: "a".to_string() }, ]; let hits = tokens.iter().filter(|token| token.word == "a").count(); let adjacent = tokens[0].line == tokens[1].line && tokens[1].position == tokens[0].position + 1; println!("{} {}", hits, adjacent); }Answer
2 true
Two tokens say a, and the first two are adjacent on one line.
-
What does this program print?
fn main() { let text = "the state-of-the-art index"; let words: Vec<&str> = text.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty()).collect(); println!("{}", words.len()); }Answer
6
The hyphens split the compound into four words, and the other three words follow.
-
What does this program print?
fn main() { let mut text = String::from("Rust"); text.push_str(" and "); text.push_str("C++"); let words: Vec<&str> = text.split(|c: char| !c.is_alphanumeric()).filter(|w| !w.is_empty()).collect(); println!("{:?}", words); }Answer
["Rust", "and", "C"]
The plus signs are separators, so the last word ends at the first of them.
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
