--- title: 'Ters Dizin' source: 'https://academia.sh/tr/kurslar/arama-motorlari/ters-dizin' course: 'Arama Motorları ve Metin Erişimi' language: tr updated: '2026-08-17T18:09:01+00:00' license: 'CC BY-SA 4.0' --- # Ters Dizin Terimden belgeye eşleyen yapının kuruluşu ve bayt hesabı: sözlük ile gönderi listesinin ayrımı, gönderi girişinde belge kimliği, terim sıklığı ve konum bilgisinin ayrı ayrı fiyatlanması, dizinin kaynak metne oranının üç biçimde ölçülmesi, gönderi listelerinin belge kimliği sırasında tutulmasının kesişim maliyetine etkisi ve konum bilgisinin satın aldığı ardışıklık ayrımı. Ö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. ```js // 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)}`, }); } ``` ```js // 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 }; } } ``` ```js // 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.