|
Bayer Mur algoritmining tariflari, tavsifi va shift qoidalari
|
| bet | 4/8 | | Sana | 17.11.2023 | | Hajmi | 50,67 Kb. | | #100256 |
Bog'liq Samarqand davlat universiteti raqamli texnologiyalar fakulteti d-hozir.org 8007254, 2 5273916464473058944Bayer Mur algoritmining tariflari, tavsifi va shift qoidalari
S[men] indeksdagi belgini bildiradi men ip S, 1dan hisoblash.
S[men..j] belgisini bildiradi pastki chiziq ip S indeksdan boshlab men va tugaydi j, shu jumladan.
A prefiks ning S substring hisoblanadi S[1..men] kimdir uchun men oralig‘ida [1, n], qaerda n ning uzunligi S.
A qo‘shimchasi ning S substring hisoblanadi S[men..n] kimdir uchun men oralig‘ida [1, n], qaerda n ning uzunligi S.
Qidirilayotgan satr naqsh va bilan belgilanadi P. Uning uzunligi n.
Qidirilayotgan satr matn va bilan belgilanadi T. Uning uzunligi m.
An hizalama ning P ga T bu indeks k yilda T ning oxirgi belgisi P indeks bilan hizalanadi k ning T.
A o‘yin yoki voqea ning P agar hizalamada sodir bo‘lsa P ga teng T[(k-n+1).
A N P A N M A N -
P A N - - - - - -
- P A N - - - - -
- - P A N - - - -
- - - P A N - - -
- - - - P A N - -
- - - - - P A N -
Naqshning hizalanması PAN matn yuborish ANPANMAN, dan k = 3 ga k = 8. Uchrashuv sodir bo‘ladi k = 5.
Boyer-Mur algoritmi paydo bo‘lishlarni qidiradi P yilda T turli xil hizalamalarda aniq belgilar taqqoslashlarini amalga oshirish orqali. A o‘rniga qo‘pol kuch bilan qidirish barcha hizalamalar (ular mavjud m-n + 1), Boyer-Mur oldindan qayta ishlash natijasida olingan ma'lumotlardan foydalanadi P imkon qadar ko‘proq hizalamaları o‘tish uchun.
Ushbu algoritmni joriy etishdan avval matn ichida izlashning odatiy usuli naqshning har bir belgisini naqshning birinchi belgisi uchun tekshirish edi. Bu topilgandan so‘ng matnning keyingi belgilarini naqsh belgilariga solishtirish mumkin edi. Agar hech qanday mos kelmasa, matni yana bir belgi bo‘yicha tekshirilib, moslikni topish uchun. Shunday qilib, matndagi deyarli har bir belgi tekshirilishi kerak.
Ushbu algoritmning asosiy tushunchasi shundan iboratki, agar naqshning oxiri matn bilan taqqoslansa, unda matnning har bir belgisini tekshirishdan ko‘ra, matn bo‘ylab sakrash mumkin. Ushbu ishning sababi shundan iboratki, naqshni naqshga bir qatorga qo‘yishda naqshning oxirgi belgisi matndagi belgi bilan taqqoslanadi. Agar belgilar mos kelmasa, matn bo‘ylab orqaga qarab qidirishni davom ettirishning hojati yo‘q. Agar matndagi belgi naqshdagi biron bir belgiga to‘g‘ri kelmasa, unda tekshiriladigan keyingi belgi joylashgan bo‘ladi n matn bo‘ylab joylashgan belgilar, qaerda n naqshning uzunligi. Agar matndagi belgi bo‘lsa bu naqshda, keyin mos keladigan belgi bo‘ylab bir qatorga kelish uchun naqshning qisman siljishi amalga oshiriladi va jarayon takrorlanadi. Matndagi har bir belgini tekshirishdan ko‘ra, taqqoslash uchun matn bo‘ylab sakrash, taqqoslashlar sonini kamaytiradi, bu algoritm samaradorligining kalitidir.
Rasmiy ravishda, algoritm tekislashdan boshlanadi k = n, shuning uchun boshlanishi P ning boshlanishiga to‘g‘ri keladi T. Belgilar P va T keyin indeksdan boshlab taqqoslanadi n yilda P va k yilda Torqaga qarab harakatlanmoqda. Iplar oxiridan mos keladi P boshlanishiga qadar P. Taqqoslashlar boshlanishiga qadar davom etadi P erishilgan (bu mos keladigan o‘yin degan ma'noni anglatadi) yoki bir nechta qoidalar tomonidan ruxsat etilgan maksimal qiymatga muvofiq hizalanish oldinga (o‘ngga) siljigan holda nomuvofiqlik paydo bo‘ladi. Taqqoslashlar yana yangi hizalamada amalga oshiriladi va jarayon hizalama oxiridan o‘tguncha takrorlanadi T, bu boshqa o‘yinlar topilmasligini anglatadi.
Shift qoidalari oldindan ishlov berish jarayonida hosil bo‘lgan jadvallardan foydalangan holda doimiy jadvallarni qidirish sifatida amalga oshiriladi P.
Shift ikki qoidani qo‘llash orqali hisoblanadi: yomon belgilar qoidasi va yaxshi qo‘shimchalar qoidasi. Haqiqiy siljish ofseti - bu qoidalar bo‘yicha hisoblangan maksimal siljishlar.
Yomon belgilar qoidasi
Tavsif
Yomon belgilar qoidasi belgini in T unda taqqoslash jarayoni muvaffaqiyatsiz tugadi (agar bunday nosozlik yuz bergan bo‘lsa). Ushbu belgining navbatdagi ko‘rinishi chap tomonda P topilgan va bu sodir bo‘lishni mos kelmaydigan hodisaga mos keladigan siljish T taklif qilingan. Agar mos kelmagan belgi chap tomonda ko‘rinmasa P, butunlay siljitadigan siljish taklif etiladi P nomuvofiqlik nuqtasidan o‘tgan.
- - - - X - - K - - -
A N P A N M A N A M -
- N N A A M A N - - -
- - - N N A A M A N -
Yomon belgilar qoidasini naqsh bilan namoyish etish NNAAMAN.
Oldindan ishlov berish
Uslublar noto‘g‘ri belgilar qoidalari jadvalining aniq shaklidan farq qiladi, ammo doimiy doimiy qidirish echimi quyidagicha: birinchi bo‘lib belgi indekslari bilan indekslangan 2 o‘lchovli jadval yarating. v alifboda va indeks bo‘yicha ikkinchi men naqshda. Ushbu qidiruv sodir bo‘lganlikni qaytaradi v yilda P keyingi eng yuqori ko‘rsatkich bilan j Quyidagi C va Java dasturlarida a mavjud Ok) kosmik murakkablik (make_delta1, makeCharTable). Bu asl delta1 va BMH yomon belgilar jadvali. Ushbu jadval belgini pozitsiyada xaritada aks ettiradi men o‘tish { displaystyle operatorname {len} (p) -1-i}, oxirgi instansiya bilan - eng kam siljish miqdori birinchi o‘ringa olinadi. Barcha ishlatilmaydigan belgilar quyidagicha o‘rnatiladi { displaystyle operatorname {len} (p)} qo‘riqchi qiymati sifatida.
Yaxshi qo‘shimchaning qoidasi
Tavsif
Yaxshi qo‘shimchalar qoidasi tushunchada ham, amalga oshirishda ham yomon belgilar qoidalariga qaraganda ancha murakkabroq. Yomon belgilar qoidasi singari, u algoritmning taqqoslash xususiyatidan foydalanadi va naqsh oxirida boshlanadi va naqsh boshlanishiga qarab davom etadi. Buni quyidagicha ta'riflash mumkin:
- - - - X - - K - - - - -
M A N P A N A M A N A P -
A N A M P N A M - - - - -
- - - - A N A M P N A M -
Yaxshi qo‘shimchalar qoidasini naqsh bilan namoyish etish ANAMPNAM.
Faraz qilaylik P va T, substring t ning T qo‘shimchasiga to‘g‘ri keladi P, lekin chapga taqqoslaganda nomuvofiqlik paydo bo‘ladi. Agar mavjud bo‘lsa, unda eng to‘g‘ri nusxasini toping t ' ning t yilda P shu kabi t ' ning qo`shimchasi emas P va chap tomonidagi belgi t ' yilda P belgidan chapga qarab farq qiladi t yilda P. Shift P o‘ng tomonga, shunday qilib substring t ' yilda P pastki chiziq bilan tekislanadi t yilda T. Agar t ' mavjud emas, keyin chap uchini siljiting P chap uchidan o‘tgan t yilda T ko‘chirilgan naqshning prefiksi qo‘shimchaga to‘g‘ri kelishi uchun eng kam miqdorda t yilda T. Agar bunday siljish mumkin bo‘lmasa, u holda siljiting P tomonidan n o‘ng tomonda joylashgan joylar. Agar paydo bo‘lsa P topildi, keyin siljiting P eng kam miqdorda, shunday qilib a to‘g‘ri smenaning prefiksi P ning yuzaga kelgan qo‘shimchasiga mos keladi P yilda T. Agar bunday siljish mumkin bo‘lmasa, u holda siljiting P tomonidan n joylar, ya'ni siljish P o‘tmish t.
Oldindan ishlov berish
Yaxshi qo‘shimchalar qoidasi ikkita jadvalni talab qiladi: biri umumiy holatda foydalanish uchun, ikkinchisi esa umumiy holat hech qanday mazmunli natija bermagan yoki mos kelmasa foydalanish uchun. Ushbu jadvallar belgilanadi L va H navbati bilan. Ularning ta'riflari quyidagicha:
Har biriga men, L [i] ga nisbatan eng katta pozitsiyadir n shunday ip P [i..n] qo‘shimchasiga to‘g‘ri keladi P [1..L [i]] va shu qo‘shimchadan oldingi belgi teng bo‘lmasligi uchun P [i-1]. L [i] shartni qondiradigan pozitsiya bo‘lmasa, nolga teng deb belgilanadi.
Ruxsat bering H [i] ning eng katta qo‘shimchasining uzunligini belgilang P [i..n] bu ham prefiksidir P, agar mavjud bo‘lsa. Agar yo‘q bo‘lsa, ruxsat bering H [i] nolga teng
Ushbu jadvallarning ikkalasi ham tuzilishi mumkin O (n) vaqt va foydalanish O (n) bo‘sh joy. Indeks uchun hizalama siljishi men yilda P tomonidan berilgan n-L [i] yoki n-H [i]. H faqat agar ishlatilishi kerak L [i] nolga teng yoki gugurt topilgan
|
| |
