Capstone 3: a tokenizer
The third capstone is a search engine over a folder of text files. It has the same shape as the first two: a tokenizer that turns a document into words, an index that maps a word to the documents that contain it, a query layer and a benchmark.
The tokenizer is the smallest piece and the one that decides what the search can find. A word is a run of letters, the case is folded, and the position is kept so that the phrase search of lesson 149 can check that two words are neighbours.
The tokenizer is also the only place that knows about the encoding of the text. A document in UTF-8 with letters outside ASCII is handled byte by byte here, which is a limitation the tests record rather than hide.
Words, case and positions
tokenize walks the text and starts a word at the first letter. It lower-cases each letter with std::tolower and remembers the index of the first one, so a later search can report where the word was.
The program tokenizes The Cat sat and prints each word with its position: the@0 cat@4 sat@8. The position counts bytes from the start, which is the same choice as the JSON lexer of lesson 137.
Folding the case at the tokenizer is what lets the query cat find Cat. The alternative is to fold at query time as well, and then the index and the query must agree; doing it once, at the source, is simpler.
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
struct word
{
std::string text;
std::size_t position;
};
std::vector<word> tokenize(const std::string& text)
{
std::vector<word> words;
for (std::size_t i = 0; i < text.size();) {
if (!std::isalpha(static_cast<unsigned char>(text[i]))) {
++i;
continue;
}
std::size_t start = i;
std::string value;
while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) {
value.push_back(static_cast<char>(std::tolower(static_cast<unsigned char>(text[i]))));
++i;
}
words.push_back({value, start});
}
return words;
}
int main()
{
for (const word& item : tokenize("The Cat sat")) {
std::cout << item.text << '@' << item.position << '\n';
}
}
g++ -std=c++23 -Wall -Wextra words.cpp -o tokenizer_words
./tokenizer_words
the@0
cat@4
sat@8
Punctuation falls away
The loop skips every character that is not a letter, so a comma, a full stop and a digit never start a word and never end one. That is the whole rule for punctuation in this project.
The program tokenizes a sentence with three marks and prints the four words. The marks are gone, and C++23 becomes c: the letters are kept, and the plus signs and the digits are not, which is a decision worth knowing.
A tokenizer that kept digits would produce c23 and find the term. The project chooses letters, so C++23 is indexed as c, which is a limitation stated rather than hidden.
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> tokenize(const std::string& text)
{
std::vector<std::string> words;
for (std::size_t i = 0; i < text.size();) {
if (!std::isalpha(static_cast<unsigned char>(text[i]))) {
++i;
continue;
}
std::string value;
while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) {
value.push_back(static_cast<char>(std::tolower(static_cast<unsigned char>(text[i]))));
++i;
}
words.push_back(value);
}
return words;
}
int main()
{
std::vector<std::string> words = tokenize("alpha, beta. gamma! C++23");
std::cout << words.size() << ' ';
for (const std::string& item : words) {
std::cout << item << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra punctuation.cpp -o tokenizer_punctuation
./tokenizer_punctuation
4 alpha beta gamma c
The line a word came from
A position in the file is exact and awkward to read. The tokenizer also counts newlines, so each word carries the line number, which is what a search result shows.
The program tokenizes a document of three lines and prints word:line for each word. The first line has two words, the second one and the third two, and the numbers match.
The line counter is incremented in the same loop that skips characters, so a newline updates both the position and the line. That is why the tokenizer reads the text once rather than splitting it twice.
#include <cctype>
#include <iostream>
#include <string>
#include <vector>
struct word
{
std::string text;
int line;
};
std::vector<word> tokenize(const std::string& text)
{
std::vector<word> words;
int line = 1;
for (std::size_t i = 0; i < text.size();) {
if (text[i] == '\n') {
++line;
++i;
continue;
}
if (!std::isalpha(static_cast<unsigned char>(text[i]))) {
++i;
continue;
}
std::string value;
while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) {
value.push_back(static_cast<char>(std::tolower(static_cast<unsigned char>(text[i]))));
++i;
}
words.push_back({value, line});
}
return words;
}
int main()
{
std::vector<word> words = tokenize("one two\nthree\nfour five");
for (const word& item : words) {
std::cout << item.text << ':' << item.line << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra lines.cpp -o tokenizer_lines
./tokenizer_lines
one:1 two:1 three:2 four:3 five:3
The file that will not open
The indexer reads files, and the first file it is given may not exist. The stream reports it, and the loader turns it into an exception with the path, as the task storage did in lesson 143.
The program opens a file that was never written and catches the exception. The output is cannot open missing.txt, and the index build of the next lesson catches the same error per file and keeps going.
Skipping a missing file is the right policy for a folder scan, where one broken name should not stop the others. A single named document is the other case, and there the error ends the command.
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
std::string read_file(const std::string& path)
{
std::ifstream in{path};
if (!in) {
throw std::runtime_error("cannot open " + path);
}
std::ostringstream buffer;
buffer << in.rdbuf();
return buffer.str();
}
int main()
{
try {
read_file("missing.txt");
} catch (const std::runtime_error& error) {
std::cout << error.what() << '\n';
}
}
g++ -std=c++23 -Wall -Wextra missing.cpp -o tokenizer_missing
./tokenizer_missing
cannot open missing.txt
Exercises
- Keep the digits as part of a word and check that C++23 becomes c23.
- Add the sentence number to each word and print it next to the line.
- Write a test that tokenizes the empty string and checks that the result is empty.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is a word in this tokenizer?
Answer
A run of letters
The loop skips anything that is not a letter, so digits and marks end a word.
-
Why lower-case the letters while tokenizing?
Answer
So the query and the index agree without a second fold
One fold at the source means every later comparison is on the same form.
-
What is the position of a word?
Answer
The byte index of its first letter
The index into the string is exact, and the line number is carried separately.
-
What does this program print?
#include <cctype> #include <iostream> #include <string> int main() { std::string text = "The Cat sat"; for (std::size_t i = 0; i < text.size();) { if (!std::isalpha(static_cast<unsigned char>(text[i]))) { ++i; continue; } std::size_t start = i; while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) ++i; std::string word = text.substr(start, i - start); for (char& c : word) c = static_cast<char>(std::tolower(static_cast<unsigned char>(c))); std::cout << word << '@' << start << ' '; } }Answer
the@0 cat@4 sat@8
The case is folded and each word prints the index of its first letter.
-
What does this program print?
#include <cctype> #include <iostream> #include <string> #include <vector> int main() { std::string text = "alpha, beta. gamma! C++23"; std::vector<std::string> words; for (std::size_t i = 0; i < text.size();) { if (!std::isalpha(static_cast<unsigned char>(text[i]))) { ++i; continue; } std::string word; while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) word += static_cast<char>(std::tolower(static_cast<unsigned char>(text[i++]))); words.push_back(word); } std::cout << words.size() << ' '; for (const auto& word : words) std::cout << word << ' '; }Answer
4 alpha beta gamma c
Three words plus the letter c of C++23; the plus signs and digits are skipped.
-
What does this program print?
#include <cctype> #include <iostream> #include <string> int main() { std::string text = "one two\nthree\nfour five"; int line = 1; for (std::size_t i = 0; i < text.size();) { if (text[i] == '\n') { ++line; ++i; continue; } if (!std::isalpha(static_cast<unsigned char>(text[i]))) { ++i; continue; } std::string word; while (i < text.size() && std::isalpha(static_cast<unsigned char>(text[i]))) word += static_cast<char>(std::tolower(static_cast<unsigned char>(text[i++]))); std::cout << word << ':' << line << ' '; } }Answer
one:1 two:1 three:2 four:3 five:3
The newline increments the line before the next word, so the third line holds two words on 3.
-
What does this program print?
#include <fstream> #include <iostream> #include <stdexcept> #include <string> int main() { try { std::ifstream in{"missing.txt"}; if (!in) throw std::runtime_error("cannot open missing.txt"); } catch (const std::runtime_error& error) { std::cout << error.what(); } }Answer
cannot open missing.txt
The stream reports the missing file, and the catch prints the path.
-
Why is the line counter incremented in the skipping loop?
Answer
So one pass over the text gives both positions and lines
The loop already visits every character, so the line changes where the newline is.
-
What is the cost of ignoring digits?
Answer
A document about C++23 is found only by the letter c
The choice is stated in the lesson: letters only, so numeric terms are not searchable.
-
What should a folder scan do when one file is missing?
Answer
Skip it and continue with the others
One broken name should not hide the rest of the folder, which is the next lesson's policy.
The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev