Izlash algoritmlari. knut va more algoritmlari
![Izlash algoritmlari
Satrlardan qismiy satrni qidirish algoritmi – bu matnda (text) qismiy satr
(pattern) topishga imkon beradigan satrlar ustidagi algoritmlar sinfi. U matn
muharrirlari, MBBT, qidiruv tizimlari, dasturlash tillari va boshqalarda o'rnatilgan
funksiya sifatida ishlatiladi.
Qidiruv vazifalarida qidiruv satrni “igna” (inglizchadan - "needle") va
qidiruv o'tkaziladigan satrni “g’aram” (ingliz tilidan - "haystack") deb belgilash
odat tusiga kirgan. Shuningdek, biz qidirish olib boriladigan alifboni Σ bilan
belgilaymiz.
Primitiv algoritmning muvaffaqiyatsizligi. Agar satrlar birdan boshlab
raqamlangan deb hisoblasak, eng oddiy “qo'pol kuch” (Brute force) algoritmi
(sodda algoritm) quyidagicha bo’ladi:
for i=0...|haystack|-|needle|
for j=0...|needle|
if haystack[i+j + 1]<>needle[j]
then goto 1
output("Topildi: ", i+1)
1:
Eng oddiy qidirish algoritmi, eng yaxshisi, |haystack| - |needle| +1
taqqoslash; agar bir-biriga o'xshashliklar ko'p bo'lsa, tezlik O(|haystack|·|needle|)
ga tushadi.
Primitiv algoritm o'rtacha 2 soatlik taqqoslashda ishlayotgani isbotlangan.
Bugungi kunda qismiy satrlarni qidirish algoritmlarining xilma-xilligi
mavjud. Dasturchi bunday omillarga qarab, mosini tanlashi kerak.
1. Optimallashtirish kerakmi yoki primitiv algoritm yetarlimi? Jimlik
bo’yicha, bu dasturlash tillarining standart kutubxonalari amalga oshiradi.
2. Foydalanuvchining "dushmanligi". Boshqacha aytganda:
foydalanuvchi ataylab algoritm sekin bajariladigan ma'lumotlarni
aniqlaydimi? Eng oddiy holatda O (| haystack | · | needle|) ball qo'yadigan
juda oddiy algoritmlar mavjud, lekin "muntazam" ma'lumotlarda
solishtirishlar soni | haystack | dan ancha kam. Faqat 1990-yillarda O (|
haystack |) ning murakkabligini, eng yomon holatda va | haystack |
o'rtacha.
3. Tilning grammatikasi qidiruvni "o'rtacha" tezlashtiradigan ba'zi
evristikalarga dushman bo'lishi mumkin.
4. Protsessor arxitekturasi. Ba'zi protsessorlarda avtomatik kattalashtirish
yoki SIMD amallari mavjud bo'lib, ular sizga ikkita operativ xotirani tez
taqqoslashga imkon beradi (masalan, x86-da rep cmpsd). Bunday
protsessorlarda “needle”ni “haystack” bilan taqqoslaydigan algoritmni
qo'llash juda qiziq - albatta, hamma pozitsiyalarda emas.
5. Alifbo o'lchami. Ko'p algoritmlar (ayniqsa, oxirigacha taqqoslashga
asoslangan), mos kelmaydigan belgi bilan bog'liq evristikaga ega. Katta
9](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_9.png?v=1)
![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 < m-1;i++ )
{
h= ( h*d ) %q;
}
/* matn va m uzunligining birinchi ichki satri uchun xesh qiymatini
hisoblash */
for ( int i=0;i < m;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 < m;j++ )
{
if ( text [ i+j ] !=pattern [ j ])
{
flag=1;
break;
}
}
/* agar barcha belgilar mos keladigan bo'lsa, ichki satrning boshlang'ich
indeksini chop etish.*/
if ( flag==0 )
{
cout << " Indeksda berilgan satr osti topildi:" << i+1 << endl;
}
}
14](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_14.png?v=1)
![/*oldingi ichki satrdan birinchi belgini olib tashlash orqali keyingi ichki
satrning xesh qiymatini toping va keyingi satrni oldingi satr oxiriga
qo'shing*/
/*xesh qiymatlarini topish uchun O (1) vaqt kerak bo'ladi*/
if ( i < n-m )
{
t= ( d* ( t-text [ i ] *h ) +text [ i+m ]) %q;
if ( t < 0 )
{
t= ( t+q ) ;
}
}
}
}
int main ()
{
/*o’zgaruvchilarni kiritish*/
string text;
cin >> text;
string pattern;
cin >> pattern;
rabin_karp ( text,pattern,97 ) ;
return 0;
}
Boyer-Mur algoritmi. 1977-yilda Robert Boyer va Jey Mur tomonidan
ishlab chiqilgan, matnda oldindan ishlov berish imkoniyati bo'lmagan taqdirda,
satrda qismiy satrni topish algoritmlari orasida eng tezkori hisoblanadi .
Algoritm g'oyasi quyidagicha:
- Chapdan o'ngga skanerlash, o'ngdan chapga taqqoslash.
- To'xtash belgisini topish
o agar taqqoslanadigan birinchi harf mos kelmasa, shablon eng yaqiniga
o'tkaziladi
o to'xtash belgisi bo'lmasa, shablon uning orqasiga siljiydi
- Mos keladigan qo'shimchani topish
o agar 1 yoki undan ortiq belgi mos kelsa, shablon bu qo'shimchaning
birinchi mos kelishiga qadar o'ngga siljiydi
1. q w t e e q e w q r w q w r q r
q w r q r
15](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_15.png?v=1)
![1991-yilda Koul shuni ko'rsatdiki, davriy bo'lmagan sxemalar bo'yicha,
algoritm satr bo'ylab to'liq o'tishda 3·|haystack| tadan ko'p bo'lmagan taqqoslashni
amalga oshiradi.
Boyer-Mura algoritmi (C++)
#include <bits/stdc++.h>
using namespace std;
# define NO_OF_CHARS 256
void badCharHeuristic( string str, int size, int badchar[NO_OF_CHARS])
{
int i;
for (i = 0; i < NO_OF_CHARS; i++)
badchar[i] = -1;
for (i = 0; i < size; i++)
badchar[(int) str[i]] = i;
}
void search( string txt, string pat)
{
int m = pat.size();
int n = txt.size();
int badchar[NO_OF_CHARS];
badCharHeuristic(pat, m, badchar);
int s = 0;
while(s <= (n - m))
{
int j = m - 1;
while(j >= 0 && pat[j] == txt[s + j])
j--;
if (j < 0)
{
cout << s << endl;
s += (s + m < n)? m-badchar[txt[s + m]] : 1;
}
else
s += max(1, j - badchar[txt[s + j]]);
}
17](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_17.png?v=1)
![// satrdagi naqsh boshi indeksini qaytaradi, topilmasa -1
int find (char * namuna, char * string1)
{
// i- biz qidirayotgan qatorning qayerida
// j-namunaning qaysi joyidan izlayapmiz
for (int i=0; string1 [i];++i) {
for (int j=0;;++j) {
if (!namuna [j]) return i;
if(string1[i+j]!=namuna [j]) break;
}
// hali topilmadi, tashqi sikl bilan davom eting
}
// namuna yo'q
return -1;
}
Funktsiya ishlaydi va agar namunalar va satr "yaxshi" bo'lsa, juda tez ishlaydi.
Yaxshi bo'lganlar, ichki pastadir tezda uzilib qolganda (1-3 qadamda, aytaylik,
oddiy holatda bo'lgani kabi). Ammo agar naqsh va satr tez-tez takrorlanadigan
ichki qismlarni o'z ichiga olsa (yuqoridagi murakkab holatda bo'lgani kabi), u
holda ichki halqa naqsh oxiriga kelib uziladi va qidiruv vaqti O (<naqsh uzunligi>
* <string uzunligi) sifatida baholanadi. >). Agar ipning uzunligi 100 ming, namuna
uzunligi 100 bo'lsa, biz O (10 million) ni olamiz. Albatta, aslida siz 100
uzunlikdagi naqshni kamdan-kam uchratasiz, ammo olimpiada muammolarida
"qidirish uchun" bu odatiy holdir, shuning uchun oddiy qidiruv ko'pincha mos
kelmaydi. , va siz yozayotganda tezda. so'z (brauzerlar buni qanchalik tez
bajarayotganini payqadingizmi)? KMP algoritmi satrda naqshning barcha paydo
bo'lishini va uning tezligini O (<naqsh uzunligi> + <string uzunligi>) topadi,
shuning uchun katta matnlarda / namunalarda yoki zaif protsessorlarda (past
budjetli uyali telefonlar kabi) bu raqobatdan tashqari.Endi sarlavhaga qaraylik?
Nima uchun "kichik"? Chunki KMP ning diqqatga sazovor joyi prefiks
20](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_20.png?v=1)
![funktsiyasidir va u haqiqatan ham kichikdir. Nega "mo''jiza"? Chunki u butunlay
boshqa masalani yechayotgandek tuyuladi va bu yechim qandaydir ajoyib hiyladan
so‘ng satrda naqshning barcha ko‘rinishlarini topish masalasining yechimiga
aylanadi.Prefiks funksiyasi nima va qanday ishlashini tushunish uchun ko‘rib
chiqamiz. murakkab qatorda
a a b a a b a a a a b a a b а a a b
1 2 3 4 5 6 7 8 9 1
0 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8
0 1 0 1 2 3 4 5 2 2 3 4 5 6 7 8 9 3
Uning ostidagi chiziq satrdagi belgining raqami (pozitsiyasi) (algoritmni tavsiflash
qulayligi uchun biz raqamni 1 dan hisoblaymiz), pastki qator esa M prefiks
uzunliklari massivi bo'lib, uni tushunish kalitidir. prefiks funktsiyasi. 7 raqamiga
ega bo'lgan belgini oling (bu a) va 1 dan 6 gacha bo'lgan K uchun prefiks satrlarni
(satrning birinchi indeksidan boshlanadigan pastki qator) va qo'shimchalarni
(pastki satr, oxirgi belgisini ko'rib chiqing). 7-pozitsiyadagi satr (bu "bizning" a
belgisi) uzunligi K.
Endi yana bir holat - P8 kengaytirilmadi, ya'ni. S [9] = a belgisi M [8] + 1 = 6 b
pozitsiyasidagi S qatorning belgisiga mos kelmadi. Qo'shimcha osongina
kengayadi (chunki yangi belgi oxiriga qo'shiladi), lekin muammoli prefiks bilan,
chunki qo'shimchasiga qo'shilgan belgi keyingi prefiks belgisiga mos kelmasligi
mumkin. Agar P (k) prefiksi mos kelmasa, siz bir xil qo'shimchaga ega bo'lgan
qisqaroq boshqa prefiksni topishingiz va uni kengaytirishga harakat qilishingiz
kerak. Ammo prefiks qisqaroq va xuddi shu qo'shimcha bilan u S [M [M [k]],
chunki M massivni to'ldirishda har bir element bir xil qo'shimchali eng uzun
21](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_21.png?v=1)
![prefiksning uzunligini o'z ichiga oladi. Shuning uchun, agar S (M [k]) ni
kengaytirishning iloji bo'lmasa, S (M [M [k]]) va boshqalarni mos kelguncha yoki
biz nolga teng bo'lgunga qadar kengaytirishga harakat qiling (keyin keyingi belgi S
shunchaki. S satrning 1-belgisi bilan solishtirish kerak). Tegishli prefikslarni
qidirish tsikli juda tez tugaydi, chunki buning uchun zarur bo'lgan barcha
ma'lumotlar allaqachon M massivida. Bizning P (8) qatorimiz P (7) ning bir belgi
bilan kengaytmasi bo'lib, 1 ta taqqoslash kerak bo'ldi. Biroq, P (8) ni P (9) ga
kengaytirib bo'lmadi, chunki S [9] = a va S [M [8] + 1 = 6] = b. M [8] = 5
uzunlikdagi P8 prefiksi mos kelmaganligi sababli, M [5] = 2 uzunlikdagi prefiksni
sinab ko'ring. U ham mos kelmaydi: S [2 + 1] = b. Biz M [2] = 1 uzunlikdagi
prefiksni sinab ko'ramiz va uni uzaytirish mumkin, chunki S [1 + 1] = a. Shuning
uchun, M [9] = 2, kengaytirilgan prefiksning uzunligidan biriga ko'proq. M [10] ni
to'ldirish uchun sizga 2 ta taqqoslash kerak (tekshirishingiz mumkin). Ammo 11
dan 17 gacha bo'lgan elementlarni to'ldirish uchun sizga bitta taqqoslash kerak.
Natijada, massiv qiymatlarini hisoblash O tartibidagi vaqtni oladi (satr uzunligi)
Shunday qilib, to'ldirish algoritmi ko'proq yoki kamroq aniq.
Keling, hiyla-nayrangga o'tamiz.
aabaabaaaabaabaaab qatorida aabaa naqshini topish uchun naqshni shunday
chiziqqa yopishtiring aabaa @ aabaabaaaaaaabaaab va massivni to'ldirish uchun
prefiks funksiyasini chaqiring.
22](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_22.png?v=1)
 mutable
{
i++;
if (i <= n)
{
sample.push_back(item);
}
else if (std::rand() % i < n)
{
sample[std::rand() % n] = item;
}
23](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_23.png?v=1)
![return sample;
};
}
int main() {
std::srand(std::time(NULL));
int bin[10] = {0};
for (int trial = 0; trial < 100000; trial++)
{
auto s_of_n = s_of_n_creator<int>(3);
std::vector<int> sample;
for (int i = 0; i < 10; i++)
sample = s_of_n(i);
for (int s : sample)
bin[s]++;
}
for (int x : bin)
std::cout << x << std::endl;
return 0;
}
24](https://docx.uz/documents/f3a179a1-495c-4273-975f-22804fbf93d4/page_24.png?v=1)
Izlash algoritmlari. knut va more algoritmlari