Parçalar ve Kopyalar

Önceki ders parça sayısını dörtte sabit tuttu ve her parçadan sabit sayıda aday çekti. Bu iki sayı sessizce bir şey varsayıyordu: her parçanın gönderdiği ilk on aday, gerçekten de o parçanın en iyi on belgesi. Oysa bir parça puanı hesaplarken kendi gördüğü belge sıklığını kullanır. Dört parçalı bir kümede her parça derlemin dörtte birini görür, on altı parçalıda on altıda birini; terim seyreldikçe ters belge sıklığı sapar ve parçanın “en iyi” dediği belge değişir. Bu ders parça sayısını 1’den 16’ya çıkarıp aynı dört katalog sorgusunun ilk on sonucunun ne kadar bozulduğunu sayar, sonra kopya sayısını ayrı bir karar olarak ölçer.

Düzenek

Ölçüt bellidir: tek parçalı dizinin ilk on sonucu — bütün derlemin istatistiğini gören tek yerleşim odur. İki doğruluk ölçüsü kullanılıyor: ortak belge sayısı ve ortak belgelerin ortalama basamak kayması. Bedel sütunları toplanan aday, birleştirme adımı ve toplam dizin baytıdır.

Küme burada da süreç içi bir modeldir: parçalar aynı süreçte ayrı ters dizinlerdir, ağ yoktur. Ölçülen şey süre değil, istek sayısı ve sayılabilir yapı büyüklükleridir.

AK3 — belgeler parçalara kimlik kalanına göre, yani içerikten bağımsız ve dengeli dağılır. Bu en iyi durumdur: konuya göre dağıtılan bir derlemde her parçanın gördüğü sözcük dağılımı daha çarpık olur ve aşağıdaki sapma büyür. AK4 — sorgu her parçanın yalnızca bir kopyasına gider ve kopyalar aynı belgeleri taşır; kopya gecikmesi sıfır kabul edilir.

// kume/derlem.mjs — kutuphane katalogu derlemi ve ters dizin. Uretec kendi yazilmistir, tohum
// gorunurdur: her kosumda ayni 4000 kayit cikar. Dizin bir sozluk tutar: terim -> gonderi
// listesi; gonderi burada bir belge girisidir (belge kimligi + terim sikligi).
const ORTAK = ["kitap", "yazar", "eser", "metin", "bolum", "baski", "sayfa", "dil", "cilt", "yayin"];
const OZEL = {
  cocuk: ["masal", "resimli", "okul", "oyun", "hayvan", "cizgi"], oyku: ["kisa", "anlati", "derleme", "gunluk", "yalnizlik", "kasaba"],
  roman: ["kahraman", "kent", "kusak", "ev", "yolculuk", "mektup"], tarih: ["imparatorluk", "belge", "arsiv", "savas", "yuzyil", "vakayiname"],
  gezi: ["deniz", "yol", "harita", "sehir", "liman", "gemi"], siir: ["dize", "olcu", "imge", "ses", "sessizlik", "kafiye"],
  deneme: ["dusunce", "elestiri", "okuma", "zaman", "not", "soylesi"], bilim: ["olcum", "deney", "kuram", "veri", "gozlem", "denklem"],
};
const NADIR = ["fener", "kuyu", "ipek", "kule", "bahce", "kar", "ada", "koru", "tas", "cinar", "kirlangic", "demirci", "pusula", "kehribar"];
const KONU = Object.keys(OZEL);

export function derlem({ adet = 4000, tohum = 20260731 } = {}) {
  let s = tohum % 2147483647;
  const r = () => (s = (s * 48271) % 2147483647) / 2147483647;
  const sec = (a) => a[Math.floor(r() * a.length)], belge = [];
  for (let i = 1; i <= adet; i += 1) {
    const konu = sec(KONU), oz = OZEL[konu], soz = [sec(oz), sec(NADIR)];
    if (r() < 0.5) soz.push(sec(ORTAK));
    for (let j = 0, n = 10 + Math.floor(r() * 7); j < n; j += 1)
      soz.push(r() < 0.45 ? sec(ORTAK) : r() < 0.85 ? sec(oz) : sec(NADIR));
    belge.push({ id: i, konu, yil: 1990 + Math.floor(r() * 36), metin: [soz[0], soz[1], konu, ...soz.slice(2)].join(" ") });
  }
  return belge;
}

