Analyzer Chain

The previous lesson’s index split text into words with a single rule, and that rule was never questioned. Yet denizler and deniz being two separate terms is not a law of nature, it is the result of that rule. The sequence of rules that turns text into terms is called the analyzer chain, and it has three steps: tokenization splits the text into pieces, normalization collapses the pieces to a single spelling, and filters change or drop the remaining tokens.

It is essential that this chain runs in two places at once: when a document is indexed and when a query is evaluated. If the two use different rules, the query searches for a term that does not exist in the index. The lesson builds this chain in three separate configurations and runs the same questions on all three.

Links in the Chain

Here, tokenization means splitting text into search units. In M06/K01, a token names the symbol entering a grammar parser, where the splitting criterion is a grammar rule; here the criterion is the search contract. Normalization is likewise a separate thing: M17/K01’s relational normalization removes data repetition by splitting it across tables, while normalization here collapses different spellings of the same word into a single term.

Three configurations are compared. The raw chain splits only on whitespace; punctuation stays stuck to the token, and case is kept as written. The lowercase chain splits on every character that is not a letter or digit and folds case using the Turkish locale — this is the chain used in the previous two lessons. The stem + stop chain adds two filters on top of this: terms occurring in more than 60 percent of documents are dropped, and the longest inflectional suffix is stripped once from the remaining tokens.

IA1: the corpus is unchanged — 600 records, seed 20250317, indexed fields title and summary. IA2: the byte constants are the same constants as the previous lesson and are identical across all three chains. IA3: the stop word list is not written by hand, it is measured: the document-frequency threshold is 60 percent. IA4: the stemmer strips the longest suffix once and never leaves a stem shorter than three letters; it does not know consonant softening or vowel drop.

// 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/analyzer.mjs — the same corpus is indexed with three analyzer chains: raw, lowercase,
// stemming + stop word. Index size, returned set, first five results, and Turkish measures.
import { corpus, DOC_COUNT, SEED, STEMS as STEM_FORMS } from "./catalog.mjs";
import { InvertedIndex } from "./index.mjs";

const text = (b) => `${b.title} ${b.summary}`;
const SPLIT = (s) => s.split(/[^\p{L}\p{N}]+/u).filter(Boolean);
const RAW = (s) => s.split(/\s+/).filter(Boolean);             // no splitting, no transformation
const LOWERCASE = (s) => SPLIT(s.toLocaleLowerCase("tr"));
const SUFFIXES = ["ları", "leri", "lerin", "ların", "nin", "nın", "nun", "nün", "dan", "den", "tan",
  "ten", "ler", "lar", "ya", "ye", "da", "de", "ta", "te", "in", "ın", "un", "ün", "a", "e"]
  .sort((x, y) => y.length - x.length);
const stem = (t) => {                                          // strips the longest suffix once, stem >= 3
  for (const e of SUFFIXES) if (t.length - e.length >= 3 && t.endsWith(e)) return t.slice(0, -e.length);
  return t;
};
// stop word list is chosen by measurement: a term occurring in more than 60% of documents
const pre = new InvertedIndex({ analyze: LOWERCASE, position: false });
for (const b of corpus) pre.add(b.id, text(b));
const STOP_WORDS = new Set([...pre.dictionary].filter(([, l]) => l.length > DOC_COUNT * 0.6).map(([t]) => t));
const STEMMED = (s) => LOWERCASE(s).filter((t) => !STOP_WORDS.has(t)).map(stem);

const chain = [["raw", RAW], ["lowercase", LOWERCASE], ["stem + stop", STEMMED]];
const index = new Map(chain.map(([label, analyze]) => {
  const d = new InvertedIndex({ analyze });
  for (const b of corpus) d.add(b.id, text(b));
  return [label, d];
}));
const source = corpus.reduce((t, b) => t + Buffer.byteLength(text(b)), 0);

console.log(`seed ${SEED}; corpus ${DOC_COUNT} docs, ${source} bytes of text`);
console.log(`stop words (df > 60%): ${[...STOP_WORDS].join(", ")}`);
console.log(`\n${"analyzer".padEnd(14)}${"terms".padStart(7)}${"postings".padStart(9)}${"positions".padStart(10)}` +
  `${"index bytes".padStart(12)}${"share of text".padStart(14)}`);
for (const [label, d] of index) {
  const b = d.bytes();
  console.log(label.padEnd(14) + String(b.terms).padStart(7) + String(b.postings).padStart(9) +
    String(b.positions).padStart(10) + String(b.total).padStart(12) + `%${(b.total * 100 / source).toFixed(1)}`.padStart(14));
}

