Terim ve İfade Sorguları

Önceki ders bileşik sorguyu bir ağaç olarak kurdu ve terimler arasındaki ilişkiyi “aynı belgede geçsin” düzeyinde bıraktı. Katalog sorularının bir bölümü bundan fazlasını ister. Bir okur kitabın tam adını hatırlamıyor, ama iki sözcüğün yan yana geçtiğini biliyor. “Eleştirel deneme” ile “eleştirel bir deneme” aynı iki terimi taşır; ilkinde terimler bitişiktir, ikincisinde araya bir sözcük girmiştir. Belge düzeyinde bakan bir sorgu ikisini ayırt edemez — üstelik terimlerin cümlenin iki ucunda durduğu, aralarında hiçbir ilgi bulunmayan belgeleri de aynı kümeye koyar.

İfade sorgusu (phrase query) bu ayrımı yapar: terimlerin yalnız varlığını değil, konumlarını da koşula çevirir. Ters dizinin gönderi listelerinde tutulan konum bilgisi tam olarak bunun içindir ve şimdiye kadar hiç kullanılmadı. Kayma payı (slop) ise koşulu gevşetir: aradaki fazladan sözcüklere izin verir. Bu ders üç sayıyı birlikte ölçer — ifadenin daralttığı küme, kayma payının geri getirdiği belgeler ve konum bilgisinin dizine ödettiği bedel.

Derlem ve Kayma Payı Tanımı

Derlem önceki dersteki modüldür: 6.000 kitap kaydı, tohum 271828, belirlenimli üretim. SI4 (varsayım): kayma payı, iki terim arasındaki fazladan sözcük sayısıdır; terimler sorgudaki sırayla eşleşiyorsa aradaki sözcük sayısı, ters sırada eşleşiyorsa bu sayıya iki eklenir — bir terimin ötekinin diğer yanına geçmesi iki adım sayılır. Ölçülen ifade iki terimlidir; daha uzun ifadeler aynı kuralın ardışık uygulanmasıdır.

// 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 };
}

Ölçüm

SI5 (varsayım): dizin boyutu, gönderi listelerinin değişken uzunluklu tamsayı kodlamasıyla hesaplanır: belge numaraları ve konumlar farklarıyla yazılır, her sayı büyüklüğüne göre 1–4 bayt tutar, sözlükte terim adı artı bir bayt sayılır. Konumsuz dizinde belge farkı ve terim sıklığı, konumlu dizinde ayrıca konum farkları yazılır.

// ifade.mjs — terim sorgusu ile ifade sorgusu. Ayni dizinde derlem.mjs bulunur.
// Kayma payi: iki terim arasindaki fazladan sozcuk sayisi; terimler ters sirada
// eslesiyorsa bu sayiya iki eklenir. Olculen ifade iki terimlidir.
import { KATALOG, TOHUM, tersDizin } from "./derlem.mjs";
const { g } = tersDizin(["ad", "ozet", "etiket"]);
const liste = (alan, terim) => g.get(`${alan}|${terim}`) ?? new Map();

function enYakin(k1, k2, s) {                      // iki konum dizisi arasindaki en kucuk maliyet
  let en = Infinity;
  for (const a of k1) for (const b of k2) { s.konum += 1; en = Math.min(en, b > a ? b - a - 1 : a - b + 1); }
  return en;
}
function ifadeSorgusu(alan, t1, t2, kayma, s) {
  const l2 = liste(alan, t2), sonuc = [];
  for (const [d, k1] of liste(alan, t1)) {
    const k2 = l2.get(d);
    if (k2 && enYakin(k1, k2, s) <= kayma) sonuc.push(d);
  }
  return sonuc;
}
const vb = (n) => (n < 128 ? 1 : n < 16384 ? 2 : n < 2097152 ? 3 : 4);   // degisken uzunluklu tamsayi
function dizinBayt(konumlu) {
  let b = 0;
  for (const [anahtar, l] of g) {
    b += Buffer.byteLength(anahtar) + 1;
    let onceki = 0;
    for (const [d, konum] of l) {
      b += vb(d - onceki) + vb(konum.length); onceki = d;
      if (konumlu) { let p = 0; for (const k of konum) { b += vb(k - p); p = k; } }
    }
  }
  return b;
}
const yaz = (ad, n, ek) => console.log(`${ad.padEnd(30)} ${String(n).padStart(4)} belge   ${ek}`);

