Inverted Index

The previous lesson used the inverted index as a black box: a term went in, document ids came out. This lesson opens the box. The structure has two parts. The dictionary holds each distinct term in the corpus exactly once and places a pointer next to each term to that term’s list. The posting list is the record of the documents the term appears in: each entry reports one document.

In this course, a posting is an index record that reports a term’s occurrence in a particular document. The same word names a message published in another curriculum; that usage is unrelated to this one. A posting entry carries at minimum the document id, and may optionally carry how many times the term occurs in that document (term frequency) and where it occurs (position). All three components carry a cost, and this lesson counts that cost.

Dictionary, Postings, and Position

A sorted index is built on the entire value and goes from a record to a value; the inverted index does the opposite, going from a term to a set of documents, which is why the same document appears in dozens of posting lists at once. That is the difference in one sentence, and it is also what determines index size: the index’s size does not scale with the number of documents, it scales with the number of distinct terms per document.

IA1: the corpus is the same corpus as the previous lesson — 600 book records, seed 20250317. IA2: the byte accounting uses the following constants — a dictionary entry costs the term’s UTF-8 bytes plus 8 bytes (document frequency and a list pointer), a posting entry costs 4 bytes for the document id, 4 more bytes if term frequency is stored, and 4 bytes per position. IA3: the indexed text is the union of the title and summary fields; the previous lesson indexed only the summary field, so the term count differs there.

// search/catalog.mjs — corpus shared by three topics: generated from a library catalog,
// 600 book records, seed 20250317. Fields: title, summary, subjects, author, year, language, shelf.
export const SEED = 20250317, DOC_COUNT = 600;
let state = SEED;
const random = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;
const pick = (d) => d[Math.floor(random() * d.length)];
const pickSkewed = (d) => d[Math.floor(random() ** 2 * d.length)];   // frequency is skewed in real text
const splitBar = (s) => s.split("|");

// stem forms: base, genitive, plural, dative, ablative, locative
export const STEMS = splitBar("deniz denizin denizler denize denizden denizde|kitap kitabın kitaplar kitaba \
kitaptan kitapta|çocuk çocuğun çocuklar çocuğa çocuktan çocukta|şehir şehrin şehirler şehre \
şehirden şehirde|yol yolun yollar yola yoldan yolda|ada adanın adalar adaya adadan adada|bahçe \
bahçenin bahçeler bahçeye bahçeden bahçede|mektup mektubun mektuplar mektuba mektuptan mektupta|\
gemi geminin gemiler gemiye gemiden gemide|köprü köprünün köprüler köprüye köprüden köprüde|\
okul okulun okullar okula okuldan okulda|kuş kuşun kuşlar kuşa kuştan kuşta").map((s) => s.split(" "));
const PATTERNS = splitBar("0 {} ve gündelik hayat üzerine notlar sunar|0 {} bu derlemenin ana izleğidir|\
1 {} tarihine geniş yer ayırır|1 {} çevresinde gelişen olayları anlatır|2 {} üzerine derlenmiş \
yazılar içerir|2 {} hakkında kısa öyküler toplar|3 {} açılan bir yolculuğu izler|4 {} toplanmış \
belgeleri sıralar|5 {} tutulan günlüklerden seçmeler verir|5 {} geçen bölümleri İstanbul'un eski \
mahallelerine bağlar").map((s) => [Number(s[0]), s.slice(2)]);
const PATTERNS2 = splitBar("{Y} kütüphanesinde tutulan {N} üzerine kuruludur|{N} arasından seçilmiş \
örnekler taşır|{Y} ve çevresindeki {N} listesini verir|{Y} basımı bir {N} derlemesine dayanır");
const EXTRA = splitBar("denizci gelenekleri üzerine bir ek bölüm bulunur|Karadeniz kıyısındaki kasabaları \
anlatır|çocukluk anılarına yer verir|kitapçı raflarındaki dağılımı tartışır|yolculuk notlarıyla \
kapanır|adacıklardaki kuş türlerini sayar");
const PLACES = splitBar("Ankara|İzmir|Trabzon|Kars|Bursa|Edirne|Sinop|Antakya");
const OBJECTS = splitBar("harita|fotoğraf|söyleşi|günlük|arşiv belgesi|liman kaydı|kasaba adı|el yazması|gazete kupürü|şarkı sözü");
const PREFIXES = splitBar("Uzak|Kayıp|Sessiz|Eski|Kısa|Büyük|Küçük|Unutulmuş|Beyaz|Yedi");
const SUFFIXES = splitBar("Günleri|Öyküleri|Üzerine Notlar|Anıları|Sözlüğü|Rehberi|Yılları|Defteri");
const SUBJECTS = splitBar("çocuk edebiyatı|roman|kısa öykü|şiir|deniz tarihi|coğrafya|biyografi|gezi yazısı|halk bilimi|mimarlık|müzik|felsefe");
const FIRST_NAMES = splitBar("Ahmet|Ayşe|Zeynep|Cemal|Nuran|Selim|Elif|Kerem|Hatice|Bedri|Sevgi|Nazlı");
const LAST_NAMES = splitBar("Yılmaz|Kaya|Demir|Şahin|Çelik|Aydın|Doğan|Arslan|Koç|Ertem");
const LANGUAGES = splitBar("Türkçe|Türkçe|Türkçe|İngilizce|Almanca|Fransızca");

