22. Qidiruv algoritmlarida indekslash nima?

Hash funktsiyalari

Hashlash (inglizcha xeshdan) - bu o'zboshimchalik uzunlikdagi dastlabki ma'lumot massivini sobit uzunlikdagi bitli qatorga aylantirish.
Xash funktsiyalari uchun ko'plab algoritmlar mavjud, ammo ular xarakteristikalari bilan farq qiladi - kriptografik kuch, bit chuqurligi, hisoblash murakkabligi va boshqalar.
Kriptografik jihatdan kuchli xash funktsiyalari bizni qiziqtiradi. Odatda bu ikkita talab:

• 
  Berilgan C xabari uchun xuddi shu xash bilan boshqa C "xabarini topish deyarli mumkin emas
  
• 
  Xuddi shu xashga ega bo'lgan juft xabarlarni (SS ") topish deyarli mumkin emas.
  

Talablar navbati bilan I va II tip to'qnashuvlarga qarshilik deb ataladi. Bunday funktsiyalar uchun yana bir talab muhim bo'lib qolmoqda: argumentning ozgina o'zgarishi bilan funktsiyalarning o'zida sezilarli o'zgarishlar bo'lishi kerak. Shunday qilib, xash qiymati argumentning alohida bitlari haqida ham ma'lumot bermasligi kerak.

Xash algoritmlariga misollar

• 
  Adler-32
  
• 
  SHA-1
  
• 
  SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
  
• 
  XAVAL
  
• 
  N-xash
  
  • 
    RIPEMD-160
    
• 
  RIPEMD-256
  
• 
  RIPEMD-320
  
• 
  Skein
  
• 
  Snefru
  
• 
  Tiger (TTH)
  
• 
  Girdob
  
• 
  GOST R34.11-94 (GOST 34.311-95)
  
• 
  IP Internet summasi (RFC 1071)
  
• 
  28. To’xtash so’zlari haqida ma’lumot bering.
  
• 
  B a'zan foydalanuvchilarning axborot ehtiyojlarini qondirish uchun ahamiyatsiz bo'lgan juda keng tarqalgan ba'zi so'zlar odatda leksikon tarkibidan chiqarib tashlanadi. Ular to'xtash so'zlari (stop-words)deb nomlanadi. Odatda, so'zlarni to'xtatish ro'yxatlarini yaratish uchun atamalar to'plamdagi chastota bo'yicha tartiblanadi (bu hujjatlar to'plamidagi atamani takrorlashining umumiy soniga teng), so'ngra ular asosida eng ko'p qo'llaniladigan atamalar, indeksatsiya qilinayotgan hujjatlarning predmet sohasi bilan semantik aloqalar, indekslash paytida elementlari bekor qilinadigan to'xtash ro'yxatiga (stop-list) kiritiladi. To'xtash so'zlar ro'yxatining namunasi shakl. 2.5. To’xtash-so’zlar ro'yxati tizimda saqlanishi kerak bo'lgan pozitsiyalar sonini sezilarli darajada kamaytiradi; Ko'pgina hollarda indekslashda to'xtash so'zlarini e'tiborsiz qoldirish muammo tug'dirmaydi; the va by kabi kalit so'zlarni izlash deyarli foydali emas. Biroq, iboralarni qidirishda bunday emas. Ikkita so'zni o'z ichiga olgan President of the United States iborasini topish uchun so'rov, President AND "United States" so'roviga qaraganda aniqroq. Agar flights to London iborasining ma'nosi, undan to to'xtovchi so'zi chiqarib yuborilsa yo'qolishi mumkin. Vannevar Bushning (Vannevra Bush) As we may think agar dastlabki uchta so'z e'tiborsiz qoldirilsa va tizim shunchaki think so'zini o'z ichiga olgan hujjatlarni qidirib topsa juda qiyin bo'lar edi. So'rovlarning ayrim turlari boshqalarga qaraganda ko'proq zarar ko'rishi mumkin. Ba'zi qo'shiq nomlari va taniqli she'r parchalari butunlay to'xtash so'zlaridan iborat. Masalan:
  
• 
  2.5-rasm
  
• 
  
  
• 
  Vaqt o'tishi bilan axborot qidirish tizimlarida taqiqlangan so'zlarning ro'yxatlari uzunligi 200-300 dan 7-12 gacha qisqardi va ba'zi tizimlarda ulardan foydalanishdan voz kechildi. Masalan, veb-qidiruv tizimlarida so'zlarni to'xtatish ro'yxatlari odatda qo'llanilmaydi. Ba'zi zamonaviy axborot-qidirish tizimlarini ishlab chiquvchilari eng keng tarqalgan so'zlarni eng samarali qayta ishlash uchun tilning statistik xususiyatlaridan foydalanishga e'tibor berishdi.
  
•