How search engines are fast
Scanning every document for every query is O(total text). An inverted index flips it around: for each word, the list of documents containing it (its *posting list*). A query for several words is then the intersection of short sorted lists — the two-pointer technique from Algorithms.
Build, intersect, rank
function buildIndex(docs) {
const index = new Map(); // word -> Map(doc id -> how many times)
for (const doc of docs) {
for (const w of words(doc.text)) {
if (!index.has(w)) index.set(w, new Map());
const posting = index.get(w);
posting.set(doc.id, (posting.get(doc.id) ?? 0) + 1);
}
}
return index;
}
function intersect(a, b) {
const out = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
if (a[i] === b[j]) {
out.push(a[i]);
i++;
j++;
} else if (a[i] < b[j]) i++;
else j++;
}
return out;
}
function search(index, query) {
const terms = words(query);
if (!terms.length) return [];
let ids = null;
for (const t of terms) {
const posting = index.get(t);
if (!posting) return [];
const list = [...posting.keys()].sort((x, y) => x - y);
ids = ids ? intersect(ids, list) : list;
}
const score = (id) => terms.reduce((s, t) => s + index.get(t).get(id), 0);
return ids.sort((a, b) => score(b) - score(a) || a - b);
}