Ters Dizin

Önceki ders ters dizini bir kara kutu olarak kullandı: terim verildi, belge kimlikleri geldi. Bu ders kutuyu açıyor. Yapı iki parçadan oluşur. Sözlük derlemdeki her ayrı terimi bir kez tutar ve her terimin karşısına o terimin listesini gösteren bir bağ koyar. Gönderi listesi ise o terimin geçtiği belgelerin kaydıdır: her giriş bir belgeyi bildirir.

Bu kursta gönderi, bir terimin belirli bir belgede geçtiğini bildiren dizin kaydıdır. Sözcük başka bir müfredatta yayımlanan bir iletiyi de adlandırıyor; buradaki kullanımla ilgisi yoktur. Bir gönderi girişi en az belge kimliğini taşır, isteğe bağlı olarak terimin o belgede kaç kez geçtiğini (terim sıklığı) ve nerelerde geçtiğini (konum) da taşıyabilir. Bu üç bileşenin üçünün de bir fiyatı vardır ve ders bu fiyatı sayıyor.

Sözlük, Gönderi ve Konum

Sıralı bir dizin değerin tamamı üzerinde kuruludur ve bir kayıttan bir değere gider; ters dizin bunun tersine bir terimden bir belge kümesine gider, bu yüzden aynı belge onlarca gönderi listesinde birden görünür. Fark tek cümlede budur ve dizin boyutunu belirleyen de budur: dizinin büyüklüğü belge sayısıyla değil, belge başına düşen ayrı terim sayısıyla ölçeklenir.

DC1: derlem önceki dersteki derlemdir — 600 kitap kaydı, tohum 20250317. DC2: bayt hesabı şu sabitlerle yapılır — sözlük girişi terimin UTF-8 baytı artı 8 bayt (belge sıklığı ve liste göstergesi), gönderi girişi 4 bayt belge kimliği, terim sıklığı tutuluyorsa 4 bayt daha, her konum 4 bayt. DC3: dizinlenen metin ad ve ozet alanlarının birleşimidir; önceki ders yalnız ozet alanını dizinlediği için terim sayısı orada farklıdır.

// 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/dizin-olcum.mjs — ayni derlem uc dizin bicimiyle kurulur: yalniz kimlik, kimlik+siklik,
// kimlik+siklik+konum. Terim, gonderi girisi, bayt, taranan giris ve karsilastirma sayilir.
import { derlem, BELGE, TOHUM } from "./katalog.mjs";
import { TersDizin } from "./dizin.mjs";

const metin = (b) => `${b.ad} ${b.ozet}`;                  // DC3: dizinlenen alanlar
const kaynak = derlem.reduce((t, b) => t + Buffer.byteLength(metin(b)), 0);
const kur = (ayar) => { const d = new TersDizin(ayar); for (const b of derlem) d.ekle(b.id, metin(b)); return d; };
const bicim = [["yalniz kimlik", { siklik: false, konum: false }],
  ["kimlik + siklik", { siklik: true, konum: false }], ["kimlik + siklik + konum", {}]];

console.log(`tohum ${TOHUM}; derlem ${BELGE} belge, dizinlenen metin ${kaynak} bayt`);
console.log(`${"dizin bicimi".padEnd(24)}${"terim".padStart(7)}${"gonderi".padStart(9)}${"konum".padStart(7)}` +
  `${"sozluk".padStart(8)}${"gonderi bayt".padStart(14)}${"konum bayt".padStart(12)}${"toplam".padStart(9)}${"metne oran".padStart(12)}`);
let tam;
for (const [ad, ayar] of bicim) {
  const d = kur(ayar), b = d.bayt();
  tam = d;
  console.log(ad.padEnd(24) + String(b.terim).padStart(7) + String(b.giris).padStart(9) + String(b.konum).padStart(7) +
    String(b.sozluk).padStart(8) + String(b.gonderi).padStart(14) + String(b.konumBayt).padStart(12) +
    String(b.toplam).padStart(9) + `%${(b.toplam * 100 / kaynak).toFixed(1)}`.padStart(12));
}

const ilk = tam.liste("deniz").slice(0, 3).map((g) => `(#${g.id}, tf ${g.tf}, konum ${g.konum.join("-")})`);
console.log(`\n"deniz" gonderi listesi ${tam.liste("deniz").length} giris; ilk ucu: ${ilk.join(" ")}`);
const tfDagilim = new Map();
for (const g of tam.liste("deniz")) tfDagilim.set(g.tf, (tfDagilim.get(g.tf) ?? 0) + 1);
console.log(`terim sikligi dagilimi: ${[...tfDagilim].sort().map(([t, n]) => `tf ${t} -> ${n} belge`).join(", ")}`);

