22. Qidiruv algoritmlarida indekslash nima?

64. Qidiruv algoritmlari va usullari haqida gapiring.

Turli xil qidiruv algoritmlari ma'lum. To'g'ridan-to'g'ri qidiruv deb nomlanadi, uning algoritmi hujjatlarni ketma-ket skanerlashga asoslangan.

To'g'ridan-to'g'ri qidirish - to'g'ridan-to'g'ri hujjatlar matnidan qidirish, dastlabki ishlovsiz (indekslashsiz). To'g'ridan-to'g'ri matn qidirish satrni ko'rib chiqishdan (chapdan o'ngga) va har bir pozitsiyani kerakli substring bilan ketma-ket taqqoslashdan iborat. Buning uchun barcha belgilar taqqoslanadi.

Boshqa algoritmlarda qidiruvni soddalashtirish va tezlashtirishga mo'ljallangan "indeks" yordamchi fayl yaratuvchi "indekslash", hujjatlarni oldindan qayta ishlash talab etiladi. Bu teskari fayllar, qo'shimchalar daraxtlari va imzolar algoritmlari.

Bir matndan qidirish so'zlarining buyurtma qilingan to'liq ro'yxati - teskari faylni olishga asoslangan qidiruv algoritmi keng qo'llaniladi. Inverted file (teskari fayl, teskari indeks, teskari ro'yxat) - qidiruv tizimining indekslari, unda hujjatlar to'plamining so'zlari keltirilgan va har bir so'z uchun u sodir bo'lgan barcha joylar keltirilgan. Qidiruv algoritmi kerakli so'zni topish va allaqachon kengaytirilgan pozitsiyalar ro'yxatini xotirasiga yuklashdan iborat

Qoida tariqasida teskari fayl siqiladi, masalan, faqat hujjat raqami va unda ushbu so'z necha marta ishlatilganligi ko'rsatilgan. Aynan shu soddalashtirilgan tuzilma axborot qidirishning klassik nazariyasida asosiy hisoblanadi. Teskari faylni siqishning ikkinchi usuli har bir so'z uchun manzillarni o'sish tartibida tartiblash va har bir pozitsiya uchun to'liq manzilini emas, balki avvalgisidan farqini saqlashni o'z ichiga oladi. Ta'riflangan usullarni qo'llash natijasida teskari fayl hajmi, qoida tariqasida, manzil detaliga qarab, asl matn hajmining 7 dan 30 foizigacha.

Teskari va to'g'ridan-to'g'ri qidirishdan tashqari algoritmlar va ma'lumotlar tuzilmalaridan foydalaniladi. Bu imzo bilan bir qatorda qo'shimchali daraxtlar. Imzo usuli - bu hujjatning so'zlarning xash qiymatlari jadvallarini blokirovka qilish uchun konvertatsiya qilish, bu "imzo" deb nomlanadi va qidirish paytida "imzolarni" ketma-ket skanerlash.

Imzo (signature, imzo) - ma'lum bir blok blokidagi so'zlarning xash qiymatlari to'plami. Imzo usuli yordamida qidirish paytida to'plamdagi barcha bloklarning imzolari ketma-ket skanerdan o'tkaziladi, so'rov so'zlarining xash qiymatlari bilan mos keladigan narsalarni qidiradi.

Qo'shimcha daraxtlar (suffix trees, suffix arrays, PAT-arrays - qo'shimchalar qatorlari, PAT-massivlar) usuli ierarxik modellar nazariyasida daraxt (trie) sifatida ma'lum bo'lgan ma'lumotlar tarkibidagi matnning barcha muhim qo'shimchalarini aks ettirishga asoslangan. Ushbu indeksdagi qo'shimchalar yordamida men matnning biron bir pozitsiyasidan boshlanadigan (matn bitta uzluksiz qator deb qaraladi) va oxirigacha davom etadigan har qanday "substring" ni nazarda tutyapman. Haqiqiy dasturlarda qo'shimchalarning uzunligi cheklangan va faqat muhim pozitsiyalar indekslangan - masalan, so'zlarning boshlanishi. Ushbu indeks teskari fayllarga asoslangan indeksga qaraganda ancha murakkab so'rovlarni amalga oshirishga imkon beradi.