Vurgulama ve Sayfalama

Buraya kadarki bütün ölçümler belge kimlikleri ve puanlar üzerinde yapıldı. Okurun gördüğü şey ise kimlik değil, kitabın adı ve özetinden alınmış kısa bir parçadır; parçanın içinde aradığı sözcük işaretlidir. İkinci bir şey daha var: liste on satırda bitmiyor, okur ikinci sayfaya, sonra yirminci sayfaya geçiyor.

Bu iki iş birbirine benzemez. Vurgulama yalnız gösterilen belgelere dokunur ve bedeli sayfa derinliğinden bağımsızdır. Sayfalama ise derinleştikçe pahalanır ve pahalanma dizinin kaç parçaya bölündüğüyle çarpılır. Ders ikisini de aynı derlem üzerinde ölçer.

Derlem, Sayfa ve Parça

Kod	Varsayım	Değer	Gerekçe
SI18	sayfa boyu ve gösterilen alan	10 sonuç; ad ve özet	vurgulama yalnız bu iki alanda yapılır
SI19	vurgulama penceresi	30 karakter, ilk eşleşmenin çevresi	parça bir satıra sığmalı
SI20	dizin parçası	4 parça, her parça kendi sıralamasını üretir	birleştirme aynı süreçte yapılır
SI21	aday girişi	12 bayt (kimlik 4, puan 8)	birleştiricide tutulan adayın boyu

SI20 bu dersin ölçüm düzeneğidir: parçalar aynı süreçte koşar, aralarındaki ağ yoktur; ölçülen şey parçadan çekilen aday sayısıdır, süre değil.

// derlem.mjs — kutuphane katalogu: tohumlu derlem, ters dizin ve puanlayici.
export const N = 1200, TOHUM = 20260801, ALANLAR = ["ad", "ozet", "konu", "yazar"];
let d = TOHUM;                                            // 32 bit uretec, tasma yok
export const rast = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const sec = (a) => a[Math.floor(rast() * a.length)];
const TEMA = [["öykü|hikâye", "edebiyat", "kısa seçki derleme anlatı kurgu taşra"],
  ["masal", "çocuk edebiyatı", "çocuk resimli okul genç orman uyku"],
  ["tarih", "tarih", "osmanlı cumhuriyet arşiv belge kronik vakıf"],
  ["deniz", "gezi", "kıyı balıkçı liman gemi ada fener"],
  ["matematik", "bilim", "geometri sayı kanıt kuram çözüm olasılık"],
  ["şiir", "şiir", "dize toplu divan çeviri seçme aruz"]]
  .map(([k, konu, a]) => ({ k: k.split("|"), konu, ana: a.split(" ") }));
const ORTAK = "kitap cilt baskı yayın inceleme notlar giriş sözlük".split(" ");
const AD = "Ahmet Elif Selim Nuray Kemal Deniz Ayşe Ozan Meral Barış".split(" ");
const SOY = "Yıldız Aksu Demir Karaca Toprak Şen".split(" ");

export const belgeler = Array.from({ length: N }, (_, id) => {
  const t = sec(TEMA), cek = t.k[t.k.length > 1 && rast() < 0.5 ? 1 : 0], oz = [cek, cek];
  const ad = [...new Set([cek, sec(t.ana), sec(t.ana)])];
  t.ana.forEach((s, j) => { if (rast() < 1 / (1 + j * 0.42)) oz.push(s); });
  ORTAK.forEach((s, j) => { if (rast() < 0.55 / (1 + j * 0.28)) oz.push(s); });
  if (rast() < 0.5) oz.push(sec(sec(TEMA).ana));          // baska temadan sizan sozcuk
  for (let k = oz.length - 1; k > 0; k -= 1) { const j = Math.floor(rast() * (k + 1));
    [oz[k], oz[j]] = [oz[j], oz[k]]; }
  // konu etiketi yayinevi kararidir: belgelerin dortte birinde metinle ayni temada degil
  return { id, ad: ad.join(" "), ozet: oz.join(" "), konu: (rast() < 0.25 ? sec(TEMA) : t).konu,
    yazar: `${sec(AD)} ${sec(SOY)}`, yil: 1975 + Math.floor(rast() ** 0.6 * 50),
    odunc: Math.floor(rast() ** 3 * 400) };
});

