Belge Yaşam Döngüsü

Önceki iki ders belgeleri bir kez alıp bıraktı: kayıt geldi, eşleme kuruldu, dizin yazıldı. Katalog ise durmuyor. Bir kitabın özeti düzeltiliyor, konu etiketi değiştiriliyor, kayıp bir kitap kayıttan çıkarılıyor. Bu ders o üç işlemin dizinde ne yaptığını ölçüyor.

Ters dizinin yapısı bir kısıtlama getirir. Gönderi listeleri terim başına tutulur ve belge kimliğine göre sıralıdır; bir belgenin metni değiştiğinde o belgenin girişleri onlarca ayrı listede dağınık durur. Bu girişleri yerinde düzeltmek, her listeyi bulup içinden bir kaydı çıkarmak demektir. Bunun yerine dizin daha ucuz olanı yapar: eski kaydı ölü işaretler, yeni metni yeni bir kayıt olarak sona ekler. Güncelleme bu yüzden ayrı bir işlem değil, silme ile eklemedir.

İç Kimlik ve Silme İşareti

Bu mekanizma iki kimlik gerektirir. Dış kimlik katalogun kitap numarasıdır ve değişmez. İç kimlik belgenin dizine giriş sırasıdır ve her yazmada yenisi verilir. Gönderi listeleri iç kimliği taşır; dış kimlik ile iç kimlik arasındaki eşleştirme ayrı tutulur. Bir belge güncellendiğinde eşleştirme yeni iç kimliğe döner, eskisi silme işaretine girer.

DC1: derlem aynıdır — 600 kayıt, tohum 20250317; işlem dizisi 20250318 tohumundan üretilir. DC2: bayt sabitleri önceki derslerdekiyle aynıdır ve konum tutulmuyor. DC3: silme işareti iç kimlik başına 1 bit sayılır. DC4: her tur 60 güncelleme, 20 silme ve 20 ekleme uygular; ölü giriş oranı %20’yi aştığında dizin canlı belgelerden yeniden yazılır. DC5: ölü girişler sorgu sonucundan elenir, ama taranan girişe dahildir.

// arama/katalog.mjs — uc konunun paylastigi derlem: kutuphane katalogundan uretilmis
// 600 kitap kaydi, tohum 20250317. Alanlar: ad, ozet, konu, yazar, yil, dil, raf.
export const TOHUM = 20250317, BELGE = 600;
let cekirdek = TOHUM;
const rast = () => (cekirdek = (cekirdek * 1103515245 + 12345) % 2147483648) / 2147483648;
const sec = (d) => d[Math.floor(rast() * d.length)];
const secZ = (d) => d[Math.floor(rast() ** 2 * d.length)];   // gercek metinde siklik carpiktir
const ayir = (s) => s.split("|");

