Süzme ve Sorgu Ayrımı

Önceki ders üç koşul bağlamını ayırdı, ama üçünün de ortak bir yanı vardı: hepsi puanlayıcının önünden geçiyordu. Zorunlu koşul kümeyi belirlerken puana da katkı veriyor, isteğe bağlı koşul zaten yalnız bunun için bulunuyordu. Katalog koşullarının bir bölümü için bu yanlıştır. “Yayın yılı 2010 ve sonrası”, “dili türkçe”, “konu başlığında eğitim geçsin” gibi koşullar ya sağlanır ya sağlanmaz; bir kitabın 2015 basımı olması onu 2011 basımı bir kitaptan daha ilgili yapmaz.

Bu ayrım süzme bağlamı (filter context) ile sorgu bağlamı (query context) olarak adlandırılır. Aynı koşul her iki bağlamda da aynı belgeleri geçirir — küme değişmez. Değişen şey, koşulun puana katkı verip vermemesidir ve bunun iki sonucu vardır: sıra başka çıkar, bedel başka olur. Bu ders aynı koşulu iki bağlamda çalıştırıp üç sayıyı karşılaştırır: dönen belge, ilk on sonuç ve okunan giriş.

Derlem ve Puan Kuralı

Derlem önceki derslerin modülüdür: 6.000 kitap kaydı, tohum 271828, belirlenimli üretim. SI7 (varsayım): bu derste puan, puanlanan her koşulun terim sıklığının o alandaki belirteç sayısına bölümüdür ve koşullar üzerinden toplanır. Seyreklik çarpanı henüz yoktur; tam model bu konunun beşinci dersinde kurulur. Ölçülen şey puanın büyüklüğü değil, bir koşulun puana girip girmemesinin sıraya etkisidir.