export const belirtec = (s) => s.toLocaleLowerCase("tr").match(/[\p{L}\p{N}]+/gu) ?? [];
export function dizinKur(bs) {                            // alan basina ters dizin
  const dz = {};
  for (const a of ALANLAR) {
    const gonderi = new Map(), boy = new Float64Array(bs.length);
    for (const b of bs) {
      const ts = belirtec(b[a]), say = new Map();
      boy[b.id] = ts.length;
      for (const t of ts) say.set(t, (say.get(t) ?? 0) + 1);
      for (const [t, tf] of say) {
        if (!gonderi.has(t)) gonderi.set(t, []);
        gonderi.get(t).push({ id: b.id, tf });
      }
    }
    dz[a] = { gonderi, boy, ort: boy.reduce((x, y) => x + y, 0) / bs.length };
  }
  return dz;
}
export function ara(dz, sorgu) {          // esit alan agirligiyla puanlanmis sonuc listesi
  const terimler = belirtec(sorgu), k1 = 1.2, b = 0.75, p = new Map();
  for (const a of ALANLAR) for (const t of terimler) {
    const g = dz[a].gonderi.get(t);
    if (!g) continue;
    const idf = Math.log(1 + (N - g.length + 0.5) / (g.length + 0.5));
    for (const e of g) {
      const nrm = 1 - b + (b * dz[a].boy[e.id]) / dz[a].ort;
      p.set(e.id, (p.get(e.id) ?? 0) + (idf * e.tf * (k1 + 1)) / (e.tf + k1 * nrm));
    }
  }
  return [...p].sort((x, y) => y[1] - x[1] || x[0] - y[0]);
}

Vurgulamanın Belge Başına Bedeli

Ters dizin hangi belgede hangi terimin geçtiğini bilir, ama terimin metnin neresinde geçtiğini bilmez: dizine giren şey belirteçtir, belirtecin karakter konumu değil. Vurgulama tam da bu bilgiyi ister. İki yol var: konumu dizinde saklamak ya da sorgu anında gösterilen belgeleri yeniden çözümlemek.

// vurgula.mjs — vurgulama bedeli: sorgu aninda yeniden cozumleme mi, konumu dizinde tutmak mi.
import { belgeler, dizinKur, ara, belirtec, N, TOHUM } from "./derlem.mjs";
const dz = dizinKur(belgeler), SORGU = "deniz gemi kitap";
const terim = new Set(belirtec(SORGU)), sonuc = ara(dz, SORGU);
const PARCA = /[\p{L}\p{N}]+/gu, tr = (x) => Math.round(x).toLocaleString("tr-TR");

function coz(metin) {                       // yeniden cozumleme: belirtecle, konumlari isaretle
  const kon = [];
  let sayi = 0;
  for (const m of metin.matchAll(PARCA)) {
    sayi += 1;
    if (terim.has(m[0].toLocaleLowerCase("tr"))) kon.push([m.index, m[0].length]);
  }
  return { karakter: metin.length, belirtec: sayi, kon };
}
const PENCERE = 30;
const parca = (metin, kon, en = PENCERE) => {    // ilk eslesmenin cevresinden pencere
  if (kon.length === 0) return "";
  const b = Math.max(0, kon[0][0] - 12), son = b + en < metin.length;
  let s = metin.slice(b, b + en);
  if (son) s = s.slice(0, s.lastIndexOf(" "));
  return (b > 0 ? "…" : "") + s.replace(PARCA, (w) =>
    terim.has(w.toLocaleLowerCase("tr")) ? `[${w}]` : w) + (son ? "…" : "");
};

console.log(`derlem ${N} belge, tohum ${TOHUM}; sorgu "${SORGU}" ${sonuc.length} belge eşleştirdi`);
console.log("gösterilen".padEnd(12) + "yeniden çözümlenen karakter".padStart(28) +
  "üretilen belirteç".padStart(19) + "bulunan eşleşme".padStart(17) +
  "pencere dışında kalan".padStart(23));
for (const gosterilen of [10, 50, 100]) {
  let k = 0, b = 0, e = 0, bos = 0;
  for (const [id] of sonuc.slice(0, gosterilen)) {
    const a = coz(belgeler[id].ad), o = coz(belgeler[id].ozet);
    k += a.karakter + o.karakter; b += a.belirtec + o.belirtec;
    e += a.kon.length + o.kon.length;
    const bas = o.kon.length ? Math.max(0, o.kon[0][0] - 12) : 0;
    bos += o.kon.filter(([i]) => i < bas || i >= bas + PENCERE).length;
  }
  console.log(`${gosterilen} belge`.padEnd(12) + tr(k).padStart(28) + tr(b).padStart(19) +
    tr(e).padStart(17) + `${bos}`.padStart(23));
}