// sirasiz liste ile karsilastirma: her giris icin obur listede dogrusal arama
const sirasiz = (...t) => {
  const l = t.map((x) => tam.liste(x)), en = l.reduce((a, x) => (x.length < a.length ? x : a));
  let k = 0;
  const kume = en.filter((g) => l.every((x) => { for (const y of x) { k += 1; if (y.id === g.id) return true; } return false; }));
  return { n: kume.length, k };
};
console.log(`\n${"sorgu".padEnd(20)}${"taranan giris".padStart(14)}${"kimlik sirali".padStart(14)}` +
  `${"sirasiz".padStart(9)}${"donen belge".padStart(12)}${"ilk uc kimlik".padStart(15)}`);
for (const s of [["deniz"], ["çocuk"], ["deniz", "çocuk"], ["deniz", "çocuk", "kitap"]]) {
  const r = tam.ara(...s), y = s.length > 1 ? String(sirasiz(...s).k) : "-";
  console.log(s.join("+").padEnd(20) + String(r.giris).padStart(14) + String(r.kars).padStart(14) +
    y.padStart(9) + String(r.kume.length).padStart(12) + r.kume.slice(0, 3).join(",").padStart(15));
}

// konum bilgisi ne satin aliyor: ayni belgede gecmek ile yan yana gecmek
const [a, b] = ["deniz", "günleri"];
const ikinci = new Map(tam.liste(b).map((g) => [g.id, g.konum]));
const ardisik = tam.liste(a).filter((g) => ikinci.has(g.id) &&
  g.konum.some((x) => ikinci.get(g.id).some((y) => y - x === 1))).map((g) => g.id);