const capitalize = (s) => s[0].toLocaleUpperCase("tr") + s.slice(1);
function generateSummary() {
  const parts = [];
  for (let i = 0; i < 3; i += 1) { const [d, k] = pickSkewed(PATTERNS); parts.push(k.replace("{}", pickSkewed(STEMS)[d])); }
  parts.push(pick(PATTERNS2).replace("{Y}", pick(PLACES)).replace("{N}", pick(OBJECTS)));
  if (random() < 0.45) parts.push(pick(EXTRA));
  return capitalize(parts.join(", ")) + ".";
}
function generateTitle() {
  const k = pickSkewed(STEMS), o = pick(PREFIXES), s = pick(SUFFIXES), t = random();
  if (t < 0.25) return `${o} ${capitalize(k[2])}`;
  if (t < 0.5) return `${capitalize(k[0])} ${s}`;
  if (t < 0.75) return `${o} ${capitalize(k[0])} ${s}`;
  return `${capitalize(k[1])} ${s}`;
}
export const corpus = [];
for (let i = 1; i <= DOC_COUNT; i += 1) {
  const subjects = [pick(SUBJECTS)];
  if (random() < 0.55) subjects.push(pick(SUBJECTS));
  if (random() < 0.2) subjects.push(pick(SUBJECTS));
  corpus.push({
    id: i, title: generateTitle(), summary: generateSummary(), subjects: [...new Set(subjects)], author: `${pick(FIRST_NAMES)} ${pick(LAST_NAMES)}`,
    year: 1968 + Math.floor(random() * 57), language: pick(LANGUAGES),
    shelf: `${pick(splitBar("TR|EN|DE|FR"))}-${800 + Math.floor(random() * 99)}.${Math.floor(random() * 9)}`,
  });
}

// search/index.mjs — a hand-written inverted index: dictionary, posting list (document id, term
// frequency, position) and byte accounting. The analyzer is supplied from outside; later lessons use it.
export const SIMPLE = (s) => s.toLocaleLowerCase("tr").split(/[^\p{L}\p{N}]+/u).filter(Boolean);
export const DOC_ID_BYTES = 4, FREQ_BYTES = 4, POSITION_BYTES = 4, DICTIONARY_OVERHEAD = 8;   // IA2: byte constants

export class InvertedIndex {
  dictionary = new Map();                // term -> posting list
  documentCount = 0;
  constructor({ analyze = SIMPLE, frequency = true, position = true } = {}) { Object.assign(this, { analyze, frequency, position }); }

  add(id, text) {
    const local = new Map();
    this.analyze(text).forEach((t, i) => (local.get(t) ?? local.set(t, []).get(t)).push(i));
    for (const [t, k] of local) {
      if (!this.dictionary.has(t)) this.dictionary.set(t, []);
      this.dictionary.get(t).push({ id, tf: k.length, position: this.position ? k : [] });
    }
    this.documentCount += 1;
  }

  postings(t) { return this.dictionary.get(t) ?? []; }

  search(...terms) {                     // intersection: lists are id-sorted, so one pass suffices
    const l = terms.map((t) => this.postings(t)), p = l.map(() => 0), results = [];
    let comparisons = 0;
    while (l.every((x, i) => p[i] < x.length)) {
      const maxId = Math.max(...l.map((x, i) => x[p[i]].id));
      let matched = true;
      for (let i = 0; i < l.length; i += 1) {
        while (p[i] < l[i].length && l[i][p[i]].id < maxId) { p[i] += 1; comparisons += 1; }
        comparisons += 1;
        if (p[i] >= l[i].length || l[i][p[i]].id !== maxId) { matched = false; break; }
      }
      if (matched) { results.push(maxId); p.forEach((_, i) => (p[i] += 1)); }
    }
    return { results, postings: l.reduce((t, x) => t + x.length, 0), comparisons };
  }

