Capstone B: ranking the results

The index of the previous lesson answers one question: which documents hold this word. A search is a question with several words and an order, so the layer above the index turns a query into a set of terms, collects the documents that hold at least one of them, and gives each one a number.

The number is the count of the query terms in the document, which is the simplest relevance score that is not nonsense: a document that says cat twice is more about cats than one that says it once. The lesson writes the query module, runs four queries through it and shows the order, including the two documents that tie.

The folder holds the manifest, the lint config, the tokenizer and the index. This lesson adds src/query.js and rewrites the check program.

The candidates the index gives

A query with two words needs the documents that hold either of them, and the index answers that with one lookup per word. The ids go into a Set, which removes the document that holds both words without a check, and the set is the only place where the index is read.

A query whose words are all stop words gives an empty set before any document is looked at, and the function returns an empty array. The alternative, a scan of every document, would give the same answer for more work and would hide the rule that a query of nothing finds nothing.

The file src/query.js:

vi src/query.js

const { tokenize } = require('./tokenizer'); function candidates(index, words) { const ids = new Set(); for (const word of words) { for (const id of index.terms.get(word) || []) { ids.add(id); } } return ids; } function scoreOf(document, words) { let score = 0; for (const word of tokenize(document.text)) { if (words.has(word)) { score += 1; } } return score; } function search(index, text) { const words = new Set(tokenize(text)); if (words.size === 0) { return []; } const results = []; for (const id of candidates(index, words)) { const document = index.documents.find((entry) => entry.id === id); results.push({ id: document.id, title: document.title, score: scoreOf(document, words) }); } results.sort((left, right) => right.score - left.score || left.id - right.id); return results; } function format(results) { if (results.length === 0) { return 'no results'; } return results.map((result) => result.id + ' (' + result.score + ') ' + result.title).join('\n'); } module.exports = { format, search };

index.terms.get(word) || [] is the same guard that postings gives the check program. The module uses the map directly rather than through that function so that the two loops of the query are in one place; a caller who has an index can use either.

Counting the terms

The score counts the words of a document that are in the query and adds nothing else. It tokenizes the text again rather than reading a count from the index, which costs a second pass over three short documents and keeps the index as small as the previous lesson made it. The exercise at the end of this lesson is the version that stores the count and skips the pass.

A term that appears in the query twice counts once, because the query is turned into a Set before the loop: cat cat is the same query as cat. That is a decision, and it is the one a reader expects from a search box that trims and ignores case.

The find inside the scoring loop looks the document up by id. With three documents it is a scan of three entries; a thousand documents would want a map from id to document, which the exercise asks for.

The order of the results

The sort compares two results by their score and subtracts the second from the first, so the higher score comes first. When the two scores are equal the difference is zero, which the short-circuit || turns into the second comparison: the id, ascending. The comparator therefore answers with one expression and never with a boolean.

A tie broken by the id is what makes a search reproducible. Two documents with the same score have no reason to swap places between two runs, and a stable order means a test can compare an array of ids instead of a set of them.

format turns the results into the lines a reader sees, and it is separate from the search because the HTTP answer of project C wants the objects and not the text. The lesson on sorting covers the comparator and the stable sort.

Four queries

The check program runs four queries and one control. The first has two words and a clear winner, the second has one word in two documents and therefore a tie, the third has two words and a tie at the top, and the fourth has a word that no document holds. The control is a query of stop words only.

The file check.js:

vi check.js

const { DOCUMENTS, buildIndex } = require('./src/index'); const { format, search } = require('./src/query'); const index = buildIndex(DOCUMENTS); for (const text of ['cat mat', 'slept', 'cat and dog', 'the fox']) { console.log('query: ' + text); console.log(format(search(index, text))); } console.log('a query of stop words only: ' + search(index, 'the and a').length + ' result(s)');

node check.js

query: cat mat
1 (4) The cat on the mat
3 (2) The cat and the dog
query: slept
1 (1) The cat on the mat
2 (1) The dog on the log
query: cat and dog
1 (2) The cat on the mat
3 (2) The cat and the dog
2 (1) The dog on the log
query: the fox
no results
a query of stop words only: 0 result(s)

The first query gives document 1 four points, two for cat and two for mat, and document 3 two points, one for each word. The second query is the tie: both documents hold slept once, and document 1 comes first because its id is smaller.

The third query is the interesting one. Documents 1 and 3 both score two and the tie is broken by the id, while document 2 scores one and comes last. The reader who typed two words gets the document that holds both of them before the one that holds one, which is the whole of the ranking this project needs.

Exercises

  1. Search for cat cat mat and compare the result with cat mat. Which line of the module makes the two the same?
  2. Store the count of each term in the postings and skip the second tokenize. Which two functions change, and which one gets shorter?
  3. Build a Map from id to document once and use it in the scoring loop. Which line disappears from the loop?
  4. Sort by the title instead of the id when the scores are equal. Which order do the two tied documents get, and is that better than the id?
  5. Give a word in the title two points and a word in the text one. Which function changes, and what happens to the first query?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is the score of a document in this project?

    Answer

    The number of query terms it holds, counted once per appearance

    A term frequency is the simplest relevance score, and it ranks a document that repeats the word.

  2. What does this program print? const results = [{ id: 1, score: 2 }, { id: 2, score: 5 }]; results.sort((left, right) => right.score - left.score); console.log(results.map((result) => result.id).join(","));

    Answer

    2,1

    The comparator subtracts the left score from the right one, so the higher score comes first.

  3. Why is a tie broken by the id?

    Answer

    So two runs of the same query give the same order

    A stable order lets a test compare an array of ids and a reader see a reproducible answer.

  4. What does this program print? const compare = (left, right) => right.score - left.score || left.id - right.id; console.log(compare({ id: 2, score: 1 }, { id: 1, score: 1 }));

    Answer

    1

    The scores cancel and the ids decide: two minus one is one, so the second result comes first.

  5. Which documents does a query of two words look at?

    Answer

    The ones that hold at least one of the two

    The candidates come from the postings of each term, so a document with one of them is a candidate.

  6. What does this program print? const ids = new Set([1, 3]); ids.add(3); ids.add(2); console.log(ids.size, [...ids].join(","));

    Answer

    3 1,3,2

    The set keeps one of each id and the insertion order of the first appearance.

  7. What does the score of a query of stop words alone do?

    Answer

    It returns no results at all

    The terms of the query are empty, and an empty query finds nothing.

  8. What does this program print? const text = "the cat and the cat"; const words = new Set(text.split(" ").filter((word) => word !== "the" && word !== "and")); console.log(words.size);

    Answer

    1

    The two cat words are one entry of the set.

  9. Why is the formatter separate from the search?

    Answer

    The HTTP answer needs the objects and the terminal needs the text

    One function returns data and another turns it into lines, so each caller picks what it needs.

  10. What does this program print? const hits = [{ id: 3, score: 2 }, { id: 1, score: 2 }, { id: 2, score: 1 }]; hits.sort((left, right) => right.score - left.score || left.id - right.id); console.log(hits.map((hit) => hit.id).join(" "));

    Answer

    1 3 2

    The two documents with two points are ordered by id and the one with a single point is last.

The programs on this page were run with Node.js 24.22.1 and linted with ESLint 10.14.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev