Bizda quyidagi matn bor bo’lsin

Matn ichida qidiruv uchun yana bir diqqatga molik algoritmlardan biri – Rabin-Karp algoritmi hashing usuliga asoslanadi. Uning ishlash tartibini batafsil tushuntirishga harakat qilaman.
Bizda quyidagi matn bor bo’lsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE

1. 
   patterndagi 0 dan M-1 gacha belgilar bo’yicha hash soni generatsiya qilinadi. Bunda M – patterndagi belgilar soni.
   
2. 
   har bir [i..N-1] sikl ichida matndagi i dan M + i – 1 gacha belgilar bo’yicha hash soni generatsiya qilinadi. Bunda N – matndagi belgilar soni
   
3. 
   Agar pattern hash va matn substring hash bir-biriga teng bo’lsa, pattern matn ichidan topilgan hisoblanadi.
   

Hash sonini generatsiya qilishning eng tezkor, oson usullardan biri – pattern’ning har bir belgisi kodini olib, ularni birlashtirish va uni biror katta tub songa bo’lib, qoldig’ini qoldirish kerak. Javascriptda bu ish quyidagicha bajariladi:
const primeNumber = 997 // tub son
const pattern = "NEEDLE" // qidiriladigan so'z
const hash = pattern.split('').map(char => char.charCodeAt()).join('') % primeNumber
// pattern uchun hash soni 769
Demak bizda patternning hash soni generatsiya qilindi. Endi uni matndagi har bir i dan M + i – 1 gacha substring’lardan hash son generatsiya qilib uni pattern’ning hash soniga solishtirib chiqiladi. Substring uchun ham, pattern uchun ham bir xil usulda hash generatsiya qilinadi.
FINDINAHAYSTACKNEEDLEINA
FINDIN // 5 != 769
INDINA // 877 != 769
NDINAH // 105 != 769
DINAHA // 259 != 769
INAHAY // 541 != 769
NAHAYS // 414 != 769
AHAYST // 271 != 769
HAYSTA // 963 != 769
AYSTAC // 805 != 769
YSTACK // 535 != 769
STACKN // 507 != 769
TACKNE // 178 != 769
ACKNEE // 98 != 769
CKNEED // 615 != 769
KNEEDL // 317 != 769
NEEDLE // 769 == 769
Juda oddiy va mohirona usul!
Yuqoridagi hash generatsiya qilish usuli split() va join() metodlari ishlatilgani sababli sekinroq ishlashi mumkin. Shuning uchun biz hash generatsiya qilishni sinalgan usul – Horner metodi yordamida amalga oshiramiz. Umumiy formula quyidagicha:
x_i = ( t_i * R^M-1 + t_i+1 * R^M-2 + … + t_i+M-1 * R⁰ ) % Q
Bu yerda:
x_i – matndagi [i..M + i – 1] substring uchun hash soni.
t_i – str.charCodeAt(i) – matn/pattern belgisining ASCII jadvalidagi raqami.
R – radix soni. ASCII uchun 128 yoki 256.
M – patterndagi belgilar soni.
Q – tub son.
Hash funksiya kodi:
function hornerHash(str, M) {
const R = 128
const Q = 997
let hash = 0

for (let j = 0; j < M; j++) {

hash = (R * hash + str.charCodeAt(j)) % Q
}

return hash

}
Hash funksiyada kolliziya ehtimolligi Q tub sonning qanchalik katta son ekanligiga bog’liq. Masalan agar Q son M * N² dan katta bo’lsa, kolliziya ehtimoli 1/N ga teng bo’ladi.
Kod

	function RKSearch(str, pattern) {
	const N = str.length
	const M = pattern.length
	const patHash = hornerHash(pattern, M)
	for (let i = 0; i < N - M; i++) {
	if (hornerHash(str.substring(i, i + M), M) === patHash) {
	return i;
	}
	}
	return -1
	// Hash function
	function hornerHash(str, M) {
	const R = 128
	const Q = 997
	let hash = 0
	for (let j = 0; j < M; j++) {
	hash = (R * hash + str.charCodeAt(j)) % Q;
	}
	return hash;
	}
	}
	/**
	* USAGE
	*/
	console.log(RKSearch("FINDINAHAYSTACKNEEDLEINA", "NEEDLE")

Rabin-Karp algoritmi. Rabin-Karp algoritmi-bu matnni xeshlash yordamida berilgan satrdan ichki satrni qidiradigan qidirish algoritmi. U 1987-yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan. Algoritm kamdan-kam hollarda bitta qismiy satrni topish uchun ishlatiladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi bir nechta qismiy satr uchun moslikni topishda juda samarali. n uzunlikdagi matn va m uzunlikdagi qismiy satr uchun uning o'rtacha va eng yaxshi bajarilish vaqti to'gʻri xesh funksiyasi bilan O (n) dir, lekin eng yomon holatda uning samaradorligi O (nm) ga teng. Bu esa keng qo'llanilmasligining sabablaridan biridir.
Rabin-Karp algoritmining eng oddiy amaliy qo'llanmalaridan biri plagiatni aniqlashdir. Rabin-Karp algoritmi tekshirilgan maqoladagi manba materiallardan ba'zi jumlalar paydo bo'lishining misollarini tezda topishi mumkin. Algoritmning kichik farqlarga sezgirligini yo'q qilish uchun siz ularni olib tashlash orqali harf yoki tinish belgi kabi tafsilotlarni e'tiborsiz qoldirishingiz mumkin. Biz qidirayotgan qatorlar soni juda katta bo'lgani uchun, bitta satrlarni topishning an'anaviy algoritmlari samarasiz bo'lib qoladi. Quyidagi misol orqali Rabin-Karp algoritmini koʻrib chiqamiz