Capstone B: the inverted index
A reader of a book looks at the index at the back, finds the word and learns which pages hold it. An inverted index is the same thing in the other direction: the words are the keys and the pages are the ids of the documents, and the whole structure is a Map from a string to an array of numbers.
The lesson adds the three documents the project searches and the function that builds the map out of them. The index is the only thing a query needs, so the module also gives it a plain-data form: an object that a program can write to a file or send over the network without the documents themselves.
The folder holds the manifest, the lint config and the tokenizer of the previous lesson. This lesson adds src/index.js and rewrites the check program.
Three documents
The corpus is three short documents with an id, a title and a text. Three is enough to see every case the index has: a word in one document, a word in two, and a word that is not there at all. A real corpus arrives from a folder, which is the second exercise of the last lesson.
The id is a small integer and the title is the line a result prints. The text is what the tokenizer reads, and it is the only field the index touches.
The documents of src/index.js:
{ id: 1, title: 'The cat on the mat', text: 'The cat sat on the mat. The cat slept on the mat.' }
{ id: 2, title: 'The dog on the log', text: 'The dog sat on the log and slept.' }
{ id: 3, title: 'The cat and the dog', text: 'A cat and a dog met on the mat.' }
Document 1 holds cat twice, document 3 holds it once, and document 2 does not hold it at all. That difference is the whole of the ranking lesson, and it is already visible in the texts.
The build loop
The loop walks the documents in order and the words of each document in order. For every word it asks the map for the current array and either creates it with this document id or appends the id when the document is new. The includes check is what keeps a word that appears twice in one document from adding the document twice.
The index keeps the documents beside the terms rather than the texts alone, so a caller can print a title without a second structure. The returned object is the contract of the module: a list of documents and a map of terms.
The file src/index.js:
vi src/index.js
const { tokenize } = require('./tokenizer');
const DOCUMENTS = [
{ id: 1, title: 'The cat on the mat', text: 'The cat sat on the mat. The cat slept on the mat.' },
{ id: 2, title: 'The dog on the log', text: 'The dog sat on the log and slept.' },
{ id: 3, title: 'The cat and the dog', text: 'A cat and a dog met on the mat.' },
];
function buildIndex(documents) {
const terms = new Map();
for (const document of documents) {
for (const word of tokenize(document.text)) {
const ids = terms.get(word);
if (ids === undefined) {
terms.set(word, [document.id]);
} else if (!ids.includes(document.id)) {
ids.push(document.id);
}
}
}
return { documents, terms };
}
function postings(index, word) {
const ids = index.terms.get(word);
return ids === undefined ? [] : ids;
}
function toJSON(index) {
const terms = {};
for (const [word, ids] of index.terms) {
terms[word] = ids;
}
return { documents: index.documents.length, terms };
}
module.exports = { DOCUMENTS, buildIndex, postings, toJSON };
postings is the one-line reader that turns a missing term into an empty array, so no caller has to write ?? []; the lesson on Map covers the get, set and has calls the loop makes.
Reading the map
The map keeps the order in which the terms were first seen, which is a property of Map and not of the index: the words of document 1 come first, then the words that document 1 did not have. That order is neither alphabetical nor useful to a reader, and it is worth knowing that the loop of the check prints the terms in it.
A term in two documents is one entry with two ids, and a term in no document is not an entry at all. The second case is the one a query has to handle, and the empty array that postings returns is the answer that keeps the query simple.
The index as plain data
A Map does not survive JSON.stringify: the function writes {} for it. toJSON therefore copies the entries into an object, and the result is the index in the form that a file or an HTTP answer can hold.
The plain form loses the order of the three documents, which is why the document count is a number and the documents themselves stay beside the terms. A program that needs the titles sends them along; a program that only counts the hits needs the map alone.
The file check.js:
vi check.js
const { DOCUMENTS, buildIndex, postings, toJSON } = require('./src/index');
const index = buildIndex(DOCUMENTS);
console.log('documents: ' + index.documents.length);
console.log('terms: ' + index.terms.size);
for (const [word, ids] of index.terms) {
console.log(' ' + word + ' -> ' + ids.join(', '));
}
console.log('postings of mat: ' + postings(index, 'mat').join(', '));
console.log('postings of zebra: ' + postings(index, 'zebra').length);
console.log('the same word twice gives one entry: ' + postings(index, 'cat').join(', '));
const data = toJSON(index);
console.log('the data holds ' + Object.keys(data.terms).length + ' terms and ' + data.documents + ' documents');
console.log('one term as data: ' + JSON.stringify(data.terms.cat));
node check.js
documents: 3
terms: 7
cat -> 1, 3
sat -> 1, 2
mat -> 1, 3
slept -> 1, 2
dog -> 2, 3
log -> 2
met -> 3
postings of mat: 1, 3
postings of zebra: 0
the same word twice gives one entry: 1, 3
the data holds 7 terms and 3 documents
one term as data: [1,3]
Seven terms, and the seven lines are the map in its insertion order. sat is in documents 1 and 2, mat in 1 and 3, and met only in document 3. The word that appears twice in document 1 is still one id in its entry, and the word that is in no document is an empty array rather than an error.
The last two lines are the plain form: the same seven terms as an object, and one term shown as the array of ids that a JSON file would hold.
Exercises
- Build the index for an empty array of documents. What does the map hold, and which line of the check would show it?
- Remove the includes check and build the index again. Which entry changes, and why would a query still work?
- Store the count of each term beside the id instead of the id alone. Which function of the next lesson gets shorter?
- Print JSON.stringify(index.terms) without the conversion. What does the output hold, and why?
- Add a fourth document and list the entries that change. Which word is now in three documents, and which one is in four?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What is an inverted index?
Answer
A map from a term to the ids of the documents that hold it
The word is the key, which is what turns a word into the documents that contain it.
-
What does this program print?
const terms = new Map(); terms.set("cat", [1]); terms.set("dog", [2]); console.log(terms.size, terms.get("cat")[0]);Answer
2 1
The map has two keys, and the first id of the entry for cat is one.
-
Why does the build loop check
includesbefore it appends an id?Answer
A word that appears twice in one document is still one document for that term
The postings are the set of documents, and the order of the appearances does not matter.
-
What does this program print?
const terms = new Map([["a", [1, 2]]]); console.log(terms.get("b") === undefined, (terms.get("b") ?? []).length);Answer
true 0
A missing key answers undefined, and the empty array stands in for it.
-
What does
JSON.stringify(new Map([["a", [1]]]))write?Answer
{}
A Map has no own enumerable fields, which is why the module converts it first.
-
What does this program print?
const ids = [1, 3]; const again = [...ids]; console.log(ids === again, ids.join(",") === again.join(","));Answer
false true
The spread copies the array, so the two are different objects with the same values.
-
Which term is in document 3 but not in document 1 or 2?
Answer
met
Only the third document says that the cat and the dog met.
-
What does this program print?
const index = { terms: new Map([["cat", [1, 3]]]) }; console.log(index.terms.get("cat").length + index.terms.get("cat")[0]);Answer
3
The entry has two ids and the first one is 1, so two plus one is three.
-
Why does the index keep the documents beside the terms?
Answer
A result has to print a title, and the id alone does not show one
The ids are the link and the documents are the data a reader sees.
-
What does this program print?
const words = ["cat", "sat", "cat"]; const counts = new Map(); for (const word of words) { counts.set(word, (counts.get(word) ?? 0) + 1); } console.log(counts.get("cat"), counts.get("sat"));Answer
2 1
The first word is counted twice and the second one once.
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