|
Mustaqil ish mavzu: Marshurutlar va ularning vazifalari Qabullagan: Bajargan: nukus-2024
|
| bet | 4/5 | | Sana | 20.05.2024 | | Hajmi | 254,53 Kb. | | #244908 |
Bog'liq marshrut Asoslarning tarkibi, tuzilishi va nomlanishi. 7 - sinf , asl, Buxoro tarixi, tarmoq xavsizligi 3, 98380, 117-royxat, Tasdiqlayman, CHEVARXONA, amaliy ish, word, Dif. tenglamalar-2024 (2), visual studio, ehtimol topshiriq, diskretRabin-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. 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
|
Quyida simvollar uchun xesh-kod keltirilgan:
a
|
→
|
1
|
b
|
→
|
2
|
c
|
→
|
3
|
d
|
→
|
4
|
e
|
→
|
5
|
f
|
→
|
6
|
…
|
→
|
…
|
z
|
→
|
26
|
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
qadam. Agar m qismiy satr uzunligi bo'lsa, biz matn satrining boshidan m uzunlikdagi qismiy satrni olishni boshlaymiz. Shundan so'ng, qismiy satr uchun xesh-kod qiymatini topamiz va shablon satrining xesh-kod qiymatiga mos kelishini tekshiramiz. Agar u mos keladigan bo'lsa, belgini birma-bir tekshiradi, aks holda keyingi qismiy satrga o'tadi.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
1
|
5
|
22
|
5
|
|
|
|
|
|
Xesh kod qiymati: 1+5+22+5 = 33
Xesh-kod qiymati mos kelmaydi, keyin biz m (4) uzunlikdagi keyingi satrga o'tamiz.
qadam.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
5
|
22
|
5
|
19
|
|
|
|
|
Xesh kod qiymati: 5+22+5+19 = 51
Xesh-kod qiymati mos kelmaydi, keyin m uzunlikdagi keyingi satrga o'tamiz.
qadam.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
22
|
5
|
19
|
1
|
|
|
|
Xesh kod qiymati: 22+5+19+1 = 47
Xesh-kod qiymati mos kelmaydi, keyin biz m uzunlikdagi keyingi satrga o'tamiz.
qadam.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
5
|
19
|
1
|
16
|
|
|
Xesh kod qiymati: 5+19+1+16 = 41
Bu yerda xesh-kodining qiymati bir xil, shuning uchun biz ichki qismiy belgilarini qidiriluvchi satr bilan birma -bir tekshiramiz.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
e
|
s
|
a
|
p
|
|
|
Barcha belgilar mos keladi, keyin biz ichki satrning boshlangʻich indeksini chop etamiz va iloji bo'lsa, m uzunlikdagi keyingi qismiy satrga o'tamiz.
qadam.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
|
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
19
|
1
|
16
|
14
|
|
Xesh kod qiymati: 19+1+16+14 = 50
Joriy ichki satrning xesh qiymati qismiy satrning xesh qiymatiga mos kelmaydi. Shunday qilib, iloji bo'lsa, m uzunligining keyingi ichki satriga oʻtamiz, aks holda to'xtatamiz.
qadam.
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
a
|
e
|
v
|
e
|
s
|
a
|
p
|
n
|
g
|
|
|
|
|
|
↓
|
↓
|
↓
|
↓
|
|
|
|
|
|
1
|
16
|
14
|
7
|
Xesh kod qiymati: 1+16+14 +7= 38
Bu yerda ham xesh kodi qiymati mos kelmaydi va bu m uzunligining oxirgi ichki satri. Shunday qilib, bu yerda o'z jarayonimizni to'xtatamiz.
Eslatma: Bu yerda xesh funksiyasini yaratish yoki aniqlashning turli usullari mavjud. Yaxshi tushunish uchun oddiy xesh funksiyasidan foydalanildi.
Rabin-Karp algoritmi (C++)
#include using namespace std;
void rabin_karp(string &text,string &pattern, int q)
{
/*qismiy satr uzunligi*/ int m = pattern.length();
/*Berilgan satr uzunligi*/ int n = text.length();
int p=0,t=0,h=1,d=26; // bu yerda p - matn uchun xesh qiymati, t – qismiy satrning xesh qiymati;
/*h=pow(d,M-1) bu yerda d - 26, agar matnda faqat katta harflar bo'lsa.*/ for(int i=0;i
{
h=(h*d)%q;
}
/* matn va m uzunligining birinchi ichki satri uchun xesh qiymatini hisoblash
*/
for(int i=0;i
{
p=(d*p+pattern[i])%q;; t=(d*t+text[i])%q;
}
/* m uzunlikdagi qolgan satr uchun */ for(int i=0;i<=n-m;i++)
{
/* agar xesh qiymatlari bir xil bo'lsa, xeshni ichki satr va qismiy satridagi belgilar bo'yicha tekshirish */
if(p==t)
{
int flag=0;
for(int j=0;j
{
if(text[i+j]!=pattern[j])
{
flag=1; break;
}
}
/* agar barcha belgilar mos keladigan bo'lsa, ichki satrning boshlangʻich indeksini chop etish.*/
|
| |
