69 / 69

Rabin-Karp Algorithm

Rabin-Karp algoritmi nima?

Rabin-Karp algoritmi — bu matn ichidan berilgan andozani (pattern/qidirilayotgan satrni) xesh funksiyasi (hash function) yordamida tezkor qidirish va mosliklarni topish algoritmidir.

Oddiy (Naive) satr qidirish algoritmidan farqli o'laroq, Rabin-Karp dastlabki bosqichda har bir belgini birma-bir solishtirib chiqmaydi. Buning o'rniga, u avval andoza va matn oynasining xesh qiymatlarini solishtiradi. Faqat xesh qiymatlari mos kelgandagina harflarni to'liq tekshiruvdan o'tkazadi. Bu esa mos kelmaydigan qismlarni bir zumda chetlab o'tish imkonini beradi.

[!NOTE] Xesh funksiyasi (Hash function) — katta hajmdagi kiruvchi ma'lumotni kichik sonli qiymatga akslantiruvchi vositadir. Hosil bo'lgan natija xesh qiymati (hash value) deyiladi.

Rabin-Karp algoritmi qanday ishlaydi?

Keling, algoritmni quyidagi misol yordamida bosqichma-bosqich tushunib olaylik:

Asosiy matn berilgan:

Matn: ABCCDDAEFG

Va ushbu matndan qidirilishi kerak bo'lgan andoza (pattern):

Andoza (Pattern): CDD
Qulaylik uchun masalada ishlatiladigan belgilarga sonli qiymatlar (og'irliklar / weights) biriktiramiz. Bu yerda alifboning dastlabki 10 ta harfi (A dan J gacha) olingan:

Belgilar og'irliklari (A=1, B=2, ..., J=10)
m — andoza uzunligi (m = 3) va n — matn uzunligi (n = 10).
d — kiruvchi belgilar to'plamidagi belgilar soni (alfavit o'lchami, bu yerda d = 10).
Andozaning (CDD) xesh qiymatini hisoblaymiz:

Andoza xesh qiymati hisoblanishi
text
```
hash(p) = Σ(v * d^(m-1)) mod 13 
        = ((3 * 10^2) + (4 * 10^1) + (4 * 10^0)) mod 13 
        = 344 mod 13 
        = 6
```
Yuqoridagi hisob-kitobda amallarni bitta aniqlikda tez bajarish uchun tub sondan (bu yerda q = 13) modul olinadi.

Matnning m o'lchamli birinchi oynasi (ABC) uchun xesh qiymatini hisoblaymiz:

text

hash(t) = ((1 * 10^2) + (2 * 10^1) + (3 * 10^0)) mod 13 
        = 123 mod 13 
        = 6

Andozaning xesh qiymati (p = 6) bilan matn oynasining xesh qiymatini (t = 6) solishtiramiz. Ular bir xil chiqdi! Endi belgilarni birma-bir taqqoslaymiz: ABC va CDD teng emas. Demak, bu soxta to'qnashuv bo'lib, keyingi oynaga o'tamiz.
Keyingi oyna xeshini noldan qayta hisoblamasdan, sirpanuvchi xesh (rolling hash) formulasi orqali eskisidan 1-belgini chiqarib, yangisini qo'shamiz:
text
```
t = (d * (t - v[chiqariladigan_belgi] * h) + v[qo'shiladigan_belgi]) mod 13
```
Bu yerda h = d^(m-1) mod 13 = 10^(3-1) mod 13 = 100 mod 13 = 9.
Har bir keyingi oyna uchun shu tarzda xesh tekshirib boriladi. 4-pozitsiyada CDA va nihoyat CDD to'liq mos keladi:

Matndagi har bir oynaning xesh qiymati

Rabin-Karp algoritmi psevdokodi

text

n = t.length
m = p.length
h = d^(m-1) mod q
p = 0
t0 = 0

for i = 1 to m:
    p = (d*p + p[i]) mod q
    t0 = (d*t0 + t[i]) mod q

for s = 0 to n - m:
    if p == ts:
        if p[1...m] == t[s+1 ... s+m]:
            print "Andoza quyidagi pozitsiyada topildi:", s + 1
    if s < n - m:
        ts+1 = (d * (ts - t[s+1]*h) + t[s+m+1]) mod q

Dasturiy kod

package main

import (
	"fmt"
)

const d = 10 // Alifbodagi belgilar soni

// Rabin-Karp qidiruv algoritmi
func search(pattern, text string, q int) {
	m := len(pattern)
	n := len(text)
	p := 0 // Andoza (pattern) uchun xesh qiymati
	t := 0 // Matn oynasi (text window) uchun xesh qiymati
	h := 1

	// h = pow(d, m-1) % q ni hisoblash
	for i := 0; i < m-1; i++ {
		h = (h * d) % q
	}

	// Andoza va matnning dastlabki oynasi uchun xesh qiymatini hisoblash
	for i := 0; i < m; i++ {
		p = (d*p + int(pattern[i])) % q
		t = (d*t + int(text[i])) % q
	}

	// Matn bo'ylab oynani bittalab surib chiqish
	for i := 0; i <= n-m; i++ {
		// Agar xesh qiymatlari mos kelsa, belgilarni birma-bir tekshiramiz
		if p == t {
			match := true
			for j := 0; j < m; j++ {
				if text[i+j] != pattern[j] {
					match = false
					break
				}
			}
			if match {
				fmt.Printf("Pattern is found at position: %d\n", i+1)
			}
		}

		// Keyingi oyna uchun sirpanuvchi xeshni (rolling hash) hisoblash
		if i < n-m {
			t = (d*(t-int(text[i])*h) + int(text[i+m])) % q
			// Agar t manfiy bo'lib qolsa, musbatga o'tkazamiz
			if t < 0 {
				t = t + q
			}
		}
	}
}

func main() {
	text := "ABCCDDAEFG"
	pattern := "CDD"
	q := 13 // Xesh to'qnashuvlarini kamaytirish uchun tub son

	search(pattern, text, q)
}

Limitations of Rabin-Karp Algorithm

Spurious Hit

Soxta moslik:

Andozaning xesh qiymati matn oynasining xesh qiymatiga teng bo'lib qolsa-da, aslida belgilar mos kelmasligi soxta moslik (spurious hit) deyiladi.

Soxta mosliklar algoritmning vaqt sarfini oshiradi, chunki ular har safar belgilarni tekshirishga majbur qiladi. Soxta mosliklarni minimallashtirish uchun yetarlicha katta tub son bilan modul olinadi.

Rabin-Karp algoritmining murakkabligi

O'rtacha va eng yaxshi holatdagi vaqt murakkabligi: O(m + n) (bu yerda m — andoza uzunligi, n — matn uzunligi).
Eng yomon holatdagi vaqt murakkabligi: O(m * n) (agar xesh to'qnashuvlari — soxta mosliklar deyarli har bir oynada takrorlansa).
Xotira murakkabligi: O(1).

Rabin-Karp algoritmining qo'llanilishi

Matnlarda andozalarni qidirish (Pattern Matching): Bir vaqtning o'zida bir nechta andozalarni tezkor qidirish.
Plagiatni aniqlash tizimlari: Hujjatlar va ilmiy ishlardagi matn o'g'irlashlarini jumlalar xeshlari orqali solishtirish.
Katta matnli ma'lumotlar bazalarida qidiruv.

Oldingi

Tugatish