console.log(`derlem ${KATALOG.length} belge, tohum ${TOHUM}`);
console.log(`ozet|eleştirel ${liste("ozet", "eleştirel").size} belge, ozet|deneme ${liste("ozet", "deneme").size} belge`);
const terim = [...liste("ozet", "eleştirel").keys()].filter((d) => liste("ozet", "deneme").has(d));
yaz("terim sorgusu, ikisi de gecsin", terim.length, `${" ".repeat(28)}okunan konum     0`);
let onceki = 0;
for (const kayma of [0, 1, 2, 3, 4]) {
  const s = { konum: 0 };
  const k = ifadeSorgusu("ozet", "eleştirel", "deneme", kayma, s);
  yaz(`ifade sorgusu, kayma payi ${kayma}`, k.length,
    `giren ${String(k.length - onceki).padStart(3)}   disarida ${String(terim.length - k.length).padStart(4)}   ` +
    `okunan konum ${String(s.konum).padStart(5)}`);
  onceki = k.length;
}
const konumsuz = dizinBayt(false), konumlu = dizinBayt(true);
console.log(`dizin bayt   konumsuz ${konumsuz}   konumlu ${konumlu}   artis %${((konumlu / konumsuz - 1) * 100).toFixed(1)}`);

// Sira: ayni kume, iki olcut. Terim kumesi bitisiklik uzakligina gore siralanir.
const s1 = { konum: 0 }, uzaklik = new Map();
for (const d of terim) uzaklik.set(d, enYakin(liste("ozet", "eleştirel").get(d), liste("ozet", "deneme").get(d), s1));
const yakinSira = [...terim].sort((a, b) => uzaklik.get(a) - uzaklik.get(b) || a - b);
const bitisik = (l) => l.slice(0, 10).filter((d) => uzaklik.get(d) === 0).length;
console.log(`ilk on sonucta bitisik eslesme: dizin sirasinda ${bitisik(terim)}, uzakliga gore ${bitisik(yakinSira)}`);
const uzak = terim.find((d) => uzaklik.get(d) > 4);
console.log(`bitisik  ${KATALOG[yakinSira[0]].id}: ${KATALOG[yakinSira[0]].ozet}`);
console.log(`uzak     ${KATALOG[uzak].id} (uzaklik ${uzaklik.get(uzak)}): ${KATALOG[uzak].ozet}`);

derlem 6000 belge, tohum 271828
ozet|eleştirel 1487 belge, ozet|deneme 2983 belge
terim sorgusu, ikisi de gecsin  757 belge                               okunan konum     0
ifade sorgusu, kayma payi 0     144 belge   giren 144   disarida  613   okunan konum   869
ifade sorgusu, kayma payi 1     230 belge   giren  86   disarida  527   okunan konum   869
ifade sorgusu, kayma payi 2     303 belge   giren  73   disarida  454   okunan konum   869
ifade sorgusu, kayma payi 3     377 belge   giren  74   disarida  380   okunan konum   869
ifade sorgusu, kayma payi 4     377 belge   giren   0   disarida  380   okunan konum   869
dizin bayt   konumsuz 216480   konumlu 330578   artis %52.7
ilk on sonucta bitisik eslesme: dizin sirasinda 1, uzakliga gore 10
bitisik  K-0069: tarih alanında eleştirel deneme; bellek ve eğitim üzerine tartışmalı bir inceleme olarak okunabilir.
uzak     K-0002 (uzaklik 8): bilim alanında eleştirel bir anlatı; müzik ve savaş üzerine kapsamlı bir deneme olarak okunabilir.

Küme: İfade Terim Sorgusunun Beşte Birini Bırakır

“Eleştirel” 1.487 özette, “deneme” 2.983 özette geçer; ikisinin birden geçtiği belge sayısı 757’dir. Bitişik ifade koşulu bu kümeyi 144 belgeye indirir — terim sorgusunun %19,0’ı. Dışarıda kalan 613 belge terimlerin ikisini de taşır, ama yan yana taşımaz. Çıktının son satırı bunlardan birini gösteriyor: K-0002’nin özetinde “eleştirel” bir anlatıyı niteler, “deneme” ise cümlenin öbür ucundaki bir başka türü adlandırır; iki terimin arasındaki uzaklık 8’dir ve aralarında anlamca hiçbir bağ yoktur. Terim sorgusu bu belgeyi yanlış getirmiştir, ifade sorgusu getirmez.

Kayma payı bu koşulu adım adım gevşetir. Bir birim kayma “eleştirel bir deneme” biçimini kümeye sokar ve 86 belge girer; iki birim “eleştirel ve kuramsal deneme” biçimini sokar, 73 belge girer; üç birim ters sıradaki eşleşmeyi — “deneme ve eleştirel inceleme” — sokar ve 74 belge daha girer. Dördüncü adımda kümeye hiçbir belge girmez. Bu, kayma payını büyütmenin sürekli bir etkisi olmadığını gösterir: hangi uzaklıkların var olduğunu derlemin cümle yapısı belirler, kayma payı yalnız o basamakları açar. Bir katalog arayüzünde kayma payını 0’dan 3’e çıkarmak burada kümeyi 144’ten 377’ye, yani 2,6 katına büyütür; 4’e çıkarmak hiçbir şey değiştirmez.