console.log(`\n${"query".padEnd(11)}${"analyzer".padEnd(13)}${"query term".padEnd(15)}` +
  `${"docs returned".padStart(14)}${"first five ids".padStart(22)}${"changed in first five".padStart(23)}`);
for (const query of ["Denizler", "kitap", "İstanbul"]) {
  const row = chain.map(([label, analyze]) => {
    const terms = analyze(query), r = terms.length ? index.get(label).search(...terms) : { results: [] };
    return [label, terms.join("+") || "-", r.results];
  });
  const baseline = row.find(([label]) => label === "lowercase")[2].slice(0, 5);
  for (const [label, terms, results] of row) {
    const five = results.slice(0, 5);
    const changed = label === "lowercase" ? "-"
      : String(baseline.filter((x, i) => five[i] !== x).length + Math.max(0, five.length - baseline.length));
    console.log(query.padEnd(11) + label.padEnd(13) + terms.padEnd(15) + String(results.length).padStart(14) +
      (five.join(",") || "-").padStart(22) + changed.padStart(23));
  }
}

// --- Turkish measure 1: case folding (Turkish locale versus a general rule) ---
const general = new InvertedIndex({ analyze: (s) => SPLIT(s.toLowerCase()), position: false });
for (const b of corpus) general.add(b.id, text(b));
const diverging = [...general.dictionary.keys()].filter((t) => !pre.dictionary.has(t));
console.log(`\ncase folding: Turkish rule ${pre.dictionary.size} terms, general rule ${general.dictionary.size} ` +
  `terms; diverging terms ${JSON.stringify(diverging)}`);
console.log(`  "istanbul" query: Turkish rule ${pre.search("istanbul").results.length} docs, ` +
  `general rule ${general.search("istanbul").results.length} docs`);
console.log(`  apostrophe: "İstanbul'un" -> ${JSON.stringify(LOWERCASE("İstanbul'un"))}`);

// --- Turkish measure 2: the stemmer over 12 stems x 6 forms ---
let single = 0; const split = [];
for (const row of STEM_FORMS) {
  const k = new Set(row.map(stem));
  if (k.size === 1) single += 1; else split.push(`${row[0]}: ${[...k].join("/")}`);
}
console.log(`\nstemming: ${STEM_FORMS.length} stems x 6 forms; ${single} stems collapsed to one term, ` +
  `${split.length} stems split -> ${split.join(", ")}`);
const stemGroups = new Map();
for (const t of pre.dictionary.keys()) (stemGroups.get(stem(t)) ?? stemGroups.set(stem(t), []).get(stem(t))).push(t);
const merged = [...stemGroups].filter(([, l]) => l.length > 1);
console.log(`${pre.dictionary.size} terms collapse to ${stemGroups.size} stems; ${merged.length} stems collected more than one term`);
console.log(`example: ${merged.slice(0, 3).map(([k, l]) => `${k} <- ${l.join(", ")}`).join(" | ")}`);

seed 20250317; corpus 600 docs, 135824 bytes of text
stop words (df > 60%): ve, gündelik, hayat, üzerine, notlar, sunar

analyzer        terms postings positions index bytes share of text
raw               261    14727     16489      187780        %138.3
lowercase         185    14609     16565      185982        %136.9
stem + stop       122    11722     12627      146080        %107.6

query      analyzer     query term      docs returned        first five ids  changed in first five
Denizler   raw          Denizler                   80        15,16,18,20,22                      5
Denizler   lowercase    denizler                  122         3,15,16,18,20                      -
Denizler   stem + stop  deniz                     463             2,3,4,7,8                      5
kitap      raw          kitap                      54        13,44,53,80,92                      5
kitap      lowercase    kitap                     107         7,10,13,28,30                      -
kitap      stem + stop  kitap                     178            2,5,6,7,10                      5
İstanbul   raw          İstanbul                    0                     -                      5
İstanbul   lowercase    istanbul                   73         2,21,30,32,35                      -
İstanbul   stem + stop  istanbul                   73         2,21,30,32,35                      0

case folding: Turkish rule 185 terms, general rule 186 terms; diverging terms ["i","stanbul","zmir"]
  "istanbul" query: Turkish rule 73 docs, general rule 0 docs
  apostrophe: "İstanbul'un" -> ["istanbul","un"]

