Matn ichida qidiruv. Rabin-Karp algoritmi

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

patterndagi 0 dan M-1 gacha belgilar bo’yicha hash soni generatsiya qilinadi. Bunda M – patterndagi belgilar soni.
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
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