let occ = 0, kar = 0;                       // butun derlem icin konum dizini kurulsaydi
for (const b of belgeler) { occ += belirtec(b.ad).length + belirtec(b.ozet).length;
  kar += b.ad.length + b.ozet.length; }
console.log(`\nkonum dizini seçilseydi: ${tr(occ)} belirteç geçişi, geçiş başına 8 bayt ` +
  `(başlangıç ve uzunluk) = ${tr(occ * 8)} bayt kalıcı ek yük`);
console.log(`aynı bilgi sorgu anında üretilirse kalıcı yük yoktur: derlemin ${tr(kar)} ` +
  `karakterinden yalnız gösterilen belgelerinki çözümlenir`);
for (const [id] of sonuc.slice(0, 3)) {
  const o = coz(belgeler[id].ozet), a = coz(belgeler[id].ad);
  console.log(`  ${belgeler[id].ad.padEnd(24)} özet parçası: ` +
    `${parca(belgeler[id].ozet, o.kon) || "(yok, ad alanından: " + parca(belgeler[id].ad, a.kon) + ")"}`);
}

derlem 1200 belge, tohum 20260801; sorgu "deniz gemi kitap" 817 belge eşleştirdi
gösterilen   yeniden çözümlenen karakter  üretilen belirteç  bulunan eşleşme  pencere dışında kalan
10 belge                             597                107               60                     12
50 belge                           3.315                581              263                     56
100 belge                          6.302              1.103              493                     90

konum dizini seçilseydi: 13.529 belirteç geçişi, geçiş başına 8 bayt (başlangıç ve uzunluk) = 108.232 bayt kalıcı ek yük
aynı bilgi sorgu anında üretilirse kalıcı yük yoktur: derlemin 83.666 karakterinden yalnız gösterilen belgelerinki çözümlenir
  deniz gemi               özet parçası: [kitap] liman cilt kıyı [deniz]…
  deniz kıyı gemi          özet parçası: [deniz] [gemi] [kitap] liman baskı…
  deniz gemi liman         özet parçası: [deniz] notlar [gemi] balıkçı…

Vurgulama ne kümeyi ne sırayı değiştirir: eşleşen 817 belge ve sıraları, vurgulama açık ya da kapalı olsun aynıdır. Değişen tek şey gösterilen satırın içeriğidir. Buna karşılık bedeli doğrusal ve gösterilen belge sayısına bağlıdır: on belge için 597 karakter ve 107 belirteç, yüz belge için 6.302 karakter ve 1.103 belirteç. Sayfa derinliği bu tabloda hiç görünmez; yüzüncü sayfanın on belgesini vurgulamak da 597 karakter civarında iş yapar.

Konum dizini satırı öteki yolun fiyatını veriyor: bütün derlemin 13.529 belirteç geçişi için geçiş başına sekiz bayt, toplam 108.232 bayt kalıcı ek yük. Bu yük her belge için ödenir, oysa vurgulama yalnız gösterilen on belgede yapılır. Dizin 1.200 belgeyi tutarken bir sorgu on tanesine bakıyorsa, konumu saklamak yüz yirmi belgenin işini peşin ödemek demektir. Karar bu asimetriyle verilir: konum dizini metin uzunsa ve aynı belgeler sık sık vurgulanıyorsa kazanır, katalog kaydında olduğu gibi alan kısaysa yeniden çözümleme daha ucuza gelir.

Son sütun vurgulamanın kendi kaybını sayıyor. On belgede bulunan altmış eşleşmenin on ikisi otuz karakterlik pencerenin dışında kalıyor; okur o eşleşmeleri hiç görmüyor. Pencere büyütülürse bu sayı düşer ama satır uzar. Vurgulama, eşleşmenin var olduğunu göstermez, yalnız bir tanesinin çevresini gösterir.

Derin Sayfalama

Sayfalamanın maliyeti tek bir sıralı listede tutulan bir imleçmiş gibi konuşulur. Dizin parçalara bölündüğünde bu doğru olmaktan çıkar: hiçbir parça bütün sıralamayı bilmediği için, ikinci sayfanın onuncu belgesinin hangi parçadan geleceği ancak her parçadan baştan itibaren yeterince aday çekilerek bulunabilir.

