Bitiruv malakaviy ishi mavzu: Axborotlashtirish obyektlarni ximoyalashda qo'laniladigan tarmoqlararo ekran tahlili. Bajardi: 715-20 – guruh talabasi Bo'riyev O. Ilmiy rahbar: Raximov Rustam s a m a r q a n d – 2015

2.2.3. Boyer –Mur algoritmi va uning ba’zi modifikasiyalari. 
Boyer-Mur algoritmi. 
Boyer va Mur tomonidan ishlab chiqilgan . Boyer-Mur algoritmi qism satrni 
satrda algoritmlar orasida yeng tezi hisoblanadi. Boyer-Mur algoritmining oddiy 
varianti quyidagi qadamlardan iborat. Birinchi qadamda izlanayotgan namuna 
uchun siljishlar jadvalini tuzamiz. Jadvalni tuzish quyida tavsiflangan. Keyin biz
satr va ustun boshlarini ketma–ket tushiramiz va tekshiramiz. Agar namunaning 
oxirgi simvoli va unga mos satrning simvoli ustma-ust tushmasa namuna siljishlar 
jadvalidan olingan kattalikka siljitiladi va yana namunaning oxirgi simvolidan 
boshlab taqqoslanadi va hokazo. Agar namunaning barcha simvollari qo’yilgan 
satrning barcha simvollari bilan mos tushsa, demak, biz qism satrini topdik va 
izlash tugaydi. Agar namunaning birorta (oxirgisi emas) simvoli satrning mos 
simvoli bilan ustma-ust tushmasa, u holda biz namunani bir simvol o’ngga 
Function KMPSearch(S,P:String):Integer; 
{Knut- Morris – Platt algoritmini o’rnatish } 
{ S satrda bo’sh bo’lmagan Psatrning qarashini aniqlovchi } 
Var Fl:TMas; 
i,j,n,m:Integer; 
Begin 
n:=Length(S); 
m:=Length(P); 
PrefFunc(P,Fl); 
j:=1; 
For i:=1 To n Do 
begin 
While (j<>0) And (P[j]<>S[i]) do j:=Fl[j]; 
If j=m Then Break; 
j:=j+1 
end; 
If (j=m) then Result:=i-j+1 Else Result:=0;
End; 

---

33 
siljitamiz va yana oxirgi simvoldan tekshira boshlaymiz. Butun algoritm
izlanayotgan namuna kirish topilguncha, yoki satr oxiriga etguncha bajariladi. 
Oxirgi simvol ustma-ust tushmagan holda siljish kattaligiga quyidagi 
mulohazalarga asoslanib hisoblanadi: namuna siljishi kiritishni o’tkazib, 
yuborilmasligi kerak.
Agar satrning berilgan simvoli namunada berilsa, biz namunani shunday 
siljitamizki, satr simvoli bu simvolning namunaga eng so’ng kirish bilan mos 
tushadi. Agar namuna bu simvolni umuman o’z ichiga olmasa, biz namunani uning 
uzunligiga teng kattalikka shunday siljitamizki, namuna birinchi simvoli sartning 
tekshirilayotgan simvolidan keyingisiga tushiriladi. 
Har bir simvol uning siljish kattaligi namunada simvollar tartibiga bog’liq 
shuning uchun siljishlarning oldindan hisoblash qulay va alifboning har bir 
simvoliga namunaning oxirgi simvoliga nisbatda siljish mos keladigan bir 
o’lchovli massiv shaklida saqlash lozim. 
Yuqorida aytilganlarni oddiy misolda tushuntiramiz. Bizga beshta simvoldan 
a,b,c,d,e iborat alifbo va biz “abbad” namunasini abeccacbadbabbad satrga 
kirishini topamiz. Quyidagi sistemalar algoritm bajarilish barcha bosqichlarini 
namoyish etadi. Siljishlar jadvali quyidagicha:
Izlashni boshi. 
Oxirgi simvol quyilgan satr simvoli bilan mos tushmaydi. Namunani o’ngga
5 pozisiyaga siljitamiz: 
Namuna 3ta simvolga mos tushdi, to’rtinchisi yo’q. Namunani o’ngga bir 
pozitsiyaga siljitamiz: 

---

34 
Oxirgi simvol yana satr simvoli bilan mos tushmadi. Siljishlar jadvaliga 
ko’ra namunani 2 pozitsiya siljitamiz: 
Yana bir marta namunani 2 pozitsiyaga siljitamiz: 
Endi jadvalga ko’ra, namunani bir pozitsiyaga siljitamiz va namunaning 
izlangan kirishini olamiz: 
Ko’rsatilgan algoritmni Paskal tilida amalga oshiramiz. Avvalo, “siljishlar 
jadvali” ma’lumotlar tipini aniqlash lozim. 256 simvoldan iborat kod jadvali uchun 
bu tipni aniqlash quyidagi ko’rinishda bo’ladi: 
Type TBMTable = Array [0..255] of Integer; 
So’ngra p namuna uchun siljishlar jadvalini hisoblash protsedurasi 
keltiriladi.
Endi izlashni amalga oshiruvchi funksiyani yozamiz.
StartPos narametr s satrda izlashni boshlaydigan pozitsiyani ko’rsatadi. Bu 
faqat shunda foydaliki, agar biz p ning s ga barcha kirishlarini topishni hoxlasak. 
Izlash uchun satrning boshidan boshlab StartPos ni p ga teng deb borish kerak. 
Agar izlash ayirmasi nolga teng bo’lmasa, p ning s ga navbatdagi kirishini topish 
uchun StartPos ni oldingi natijada namuna uzunligi p ga teng qilib olamiz.