Capstone 3: the inverted index
An inverted index turns the question around. A document is a list of words, and the index is a map from a word to the list of documents that contain it, which is the structure that makes a query touch only the words it mentions.
The tokenizer of lesson 147 produced the words. This lesson builds the map, adds the positions that the phrase search needs, and reads a folder instead of a list so the project has an input a user recognises.
The index is also the first structure in the course whose cost depends on the corpus rather than on the code. A hundred documents fit in a test, and a million need the measurement of the next lesson.
The scan is also the place where a symlink loop appears, which is why the recursive version of the crawler needs a visited set. The flat folder of this lesson has no such problem.
A word and its documents
The index is std::map<std::string, std::set<int>>: the key is a word and the value is the set of document ids that contain it. The set removes a duplicate when the same word appears twice in one document and keeps the ids in order.
The program indexes two documents and prints one line per word with its ids. the appears in both and prints 1,2, while cat and dog have one document each.
The map sorts the words, so the output is stable without a sort call. A std::unordered_map would be faster to build and would print in an order that depends on the hashes, which is why the project uses the ordered one at this size.
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
struct document
{
int id;
std::vector<std::string> words;
};
std::map<std::string, std::set<int>> build(const std::vector<document>& documents)
{
std::map<std::string, std::set<int>> index;
for (const document& item : documents) {
for (const std::string& word : item.words) {
index[word].insert(item.id);
}
}
return index;
}
int main()
{
std::vector<document> documents{
{1, {"the", "cat", "sat"}},
{2, {"the", "dog", "sat"}},
};
for (const auto& [word, ids] : build(documents)) {
std::cout << word << ':';
bool first = true;
for (int id : ids) {
if (!first) {
std::cout << ',';
}
first = false;
std::cout << id;
}
std::cout << '\n';
}
}
g++ -std=c++23 -Wall -Wextra map.cpp -o index_map
./index_map
cat:1
dog:2
sat:1,2
the:1,2
The positions inside a document
The phrase search of lesson 149 needs to know that two words are neighbours, so the index stores the positions as well: std::map<std::string, std::map<int, std::vector<int>>> maps a word to a document to the places it occurs.
The program indexes the same two documents with positions and prints the entry for the: document 1 at position 0 and document 2 at position 0.
The nested map is heavier than the set and it is what makes the last query possible. A search engine chooses the structure from the queries it must answer, which is the theme of the next lesson.
#include <iostream>
#include <map>
#include <string>
#include <vector>
struct document
{
int id;
std::vector<std::string> words;
};
int main()
{
std::vector<document> documents{
{1, {"the", "cat", "sat"}},
{2, {"the", "dog", "sat"}},
};
std::map<std::string, std::map<int, std::vector<int>>> index;
for (const document& item : documents) {
for (std::size_t position = 0; position < item.words.size(); ++position) {
index[item.words[position]][item.id].push_back(static_cast<int>(position));
}
}
for (const auto& [document_id, places] : index["the"]) {
std::cout << document_id << ':';
for (int place : places) {
std::cout << place;
}
std::cout << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra positions.cpp -o index_positions
./index_positions
1:0 2:0
A folder of documents
The program writes two text files, scans the directory with std::filesystem::directory_iterator, and tokenizes each one. A file that fails to open is counted and skipped, which is the policy of the previous lesson.
The output is 2 documents, 4 words: the two files exist, and the distinct words are the, cat, sat and dog, which is six occurrences of four words.
The extension check is what keeps the index to text files. A real crawler also follows subdirectories and skips binaries, and both are a loop around the same per-file function.
#include <cctype>
#include <filesystem>
#include <fstream>
#include <iostream>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <vector>
namespace fs = std::filesystem;
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()
{
fs::create_directories("docs");
{
std::ofstream{"docs/a.txt"} << "the cat sat";
std::ofstream{"docs/b.txt"} << "the dog sat";
}
std::map<std::string, std::set<int>> index;
int documents = 0;
for (const fs::directory_entry& entry : fs::directory_iterator{"docs"}) {
if (entry.path().extension() != ".txt") {
continue;
}
++documents;
std::ifstream in{entry.path()};
for (const std::string& word : tokenize(std::string{
std::istreambuf_iterator<char>{in}, std::istreambuf_iterator<char>{}})) {
index[word].insert(documents);
}
}
std::cout << documents << " documents, " << index.size() << " words\n";
}
g++ -std=c++23 -Wall -Wextra folder.cpp -o index_folder
./index_folder
2 documents, 4 words
The duplicate a vector keeps
A word that appears twice in one document must not add the document twice. A std::vector<int> of ids does exactly that, and the entry grows for every occurrence; a std::set<int> ignores the second insert.
The program inserts document 5 for the word the twice into a vector and twice into a set, and prints the two sizes: 2 and 1. The second number is the one the query layer can trust.
The duplicate is harmless in a small example and expensive in a real one: a query that intersects two lists of ids does the same work twice. The set is the structure the index needs, and the positions live in a separate map for the phrase search.
#include <iostream>
#include <set>
#include <vector>
int main()
{
std::vector<int> with_duplicates;
std::set<int> unique;
for (int repeat = 0; repeat < 2; ++repeat) {
with_duplicates.push_back(5);
unique.insert(5);
}
std::cout << with_duplicates.size() << ' ' << unique.size() << '\n';
}
g++ -std=c++23 -Wall -Wextra duplicate.cpp -o index_duplicate
./index_duplicate
2 1
Exercises
- Skip a subdirectory in the folder scan and count only the files.
- Store the total frequency of each word next to its documents and print the ten most frequent.
- Build the index twice and check that the second build produces the same map.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does the inverted index map?
Answer
A word to the documents that contain it
The inversion is the point: the query starts from a word, not from a document.
-
Why is the document set a
std::set<int>?Answer
It removes a duplicate when a word occurs twice
The index needs each document once per word, and the set enforces that.
-
What does the positions map add?
Answer
Where in each document a word occurs
The phrase search needs the places, which the set of ids cannot express.
-
What does this program print?
#include <iostream> #include <map> #include <set> #include <string> int main() { std::map<std::string, std::set<int>> index; index["the"].insert(1); index["the"].insert(2); index["cat"].insert(1); index["dog"].insert(2); index["sat"].insert(1); index["sat"].insert(2); for (const auto& [word, ids] : index) { std::cout << word << ':'; bool first = true; for (int id : ids) { if (!first) std::cout << ','; first = false; std::cout << id; } std::cout << '\n'; } }Answer
cat:1 / dog:2 / sat:1,2 / the:1,2
The map orders the words, and each line lists the ids that contain it.
-
What does this program print for the word
the?#include <iostream> #include <map> #include <string> #include <vector> int main() { std::map<std::string, std::map<int, std::vector<int>>> index; index["the"][1].push_back(0); index["the"][2].push_back(0); for (const auto& [document, places] : index["the"]) { std::cout << document << ':'; for (int place : places) std::cout << place; std::cout << ' '; } }Answer
1:0 2:0
Both documents begin with the word, so each entry has position 0.
-
What does this program print?
#include <cctype> #include <filesystem> #include <fstream> #include <iostream> #include <map> #include <set> #include <string> namespace fs = std::filesystem; int main() { fs::create_directories("docs"); { std::ofstream{"docs/a.txt"} << "the cat sat"; } { std::ofstream{"docs/b.txt"} << "the dog sat"; } std::map<std::string, std::set<int>> index; int documents = 0; for (const auto& entry : fs::directory_iterator{"docs"}) { ++documents; std::ifstream in{entry.path()}; std::string word; while (in >> word) index[word].insert(documents); } std::cout << documents << " documents, " << index.size() << " words"; fs::remove_all("docs"); }Answer
2 documents, 4 words
Two files are scanned, and the distinct words are the, cat, sat and dog.
-
What does this program print?
#include <iostream> #include <set> #include <vector> int main() { std::vector<int> with_duplicates; std::set<int> unique; for (int repeat = 0; repeat < 2; ++repeat) { with_duplicates.push_back(5); unique.insert(5); } std::cout << with_duplicates.size() << ' ' << unique.size(); }Answer
2 1
The vector keeps both inserts and the set keeps one.
-
What does a directory iterator give you?
Answer
An entry per file and subdirectory
The entry has a path, and the program opens the files it wants.
-
Why is the ordered map used for the index at this size?
Answer
The output is stable without a sort
The order makes the printed and tested result predictable, which matters more than speed here.
-
What should the scan do with a file that fails to open?
Answer
Skip it and continue
One unreadable file should not hide the rest of the folder.
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