Capstone 3: queries and ranking
A query over the index of lesson 148 is a set operation. AND is the intersection of the document sets, OR is the union, and a word that is not in the map contributes an empty set to both.
The two operations are in the standard library as std::set_intersection and std::set_union, and they need the sorted ranges that a std::set already provides. The ranking and the phrase search are loops on top of the same data.
The query layer is also where the user's words become the index's keys, which is why the tokenizer of lesson 147 runs on the query too. A query that is not folded would miss every capitalised word in the corpus.
The query parser of a real engine also handles parentheses and quoted phrases, which is a small parser of its own. The set operations underneath do not change.
AND is an intersection
std::set_intersection reads two sorted ranges and writes the ids that appear in both. The result for the AND cat is document 1, because document 2 has the first word and not the second.
The program builds a small index by hand and runs the query twice: once for a pair that matches and once for a word that is absent. The second answer is empty, which is the correct answer and not an error.
The result is a vector of ids, and the query layer turns it into lines for the user. Keeping the set operation separate from the printing is what lets the tests of lesson 146 style check the answer as data.
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
std::vector<int> query_and(const std::map<std::string, std::set<int>>& index,
const std::string& first, const std::string& second)
{
auto left = index.find(first);
auto right = index.find(second);
if (left == index.end() || right == index.end()) {
return {};
}
std::vector<int> result;
std::set_intersection(left->second.begin(), left->second.end(),
right->second.begin(), right->second.end(),
std::back_inserter(result));
return result;
}
int main()
{
std::map<std::string, std::set<int>> index{
{"the", {1, 2}},
{"cat", {1}},
{"dog", {2}},
};
std::vector<int> both = query_and(index, "the", "cat");
std::vector<int> missing = query_and(index, "the", "bird");
for (int id : both) {
std::cout << id << ' ';
}
std::cout << both.size() << ' ' << missing.size() << '\n';
}
g++ -std=c++23 -Wall -Wextra and.cpp -o query_and
./query_and
1 1 0
OR is a union
std::set_union writes every id that appears in either range, once. The query the OR dog returns both documents, and the order is the order of the sets, which is ascending.
The program unions two words and then a word with an absent one. The first answer is 1 2 and the second is 1,2 for the word that exists, because a union with nothing changes nothing.
The union of two empty sets is empty, and the query layer prints nothing rather than an error. The absence of a word is data, and the index does not distinguish it from a word with no documents.
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
std::vector<int> query_or(const std::map<std::string, std::set<int>>& index,
const std::string& first, const std::string& second)
{
std::set<int> left;
std::set<int> right;
if (auto found = index.find(first); found != index.end()) {
left = found->second;
}
if (auto found = index.find(second); found != index.end()) {
right = found->second;
}
std::vector<int> result;
std::set_union(left.begin(), left.end(), right.begin(), right.end(),
std::back_inserter(result));
return result;
}
int main()
{
std::map<std::string, std::set<int>> index{
{"the", {1, 2}},
{"cat", {1}},
{"dog", {2}},
};
std::vector<int> both = query_or(index, "the", "dog");
std::vector<int> one = query_or(index, "cat", "bird");
for (int id : both) {
std::cout << id << ' ';
}
std::cout << '|';
for (int id : one) {
std::cout << ' ' << id;
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra or.cpp -o query_or
./query_or
1 2 | 1
Ranking by occurrences
A ranking needs the number of times the word occurs in each document, which the set of ids does not keep. The program builds a map of counts and sorts the documents by the count, with the id as the tie-breaker.
The program indexes a word that appears twice in document 1 and once in document 2, and prints 1:2 2:1. The sort is by count descending, so the most relevant document comes first.
Counting occurrences is a simple ranking and it is the one a small engine can defend. A real one weights rare words higher, which is a change to the score and not to the loop.
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>
struct hit
{
int document;
int count;
};
int main()
{
std::map<std::string, std::map<int, int>> counts{
{"the", {{1, 2}, {2, 1}}},
};
std::vector<hit> hits;
for (const auto& [document, count] : counts["the"]) {
hits.push_back({document, count});
}
std::sort(hits.begin(), hits.end(), [](const hit& left, const hit& right) {
if (left.count != right.count) {
return left.count > right.count;
}
return left.document < right.document;
});
for (const hit& item : hits) {
std::cout << item.document << ':' << item.count << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra rank.cpp -o query_rank
./query_rank
1:2 2:1
A phrase needs positions
The phrase the cat matches a document only when a cat follows a the at the next position. The program looks up the positions of both words and checks the difference.
The index holds the at 0 and 3 and cat at 1 in document 1, so the phrase matches at 0. Document 2 has the and dog and no match, and the print is 1.
The check is a loop over one vector with a search in the other, which is fast because the vectors are short. That is why the index of the previous lesson kept positions at all.
#include <iostream>
#include <map>
#include <string>
#include <vector>
using places = std::map<std::string, std::map<int, std::vector<int>>>;
std::vector<int> query_phrase(const places& index, const std::string& first,
const std::string& second)
{
std::vector<int> result;
auto left = index.find(first);
auto right = index.find(second);
if (left == index.end() || right == index.end()) {
return result;
}
for (const auto& [document, positions] : left->second) {
auto other = right->second.find(document);
if (other == right->second.end()) {
continue;
}
for (int position : positions) {
for (int next : other->second) {
if (next == position + 1) {
result.push_back(document);
}
}
}
}
return result;
}
int main()
{
places index{
{"the", {{1, {0, 3}}}},
{"cat", {{1, {1}}, {2, {1}}}},
{"dog", {{2, {1}}}},
};
for (int id : query_phrase(index, "the", "cat")) {
std::cout << id << ' ';
}
std::cout << '\n';
}
g++ -std=c++23 -Wall -Wextra phrase.cpp -o query_phrase
./query_phrase
1
Exercises
- Add a NOT query that removes the documents of a word from the result of an AND.
- Rank by the total count of two words and print the scores.
- Extend the phrase search to three words and test it on a document with all three.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What operation is an AND query?
Answer
The intersection of the document sets
A document must contain both words, which is exactly the intersection.
-
What does a query for a word that is not in the index return?
Answer
An empty result
The missing word contributes an empty set, and the intersection with it is empty.
-
What does the ranking use in this lesson?
Answer
The number of occurrences in each document
The count of the word in the document is the score, and ties break on the id.
-
What does the AND program print?
Answer
1 1 0
The pair matches document 1, and the absent word gives an empty result.
-
What does the OR program print?
Answer
1 2 | 1
The union of the two words is both ids, and the union with an absent word keeps document 1.
-
What does this program print?
#include <algorithm> #include <iostream> #include <map> #include <string> #include <vector> struct hit { int document; int count; }; int main() { std::map<std::string, std::map<int, int>> counts{{"the", {{1, 2}, {2, 1}}}}; std::vector<hit> hits; for (const auto& [document, count] : counts["the"]) hits.push_back({document, count}); std::sort(hits.begin(), hits.end(), [](const hit& a, const hit& b) { return a.count != b.count ? a.count > b.count : a.document < b.document; }); for (const hit& item : hits) std::cout << item.document << ':' << item.count << ' '; }Answer
1:2 2:1
Document 1 has the word twice and comes before document 2 with one.
-
What does this program print for the phrase
the cat?#include <iostream> #include <map> #include <string> #include <vector> int main() { std::map<std::string, std::map<int, std::vector<int>>> index; index["the"][1] = {0, 3}; index["cat"][1] = {1}; index["cat"][2] = {1}; int matches = 0; for (const auto& [document, positions] : index["the"]) { if (index["cat"].count(document) == 0) continue; for (int position : positions) for (int next : index["cat"][document]) if (next == position + 1) ++matches; } std::cout << matches; }Answer
1
Only document 1 has cat at the position after the, so the phrase matches once.
-
Why does a phrase search need positions?
Answer
The document sets cannot tell whether the words are neighbours
Two words in the same document may be far apart, and only the positions show the order.
-
Which standard functions perform the two set operations?
Answer
std::set_intersectionandstd::set_unionBoth need sorted input ranges, which a std::set provides by construction.
-
Why is the set operation separated from the printing?
Answer
So the answer can be checked as data in a test
A function that returns ids is testable without a terminal.
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