// sayfala.mjs — derin sayfalama: parca basina cekilen aday, imlecle karsilastirma ve kayma.
import { belgeler, dizinKur, ara } from "./derlem.mjs";
const dz = dizinKur(belgeler), SORGU = "deniz gemi kitap", P = 4, BOY = 10, BAYT = 12;
const tam = ara(dz, SORGU), once = (a, b) => b[1] - a[1] || a[0] - b[0];
let parcalar = Array.from({ length: P }, (_, p) => tam.filter(([id]) => id % P === p));
const TEMEL = parcalar.map((pz) => [...pz]);
const tr = (x) => Math.round(x).toLocaleString("tr-TR");

const kaydirmali = (sayfa) => {                 // her parca bastan from+size aday dondurur
  const bas = (sayfa - 1) * BOY, istenen = bas + BOY, havuz = [];
  for (const pz of parcalar) havuz.push(...pz.slice(0, istenen));
  havuz.sort(once);
  return { aday: istenen * P, sayfa: havuz.slice(bas, bas + BOY) };
};
const imlecSayfa = (imlec) => {                 // her parca imlecten sonraki size adayi dondurur
  const havuz = [];
  for (const pz of parcalar)
    havuz.push(...pz.filter((e) => imlec === null || once(e, imlec) > 0).slice(0, BOY));
  havuz.sort(once);
  return havuz.slice(0, BOY);
};

console.log(`sorgu "${SORGU}": ${tam.length} sonuç, ${P} parça, sayfa boyu ${BOY}`);
console.log("sayfa".padEnd(7) + "kaydırmalı aday".padStart(16) + "imleçli aday".padStart(14) +
  "oran".padStart(8) + "birleştirme baytı".padStart(19) + "kümülatif kaydırmalı".padStart(22) +
  "kümülatif imleçli".padStart(19) + "aynı sayfa".padStart(12));
let kum = 0, imlec = null, s = [];
for (let sayfa = 1; sayfa <= 20; sayfa += 1) {
  const k = kaydirmali(sayfa);
  kum += k.aday;
  s = imlecSayfa(imlec); imlec = s[s.length - 1];
  if (![1, 5, 10, 20].includes(sayfa)) continue;
  const ayni = k.sayfa.every(([id], i) => id === s[i][0]);
  console.log(`${sayfa}`.padEnd(7) + tr(k.aday).padStart(16) + tr(BOY * P).padStart(14) +
    `${(k.aday / (BOY * P)).toFixed(0)} kat`.padStart(8) + tr(k.aday * BAYT).padStart(19) +
    tr(kum).padStart(22) + tr(sayfa * BOY * P).padStart(19) +
    (ayni ? "evet" : "hayır").padStart(12));
}

const tumu = () => parcalar.flat().sort(once).map(([id]) => id);
const s1 = kaydirmali(1).sayfa, g1 = new Set(s1.map(([id]) => id)), i1 = s1[s1.length - 1];
console.log("\nsayfa 1 gösterildikten sonra dizin değişirse sayfa 2'de ne olur");
console.log("değişiklik".padEnd(24) + "kaydırmalı tekrar".padStart(18) + "atlanan".padStart(9) +
  "imleçli tekrar".padStart(16) + "atlanan".padStart(9));
for (const [ad, deg] of [
  ["ilk sıraya yeni belge", () => parcalar[0].unshift([-1, tam[0][1] + 1])],
  ["ilk sayfadan silme", () => { const x = s1[2][0];
    parcalar[x % P] = parcalar[x % P].filter(([id]) => id !== x); }]]) {
  parcalar = TEMEL.map((pz) => [...pz]);
  deg();
  const yeni = tumu();                          // atlanan: sayfa 2 basladigi yerin onunde kalan
  const say = (s2) => [s2.filter((id) => g1.has(id)).length,
    yeni.slice(0, yeni.indexOf(s2[0])).filter((id) => id >= 0 && !g1.has(id)).length];
  const k = say(kaydirmali(2).sayfa.map(([id]) => id)), i = say(imlecSayfa(i1).map(([id]) => id));
  console.log(ad.padEnd(24) + `${k[0]}`.padStart(18) + `${k[1]}`.padStart(9) +
    `${i[0]}`.padStart(16) + `${i[1]}`.padStart(9));
}

sorgu "deniz gemi kitap": 817 sonuç, 4 parça, sayfa boyu 10
sayfa   kaydırmalı aday  imleçli aday    oran  birleştirme baytı  kümülatif kaydırmalı  kümülatif imleçli  aynı sayfa
1                    40            40   1 kat                480                    40                 40        evet
5                   200            40   5 kat              2.400                   600                200        evet
10                  400            40  10 kat              4.800                 2.200                400        evet
20                  800            40  20 kat              9.600                 8.400                800        evet

