5. Ma’ruza. Axborot izlash tizimlarida indeks yaratish

Download 30.46 Kb.
bet	8/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. 4.3. Xotirada bir martalik indekslash 4.3. Bir martalik xotirada indekslash Saralashga asoslangan blok indeksatsiyasi mukammal miqyosga ega, ammo uni amalga oshirish uchun har bir atama termID identifikatori bilan bog'lanishi kerak. Juda katta to'plamlar uchun kerakli ma'lumotlar tuzilishi xotiraga sig'masligi mumkin. Miqyos jihatidan samaraliroq - bu bir martalik xotirada indekslash yoki SPIMI algoritmi. Ushbu algoritmda ularning identifikatorlari emas, balki atamalar qo'llaniladi, har bir blokning lug'atini diskka yozadi va keyin yangi blok uchun yangi lug'at yaratishni boshlaydi. Agar sizda disk maydoni etarli bo'lsa, SPIMI algoritmidan istalgan o'lchamdagi to'plamni indekslash uchun foydalanishingiz mumkin. SPIMI algoritmi shakl. 4.4. Algoritmning hujjatlarni ajratib ko'rsatadigan qismi va ularni termin-docID juftlari oqimiga aylantiradigan qismi, bu erda biz ushbu belgilarda belgi deb ataymiz. SPIMI-Invert funktsiyasi butun to'plam qayta ishlanguncha tokenlar oqimiga qayta-qayta qo'llaniladi. SPIMI-Invert Uoken_stream) 1 outputJUe Shakl: 4.4. Xotirada bir martalik indekslashni ishlatib blokirovka inversiyasini amalga oshirish. Tokenlar navbat bilan qayta ishlanadi (4-qator). Termin bilan birinchi marta uchrashganda, u lug'atga qo'shiladi (xash lug'at uchun eng yaxshi dastur hisoblanadi) va yangi teskari ro'yxat tuziladi (6-qator). 7-qatorda qo'ng'iroq ushbu teskari ro'yxatni muddatning keyingi takrorlanishi uchun qaytaradi. BSBI va SPIMI algoritmlarining farqi shundaki, SPIMI yozuvlarni to'g'ridan-to'g'ri teskari ro'yxatga qo'shadi (10-qator). Barcha nomlangan docID juftlarini yig'ish va keyin ularni saralash o'rniga . Qisqacha aytganda, ushbu kamchilik (global lug'atga ehtiyoj) quyida tavsiflangan SPIMI algoritmining asosiy xususiyatidan (so'zlarning joylarini terminlardan ajratish) to'liq mustaqil va mustaqil ravishda bartaraf etilishi mumkin. -- Eslatma. tahrir. suv ombori BSBI algoritmi). SPIMI algoritmida har bir teskari ro'yxat dinamik (ya'ni uning hajmi kerak bo'lganda kattalashadi) va darhol yozuvlarni saqlash uchun mavjud bo'ladi. Ushbu yondashuvning ikkita afzalligi bor: u tezroq, chunki u saralashni o'z ichiga olmaydi va xotirani tejaydi, chunki u atamaning tegishli teskari ro'yxat bilan bog'liqligini kuzatib boradi va ushbu ro'yxatlar uchun lermlD identifikatorlarini saqlashga hojat yo'q. Natijada, SPIMI-Invert funktsiyasi qo'llaniladigan bloklar ancha kattaroq bo'lishi mumkin va umumiy indekslarni kompilyatsiya qilish jarayoni samaraliroq bo'ladi. Birinchi marta tanishganimizda muddat uchun teskari ro'yxat qancha bo'lishini bilmasligimiz sababli, avvaliga qisqa vaqt uchun xotira ajratamiz teskari ro'yxat, so'ngra har safar to'ldirgandan so'ng uni ko'paytiramiz (8 va 9- qatorlar) .3 Bu shuni anglatadiki, ba'zi bir xotira yo'qoladi va qidiruv ma'lumotlar tuzilmalarida termin identifikatorlarini e'tiborsiz qoldirib xotirani saqlash mumkin bo'lmaydi. Shu bilan birga, SPIM1 algoritmida dinamik ravishda qurilgan blok indeksining umumiy xotirasi talablari BSBI algoritmiga qaraganda pastroq. Xotiramiz tugagandan so'ng biz blok indeksini (lug'at va teskari ro'yxatlardan iborat) diskka yozamiz (12-qator). Biroq, bundan oldin, atamalar saralanishi kerak (II satr), chunki teskari ro'yxatlar leksikografik tartibda yozilishi kerak. Bu birlashuvning yakuniy bosqichini bajarishni osonlashtiradi. Agar har bir blokning teskari ro'yxatlari tartibsiz yozilgan bo'lsa, har bir blokni bitta ketma-ket izlashda bloklarni birlashtirish mumkin bo'lmaydi. Har bir qo'ng'iroqda SPIMI-Invert funktsiyasi, xuddi BSBI algoritmida bo'lgani kabi, blokni diskka yozadi. SPIMI algoritmining so'nggi bosqichida (7-qatorga to'g'ri keladi) Anjir. 4.2 va shaklda ko'rsatilmagan. 4.4), bloklar oxirgi teskari indeksga birlashtiriladi. Har bir blok uchun yangi lug'at tuzilishini yaratish va qimmat saralash bosqichini yo'q qilishdan tashqari, SPIMI algoritmi yana bir muhim xususiyatga ega: siqishni4. Agar siz siqishni qo'llasangiz, unda so'zlarni aniqlash va so'z birikmalarining ikkalasi ham diskda ixcham saqlanishi mumkin. Siqish algoritm samaradorligini yanada oshiradi, chunki u kattaroq bloklarni qayta ishlashga imkon beradi va diskdagi alohida bloklarni saqlash uchun xotirani tejaydi. Algoritmning ushbu jihati adabiyotlarda batafsil tavsiflangan Download 30.46 Kb.

Download 30.46 Kb.