Bedel: Konum Bilgisi Her Belgeden Alınır

Sorgu anındaki bedel küçüktür. İfade koşulu yalnız iki gönderi listesinin ortak belgelerinde konum okur: 757 aday belge için 869 konum karşılaştırması yapılır, çünkü belgelerin çoğunda her terim bir kez geçer ve tek çift karşılaştırılır. Kayma payı değiştiğinde bu sayı değişmez — kayma payı bir eşiktir, okunan konum sayısını değil, eşiği geçen belge sayısını belirler.

Asıl bedel dizindedir. Konumsuz dizin 216.480 bayt, konumlu dizin 330.578 bayttır: %52,7 artış, 114.098 bayt fark, belge başına yaklaşık 19 bayt. Bu bedelin niteliği önemlidir — sorgu başına değil, belge başına ödenir. Konum bilgisi hiç ifade sorgusu sorulmasa da her belgede tutulur, her dizinleme sırasında yazılır, her bölüt birleştirmesinde taşınır. Karar şudur: ifade sorgusuna gerek duyulmayan bir alanda konum bilgisi kapatılabilir ve dizin üçte bir küçülür; buna karşılık o alanda ifade sorgusu artık sorulamaz, yalnız terim sorgusuyla yaklaşık bir sonuç alınır — ve o yaklaşımın hatası burada ölçülmüştür: 757’ye karşı 144.

Sıra: Uzaklık Bir Sıralama Ölçütüdür

İfade koşulu bir eşik olarak kullanıldığında küme keskin biçimde bölünür: içeride 144, dışarıda 613. Aynı uzaklık bir eşik yerine sıralama ölçütü olarak da kullanılabilir ve o zaman küme hiç daralmaz. Son ölçüm bunu gösterir: 757 belgelik terim kümesi dizin sırasında verildiğinde ilk on sonucun yalnız 1 tanesi bitişik eşleşmedir; aynı küme terimler arası uzaklığa göre sıralandığında ilk onun tamamı bitişik eşleşmedir.

İki yaklaşım arasındaki fark, bu kursun temel ayrımının en yalın örneğidir. Eşik olarak kullanılan ifade koşulu kümeyi değiştirir ve 613 belgeyi tamamen görünmez kılar; sıralama ölçütü olarak kullanılan uzaklık sırayı değiştirir ve o 613 belgeyi listenin altında bırakır. İlkinde bir belge kaçırılırsa geri dönüşü yoktur, ikincisinde kullanıcı aşağı inerse bulur. Hangisinin doğru olduğu sorunun kesinliğine bağlıdır: adı tam bilinen bir kitapta eşik, konu araması olduğunda sıralama ölçütü daha uygundur.

Özet

• İfade sorgusu terimlerin varlığını değil konumlarını koşula çevirir; 6.000 belgelik derlemde (tohum 271828) terim sorgusunun 757 belgesini 144’e indirir.
• Kayma payı koşulu basamak basamak gevşetir: 1 birim 86, 2 birim 73, 3 birim 74 belge ekler, 4 birim hiçbir belge eklemez.
• Ters sıradaki eşleşme iki adım sayılır; bu yüzden “deneme ve eleştirel inceleme” biçimi ancak kayma payı 3 olduğunda kümeye girer.
• Konum bilgisi sorgu anında ucuzdur (757 aday için 869 konum karşılaştırması), dizinde pahalıdır: 216.480 bayttan 330.578 bayta, %52,7 artış.
• Aynı uzaklık ölçüsü eşik olarak kullanıldığında kümeyi böler, sıralama ölçütü olarak kullanıldığında yalnız sırayı değiştirir: ilk ondaki bitişik eşleşme 1’den 10’a çıkar.

Sonraki Adım

Şimdiye kadar kurulan koşulların hepsi aynı türdendi: sağlanmayan belge kümeden düşer. Katalog soruları bu kadar tek biçimli değildir. “Çocuk etiketli olsun” zorunlu bir koşuldur; “almanca olmasın” kümeyi daraltan ama tersinden çalışan bir koşuldur; “özetinde ‘resimli’ geçenler üstte olsun” ise hiçbir belgeyi elemeyen, yalnız sırayı etkileyen bir istektir. Üçü de tek bir bileşik sorgunun içinde yan yana durur ve üçünün kümeye etkisi birbirinden tamamen farklıdır. Sonraki ders bu üç koşul türünü ayırır ve isteğe bağlı koşulun kümeyi bir belge bile değiştirmeden ilk on sonucu nasıl baştan yazdığını sayar.