22. Qidiruv algoritmlarida indekslash nima?

40. saralashga asoslangan blok indekslash algoritmi (blocked sort-based indexing), yoki BSBI vazifasi.
Kutilgan tezlikka erishish uchun saralash vaqtida bunday algoritm disk bo'ylab disk kallakchasining tasodifiy harakatlanish sonini minimallashtirishi kerak - natijada ma'lumotlarni o'qish tezlashadi. Ushbu muammoning echimlaridan biri bu saralashga asoslangan blok indekslash algoritmi (blocked sort-based indexing), yoki BSBI, 4.2-rasmda ko’rsatilganidek. BSBI algoritmi 1) to'plamni teng qismlarga ajratadi; 2) har bir qismning "termID-docID" juftlarini xotirada saralaydi, 3) oraliq tartiblangan natijalarni diskka saqlaydi va 4) barcha oraliq natijalarni yakuniy indeksga birlashtiradi.
BSBIndexConstruction ()
1 n←0 
2 while (barcha hujjatlar ko’zda tutilmagan) 
3 do n←n + 1 
4 block←ParseNextBlock () 
5 BSBI - Invert (block) 
6 WriteBlockToDisk(block, f_n) 
7 MergeBlocks (f₁, ...,f_n,f_merged) 
4.2-rasm. Saralashga asoslangan blok indeksatsiyasi.
Ushbu algoritm sanoqdan o’tkazilgan blokni f₁, ...,f_n fayllarida va birlashtirilgan
indeksni f_merged faylda saqlaydi.
Algoritm hujjatlardan "termID-docID" juftlarini hosil qiladi va ularni belgilangan o'lchamdagi blok to'ldirilguncha xotirada yig’adi (4.2-rasmda ParseNextBlock funktsiyasi). Blok xotiraga sig'adigan va tez saralashga imkon beradigan darajaga keltiriladi. Keyin blok sanoqdan o’tkaziladi va diskka yoziladi. Inventrlash(inversion) ikki bosqichda amalga oshiriladi. Dastlab, "termID-docID" juftlari saralanadi. Ikkinchidan, bir xil identifikatorli termID-larga ega bo'lgan barcha "termID-docID" juftlari sanoq ro'yxati hosil qiladi va faqat hujjatning docID-si so’zning joylashuvi (posting) sifatida ishlaydi. O'qiladigan blok uchun sanoq indeksi bo'lgan natija diskka yoziladi. Ushbu algoritmni Reuters-RTVl kollektsiyasiga tatbiq etish va biz tezkor xotiraga 10 million “termID-docID” juftligini sig'dira olamiz deb hisoblasak, biz o'nta blokni olamiz, to'plamning bir qismiga ularning har biri teskari indeks sanaladi.
BSBI va SPIMI algoritmlarining farqi shundaki, SPIMI yozuvlarni to'g'ridan-to'g'ri sanoq ro'yxatiga qo'shadi (10-qator). Barcha docID nomlangan juftlarini yig'ish va keyin ularni saralash o'rniga (BSBI algoritmida qilingani kabi) SPIMI algoritmida har bir sanoq ro'yxat dinamik (ya'ni uning hajmi kerak bo'lganda kattalashadi) va darhol yozuvlarni saqlash mumkin bo’ladi. Ushbu yondashuvning ikkita afzalligi bor: u tezkorroq, chunki u saralashni o'z ichiga olmaydi va xotirani tejaydi, chunki u atamaning tegishli sanoq ro'yxat bilan bog'liqligini kuzatib boradi va ushbu ro'yxatlar uchun termID identifikatorlarini saqlashga hojat yo'q.