17.2. Qismiy satrlarni qidirish algoritmlarining turlari 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.
189
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.
Berilgan matn S= ―aevesapng‖
Izlanadigan satr P= ―esap‖
0
1
2
3
4
5
6
7
8
a
e
v
e
s
a
p
n
g
0
1
2
3
e
s
a
p
Quyida simvollar uchun xesh-kod keltirilgan:
a
→
1
b
→
2
c
→
3
d
→
4
e
→
5
f
→
6
… →
…
z
→
26
190
1-qadam . Belgilarga tayinlangan xesh kodi yordamida qismiy
satrning xesh kodi qiymatini topamiz.
0
1
2
3
e
s
a
p
↓
↓
↓
↓
5
19 1
16
Xesh-kod qiymati: 5+19+1+16=41
