Foydalanuvchi:Xojiyev Amal/qumloq

Rabin-Karp algoritmi

Rabin-Karp algoritmi satrlarni qidirish algoritmi bo'lib, u xeshlash yordamida matnda naqsh, ya'ni pastki qatorni qidiradi. U 1987 yilda Maykl Rabin va Richard Karp tomonidan ishlab chiqilgan.

Algoritm bitta naqshni moslashtirish uchun kamdan-kam qo'llaniladi, lekin muhim nazariy ahamiyatga ega va bir xil uzunlikdagi bir nechta naqshlarning mosligini topishda juda samarali. n uzunlikdagi matn va m uzunlikdagi naqsh uchun uning o'rtacha va eng yaxshi bajarilish vaqti to'g'ri tanlangan xesh funksiyasi bilan O(n) dir (pastga qarang), lekin eng yomon holatda u O(nm) samaradorligiga ega, bu juda keng qo'llanilmasligining sabablaridan biri. Qidiruvda noto'g'ri pozitivlarga chidash mumkin bo'lgan ilovalar uchun, ya'ni naqshning topilgan ba'zi holatlari aslida naqshga mos kelmasligi mumkin bo'lgan ilovalar uchun Rabin-Karp algoritmi kafolatlangan O(n) vaqtida va tegishli tasodifiy tanlov bilan ishlaydi. xash funktsiyasi (pastga qarang) xatolik ehtimoli juda kichik bo'lishi mumkin. Algoritm shuningdek, k ning kattaligidan qat’iy nazar, O(n) vaqt ichida berilgan bir xil uzunlikdagi k satrlardan istalgan birini o‘rtacha (xesh funksiyasini to‘g‘ri tanlash bilan) topishning o‘ziga xos xususiyatiga ega.

Rabin-Karp algoritmining eng oddiy amaliy qo'llanmalaridan biri plagiatni aniqlashdir. Aytaylik, bir talaba Mobi Dik haqida maqola yozyapti. Crafty Professor Moby Dick-dan turli manba materiallarini topadi va bu materiallardagi jumlalar ro'yxatini avtomatik ravishda oladi. Keyin Rabin-Karp algoritmi tekshirilayotgan maqoladagi manba materiallaridan ma'lum jumlalarning paydo bo'lishiga misollarni tezda topishi mumkin. Algoritmni kichik farqlarga nisbatan kamroq sezgir qilish uchun ularni olib tashlash orqali katta yoki tinish belgilari kabi tafsilotlarni e'tiborsiz qoldirishingiz mumkin. Biz izlayotgan qatorlar soni, k, juda katta bo'lgani uchun, an'anaviy bir qatorli qidiruv algoritmlari samarasiz bo'lib qoladi.

Algoritm

Algoritm quyidagicha ko'rsatiladi:

function RabinKarp(string s[1..n], string pattern[1..m])
    hpattern := hash(pattern[1..m]);
    for i from 1 to n-m+1
        hs := hash(s[i..i+m-1])
        if hs = hpattern
            if s[i..i+m-1] = pattern[1..m]
                return i
    return not found

2, 4 va 6-qatorlarning har biri O(m) vaqtni talab qiladi. Biroq, 2-qator faqat bir marta bajariladi va 6-qator faqat xesh qiymatlari mos kelsa, bajariladi, bu bir necha marta sodir bo'lishi dargumon. 5-qator O (n) marta bajariladi, lekin har bir taqqoslash faqat doimiy vaqtni talab qiladi, shuning uchun uning ta'siri O (n) dir. Muammo 4-qatorda.

s[i+1..i+m] pastki satri uchun xesh qiymatini sodda tarzda hisoblash O(m) vaqtni talab qiladi, chunki har bir belgi tekshiriladi. Xeshni hisoblash har bir tsiklda amalga oshirilganligi sababli, sodda xeshni hisoblash algoritmi O(mn) vaqtni talab qiladi, bu oddiy satrlarni moslashtirish algoritmi bilan bir xil murakkablik. Tezlik uchun xeshni doimiy vaqtda hisoblash kerak. Ayyorlik shundaki, hs o'zgaruvchisi allaqachon s[i..i+m-1] ning oldingi xesh qiymatini o'z ichiga oladi. Agar bu qiymat doimiy vaqtda keyingi xesh qiymatini hisoblash uchun ishlatilishi mumkin bo'lsa, u holda ketma-ket xesh qiymatlarini hisoblash tez bo'ladi.

Hiyla-nayrangni haddan tashqari xesh yordamida ishlatish mumkin. Rolling xesh - bu operatsiyani yoqish uchun maxsus ishlab chiqilgan xesh funktsiyasi. Arzimas (lekin unchalik yaxshi emas) xesh funksiyasi shunchaki pastki qatordagi har bir belgining qiymatlarini qo'shadi. Ushbu haddelenmiş xesh formulasi doimiy vaqt ichida oldingi qiymatdan keyingi hash qiymatini hisoblashi mumkin:

s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Bu oddiy funktsiya ishlaydi, lekin 5-bo'lim keyingi bo'limda muhokama qilingan boshqa murakkab xesh funksiyalarga qaraganda tez-tez bajarilishiga olib keladi.

Yaxshi ishlash, duch kelgan ma'lumotlar uchun yaxshi xeshlash funktsiyasini talab qiladi. Agar xeshlash yomon bo'lsa (masalan, har bir kirish uchun bir xil xesh qiymatini ishlab chiqarish), u holda 6-qator O(n) marta (ya'ni, tsiklning har bir iteratsiyasida) bajariladi. Uzunligi m boʻlgan satrlarni belgima-belgi bilan taqqoslash O(m) vaqtni oladi, shuning uchun butun algoritm eng yomon holatda O(mn) vaqt oladi.