5. Ma’ruza. Axborot izlash tizimlarida indeks yaratish

Download 30.46 Kb.
bet	4/8
Sana	25.03.2023
Hajmi	30.46 Kb.
	#46649

Bog'liq
5-ma\'ruza
xudo xoxlasa tushadi99%, 3-labarotoriya ishi Saralash usul va algoritmlarini tadqiq qilis, cmd buyruqlari, Incremental model nima, 1matematik, word sAM 1 savol, Документ Microsoft Word (4), Ma\'ruzalar (2), ЛАБОРАТОРНАЯ РАБОТА N1, Dasturlash 2, Ariza, Qalandarova Gulshoda, 1648631455, 1650692784, 1651669892 (2)

4.2.-jadval. Reuters-RTV1 to'plamining xususiyatlari. Ushbu kitobda hisoblashga qulayl bo’lishi uchun qiymatlar yaxlitlangan. Yaxlitlanmagan qiymatlar quyidgilar: 806 791 ta hujjat, har bir hujjat uchun 222 ta jeton, 391 523 ta (har xil) atamalar, bo'shliq va tinish belgilari bilan har bir jetonda 6,04 bayt, bo'sh joy yoki tinish belgilarisiz 4,5 bayt, atamalar uchun 7,5 bayt va 96 969 056 jeton uchun. Ushbu jadvaldagi raqamlar jadvalning uchinchi qatoriga to'g'ri keladi. 5.1 ("registr hisobga olinmagan"). Belgi Ko’rsatgichlar Qiymatlar N Hujjat 800 000 L ave Hujjatdagi o’rtacha tayanch iboralar 200 M Atamalar Leksemdagi o’rtacha baytlar soni (tinish belgilari va bo’sh joylarni qo’shganda) Leksemdagi o’rtacha baytlar soni (tinish belgilari va bo’sh joylarni qo’shmaganda) Atamadagi o’rtacha baytlar soni 400 000 6 4,5 7,5 T Leksemalar 100 000 000 4.1-rasm. Agar fayllarning oraliq indekslash hajmi mavjud tezkor xotira hajmiga teng bo'lsa, muammoni 5-bobda tasvirlangan siqish texnikasi yordamida hal qilish mumkin. Ammo ko'plab yirik to'plamli fayllar siqilgandan keyin ham xotiraga sig'maydi. Agar tezkor xotira hajmi etarli bo'lmasa, tashqi tartiblash algoritmi (external sorting algorithm) kerak, ya'ni diskda qo’llaydigan algoritm. Kutilgan tezlikka erishish uchun saralash vaqtida bunday algoritm disk bo'ylab disk kallakchasining tasodifiy harakatlanish sonini minimallashtirishi kerak - natijada ma'lumotlarni o'qish tezlashadi (4.1-bo'limga qarang). 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, fn) 7 MergeBlocks (f1, ...,fn,fmerged) 4.2-rasm. Saralashga asoslangan blok indeksatsiyasi. Ushbu algoritm sanoqdan o’tkazilgan blokni f1, ...,fn 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. İnventrlash(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 “termIDdocID” juftligini sig'dira olamiz deb hisoblasak, biz o'nta blokni olamiz, to'plamning bir qismiga ularning har biri teskari indeks sanaladi. Yakuniy bosqichda algoritm bir vaqtning o'zida o'nta blokni bitta katta birlashgan indeksga birlashtiradi. Ikkita blokning namunasi 4.3-rasmda keltirilgan, bu erda to'plamdagi i hujjat di ko’rinishda belgilangan. Barcha o'nta bloklar birlashish uchun bir vaqtning o'zida ochiladi, xisoblash uchun kichik o'qiydigan buferlardan va yozish uchun yakuniy birlashtirilgan indeksni yozish buferidan foydalaniladi. Har bir takrorlashda biz hozirgacha ishlov berilmagan eng past termIDni tanlaymiz. Buning uchun ustuvor navbat yoki analog ma'lumotlar tuzilishi qo’llaniladi. Mazkur termID identifikator uchun barcha sanoq ro'yxatlar o'qiladi va birlashtiriladi, so'ngra birlashtirilgan ro'yxat diskka qayta yoziladi. Har bir o'qilgan bufer, kerak bo'lganda, fayldan olingan ma'lumotlarning keyingi qismi bilan to'ldiriladi. BSBI usuli qanchalik qimmat? Uning vaqtimchalik murakkabligi Ɵ(T logT) ga teng. Chunki eng qiyin bosqich saralash va saralanishi kerak bo’lgan elementlar soni T raqami bilan cheklangan ("termID-docID" juftliklari soni). Biroq, joriy vaqt rejimida indekslashda asosiy yordamchi odatda hujjatlarni tahlil qilish (ParseNextBlock funktsiyasi) va yakuniy birlashma (MergeBlocks funktsiyasi). 4.6-mashqda RCV1 to'plami uchun indeks yaratishga sarflangan umumiy vaqtni hisoblash so’ralgan, bloklarni sanoqdan o’tkazish va ularni diskka yozish ham kiritilgan. 4.3-rasm. Saralashga asoslangan blok indeksatsiyasida birlashish. Ikki blok (“birlashtirish kerak bo’lgan so'zlar ro'yxati") diskdan xotiraga yuklanadi, u erda birlashtiriladi ("birlashtirilgan so'zlar ro'yxati") va qayta diskka yoziladi. Yuqori aniqlik uchun termID-lar o'rniga atamalar ko'rsatilgan. Shunga etibor beringki, hozirgi zamonda Reuters-RCVl to'plami shaxsiy kompyuterlar uchun standart bir yoki bir necha gigabayt bo'lgan tezkor xotirasi katta hisoblanmaydi. Tegishli siqish bilan (5-bob) biz faqat RAMdan foydalangan holda va hatto kuchli serversiz ham RCV1 to'plamida teskari indeksni yaratishimiz mumkin. Biz ta'riflagan usullar kattaligi RCV1 kollektsiyasidan kattaroq kollektsiyalar uchun zarurdir. 4.1-mashq. Aytaylik, biz 71og2r taqqoslashlarni amalga oshirishimiz kerak, bu erda • T - "termID-docID" juftliklari soni va har bir taqqoslash ikkita disk boshini sozlashni amalga oshiradi. Agar xotira o'rniga disk ishlatilsa va saralash algoritmi suboptimal (ya'ni tashqi saralash algoritmi emas) bo'lsa, Reuters-RCVl to'plamida indeks yaratish uchun qancha vaqt kerak bo'ladi? Jadvalda ko'rsatilgan tizim parametrlaridan foydalaning. 4.1. 4.2-mashq [*]. Qo'shimcha o'tishni oldini olish uchun qanday qilib saralashga asoslangan blokirovka algoritmida lug'at yaratish mumkin? Biroq, katta blok hajmi bilan, saralash bosqichini kamaytirish mumkin emas, ayniqsa BSBI algoritmi so'zlarni emas, balki so'zlarni joylashtiradi. - Eslatma. tahrir. Download 30.46 Kb.

Download 30.46 Kb.