export function dizinle(belge) {
  const gonderi = new Map(), uzunluk = new Map();
  let bayt = 0;
  for (const d of belge) {
    const t = d.metin.split(" "), sayim = new Map();
    for (const x of t) sayim.set(x, (sayim.get(x) ?? 0) + 1);
    uzunluk.set(d.id, t.length);
    for (const [x, n] of sayim) {
      if (!gonderi.has(x)) { gonderi.set(x, []); bayt += x.length + 4; }   // sozluk girisi
      gonderi.get(x).push([d.id, n]); bayt += 8;
    }
  }
  const ort = [...uzunluk.values()].reduce((a, b) => a + b, 0) / (belge.length || 1);
  return { gonderi, uzunluk, N: belge.length, ort, bayt };
}

// Puanlama: terim sikligi, ters belge sikligi ve belge uzunlugu. YEREL puanlamada df ve ortalama
// uzunluk yalniz bu dizinden okunur; kuresel verilirse butun derlemin istatistigi kullanilir.
export function ara(dz, terim, k, kuresel = null) {
  const N = kuresel ? kuresel.N : dz.N, ort = kuresel ? kuresel.ort : dz.ort, puan = new Map();
  let taranan = 0;
  for (const t of terim) {
    const g = dz.gonderi.get(t) ?? [];
    const df = kuresel ? kuresel.df.get(t) ?? 0 : g.length;
    const idf = Math.log(1 + (N - df + 0.5) / (df + 0.5));
    for (const [id, tf] of g) {
      taranan += 1;
      const norm = tf + 1.2 * (0.25 + 0.75 * dz.uzunluk.get(id) / ort);
      puan.set(id, (puan.get(id) ?? 0) + idf * tf * 2.2 / norm);
    }
  }
  const sirali = [...puan].sort((a, b) => b[1] - a[1] || a[0] - b[0]).slice(0, k);
  return { aday: sirali.map(([id, p]) => ({ id, p })), taranan, eslesen: puan.size };
}

// k-yollu birlestirme: her adimda parca listelerinin basi karsilastirilir, en yuksek puanli
// alinir. Adim sayisi gercek karsilastirma sayisidir ve makineden bagimsizdir.
export function birlestir(liste, k) {
  const konum = liste.map(() => 0), sonuc = [];
  let adim = 0, en = 0;
  while (sonuc.length < k && en >= 0) {
    en = -1;
    for (let i = 0; i < liste.length; i += 1) {
      const a = liste[i][konum[i]], b = en < 0 ? null : liste[en][konum[en]];
      if (!a) continue;
      adim += 1;
      if (!b || a.p > b.p || (a.p === b.p && a.id < b.id)) en = i;
    }
    if (en >= 0) { sonuc.push(liste[en][konum[en]]); konum[en] += 1; }
  }
  return { sonuc, adim };
}

// kume/parca.mjs — parca sayisinin ve aday derinliginin ilk on sonuca etkisi. Kume SUREC ICI
// BIR MODELDIR: parcalar ayni surecte ayri ters dizinlerdir. Olcut, tek parcali dizinin ilk on
// sonucudur; her yerlesim ona gore ortak belge ve sira kaymasi bakimindan karsilastirilir.
import { derlem, dizinle, ara, birlestir } from "./derlem.mjs";

const K = 10, SORGU = [["kisa", "oyku", "yalnizlik"], ["deniz", "liman", "gemi"],
  ["masal", "resimli", "cocuk"], ["arsiv", "belge", "yuzyil"]];
const s = (x, n) => String(x).padStart(n);
const parcala = (b, p) => Array.from({ length: p }, (_, i) => dizinle(b.filter((d) => d.id % p === i)));

// Kuresel istatistik: butun parcalarin belge sikligi toplanir. Bunu kullanmak fazladan bir tur
// demektir — esgudum dugumu once df toplar, sonra parcalara puanlatir.
function kuresel(dz) {
  const df = new Map();
  let N = 0, uz = 0;
  for (const d of dz) {
    N += d.N; uz += d.ort * d.N;
    for (const [t, g] of d.gonderi) df.set(t, (df.get(t) ?? 0) + g.length);
  }
  return { df, N, ort: uz / N };
}

