1. Dasturiy ta’minot va uning turlari

Satrlarda qismiy satrlarni qidirish algoritmlari (Qismiy satrlarni izlashda primitiv algoritmlarning kamchiligi, Rabin-Karp algoritmi, Boyer-Mur algoritmi, Suffiks jadvali)

Rabin - Karp algoritmi yoki Karp-Rabin algoritmi Richard M. Karp va Maykl O. Rabin ( 1987 ) tomonidan yaratilgan qatorni qidirish algoritmi bo'lib, matndagi naqsh qatorining aniq mosligini topish uchun xeshlashdan foydalanadi. U matnning naqshga mos kelmaydigan joylarini tezda filtrlash uchun siljish xeshidan foydalanadi va keyin qolgan pozitsiyalarda moslikni tekshiradi. Xuddi shu fikrni umumlashtirishdan bitta naqshning bir nechta mosligini topish yoki bir nechta naqsh uchun moslikni topish uchun foydalanish mumkin. Bitta naqshning yagona mosligini topish uchun algoritmning kutilgan vaqti naqsh va matnning birlashtirilgan uzunligida chiziqli bo'ladi, garchi uning eng yomon vaqt murakkabligi ikki uzunlik mahsuloti bo'lsa ham. Bir nechta mosliklarni topish uchun kutilgan vaqt kiritish uzunliklarida chiziqli va barcha mosliklarning umumiy uzunligi chiziqlidan kattaroq boʻlishi mumkin. Bundan farqli o'laroq, Aho-Corasick algoritmi bir nechta naqshlarning barcha mosliklarini eng yomon holatda vaqt va fazoda chiziqli kiritish uzunligi va mos keladiganlar soni (gugurtlarning umumiy uzunligi o'rniga) topishi mumkin. Sodda satrlarni moslashtirish algoritmi berilgan naqshni berilgan matndagi barcha pozitsiyalar bilan solishtiradi. Har bir taqqoslash naqsh uzunligiga proportsional vaqtni oladi va pozitsiyalar soni matn uzunligiga proportsionaldir. Shuning uchun, bunday usul uchun eng yomon vaqt ikki uzunlik mahsulotiga proportsionaldir. Ko'pgina amaliy holatlarda, mos kelmaslik aniqlangandan so'ng, har bir pozitsiyada taqqoslashni qisqartirish orqali bu vaqtni sezilarli darajada qisqartirish mumkin, ammo bu fikr hech qanday tezlikni kafolatlay olmaydi. Bir nechta satrlarni moslashtirish algoritmlari, jumladan Knuth-Morris-Pratt algoritmi va Boyer-Mur string-qidiruv algoritmi , har bir nomuvofiqlikdan qo'shimcha ma'lumot olish orqali satrlarni moslashtirish uchun eng yomon vaqtni qisqartiradi va ularga matn pozitsiyalarini o'tkazib yuborishga imkon beradi. naqshga mos kelmasligi kafolatlanadi. Buning o'rniga Rabin-Karp algoritmi har bir pozitsiya uchun taxminiy tekshirishni tezda amalga oshirish uchun xesh funktsiyasidan foydalangan holda o'zining tezlashishiga erishadi va keyin faqat ushbu taxminiy tekshiruvdan o'tgan pozitsiyalarda aniq taqqoslashni amalga oshiradi. Xesh funksiyasi har bir satrni uning xesh qiymati deb ataladigan raqamli qiymatga aylantiruvchi funksiyadir ; masalan, bizda bo'lishi mumkin hash("hello")=5. Agar ikkita satr teng bo'lsa, ularning xesh qiymatlari ham teng bo'ladi. Yaxshi ishlab chiqilgan xesh funksiyasi uchun teskari, taxminiy ma'noda to'g'ri bo'ladi: teng bo'lmagan satrlar teng xesh qiymatlariga ega bo'lish ehtimoli juda kam. Rabin-Karp algoritmi matnning har bir pozitsiyasida naqsh bilan bir xil uzunlikdagi ushbu pozitsiyadan boshlanadigan satrning xesh qiymatini hisoblash orqali davom etadi. Agar bu xesh qiymati naqshning xesh qiymatiga teng bo'lsa, u o'sha pozitsiyada to'liq taqqoslashni amalga oshiradi. Bu yaxshi ishlashi uchun xesh funksiyasi ko'p noto'g'ri pozitivlarni keltirib chiqarishi dargumon xesh funksiyalar turkumidan tasodifiy tanlanishi kerak , matnning naqsh bilan bir xil xesh qiymatiga ega, lekin aslida naqshga mos kelmaydigan pozitsiyalari. . Ushbu pozitsiyalar algoritmning ishlash vaqtiga keraksiz, mos kelmasdan yordam beradi. Bundan tashqari, ishlatiladigan xesh funksiyasi haddelenmiş xesh bo'lishi kerak , uning qiymati matnning har bir pozitsiyasidan keyingisiga tezda yangilanishi mumkin. Har bir pozitsiyada xesh funktsiyasini noldan qayta hisoblash juda sekin bo'ladi.

76.