// derlem.mjs — kutuphane katalogu derlemi ve konum bilgili ters dizin.
// Tohum 271828, 6000 belge; konudaki butun olcumler bu modulu paylasir.
export const TOHUM = 271828, N = 6000;
let c = TOHUM;                                       // gorunur tohum, belirlenimli uretec
const r = () => { c = (c + 0x6d2b79f5) | 0; let t = Math.imul(c ^ (c >>> 15), 1 | c);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
const sec = (d, e = 1) => d[Math.floor(r() ** e * d.length)];   // e>1: bas ogeler sik, son ogeler seyrek

const SIFAT = ["eleştirel", "kısa", "resimli", "seçme", "karşılaştırmalı"];
const TUR = ["deneme", "öykü", "roman", "inceleme", "antoloji"];
const ALAN = ["çocuk", "tarih", "bilim", "felsefe", "toplum"];
const SON = ["seçkisi", "kitabı", "derlemesi", "dizisi"];
const NIT = ["kapsamlı", "özlü", "tanıtıcı", "tartışmalı"];
const KONU = ["eğitim", "göç", "kent", "bellek", "doğa", "müzik", "hukuk", "kimlik", "emek", "aile",
  "savaş", "gelenek", "sağlık", "yolculuk", "mimarlık", "arkeoloji", "denizcilik", "gökbilim"];
const YAZAR = ["Ahmet Yıldız", "Zeynep Kaya", "Kemal Demir", "Elif Şahin", "Necati Aydın"];
const DIL = ["türkçe", "ingilizce", "almanca"];

export const KATALOG = [];
for (let i = 1; i <= N; i += 1) {
  const s = sec(SIFAT, 1.5), t = sec(TUR, 1.5), a = sec(ALAN, 2), k = r();
  const desen = k < 0.18 ? `${s} ${t}` : k < 0.30 ? `${s} bir ${t}`
    : k < 0.40 ? `${s} ve kuramsal ${t}` : k < 0.50 ? `${t} ve ${s} inceleme`
    : k < 0.70 ? `${s} bir anlatı` : k < 0.88 ? `çağdaş bir ${t}` : "alan yazını taraması";
  KATALOG.push({ id: `K-${String(i).padStart(4, "0")}`, ad: `${a} ${t} ${sec(SON)}`,
    ozet: `${a} alanında ${desen}; ${sec(KONU, 3)} ve ${sec(KONU, 3)} üzerine ` +
      `${sec(NIT)} bir ${sec(TUR, 1.5)} olarak okunabilir.`,
    etiket: [a, t], yazar: sec(YAZAR), yil: 1990 + Math.floor(r() * 35), dil: sec(DIL, 2) });
}

export const belirtecle = (m) => m.toLocaleLowerCase("tr").split(/[^\p{L}\p{N}]+/u).filter(Boolean);

// Ters dizin: "alan|terim" -> Map(belge sirasi -> konumlar); uzunluk: alan basina belirtec sayisi.
export function tersDizin(alanlar) {
  const g = new Map(), uzunluk = new Map();
  KATALOG.forEach((b, i) => {
    for (const alan of alanlar) {
      const tk = belirtecle(String(b[alan]));
      uzunluk.set(`${alan}|${i}`, tk.length);
      tk.forEach((t, p) => {
        let l = g.get(`${alan}|${t}`); if (!l) g.set(`${alan}|${t}`, (l = new Map()));
        let k2 = l.get(i); if (!k2) l.set(i, (k2 = [])); k2.push(p);
      });
    }
  });
  return { g, uzunluk };
}

İki Bağlamın Ölçümü

// suzme.mjs — ayni kosul once sorgu baglaminda, sonra suzme baglaminda. Derlem: derlem.mjs.
// Puan burada terim sikliginin alan uzunluguna bolumudur; tam model sonraki derste kurulur.
import { KATALOG, TOHUM, tersDizin } from "./derlem.mjs";
const { g, uzunluk } = tersDizin(["ad", "ozet", "etiket", "dil"]);
const liste = (alan, terim) => g.get(`${alan}|${terim}`) ?? new Map();

function sorgula(puanlanan, suzgecler, s) {
  let aday = null;
  for (const [alan, terim] of [...puanlanan, ...suzgecler]) {
    const l = liste(alan, terim); s.taranan += l.size;
    aday = aday === null ? [...l.keys()] : aday.filter((d) => l.has(d));
  }
  const puan = new Map();
  for (const d of aday) {
    let p = 0;
    for (const [alan, terim] of puanlanan) { s.hesap += 1; p += liste(alan, terim).get(d).length / uzunluk.get(`${alan}|${d}`); }
    puan.set(d, p);
  }
  return { kume: aday, puan, sirali: [...aday].sort((x, y) => puan.get(y) - puan.get(x) || x - y) };
}
const olc = (ad, puanlanan, suzgecler) => {
  const s = { taranan: 0, hesap: 0 }, c = sorgula(puanlanan, suzgecler, s);
  console.log(`${ad.padEnd(40)} ${String(c.kume.length).padStart(4)} belge   puan hesabi ${String(s.hesap).padStart(4)}` +
    `   taranan giris ${String(s.taranan).padStart(5)}`);
  return c;
};

console.log(`derlem ${KATALOG.length} belge, tohum ${TOHUM}`);
const SORGU = [["ozet", "öykü"]], KOSUL = [["ozet", "eğitim"]];
const a = olc("sorgu baglami: öykü + eğitim puanlanir", [...SORGU, ...KOSUL], []);
const b = olc("suzme baglami: eğitim yalniz suzer", SORGU, KOSUL);
console.log(`ayni kume mi: ${JSON.stringify(a.kume) === JSON.stringify(b.kume)}`);
const on = (c) => c.sirali.slice(0, 10).map((d) => KATALOG[d].id);
console.log(`ilk on, sorgu baglami ${on(a).join(" ")}`);
console.log(`ilk on, suzme baglami ${on(b).join(" ")}`);
console.log(`ilk onda degisen ${on(a).filter((x) => !on(b).includes(x)).length}/10`);
console.log(`farkli puan degeri: sorgu baglaminda ${new Set(a.puan.values()).size}, ` +
  `suzme baglaminda ${new Set(b.puan.values()).size}`);
const oynama = a.kume.map((d) => Math.abs(a.sirali.indexOf(d) - b.sirali.indexOf(d)));
console.log(`basamak oynamasi: ortalama ${Math.round(oynama.reduce((x, y) => x + y, 0) / oynama.length)}, ` +
  `en buyugu ${Math.max(...oynama)}, yerinde kalan ${oynama.filter((o) => o === 0).length} belge`);

// Onbellek: suzgecin sonucu sorgudan bagimsizdir, bit kumesi olarak saklanir.
const onbellek = new Map();
function suzgecKumesi(alan, terim, s) {
  const anahtar = `${alan}|${terim}`;
  if (onbellek.has(anahtar)) { s.isabet += 1; return onbellek.get(anahtar); }
  const l = liste(alan, terim); s.taranan += l.size;
  const bit = new Uint8Array(Math.ceil(KATALOG.length / 8));
  for (const d of l.keys()) bit[d >> 3] |= 1 << (d & 7);
  onbellek.set(anahtar, bit);
  return bit;
}
const BES = ["öykü", "roman", "deneme", "inceleme", "antoloji"];
for (const onbellekli of [false, true]) {
  onbellek.clear();
  const s = { taranan: 0, isabet: 0 };
  for (const t of BES) {
    liste("ozet", t); s.taranan += liste("ozet", t).size;
    if (onbellekli) suzgecKumesi("ozet", "eğitim", s);
    else s.taranan += liste("ozet", "eğitim").size;
  }
  console.log(`bes sorgu, ayni suzgec  ${onbellekli ? "onbellekli " : "onbelleksiz"}   ` +
    `taranan giris ${String(s.taranan).padStart(6)}   onbellek isabeti ${s.isabet}`);
}
console.log(`suzgec bit kumesi ${Math.ceil(KATALOG.length / 8)} bayt; ` +
  `ayni kosulun puan dizisi ${liste("ozet", "eğitim").size * 8} bayt`);

derlem 6000 belge, tohum 271828
sorgu baglami: öykü + eğitim puanlanir   1138 belge   puan hesabi 2276   taranan giris  5513
suzme baglami: eğitim yalniz suzer       1138 belge   puan hesabi 1138   taranan giris  5513
ayni kume mi: true
ilk on, sorgu baglami K-0836 K-2188 K-4924 K-5913 K-1025 K-1207 K-2800 K-3095 K-3253 K-3683
ilk on, suzme baglami K-0171 K-0360 K-0417 K-0709 K-0836 K-0958 K-1185 K-1325 K-1520 K-1670
ilk onda degisen 9/10
farkli puan degeri: sorgu baglaminda 9, suzme baglaminda 6
basamak oynamasi: ortalama 173, en buyugu 791, yerinde kalan 4 belge
bes sorgu, ayni suzgec  onbelleksiz   taranan giris  27836   onbellek isabeti 0
bes sorgu, ayni suzgec  onbellekli    taranan giris  13260   onbellek isabeti 4
suzgec bit kumesi 750 bayt; ayni kosulun puan dizisi 29152 bayt

Küme Aynı, Sıra Değil

İki koşum da 1.138 belge döndürür ve karşılaştırma kümelerin birebir aynı olduğunu doğrular. Bu beklenen sonuçtur: her iki bağlamda da koşul zorunludur, geçirdiği belgeler aynıdır. Küme tarafında süzme bağlamının hiçbir etkisi yoktur.

Sıra tarafında etki büyüktür. İlk on sonucun dokuzu değişir; iki listede ortak kalan tek kayıt K-0836’dır. 1.138 belgenin yalnız dördü yerinde kalır, ortalama basamak oynaması 173, en büyüğü 791 basamaktır. Farkın kaynağı puanın çözünürlüğüdür: süzme bağlamında puan yalnız bir koşuldan gelir ve 6 ayrı değer alır, sorgu bağlamında iki koşuldan gelir ve 9 ayrı değer alır. Değer sayısı arttıkça beraberlikler çözülür ve liste yeniden dizilir.

Buradan çıkan karar açıktır. “Eğitim konulu olsun” isteği bir ilgililik ölçütü değil, bir kapsam daraltmasıdır; sorgu bağlamında bırakıldığında, özeti kısa olan ya da “eğitim” sözcüğü iki kez geçen kitaplar listenin başına çıkar. Bu sıralama kullanıcının sorduğu soruyla ilgisizdir — kullanıcı eğitim sözcüğünün kaç kez geçtiğini değil, öykü kitabı arıyordur. Süzme bağlamı sıralamayı kullanıcının asıl sorusuna bırakır.

Bedel: Hesap, Okuma ve Önbellek

Puan hesabı sayısı yarıya iner: 2.276’dan 1.138’e. Her aday belge için bir çarpma ve bir bölme yerine yarısı yapılır ve bu tasarruf aday sayısıyla doğru orantılı büyür. Taranan giriş sayısı ilk koşumda değişmez (5.513) — süzgeç de sonuçta bir gönderi listesi okur.

Asıl kazanç ikinci koşumda görünür. Süzgecin sonucu sorgudan bağımsızdır: hangi serbest metin sorulursa sorulsun, “özetinde eğitim geçen belgeler” kümesi aynıdır. Bu yüzden sonuç bir bit kümesi olarak saklanabilir ve sonraki sorgularda gönderi listesine hiç dokunulmaz. Beş farklı sorgu aynı süzgeci paylaştığında önbelleksiz koşum 27.836 giriş okur, önbellekli koşum 13.260 giriş — %52,4 daha az, dört önbellek isabetiyle.

Önbelleğin boyutu bu kararı kolaylaştırır: 6.000 belgelik derlem için bit kümesi 750 bayttır. Aynı koşulun puan katkısını saklamak isteseydik 3.644 belge için sekizer baytlık ondalık sayı, yani 29.152 bayt gerekirdi — otuz dokuz katı. Puanın saklanması ayrıca işe yaramaz, çünkü nihai puan sorgudaki öteki koşullarla birlikte hesaplanır ve her sorguda başkadır. Süzgeç önbelleğe alınabilir olmasını tam da puana katılmamasına borçludur: puana katılmayan koşulun sonucu bir doğruluk değeridir, doğruluk değeri sorgudan sorguya değişmez.

Süzgecin bedelsiz olduğu söylenemez. Önbellek bellek tüketir ve her belge eklemesinde ya da silmesinde geçersizleşir; seyrek sorulan bir koşulu önbellekte tutmak boşa bellektir. Ölçüt basittir: aynı koşul kaç ayrı sorguda tekrarlanıyor. Kütüphane arayüzündeki dil ve konu daraltmaları her sorguda tekrarlanır, kullanıcının yazdığı serbest metin tekrarlanmaz.

Özet

• Aynı zorunlu koşul iki bağlamda da aynı kümeyi verir: 6.000 belgelik derlemde (tohum 271828) her iki koşum da 1.138 belge döndürür.
• Sıra tamamen değişir: ilk on sonucun dokuzu farklıdır, 1.138 belgenin yalnız dördü yerinde kalır, ortalama basamak oynaması 173, en büyüğü 791’dir.
• Farkın kaynağı puanın çözünürlüğüdür: süzme bağlamında 6, sorgu bağlamında 9 ayrı puan değeri oluşur.
• Süzme bağlamı puan hesabını yarıya indirir (2.276 → 1.138) ve sonucu sorgudan bağımsız kıldığı için önbelleklenebilir kılar: beş sorguda 27.836 giriş yerine 13.260 giriş.
• Süzgeç önbelleği 750 bayttır, aynı koşulun puan dizisi 29.152 bayt; puanı saklamak ayrıca işe yaramaz, çünkü nihai puan her sorguda başka çıkar.

Sonraki Adım

Buraya kadar puan hep yer tutucu bir formülle hesaplandı: önce karşılanan koşul sayısı, sonra terim sıklığının alan uzunluğuna bölümü. İkisi de sıralama üretti, ama ikisi de sorunun asıl yarısını atladı. Bir terimin bir belgede geçmesi, o terimin derlemde ne kadar seyrek olduğu bilinmeden anlam taşımaz: “ve” sözcüğü 6.000 belgenin hepsinde geçer ve hiçbir şey ayırt etmez, “gökbilim” iki yüz kadar belgede geçer ve tek başına belgeyi belirler. Sonraki ders puanı üç bileşene ayırır — terim sıklığı, ters belge sıklığı ve alan uzunluğu — bir belgenin sırasının hangi bileşenden geldiğini gösterir ve sonucun ne kadarının doğru olduğunu ölçmek için kesinlik ile anmayı tanımlar.