// Bir sorgu: her parca KP yerel aday dondurur, esgudum birlestirir. kur verilirse parcalar
// kuresel istatistikle puanlar (iki turlu sorgu).
function sor(dz, terim, KP, kur = null) {
  const liste = dz.map((d) => ara(d, terim, KP, kur).aday);
  const b = birlestir(liste, K);
  return { ilk: b.sonuc.map((x) => x.id), adim: b.adim, aday: liste.reduce((t, l) => t + l.length, 0) };
}

const belge = derlem(), tek = dizinle(belge);
const olcut = SORGU.map((q) => ara(tek, q, K).aday.map((x) => x.id));
const kiyas = (a, i) => {                       // olcutle ortak belge ve toplam sira kaymasi
  let ortak = 0, kayma = 0;
  a.forEach((id, j) => { const k = olcut[i].indexOf(id); if (k >= 0) { ortak += 1; kayma += Math.abs(k - j); } });
  return { ortak, kayma };
};
const ortala = (f) => { const t = SORGU.map(f); return t.reduce((a, b) => a + b, 0) / t.length; };

console.log(`${belge.length} belge, tohum 20260731, ${tek.gonderi.size} terim. Tek parcali dizin: ${tek.bayt} bayt.`);
console.log(`Olcut: tek parcali dizinin ilk ${K} sonucu, dort katalog sorgusunda ortalama.\n`);
console.log("parca | dizin bayt | aday | birlestirme | derinlik 10: ortak / kayma | derinlik 50 | kuresel df turu");
console.log("------|------------|------|-------------|----------------------------|-------------|----------------");
for (const P of [1, 2, 4, 8, 16]) {
  const dz = parcala(belge, P), kur = kuresel(dz);
  const bayt = dz.reduce((t, d) => t + d.bayt, 0);
  const d10 = ortala((q, i) => kiyas(sor(dz, q, 10).ilk, i).ortak);
  const k10 = ortala((q, i) => { const x = kiyas(sor(dz, q, 10).ilk, i); return x.kayma / x.ortak; });
  const d50 = ortala((q, i) => kiyas(sor(dz, q, 50).ilk, i).ortak);
  const dkur = ortala((q, i) => kiyas(sor(dz, q, 10, kur).ilk, i).ortak);
  const r = sor(dz, SORGU[0], 10);
  console.log(`${s(P, 5)} | ${s(bayt, 10)} | ${s(r.aday, 4)} | ${s(r.adim, 11)} | ` +
    `${s(d10.toFixed(2) + " / " + k10.toFixed(2), 26)} | ${s(d50.toFixed(2), 11)} | ${s(dkur.toFixed(2), 15)}`);
}

console.log("\nilk 10 sonuc (sorgu: kisa oyku yalnizlik):");
console.log(`${"tek parca".padEnd(21)}: ${olcut[0].join(" ")}`);
for (const P of [4, 16]) {
  const dz = parcala(belge, P);
  console.log(`${(P + " parca, derinlik 10").padEnd(21)}: ${sor(dz, SORGU[0], 10).ilk.join(" ")}`);
  console.log(`${(P + " parca, kuresel df").padEnd(21)}: ${sor(dz, SORGU[0], 10, kuresel(dz)).ilk.join(" ")}`);
}

// Kopya: her parcanin R+1 kopyasi ayri dugumlerde durur. Sorgu her parcanin BIR kopyasina
// gider; kopya sayisi sorgu genisligini degistirmez, dizin baytini ve dugum kaybini degistirir.
const P = 4, dz = parcala(belge, P), bayt = dz.reduce((t, d) => t + d.bayt, 0);
console.log("\nkopya sayisi (4 parca, bir dugum kayboluyor):");
console.log("kopya | dugum | toplam dizin bayt | dokunulan dugum | erisilemeyen parca | eslesen | ilk 10'da kalan");
for (const R of [0, 1, 2]) {
  const kayip = R === 0 ? 1 : 0;                    // R=0 iken bir dugum bir parcayi goturur
  const kalan = dz.filter((_, i) => i >= kayip);
  const eslesen = kalan.reduce((t, d) => t + ara(d, SORGU[0], K).eslesen, 0);
  const ilk = sor(kalan, SORGU[0], 10).ilk;
  console.log(`${s(R, 5)} | ${s(P * (R + 1), 5)} | ${s(bayt * (R + 1), 17)} | ${s(P, 15)} | ` +
    `${s(kayip, 18)} | ${s(eslesen, 7)} | ${s(ilk.filter((x) => olcut[0].includes(x)).length + "/10", 15)}`);
}
console.log(`\nkosumdan bagimsiz: toplanan aday P x derinlik, birlestirme adimi ${K} x P, dizin bayti` +
  ` (R+1) kati. Tek turlu sorgu P istek, kuresel df turu 2P istek eder. Sorgunun dokundugu dugum` +
  ` sayisi kopyayla degismez, parca sayisiyla degisir.`);

