Rabin-karp algoritmi

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ʻllanadi, 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.