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

Function Search (S: String; X: String; var Place: Byte): Boolean; 
{Funksiya S so’zdagi izlash natijasini qaytaradi. } 
{ Izlanayotgan funksiya uchun Xesh funksiyasini hisoblash. } 
Var Res: Boolean; i: Byte; h,NowH,LenX:Integer; HowMany:Integer; 
Begin Res:=FALSE; 
i:=1; 
h:=Hash(x); {Xesh funksiyasining keyingi qiymatini hisoblash .} 
NowH:=Hash(Copy(S,1,Length(x))); 
HowMany:=Length(S)-Length(X)+1; 
LenX:=Length(X); 
While (i<=HowMany) And Not(Res) do 
If (h=NowH) and (Copy(S,i,Length(X))=X) then 
Begin Res:=TRUE; Place:=i End
else 
Begin 
i:=i+1; 
NextHash(s,i,NowH,LenX); {Xesh-funksiyaning keyingi ifodasini 
hisoblash.} 
End; 
Search:=Res 
End; 

---

29 
eslatadigan”larini tekshirishimiz mumkin. Demak, oshkora mos tushmaslikni 
o’rnatish uchun quyidagilarni bajaradigan funksiyada foydalanamiz: 
1. Oson hisoblanadi. 
2. Mos tushmaydigan satrlarni qanday qilib, yaxshi farqlash mumkin. 
3. hash( y[i+1, i+m] ), hash( y[i, i+m-1] bo’yicha oson hisoblashi mumkin. 
X ni izlashda hash(x) ni hash(y[i, i+m-1]) bilan noldan n-m dan i uchun 
taqqoslaymiz. Agar mos tushushni topsak, u holda simvollar bo’yicha tekshiramiz. 
Misol: Satrda va namunada barcha harflar butun sonlardan iborat, ularni 
nomerlari bilan almashtiramiz. U holda qulay funksiya bo’lib, raqamlar yig’indisi 
hisoblanadi (“darcha”ni siljitishda yangi sonni qo’shish va “yo’qolganini” ayirish 
lozim). 
Lekin muammo shundaki, izlanayotgan satr uzun bo’lishi mumkin, matnda 
satrlar ham yetadi. Har bir satrga biror son mos qo’yish lozim, u holda sonlar ham 
ko’p bo’lishi kerak, sonlar katta bo’ladi (D n tartibda, bu yerda D–turli simvollar 
soni) va ular bilan ishlash noqulay. Lekin faqat qisqa satrlar va raqamlar bilan 
ishlashdan qanday foyda bor? Algoritmni ishlab chiquvchilar ish tezligida 
yo’qotishlarsiz qanday qilib bu algoritmni yaxshilash mumkinligini o’ylaydilar. 
Misol: Biror p sonining (tub bo’lishi maqsadga muvofiq) va p modul 
bo’yicha X ni tanlaymiz, n uzunlikdagi har bir so’zni butun sonlar ketma–ketligi 
sifatida qaraymiz (harflarni ularning kodlari bilan almashtiramiz). Bu sonlarni n-1 
darajali ko’phaq koefitsentlari sifatida qaraymiz. Bu oilaning funksiyalaridan biri 
bo’ladi(har bir p va x juft uchun o’z funksiyasi olinadi). ”Darsni” birga siljitish 
bosh hadni ayirishga, x ga ko’paytirishga va ozod hadni qo’shishga mos keladi. 
Bu fikr shundan dalolat beradiki, ustma-ust tushishlar unchalik ehtimolli emas. p 
soni tayinlangan va yana tup son bo’lsin, x va y n uzunlikdagi ikkita turli so’z. U 
holda ularga turli ko’phadlar mos keladi(biz faraz qilamizki, barcha harflar kodlari 
turlicha, bu alifbo harflar soni p katta bo’lganida mumkin). Funksiya 
qiymatlarining ustma-ust tushushi shuni bildiradiki, x nuqtada bu ikki turlicha 
ko’phadlar ustma–ust tushadi, ya’ni ayirmasi nolga aylanadi. Ayirma n-1 darajali 
ko’phad va n-1 tadan ko’p ildizga ega. Shunday qilib, agar n p dan juda kichik 

---

30 
bo’lsa, u holda x ning tasodifiy qiymatiga “omadsiz” nuqtaga tushish imkoni juda 
kichik. 
Aniqrog’i, butun algoritmning butun ish vaqti O(m+n+mn/P), mn/P etarlicha 
katta emas, shuning uchun ishning murakkabligi deyarli chiziqli tushunarliki, tub 
sonini katta tanlash maqsadga muvofiq, chunki bu son qancha katta bo’lsa dastur 
shuncha tez ishlaydi. 
Rabin algoritmi va ketma-ket izlash algoritmi eng kichik mehnat sarfli 
algoritmlar, shuning uchun ular ba’zi sonli masalalar yechishda foydalaniladi. 
Lekin bu algoritmlar eng optimal hisoblanmaydi (chunki, ba’zida oshkor foydasiz 
ish bajaradi, bu haqda yuqorida aytib o’tildi). Shuning uchun biz navbatdagi 
algoritmlar sinfiga o’tamiz. Bu algoritmlar ketma-ket izlash algoritmini tekshirish 
natijasida paydo bo’lgan. Tadqiqotchilar skalyarlash paytida olingan ma’lumotni 
to’laroq foydalanish uchun usullarni topishni hoxlaydilar (to’g’ridan-to’g’ri izlash 
algoritmini tashlab yuboradi ).
2.2.2 Knutt-Morris-Pratt algoritmi (KMP). 
Dastlab ba’zi tasdiqlarni qaraymiz. Ixtiyoriy x uchun uning barcha 
boshlarini, bir vaqtda uning oxirlari bo’lganligini qaraymiz va ulardan eng uzunini 
tanlaymiz (x so’zining o’zini hisobga olmaganda). Uni n(x) deb belgilaymiz. 
Bunday funksiya prefiks–funksiya nomiga ega [10].