4000 belge, tohum 20260731, 80 terim. Tek parcali dizin: 382752 bayt.
Olcut: tek parcali dizinin ilk 10 sonucu, dort katalog sorgusunda ortalama.

parca | dizin bayt | aday | birlestirme | derinlik 10: ortak / kayma | derinlik 50 | kuresel df turu
------|------------|------|-------------|----------------------------|-------------|----------------
    1 |     382752 |   10 |          10 |               10.00 / 0.00 |       10.00 |           10.00
    2 |     383496 |   20 |          20 |                8.50 / 1.28 |        8.50 |           10.00
    4 |     384984 |   40 |          40 |                6.25 / 2.50 |        6.25 |           10.00
    8 |     387960 |   80 |          80 |                4.75 / 2.04 |        4.75 |           10.00
   16 |     393912 |  160 |         160 |                4.75 / 4.01 |        4.75 |           10.00

ilk 10 sonuc (sorgu: kisa oyku yalnizlik):
tek parca            : 3159 3544 2689 2362 3370 701 2448 502 2181 2320
4 parca, derinlik 10 : 2689 701 2181 3159 1777 549 3544 2362 3370 565
4 parca, kuresel df  : 3159 3544 2689 2362 3370 701 2448 502 2181 2320
16 parca, derinlik 10: 2689 1777 3265 2323 2180 2529 3544 502 2181 1150
16 parca, kuresel df : 3159 3544 2689 2362 3370 701 2448 502 2181 2320

kopya sayisi (4 parca, bir dugum kayboluyor):
kopya | dugum | toplam dizin bayt | dokunulan dugum | erisilemeyen parca | eslesen | ilk 10'da kalan
    0 |     4 |            384984 |               4 |                  1 |     379 |            6/10
    1 |     8 |            769968 |               4 |                  0 |     515 |            7/10
    2 |    12 |           1154952 |               4 |                  0 |     515 |            7/10

kosumdan bagimsiz: toplanan aday P x derinlik, birlestirme adimi 10 x P, dizin bayti (R+1) kati. Tek turlu sorgu P istek, kuresel df turu 2P istek eder. Sorgunun dokundugu dugum sayisi kopyayla degismez, parca sayisiyla degisir.

Parça Sayısı İlk Onu Bozuyor

Birinci tablonun bedel sütunları beklendiği gibi: toplanan aday ve birleştirme adımı parça sayısıyla doğrusal artıyor, 10’dan 160’a. Toplam dizin baytı 382.752’den 393.912’ye, yüzde 2,9 çıkıyor; kaynağı gönderi listeleri değil sözlüktür — aynı 80 terim her parçada yineleniyor.

Asıl sayı doğruluk sütununda. İki parçada ilk onun ortalama 8,5’i ölçütle ortak; dörtte 6,25; sekizde ve on altıda 4,75. On altı parçada ilk on sonucun yarısından fazlası ölçütte hiç yok ve ortak kalanların ortalama basamak kayması 1,28’den 4,01’e çıkıyor.

Listeler bunu tek tek gösteriyor. Tek parçalı dizinde sıra 3159, 3544, 2689 diye başlıyor; dört parçada aynı sorgu 2689, 701, 2181 sırasıyla dönüyor — ölçütün birincisi olan 3159 dördüncü basamağa iniyor ve listeye ölçütte bulunmayan 1777, 549, 565 giriyor. On altı parçada 3159 ilk ondan tamamen çıkıyor ve ölçütle ortak yalnızca dört belge kalıyor. Hiçbir sorgu değişmedi, hiçbir belge silinmedi; değişen tek şey her parçanın kaç belge gördüğü.

Derinlik Düzeltmiyor, Fazladan Bir Tur Düzeltiyor