sayfa 1 gösterildikten sonra dizin değişirse sayfa 2'de ne olur
değişiklik               kaydırmalı tekrar  atlanan  imleçli tekrar  atlanan
ilk sıraya yeni belge                    1        0               0        0
ilk sayfadan silme                       0        1               0        0

Son sütun bütün karşılaştırmanın dayanağıdır: iki yol da aynı sayfayı üretiyor. Belgeler de, sıraları da aynı. Değişen tek şey bedeldir.

Kaydırmalı sayfalamada parça başına çekilen aday, atlanan sayı artı sayfa boyudur; dört parçayla yirminci sayfa 800 aday demektir ve bunların 790’ı atılır. Bedel sayfa derinliğiyle doğrusal büyür, parça sayısıyla çarpılır: aynı sayfa sekiz parçalı bir dizinde 1.600 aday isterdi. İmleçli gezinmede sayı sabittir: her sayfada 40 aday, çünkü her parçaya “şu puandan ve şu kimlikten sonraki ilk on belge” sorulur ve baştan sayma gerekmez.

Kümülatif sütunlar okurun bütün gezintisini gösteriyor. Yirmi sayfayı sırayla gezen bir okur kaydırmalı yolda 8.400 aday, imleçli yolda 800 aday ürettirir. Kaydırmalının kümülatifi karesel büyür, imleçlininki doğrusal; yirminci sayfada aradaki fark on buçuk kattır. Buna karşılık imleçli gezinme bir şeyi yapamaz: doğrudan yirminci sayfaya atlayamaz, çünkü imleç bir sıra numarası değil, son gösterilen belgenin puanı ile kimliğidir. Sayfa numarasıyla gezinme isteniyorsa kaydırmalı yolun bedeli ödenecektir.

Alt tablo üçüncü farkı ölçüyor. Birinci sayfa gösterildikten sonra dizine ilk sıraya girecek bir belge eklenirse, kaydırmalı yolda ikinci sayfada okurun zaten gördüğü bir belge yeniden çıkar. Birinci sayfadaki bir belge silinirse, ikinci sayfanın başına gelecek bir belge okura hiç gösterilmez. İmleçli yolda iki sayı da sıfırdır, çünkü imleç bir sayaç değil bir değerdir; listenin başında olan biten imlecin sağındaki pencereyi kaydırmaz. Sayfalama biçimi burada sunum tercihi olmaktan çıkıp okurun gördüğü kümeyi belirleyen bir karara dönüşür.

Özet

• Vurgulama kümeyi ve sırayı değiştirmez, bedeli yalnız gösterilen belge sayısıyla büyür: on belge için 597 karakter ve 107 belirteç, yüz belge için 6.302 karakter ve 1.103 belirteç.
• Konumu dizinde tutmak 13.529 belirteç geçişi için 108.232 bayt kalıcı yük ister ve bu yük bütün belgeler için ödenir; yeniden çözümleme yalnız gösterilenler için çalışır.
• Vurgulama pencereye sığmayan eşleşmeleri gizler: on belgedeki altmış eşleşmenin on ikisi otuz karakterlik pencerenin dışında kaldı.
• Kaydırmalı sayfalamada parça başına aday, sayfa derinliğiyle doğrusal büyür ve parça sayısıyla çarpılır: yirminci sayfa dört parçada 800 aday, 9.600 bayt birleştirme yükü.
• İmleçli gezinme aynı sayfayı sabit 40 adayla üretir ve dizin değişse de tekrar ile atlama vermez; karşılığında sayfa numarasıyla atlamayı bırakır.

Sonraki Adım

Sonuç sayfası artık eksiksiz: eşleşen küme belirlendi, sıralandı, ayarlandı, sayılara indirgendi ve okuyan kişiye gösterilecek biçime getirildi. Bütün bu iş tek bir varsayıma dayanıyor: sorgudaki sözcük ile belgedeki sözcük aynı sözcük. Katalogta bu varsayım sık sık tutmaz. “hikâye” arayan okur “öykü” başlıklı kitapları göremez; ters dizin için bu iki dizgi arasında hiçbir bağ yoktur ve şimdiye kadarki hiçbir ayar bu bağı kuramaz, çünkü ağırlık da işlev de yalnız eşleşmiş bir terimin puanını değiştirir. Sonraki ders sözcüğün kendisini değil, sözcüğün geçtiği bağlamı karşılaştıran bir erişim biçimini kurar ve iki yolun döndürdüğü kümeyi ve sırayı yan yana ölçer.