  bytes() {                              // dictionary + postings + positions
    let s = 0, g = 0, k = 0, postings = 0, positions = 0;
    for (const [t, list] of this.dictionary) {
      s += Buffer.byteLength(t) + DICTIONARY_OVERHEAD;
      for (const gr of list) {
        g += DOC_ID_BYTES + (this.frequency ? FREQ_BYTES : 0);
        k += gr.position.length * POSITION_BYTES;
        postings += 1; positions += gr.position.length;
      }
    }
    return { terms: this.dictionary.size, postings, positions, dictionary: s, postingBytes: g, positionBytes: k, total: s + g + k };
  }
}

// search/index-measurement.mjs — the same corpus is built in three index formats: id only,
// id+frequency, id+frequency+position. Term, posting entry, byte, scanned entry and comparisons are counted.
import { corpus, DOC_COUNT, SEED } from "./catalog.mjs";
import { InvertedIndex } from "./index.mjs";

const text = (b) => `${b.title} ${b.summary}`;             // IA3: indexed fields
const source = corpus.reduce((t, b) => t + Buffer.byteLength(text(b)), 0);
const build = (settings) => { const d = new InvertedIndex(settings); for (const b of corpus) d.add(b.id, text(b)); return d; };
const formats = [["id only", { frequency: false, position: false }],
  ["id + freq", { frequency: true, position: false }], ["id + freq + position", {}]];

console.log(`seed ${SEED}; corpus ${DOC_COUNT} docs, indexed text ${source} bytes`);
console.log(`${"index format".padEnd(24)}${"terms".padStart(7)}${"postings".padStart(9)}${"positions".padStart(10)}` +
  `${"dictionary".padStart(11)}${"posting bytes".padStart(15)}${"position bytes".padStart(15)}${"total".padStart(9)}${"share of text".padStart(14)}`);
let full;
for (const [label, settings] of formats) {
  const d = build(settings), b = d.bytes();
  full = d;
  console.log(label.padEnd(24) + String(b.terms).padStart(7) + String(b.postings).padStart(9) + String(b.positions).padStart(10) +
    String(b.dictionary).padStart(11) + String(b.postingBytes).padStart(15) + String(b.positionBytes).padStart(15) +
    String(b.total).padStart(9) + `%${(b.total * 100 / source).toFixed(1)}`.padStart(14));
}

const first = full.postings("deniz").slice(0, 3).map((g) => `(#${g.id}, tf ${g.tf}, position ${g.position.join("-")})`);
console.log(`\n"deniz" posting list ${full.postings("deniz").length} entries; first three: ${first.join(" ")}`);
const tfDistribution = new Map();
for (const g of full.postings("deniz")) tfDistribution.set(g.tf, (tfDistribution.get(g.tf) ?? 0) + 1);
console.log(`term frequency distribution: ${[...tfDistribution].sort().map(([t, n]) => `tf ${t} -> ${n} docs`).join(", ")}`);

// comparison with an unsorted list: for each entry, a linear search through the other list
const unsorted = (...t) => {
  const lists = t.map((x) => full.postings(x)), shortest = lists.reduce((a, x) => (x.length < a.length ? x : a));
  let comparisons = 0;
  const matches = shortest.filter((g) => lists.every((x) => { for (const y of x) { comparisons += 1; if (y.id === g.id) return true; } return false; }));
  return { n: matches.length, comparisons };
};
console.log(`\n${"query".padEnd(20)}${"entries scanned".padStart(16)}${"id-sorted".padStart(12)}` +
  `${"unsorted".padStart(10)}${"docs returned".padStart(15)}${"first three ids".padStart(18)}`);
for (const terms of [["deniz"], ["çocuk"], ["deniz", "çocuk"], ["deniz", "çocuk", "kitap"]]) {
  const result = full.search(...terms), unsortedComparisons = terms.length > 1 ? String(unsorted(...terms).comparisons) : "-";
  console.log(terms.join("+").padEnd(20) + String(result.postings).padStart(16) + String(result.comparisons).padStart(12) +
    unsortedComparisons.padStart(10) + String(result.results.length).padStart(15) + result.results.slice(0, 3).join(",").padStart(18));
}

// what position information buys: appearing in the same document versus appearing side by side
const [termA, termB] = ["deniz", "günleri"];
const secondPositions = new Map(full.postings(termB).map((g) => [g.id, g.position]));
const adjacent = full.postings(termA).filter((g) => secondPositions.has(g.id) &&
  g.position.some((x) => secondPositions.get(g.id).some((y) => y - x === 1))).map((g) => g.id);