// govde sozcugu: yalin, tamlayan, cogul, yonelme, ayrilma, bulunma
export const KOK = ayir("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 KALIP = ayir("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 KALIP2 = ayir("{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 EK = ayir("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 YER = ayir("Ankara|İzmir|Trabzon|Kars|Bursa|Edirne|Sinop|Antakya");
const NESNE = ayir("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 ONEK = ayir("Uzak|Kayıp|Sessiz|Eski|Kısa|Büyük|Küçük|Unutulmuş|Beyaz|Yedi");
const SONEK = ayir("Günleri|Öyküleri|Üzerine Notlar|Anıları|Sözlüğü|Rehberi|Yılları|Defteri");
const KONU = ayir("çocuk edebiyatı|roman|kısa öykü|şiir|deniz tarihi|coğrafya|biyografi|gezi yazısı|halk bilimi|mimarlık|müzik|felsefe");
const AD = ayir("Ahmet|Ayşe|Zeynep|Cemal|Nuran|Selim|Elif|Kerem|Hatice|Bedri|Sevgi|Nazlı");
const SOYAD = ayir("Yılmaz|Kaya|Demir|Şahin|Çelik|Aydın|Doğan|Arslan|Koç|Ertem");
const DIL = ayir("Türkçe|Türkçe|Türkçe|İngilizce|Almanca|Fransızca");

const buyut = (s) => s[0].toLocaleUpperCase("tr") + s.slice(1);
function ozetUret() {
  const parca = [];
  for (let i = 0; i < 3; i += 1) { const [d, k] = secZ(KALIP); parca.push(k.replace("{}", secZ(KOK)[d])); }
  parca.push(sec(KALIP2).replace("{Y}", sec(YER)).replace("{N}", sec(NESNE)));
  if (rast() < 0.45) parca.push(sec(EK));
  return buyut(parca.join(", ")) + ".";
}
function adUret() {
  const k = secZ(KOK), o = sec(ONEK), s = sec(SONEK), t = rast();
  if (t < 0.25) return `${o} ${buyut(k[2])}`;
  if (t < 0.5) return `${buyut(k[0])} ${s}`;
  if (t < 0.75) return `${o} ${buyut(k[0])} ${s}`;
  return `${buyut(k[1])} ${s}`;
}
export const derlem = [];
for (let i = 1; i <= BELGE; i += 1) {
  const konu = [sec(KONU)];
  if (rast() < 0.55) konu.push(sec(KONU));
  if (rast() < 0.2) konu.push(sec(KONU));
  derlem.push({
    id: i, ad: adUret(), ozet: ozetUret(), konu: [...new Set(konu)], yazar: `${sec(AD)} ${sec(SOYAD)}`,
    yil: 1968 + Math.floor(rast() * 57), dil: sec(DIL),
    raf: `${sec(ayir("TR|EN|DE|FR"))}-${800 + Math.floor(rast() * 99)}.${Math.floor(rast() * 9)}`,
  });
}

// arama/dizin.mjs — kendi yazilan ters dizin: sozluk, gonderi listesi (belge kimligi, terim
// sikligi, konum) ve bayt sayimi. Cozumleyici disaridan verilir; sonraki dersler bunu kullanir.
export const BASIT = (s) => s.toLocaleLowerCase("tr").split(/[^\p{L}\p{N}]+/u).filter(Boolean);
export const KIMLIK = 4, SIKLIK = 4, KONUM = 4, SOZLUK_EK = 8;   // DC2: bayt sabitleri

export class TersDizin {
  sozluk = new Map();                    // terim -> gonderi listesi
  belge = 0;
  constructor({ coz = BASIT, siklik = true, konum = true } = {}) { Object.assign(this, { coz, siklik, konum }); }

  ekle(id, metin) {
    const yerel = new Map();
    this.coz(metin).forEach((t, i) => (yerel.get(t) ?? yerel.set(t, []).get(t)).push(i));
    for (const [t, k] of yerel) {
      if (!this.sozluk.has(t)) this.sozluk.set(t, []);
      this.sozluk.get(t).push({ id, tf: k.length, konum: this.konum ? k : [] });
    }
    this.belge += 1;
  }

  liste(t) { return this.sozluk.get(t) ?? []; }

  ara(...terim) {                        // kesisim: listeler kimlik sirali oldugu icin tek gecis
    const l = terim.map((t) => this.liste(t)), p = l.map(() => 0), kume = [];
    let kars = 0;
    while (l.every((x, i) => p[i] < x.length)) {
      const en = Math.max(...l.map((x, i) => x[p[i]].id));
      let ayni = true;
      for (let i = 0; i < l.length; i += 1) {
        while (p[i] < l[i].length && l[i][p[i]].id < en) { p[i] += 1; kars += 1; }
        kars += 1;
        if (p[i] >= l[i].length || l[i][p[i]].id !== en) { ayni = false; break; }
      }
      if (ayni) { kume.push(en); p.forEach((_, i) => (p[i] += 1)); }
    }
    return { kume, giris: l.reduce((t, x) => t + x.length, 0), kars };
  }

  bayt() {                               // sozluk + gonderi + konum
    let s = 0, g = 0, k = 0, giris = 0, konum = 0;
    for (const [t, liste] of this.sozluk) {
      s += Buffer.byteLength(t) + SOZLUK_EK;
      for (const gr of liste) {
        g += KIMLIK + (this.siklik ? SIKLIK : 0);
        k += gr.konum.length * KONUM;
        giris += 1; konum += gr.konum.length;
      }
    }
    return { terim: this.sozluk.size, giris, konum, sozluk: s, gonderi: g, konumBayt: k, toplam: s + g + k };
  }
}

// arama/yasam.mjs — belge yasam dongusu: ekleme, guncelleme (sil + ekle) ve silme. Olu gonderi
// girisi, silme isaretinin bayti, sorguda elenen giris ve temizlik turu sayilir.
import { derlem, BELGE, TOHUM } from "./katalog.mjs";
import { TersDizin, BASIT, KIMLIK, SIKLIK } from "./dizin.mjs";

let c = TOHUM + 1;
const rast = () => (c = (c * 1103515245 + 12345) % 2147483648) / 2147483648;

class Depo {                                  // ters dizinin uzerinde belge yasam dongusu
  #dizin = new TersDizin({ konum: false });
  #ic = new Map();                            // dis kimlik -> ic kimlik (dizindeki sira)
  #metin = new Map();
  #silinen = new Set();                       // silme isareti: olu ic kimlikler
  sayac = 0;
  ekle(dis, metin) {                          // guncelleme de budur: eski ic kimlik olu isaretlenir
    this.sayac += 1;
    if (this.#ic.has(dis)) this.#silinen.add(this.#ic.get(dis));
    this.#ic.set(dis, this.sayac); this.#metin.set(dis, metin);
    this.#dizin.ekle(this.sayac, metin);
  }
  sil(dis) { this.#silinen.add(this.#ic.get(dis)); this.#ic.delete(dis); this.#metin.delete(dis); }
  ara(terim) {                                // olu ic kimlikler sonucdan elenir
    const l = this.#dizin.liste(terim), geri = new Map([...this.#ic].map(([d, i]) => [i, d]));
    const canli = l.filter((g) => geri.has(g.id));
    return { kume: canli.map((g) => geri.get(g.id)), giris: l.length, elenen: l.length - canli.length };
  }
  sira(dis, terim) { const k = this.ara(terim).kume.indexOf(dis); return k < 0 ? "-" : `${k + 1}`; }
  olcu() {
    const b = this.#dizin.bayt();
    const olu = [...this.#dizin.sozluk.values()].flat().filter((g) => this.#silinen.has(g.id)).length;
    return { canli: this.#ic.size, terim: b.terim, giris: b.giris, olu, dizin: b.toplam,
      isaret: Math.ceil(this.sayac / 8), oran: Math.round(olu * 100 / b.giris) };
  }
  temizle() {                                 // dizin yalniz canli belgelerden yeniden yazilir
    const canli = [...this.#metin];
    this.#dizin = new TersDizin({ konum: false }); this.#ic = new Map(); this.#silinen = new Set();
    this.sayac = 0;
    for (const [d, m] of canli) this.ekle(d, m);
  }
}

const metin = (b) => `${b.ad} ${b.ozet}`;
const depo = new Depo();
for (const b of derlem) depo.ekle(b.id, metin(b));
const ilk = depo.olcu();
console.log(`tohum ${TOHUM}; ${BELGE} belge dizine alindi: ${ilk.terim} terim, ${ilk.giris} gonderi ` +
  `girisi, ${ilk.dizin} bayt, silme isareti ${ilk.isaret} bayt (ic kimlik basina 1 bit)`);

// --- tek belgede guncellemenin mekanigi ---
const hedef = derlem.find((b) => BASIT(metin(b)).includes("kuş"));
const df = (t) => depo.ara(t).kume.length;
const ortak = [...new Set(BASIT(metin(hedef)))].filter((t) => t !== "kuş").sort((a, b) => df(b) - df(a))[0];
console.log(`\n#${hedef.id} "${hedef.ad}": ozetteki "kuş" belirteci "martı" ile degistiriliyor`);
console.log(`  once : "kuş" ${df("kuş")} belge (bu belge ${depo.sira(hedef.id, "kuş")}. sirada), ` +
  `"martı" ${df("martı")} belge, "${ortak}" sorgusunda ${depo.sira(hedef.id, ortak)}. sirada`);
depo.ekle(hedef.id, BASIT(metin(hedef)).map((t) => (t === "kuş" ? "martı" : t)).join(" "));
console.log(`  sonra: "kuş" ${df("kuş")} belge (bu belge ${depo.sira(hedef.id, "kuş")}. sirada), ` +
  `"martı" ${df("martı")} belge, "${ortak}" sorgusunda ${depo.sira(hedef.id, ortak)}. sirada`);
const k = depo.ara("kuş"), o = depo.ara(ortak);
console.log(`  "kuş" gonderi listesi ${k.giris} giris tasiyor, ${k.elenen} tanesi elenerek atiliyor; ` +
  `"${ortak}" listesinde ${o.elenen} elenen giris var`);

// --- turlar: her tur 60 guncelleme, 20 silme, 20 ekleme; olu oran %20'yi asinca temizlik ---
console.log(`\n${"tur".padStart(4)}${"islem".padStart(7)}${"canli belge".padStart(13)}${"gonderi".padStart(9)}` +
  `${"olu giris".padStart(11)}${"olu %".padStart(7)}${"dizin bayt".padStart(12)}${"isaret".padStart(8)}${"temizlikten sonra".padStart(19)}`);
let sonraki = BELGE + 1, islem = 0;
for (let tur = 1; tur <= 6; tur += 1) {
  for (let i = 0; i < 60; i += 1) {
    const b = derlem[Math.floor(rast() * BELGE)];
    depo.ekle(b.id, `${metin(b)} düzeltme ${tur}`);
  }
  for (let i = 0; i < 20; i += 1) depo.sil(1 + Math.floor(rast() * BELGE));
  for (let i = 0; i < 20; i += 1) { const b = derlem[Math.floor(rast() * BELGE)]; depo.ekle(sonraki, metin(b)); sonraki += 1; }
  islem += 100;
  const s = depo.olcu(), temiz = s.oran > 20;
  if (temiz) depo.temizle();
  console.log(String(tur).padStart(4) + String(islem).padStart(7) + String(s.canli).padStart(13) +
    String(s.giris).padStart(9) + String(s.olu).padStart(11) + `%${s.oran}`.padStart(7) +
    String(s.dizin).padStart(12) + String(s.isaret).padStart(8) +
    (temiz ? `${depo.olcu().dizin} bayt` : "-").padStart(19));
}
const son = depo.olcu();
console.log(`\nson durum: ${son.canli} canli belge, ${son.giris} gonderi girisi, ${son.olu} olu giris, ` +
  `${son.dizin} bayt; baslangicta ${BELGE} belge ${ilk.dizin} bayt tutuyordu`);

tohum 20250317; 600 belge dizine alindi: 185 terim, 14609 gonderi girisi, 119722 bayt, silme isareti 75 bayt (ic kimlik basina 1 bit)

#10 "Denizin Günleri": ozetteki "kuş" belirteci "martı" ile degistiriliyor
  once : "kuş" 92 belge (bu belge 1. sirada), "martı" 0 belge, "üzerine" sorgusunda 7. sirada
  sonra: "kuş" 91 belge (bu belge -. sirada), "martı" 1 belge, "üzerine" sorgusunda 509. sirada
  "kuş" gonderi listesi 92 giris tasiyor, 1 tanesi elenerek atiliyor; "üzerine" listesinde 1 elenen giris var

 tur  islem  canli belge  gonderi  olu giris  olu %  dizin bayt  isaret  temizlikten sonra
   1    100          600    16679       1996    %12      136322      86                  -
   2    200          603    18729       3856    %21      152731      96        121883 bayt
   3    300          607    16961       1926    %11      138596      86                  -
   4    400          616    19029       3699    %19      155149      96                  -
   5    500          625    21052       5451    %26      171342     106        127720 bayt
   6    600          635    17733       1758    %10      144785      89                  -

son durum: 635 canli belge, 17733 gonderi girisi, 1758 olu giris, 144785 bayt; baslangicta 600 belge 119722 bayt tutuyordu

Tek Güncellemenin Bıraktığı İz

İkinci bölüm tek bir belgeyi izliyor. #10 numaralı kaydın özetindeki kuş belirteci martı ile değiştiriliyor ve üç sayı birden oynuyor. kuş sorgusu 92 belgeden 91 belgeye iniyor; bu belge artık kümede yok. martı sorgusu 0 belgeden 1 belgeye çıkıyor. Buraya kadar beklenen davranış budur.

Üçüncü sayı beklenmeyendir. Belgenin değişmeyen bir terimi olan üzerine sorgusunda kayıt 7. sıradan 509. sıraya düşüyor. Metninde o terim bakımından hiçbir şey değişmediği hâlde sıranın sonuna gitmesinin nedeni iç kimliktir: güncelleme yeni bir iç kimlik verir, yeni kimlik en büyüktür ve gönderi listeleri kimlik sırasında tutulduğu için yeni giriş listenin sonuna eklenir. Bir yazım hatasının düzeltilmesi, o belgenin bütün sonuç listelerindeki yerini değiştirir.

Son satır ölü girişin fiyatını gösteriyor. kuş gönderi listesi hâlâ 92 giriş taşıyor; sorgu bunların 92’sini de okuyor, 1 tanesini eleyip 91 belge döndürüyor. Silinen belge dizinden gitmiyor, yalnız sonuçtan eleniyor. Silme işareti bunun karşılığında çok ucuzdur: 600 belgede 75 bayt, iç kimlik başına bir bit.

Turlar ve Temizlik

Üçüncü bölüm aynı deponun altı tur boyunca ne yaptığını izliyor. Her tur 60 güncelleme, 20 silme ve 20 ekleme uyguluyor; yani turun 80 işlemi dizine ölü giriş bırakıyor. Birinci turun sonunda dizin 16.679 girişin 1.996’sını (%12) ölü taşıyor ve 119.722 bayttan 136.322 bayta çıkmış oluyor. Canlı belge sayısı hâlâ 600’dür — büyümenin tamamı israftır.

İkinci turda oran %21’e çıkıyor ve eşik aşıldığı için dizin canlı belgelerden yeniden yazılıyor: 152.731 bayt 121.883 bayta iniyor, 30.848 bayt geri alınıyor. Aynı döngü beşinci turda tekrarlanıyor; orada oran %26’ya, dizin 171.342 bayta kadar çıkmış oluyor ve temizlik onu 127.720 bayta indiriyor. Dördüncü turda oran %19’da kaldığı için temizlik yapılmıyor ve 3.699 ölü giriş bir tur daha taşınıyor: eşik, israfın ne kadar biriktirileceğine dair bir karardır.

Altı turun sonunda depo 635 canlı belge tutuyor ve 144.785 bayt yer kaplıyor. Başlangıçtaki 600 belge 119.722 bayt tutuyordu; belge sayısı %6 artarken dizin %21 büyümüştür. Aradaki fark bir sonraki temizliğe kadar taşınacak olan 1.758 ölü giriştir. Silme ve güncelleme dizinde ücretsiz değildir: bedelleri anında değil, turlar boyunca birikerek ödenir.

Özet

• Ters dizinde güncelleme yerinde düzeltme değildir: eski iç kimlik ölü işaretlenir, yeni metin yeni bir iç kimlikle sona eklenir. Silme ise yalnız işaret koyar.
• Silme işareti ucuzdur — 600 belge için 75 bayt, iç kimlik başına bir bit — ama işaretlediği girişler dizinde durmaya devam eder: kuş sorgusu 92 girişi okuyup 91 belge döndürür.
• Güncelleme kümeyi ve sırayı birlikte değiştirir: #10 numaralı belge kuş kümesinden çıkar, martı kümesine girer ve hiç değişmeyen üzerine sorgusunda 7. sıradan 509. sıraya düşer.
• Ölü girişler tur tur birikir: 100 işlemde dizin 119.722 bayttan 136.322 bayta çıkar ve girişlerin %12’si ölüdür; eşik aşıldığında yeniden yazma 152.731 baytı 121.883 bayta indirir.
• Altı turun sonunda belge sayısı %6 artarken dizin %21 büyümüştür; aradaki fark bir sonraki temizliğe kadar taşınan 1.758 ölü giriştir.

Sonraki Adım

Bu konu dizini baştan sona kurdu: metin terime çevrildi, terimden belgeye eşleyen yapı yazıldı, alanların tipi kararlaştırıldı ve belge dizine girip çıkabilir duruma geldi. Sorgu tarafında ise tek bir kalıp kullanıldı. Bu konuda sorulan her soru çıplak terimlerden oluştu ve terimler tek bir kuralla — hepsinin birden bulunması koşuluyla — birleştirildi. Bir koşulun isteğe bağlı olması, bir koşulun belgeyi dışlaması, iki sözcüğün yan yana aranması ya da bir yıl aralığının verilmesi hiç sorulmadı. Sonucun hangi sırayla döneceği de hiç seçilmedi: sıra her seferinde gönderi listesinin kendi düzeniydi ve bu dersin son ölçüsü o düzenin ne kadar rastlantısal olduğunu gösterdi. Sonraki konu buradan başlıyor — koşulların nasıl birleştiği, sonucun hangi ölçüye göre sıralandığı ve her iki kararın kümeyle sırayı nasıl değiştirdiği.