stemming: 12 stems x 6 forms; 7 stems collapsed to one term, 5 stems split -> kitap: kitap/kitab, çocuk: çocuk/çocuğ, şehir: şehir/şehr, bahçe: bahç/bahçe, mektup: mektup/mektub
185 terms collapse to 128 stems; 18 stems collected more than one term
example: gemi <- gemi, gemide, gemiye, gemiler, geminin, gemiden | öykü <- öyküleri, öyküler | mektup <- mektup, mektuptan, mektupta, mektuplar

Three Chains, Three Sets

The first table shows what the chain does to the index. The raw chain produces the most terms: 261. The reason is not richness, it is the same word being counted multiple times through punctuation and case. The lowercase chain brings the term count down to 185; the stem and stop filters bring it to 122. Posting entries drop from 14,727 to 11,722, and the index from 187,780 bytes to 146,080 bytes — the filters erase about 22 percent of the index.

The second table shows the decision that actually matters. The Denizler query returns 80 documents on the raw chain, 122 on the lowercase chain, 463 on the stem chain. Same corpus, same question, a factor of five and a half. The raw chain only finds the token Denizler, written exactly with a capital letter; the lowercase chain finds the form denizler regardless of case; the stem chain reduces the query to the stem deniz and so brings back every document containing any of the six inflected forms. This was the source of the 43-document loss counted in the first lesson; the stem chain closes the part of that loss that sits on the deniz stem, and in return the set quadruples.

The order column counts this result separately. Taking the lowercase chain as the baseline, all five of the first five ids change in both the raw and the stem chain. Order here is not a relevance ranking, it is the posting list’s id layout; even so, the first results a user sees change completely when the chain changes. The İstanbul query is the extreme case: the raw chain returns zero documents, because the token in the text takes the form İstanbul'un, a single piece together with the apostrophe.

The Measure of Turkish

The third section counts three concrete difficulties of Turkish. Case folding: the same text produces 185 terms under the Turkish locale and 186 under the general rule, and the diverging terms are ["i", "stanbul", "zmir"]. The general rule converts the letter İ into i combined with a dot above, and the splitter does not count that dot as a letter, so the word İstanbul splits into i and stanbul. The result is measured: the istanbul query returns 73 documents under the Turkish rule and 0 documents under the general rule.

Apostrophe: the token İstanbul'un splits in two as ["istanbul", "un"]. The split rescues the query, but it also produces a meaningless un term.

Stemming: the measure is taken over 6 inflected forms each of 12 stems. Seven stems collapse to a single term, five stems split: kitap/kitab, çocuk/çocuğ, şehir/şehr, bahç/bahçe, mektup/mektub. The first three come from consonant softening and vowel drop, the fourth from a letter belonging to the stem itself being mistaken for a suffix and dropped. There is a cost in the opposite direction too: as 185 terms collapse to 128 stems, 18 stems collect more than one term, and not all of these are correct merges. This lesson does not solve Turkish stemming, it counts where the rule holds and where it does not; when the query is kitap, documents containing kitabın still stay outside the set.

The stop word filter was also built by measurement: six terms were dropped because they occur in more than 60 percent of documents. The presence of non-conjunction words on the list shows that the list was determined by frequency, not by hand.

Summary

• The analyzer chain consists of tokenization, normalization, and filters, and it must work identically on both the indexing side and the query side.
• The three chains produce 261, 185, and 122 terms on the same corpus; the index holds 187,780, 185,982, and 146,080 bytes — the filters erase about 22 percent of the index.
• The Denizler query returns 80, 122, and 463 documents across the three chains; measured against the baseline, all five of the first five ids change depending on the chain. The chain choice directly determines both the set and the order.
• Turkish case folding flips the decision: the istanbul query returns 73 documents under the Turkish locale and 0 under the general rule; the apostrophe splits the token İstanbul'un in two.
• The stemmer collapses 7 of 12 stems to a single term and splits 5 due to consonant softening and vowel drop; as 185 terms collapse to 128 stems, 18 stems collect more than one term.

Next Step

This lesson’s three chains all applied the same rule to the entire text. But not every field in the catalog is text: the shelf code TR-879.4, the language Türkçe, the subject tag çocuk edebiyatı (children’s literature) — are these text to be split into words, or values that must stay a single piece? The next lesson indexes the same field with two types and measures the difference: which type exact matching works on, which type sorting is defined on, how many buckets aggregation produces, and how far apart the two types’ index sizes fall.