console.log(`\n"${termA} ${termB}": same document ${full.search(termA, termB).results.length}, adjacent ${adjacent.length} docs ` +
  `(${adjacent.slice(0, 3).map((i) => `#${i} ${corpus[i - 1].title}`).join(", ")})`);

seed 20250317; corpus 600 docs, indexed text 135824 bytes
index format              terms postings positions dictionary  posting bytes position bytes    total share of text
id only                     185    14609         0       2850          58436              0    61286         %45.1
id + freq                   185    14609         0       2850         116872              0   119722         %88.1
id + freq + position        185    14609     16565       2850         116872          66260   185982        %136.9

"deniz" posting list 261 entries; first three: (#3, tf 1, position 0) (#4, tf 1, position 14) (#7, tf 1, position 14)
term frequency distribution: tf 1 -> 206 docs, tf 2 -> 52 docs, tf 3 -> 3 docs

query                entries scanned   id-sorted  unsorted  docs returned   first three ids
deniz                            261         261         -            261             3,4,7
çocuk                             84          84         -             84             5,6,8
deniz+çocuk                      345         470     19622             25           8,67,77
deniz+çocuk+kitap                452         630     22135              3       158,309,491

"deniz günleri": same document 23, adjacent 10 docs (#3 Deniz Günleri, #123 Büyük Deniz Günleri, #154 Beyaz Deniz Günleri)

Three Formats, Three Prices

The first table indexes the same 600 documents three times, and the only thing that changes is what the posting entry carries. The dictionary is identical across all three: 185 terms, 2,850 bytes. The index’s weight is not in the dictionary, it is in the 14,609 posting entries. When only the document id is stored, the index is 61,286 bytes, about 45.1 percent of the source text. Adding term frequency exactly doubles the posting section, and the index reaches 119,722 bytes, 88.1 percent of the text. Adding position brings it to 185,982 bytes — larger than the text itself.

This last line is the lesson’s most concrete result: an inverted index that keeps position can take up more space than the text it indexes. The reason shows up in the second and third columns — against 14,609 posting entries there are 16,565 position records, because a term can occur more than once in the same document. The frequency distribution of the term deniz counts this directly: once in 206 documents, twice in 52 documents, three times in 3 documents.

Order Is a Decision

Posting lists are kept in document id order, and this is not a preference, it is a decision that determines how the intersection works. The deniz+çocuk query reads two lists of 261 and 84 entries, 345 entries total. Because both lists are sorted, the intersection runs in a single pass, and 470 comparisons are enough. If the same intersection ran on unsorted lists, each entry of the shorter list would require a search from the start of the longer list: 19,622 comparisons, forty times more. For the three-term query, the ratio is 630 against 22,135.

The order’s second consequence shows up in the returned set. deniz alone returns 261 documents, çocuk returns 84; their intersection drops to 25 documents, and to 3 once a third term is added. Every condition narrows the set, and the cost of narrowing is a growing entry count: from 345 to 452. The returned documents arrive in the order 8, 67, 77; this order is again document id, that is, the order documents entered the index. Which document is more relevant is still not asked.

What Position Buys

Position information is the index’s most expensive component — 66,260 bytes on its own, 35.6 percent of the index. In return it buys exactly one thing: knowing whether two terms sit next to each other in a document. The last line counts this. The terms deniz and günleri occur together in 23 documents; only 10 of these documents have the two terms adjacent, and the titles of those 10 documents genuinely follow the pattern Deniz Günleri. An index that does not keep position cannot tell the two sets apart and returns all 23 documents.

The decision is put this way: 66,260 bytes buys a 13-document narrowing. Whether that narrowing is worth it in a catalog search depends on the type of question — for a reader searching for a book by two words without knowing its exact title, the adjacency distinction gives the correct result directly. The query form that uses this distinction is built in the second topic; this lesson only shows that the data sits in the index and what it holds.

Summary

• The inverted index has two parts: the dictionary (185 terms, 2,850 bytes) and the posting lists (14,609 entries). The weight sits on the posting side; the dictionary is about 1.5 percent of the index.
• What a posting entry carries sets the price: id only costs 61,286 bytes (45.1 percent of the text), adding term frequency costs 119,722 bytes (88.1 percent), adding position costs 185,982 bytes (136.9 percent) — the index becomes larger than the source text.
• 16,565 position records fall against 14,609 posting entries; the term deniz occurs once in 206 documents, twice in 52, three times in 3.
• Keeping posting lists in document id order reduces the intersection to a single pass: deniz+çocuk finishes in 470 comparisons, against 19,622 comparisons on an unsorted list.
• Position information costs 66,260 bytes and buys the ability to narrow the set from 23 documents to 10 in the deniz günleri query.

Next Step

This lesson’s index split text into words with a single rule: split on every character that is not a letter or digit, then lowercase using Turkish rules. That rule itself was never questioned. Yet denizler and deniz become two separate terms because of this rule, and the 43-document loss from the first lesson comes from exactly this. The next lesson indexes the same corpus with three separate analyzer chains — raw, lowercasing, and stemming with a stop-word filter — and runs the same query on all three: the returned set, order, and index size are measured side by side across the three configurations.