Sapmayı kapatmanın akla gelen ilk yolu her parçadan daha çok aday çekmektir. Tablo bunu çürütüyor: aday derinliği 10’dan 50’ye çıkarıldığında ortak belge sayısı hiç değişmiyor (8,50 / 6,25 / 4,75 / 4,75). Hata kırpmadan gelmiyor: her parça listesini kendi yerel puanına göre sıralıyor ve birleştirici o puanlara güveniyor. Yanlış olan sıranın uzunluğu değil, sıranın kendisidir.

Düzelten şey son sütunda: eşgüdüm düğümü önce bütün parçalardan terim başına belge sıklığını toplar, sonra parçalara küresel istatistikle puanlatır. Ortak belge sayısı her parça sayısında 10,00’a dönüyor; dört ve on altı parçanın listeleri tek parçalı dizininkiyle birebir aynı. Bedeli sorgunun tek turdan iki tura, P istekten 2P isteğe çıkmasıdır.

Kopya Sayısı Kümeyi Korur, Sırayı Düzeltmez

İkinci tablo kopyayı ayrı bir karar olarak ölçüyor. Kopyasız dört parçalı kümede bir düğümün kaybı bir parçayı tümüyle götürüyor: eşleşen belge 515’ten 379’a düşüyor — 136 katalog kaydı sorguya hiç görünmüyor — ve ilk ondaki ortak belge 7’den 6’ya iniyor. Bir kopya eklendiğinde aynı düğüm kaybı hiçbir şey değiştirmiyor.

Bedel dizin baytıdır ve doğrusaldır: 384.984’ten 769.968’e, iki kopyada 1.154.952’ye. Sorgunun dokunduğu düğüm sayısı üç satırda da 4 — kopya eklemek sorguyu genişletmez.

Son sütunun 7/10’da kalması bu dersin ayrımıdır: kopya kaybolan belgeleri geri getirdi, yanlış sırayı getirmedi. O üç belgelik fark yerel puanlamadan geliyor ve ancak küresel istatistik turuyla kapanır. Yedeklilik bir dayanıklılık kararıdır; bölümleme aynı anda bir puanlama kararıdır.

Özet

• Parça sayısı 1’den 16’ya çıktığında toplanan aday ve birleştirme adımı 10’dan 160’a, toplam dizin baytı 382.752’den 393.912’ye çıktı; artış gönderi listelerinden değil, her parçada yinelenen sözlükten geliyor.
• İlk onun ölçütle ortak belge sayısı dört parçada 6,25’e, on altı parçada 4,75’e düştü; ortak belgelerin ortalama basamak kayması 4,01’e çıktı.
• Aday derinliğini 10’dan 50’ye çıkarmak doğruluğu hiç değiştirmedi: hata kırpmadan değil, parça başına yerel belge sıklığından geliyor.
• Küresel belge sıklığı turu ilk onu her parça sayısında 10,00’a döndürdü ve listeleri tek parçalı dizinle birebir eşitledi; bedeli sorgunun P istekten 2P isteğe çıkmasıdır.
• Kopyasız kümede bir düğüm kaybı eşleşen belgeyi 515’ten 379’a indirdi; bir kopya bunu tümüyle önledi, dizin baytını iki katına çıkardı, dokunulan düğüm sayısını değiştirmedi. Kopya kaybolan kümeyi geri getirir, bozulan sırayı getirmez: ilk onun ortak belge sayısı 7/10’da kaldı.

Sonraki Adım

Bu ders kopyayı bir yedeklilik kararı olarak ölçtü ve kopyaların aynı belgeleri taşıdığını varsaydı; küme sağlamken bu doğrudur. Ağ ikiye bölündüğünde ise kopyalar birbirini göremez ve her yarı kendi başına yazma kabul edebilir: aynı dizine iki yerden belge girer, iki yarının gönderi listeleri ayrışır. Sonraki ders beş kopyalı bir dizini üç ve iki düğümlük iki yarıya böler, çoğunluk gerekliliğini açıp kapatır ve iki şeyi sayar — azınlıkta kabul edilen dizinleme işlemlerinden kaçının bölünme onarıldığında kaybolduğunu, ve bölünme sürerken her iki yarıya gelen sorgunun eksik döndürdüğü belge sayısını.