console.log(`\n"${a} ${b}": ayni belgede ${tam.ara(a, b).kume.length}, ardisik ${ardisik.length} belge ` +
  `(${ardisik.slice(0, 3).map((i) => `#${i} ${derlem[i - 1].ad}`).join(", ")})`);

tohum 20250317; derlem 600 belge, dizinlenen metin 135824 bayt
dizin bicimi              terim  gonderi  konum  sozluk  gonderi bayt  konum bayt   toplam  metne oran
yalniz kimlik               185    14609      0    2850         58436           0    61286       %45.1
kimlik + siklik             185    14609      0    2850        116872           0   119722       %88.1
kimlik + siklik + konum     185    14609  16565    2850        116872       66260   185982      %136.9

"deniz" gonderi listesi 261 giris; ilk ucu: (#3, tf 1, konum 0) (#4, tf 1, konum 14) (#7, tf 1, konum 14)
terim sikligi dagilimi: tf 1 -> 206 belge, tf 2 -> 52 belge, tf 3 -> 3 belge

sorgu                taranan giris kimlik sirali  sirasiz donen belge  ilk uc kimlik
deniz                          261           261        -         261          3,4,7
çocuk                           84            84        -          84          5,6,8
deniz+çocuk                    345           470    19622          25        8,67,77
deniz+çocuk+kitap              452           630    22135           3    158,309,491

"deniz günleri": ayni belgede 23, ardisik 10 belge (#3 Deniz Günleri, #123 Büyük Deniz Günleri, #154 Beyaz Deniz Günleri)

Üç Biçim, Üç Fiyat

İlk tablo aynı 600 belgeyi üç kez dizinliyor ve tek değişen şey gönderi girişinin ne taşıdığı. Sözlük üçünde de aynıdır: 185 terim, 2.850 bayt. Dizinin ağırlığı sözlükte değil, 14.609 gönderi girişindedir. Yalnız belge kimliği tutulduğunda dizin 61.286 bayt, kaynak metnin %45,1’i kadardır. Terim sıklığı eklendiğinde gönderi bölümü tam iki katına çıkar ve dizin 119.722 bayta, metnin %88,1’ine ulaşır. Konum eklendiğinde 185.982 bayta, yani metnin kendisinden büyüğe çıkar.

Bu son satır dersin en somut sonucudur: konum tutan bir ters dizin, dizinlediği metinden daha çok yer kaplayabilir. Nedeni ikinci ve üçüncü sütunda görünüyor — 14.609 gönderi girişine karşılık 16.565 konum kaydı var, çünkü bir terim aynı belgede birden çok kez geçebiliyor. deniz teriminin sıklık dağılımı bunu açıkça sayıyor: 206 belgede bir kez, 52 belgede iki kez, 3 belgede üç kez.

Sıra Bir Karardır

Gönderi listeleri belge kimliği sırasında tutuluyor ve bu bir tercih değil, kesişimin çalışma biçimini belirleyen bir karardır. deniz+çocuk sorgusu 261 ve 84 girişlik iki listeyi okuyor, toplam 345 giriş. İki liste de sıralı olduğu için kesişim tek geçişte yapılıyor ve 470 karşılaştırma yetiyor. Aynı kesişim listeler sırasız olsaydı, kısa listenin her girişi için uzun listede baştan arama gerekirdi: 19.622 karşılaştırma, kırk kat fazla. Üç terimli sorguda oran 630’a karşı 22.135 olur.

Sıranın ikinci sonucu dönen kümededir. deniz tek başına 261 belge, çocuk 84 belge döndürüyor; ikisinin kesişimi 25 belgeye, üçüncü terim eklendiğinde 3 belgeye iniyor. Her koşul kümeyi daraltıyor ve daraltmanın bedeli okunan giriş sayısının artmasıdır: 345’ten 452’ye. Dönen belgeler 8, 67, 77 sırasıyla geliyor; bu sıra yine belge kimliğidir, yani belgelerin dizine giriş sırasıdır. Kimin daha ilgili olduğu hâlâ sorulmuyor.

Konumun Satın Aldığı

Konum bilgisi dizinin en pahalı bileşenidir — tek başına 66.260 bayt, dizinin %35,6’sı. Karşılığında tek bir şey satın alır: iki terimin belgede yan yana geçip geçmediğini bilmek. Son satır bunu sayıyor. deniz ve günleri terimleri 23 belgede birlikte geçiyor; bu belgelerin yalnız 10’unda iki terim ardışıktır ve o 10 belgenin adı gerçekten Deniz Günleri kalıbındadır. Konum tutmayan bir dizin bu iki kümeyi ayırt edemez ve 23 belgenin tamamını döndürür.

Karar şu biçimde konur: 66.260 bayt karşılığında 13 belgelik bir daralma satın alınıyor. Katalog aramasında bu daralmanın değerli olup olmadığı sorunun türüne bağlıdır — tam adı bilinmeyen bir kitabı iki sözcüğüyle arayan okur için ardışıklık ayrımı doğrudan doğru sonucu verir. Bu ayrımı kullanan sorgu biçimi ikinci konuda kuruluyor; bu ders yalnız verinin dizinde durduğunu ve ne tuttuğunu gösteriyor.

Özet

• Ters dizin iki parçadır: sözlük (185 terim, 2.850 bayt) ve gönderi listeleri (14.609 giriş). Ağırlık gönderi tarafındadır; sözlük dizinin %1,5’i kadardır.
• Gönderi girişinin içeriği fiyatı belirler: yalnız kimlik 61.286 bayt (metnin %45,1’i), terim sıklığı eklenince 119.722 bayt (%88,1), konum eklenince 185.982 bayt (%136,9) — dizin kaynak metinden büyük olur.
• 14.609 gönderi girişine 16.565 konum kaydı düşer; deniz terimi 206 belgede bir, 52 belgede iki, 3 belgede üç kez geçer.
• Gönderi listelerinin belge kimliği sırasında tutulması kesişimi tek geçişe indirir: deniz+çocuk 470 karşılaştırmayla, sırasız listede 19.622 karşılaştırmayla biter.
• Konum bilgisi 66.260 bayta mal olur ve deniz günleri sorusunda kümeyi 23 belgeden 10 belgeye indirme yeteneğini satın alır.

Sonraki Adım

Bu dersin dizini metni tek bir kuralla sözcüklere ayırdı: harf ve rakam dışındaki her karakterde böl, Türkçe kurallarıyla küçük harfe indir. Bu kuralın kendisi hiç sorgulanmadı. Oysa denizler ile deniz bu kural yüzünden iki ayrı terim ve ilk dersteki 43 belgelik kayıp buradan geliyordu. Sonraki ders aynı derlemi üç ayrı çözümleyici zinciriyle dizinliyor — ham, küçük harfe indiren, kök bulan ve durak sözcük atan — ve aynı sorguyu üçünde koşturuyor: dönen küme, sıralama ve dizin boyutu üç yapılandırmada yan yana ölçülüyor.