|
Bayer Mur algoritmining tariflari, tavsifi va shift qoidalari
|
| bet | 4/7 | | Sana | 16.12.2023 | | Hajmi | 137,71 Kb. | | #120571 |
Bog'liq Bayer va mur algoritimlari1.2 Bayer 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
II BOB. MUR ALGORITMIDA GALIL QOIDASI ,TURLI TILLARDA ISHLASH PRINSIPI VA TAHLIL QILSH
2.1 Galil qoidasi va ishlash prinsipi
Boyer-Murni sodda, ammo muhim optimallashtirish taklif qilindi Galil 1979 yilda.Ko‘chirishdan farqli o‘laroq, Galil qoidasi har bir hizalamada aniq taqqoslashni tezlashishi bilan mos keladigan qismlarni o‘tkazib yuborish bilan shug‘ullanadi. Faraz qilaylik k1, P bilan taqqoslanadi T belgiga qadar v ning T. Keyin agar P ga o‘tkaziladi k2 uning chap uchi o‘rtasida bo‘lishi kerak v va k1, keyingi taqqoslash bosqichida P pastki qatorga mos kelishi kerak T[(k2 - n)..k1]. Shunday qilib, agar taqqoslashlar pozitsiyaga tushsa k1 ning T, sodir bo‘lishi P o‘tmishni aniq taqqoslamasdan yozib olish mumkin k1. Boyer-Mur samaradorligini oshirishga qo‘shimcha ravishda, eng yomon holatda chiziqli vaqt bajarilishini isbotlash uchun Galil qoidasi talab qilinadi.
Galil qoidasi o‘zining asl nusxasida faqat bir nechta mos keladigan versiyalar uchun amal qiladi. Substring oralig‘ini faqat yangilaydi v = 0, ya'ni to‘liq o‘yin. Submatchlar bilan ishlashning umumlashtirilgan versiyasi 1985 yilda Apostoliko - Giankarlo algoritmi.
Ishlash
Boyer-Mur algoritmining asl nusxasida ko‘rsatilganidek, eng yomon ish vaqti mavjud O (n + m) faqat naqsh bo‘lsa emas matnda ko‘rinadi. Bu birinchi marta isbotlangan Knuth, Morrisva Pratt 1977 yilda,dan so‘ng Gibalar va Odlyzko 1980 yilda ning yuqori chegarasi bilan 5n eng yomon holatda taqqoslashlar. Richard Koul ning yuqori chegarasi bilan dalil keltirdi 3n 1991 yildagi eng yomon holatda taqqoslashlar.
Qachonki naqsh qiladi matnda uchraydi, asl algoritmning ishlash vaqti O (nm) eng yomon holatda. Ikkala naqsh va matn faqat bir xil takrorlangan belgidan iborat bo‘lganda buni ko‘rish oson. Shu bilan birga Galil hukmronligi barcha holatlarda chiziqli ish vaqtiga olib keladi.
Turli xil dasturlar turli xil dasturlash tillarida mavjud. Yilda C ++ u C ++ 17 dan beri standart kutubxonaning bir qismidir Boost beradi umumiy Boyer-Mur izlash ostida amalga oshirish Algoritm kutubxona. Yilda Go (dasturlash tili) dastur mavjud search.go. D (dasturlash tili) foydalanadi BoyerMooreFinder Phobos Runtime Library kutubxonasi tarkibidagi intervallarni predikatlar asosida moslashtirish uchun.
Boyer-Mur algoritmi ham ishlatiladi GNU"s grep.
Quyida bir nechta oddiy dasturlar mavjud.
# shu jumladan # shu jumladan # shu jumladan # shu jumladan #Alphabet_LEN-ni aniqlang 256#define max (a, b) ((a // YOMON XARAKTER QOIDASI.// delta1 jadvali: delta1 [c] oxirgisi orasidagi masofani o‘z ichiga oladi// patning xarakteri va patning eng to‘g‘ri paydo bo‘lishi.//// Agar patda c sodir bo‘lmasa, u holda delta1 [c] = patlen.// Agar c [i] qatorda va c! = Pat [patlen-1] bo‘lsa, biz xavfsiz ravishda i siljitishimiz mumkin// siljish uchun zarur bo‘lgan minimal masofa bo‘lgan delta1 [c] ustiga// pat ichida biron bir belgi bilan qatorlangan [i] qatorini olish uchun oldinga siljiting.// c == pat [patlen-1] nolni qaytarish faqat BMH uchun tashvishlidir// delta2 ga ega emas. BMH bunday holatda qiymat patlenini hosil qiladi.// Biz bu tanlovni asl 0 o‘rniga bajaramiz, chunki u o‘tkazib yuboradi// Ko‘proq. (to‘g‘rimi?)//// Ushbu algoritmphabet_len + patlen vaqtida ishlaydi.bekor make_delta1(ptrdiff_t *delta1, uint8_t *pat, hajmi_t patlen) { uchun (int men=0; men < ALPHABET_LEN; men++) { delta1[men] = patlen; } uchun (int men=0; men < patlen-2; men++) { delta1[pat[men]] = patlen-1 - men; }}// so‘zdan boshlanadigan so‘zning qo‘shimchasi prefiks bo‘lsa, to‘g‘ri// so‘zbool is_prefix(uint8_t *so‘z, hajmi_t so‘zlar, ptrdiff_t pos) { int qo‘shimchasi = so‘zlar - pos; // bu erda strncmp () kutubxona funktsiyasidan ham foydalanishi mumkin // qayt! strncmp (so‘z, & so‘z [pos], qo‘shimchalar); uchun (int men = 0; men < qo‘shimchasi; men++) { agar (so‘z[men] != so‘z[pos+men]) { qaytish yolg‘on; } } qaytish to‘g‘ri;}// so‘z bilan tugaydigan so‘zning eng uzun qo‘shimchasining uzunligi [pos].// suffix_length ("dddbcabc", 8, 4) = 2hajmi_t suffiks_length(uint8_t *so‘z, hajmi_t so‘zlar, ptrdiff_t pos) { hajmi_t men; // qo‘shimchaning uzunligi i birinchi mos kelmasligi yoki boshlanishiga qadar // so‘z uchun (men = 0; (so‘z[pos-men] == so‘z[so‘zlar-1-men]) && (men < pos); men++); qaytish men;}// YAXSHI SUFFIX QOIDASI.// delta2 jadvali: pat [pos] da nomuvofiqlik berilgan bo‘lsa, biz hizalamoqchimiz// keyingi mumkin bo‘lgan to‘liq o‘yin biz nimaga asoslangan bo‘lishi mumkin// pat [pos + 1] haqida pat [patlen-1] haqida bilish.//// holda 1:// pat [pos + 1] pat [patlen-1] patning boshqa joylarida uchramaydi,// navbatdagi ishonchli o‘yin mos kelmaslik yoki undan keyin boshlanadi.// Agar pat [pos + 1 .. patlen-1] pastki qatorida prefiks yotsa// pat, keyingi ishonchli o‘yin bu erda (agar bir nechta bo‘lsa)// pastki qatorda prefikslar, eng uzunini tanlang). Aks holda// keyingi ishonchli o‘yin moslashtirilgan belgidan o‘tib ketadi// pat [patlen-1].//// holda 2:// pat [pos + 1] pat [patlen-1] patning boshqa joylarida uchraydi. The// mos kelmaslik bizga o‘yin oxiriga qaramasligimizni bildiradi.// Ammo, biz o‘yin o‘rtalariga qarab turibmiz.//// 1-holatni ko‘rib chiqadigan birinchi tsikl o‘xshashdir// bilan "orqaga qarab" skanerlash tartibiga moslashtirilgan KMP jadvali// pastki qatorlarni qo‘shimcha cheklash// potentsial prefikslari barchasi qo‘shimchalar. Eng yomon stsenariyda// pat bir xil takrorlangan harfdan iborat, shuning uchun har bir qo‘shimchalar shunday bo‘ladi// prefiks. Faqatgina ushbu tsikl etarli emas, ammo:// Deylik, pat "ABYXCDBYX", matn esa "..... ABYXCDEYX".// Biz X, Y ga mos kelamiz va B! = E ni topamiz. Patning prefiksi yo‘q// "YX" qo‘shimchasida, shuning uchun birinchi tsikl oldinga o‘tishni aytadi// 9 ta belgidan iborat.// KMP jadvaliga yuzaki o‘xshash bo‘lsa ham, KMP jadvali// qisman o‘yin boshlanishi haqidagi ma'lumotlarga tayanadi// BM algoritmi mavjud emas.//// Ikkinchi tsikl 2-holatga murojaat qiladi, chunki suffix_length bo‘lmasligi mumkin// noyob, biz aytadigan minimal qiymatni olishni istaymiz// eng yaqin potentsial o‘yin qanchalik uzoq.bekor make_delta2(ptrdiff_t *delta2, uint8_t *pat, hajmi_t patlen) { ssize_t p; hajmi_t oxirgi_prefix_index = patlen-1; // birinchi tsikl uchun (p=patlen-1; p>=0; p--) { agar (is_prefix(pat, patlen, p+1)) { oxirgi_prefix_index = p+1; } delta2[p] = oxirgi_prefix_index + (patlen-1 - p); } // ikkinchi tsikl uchun (p=0; p < patlen-1; p++) { hajmi_t slen = suffiks_length(pat, patlen, p); agar (pat[p - slen] != pat[patlen-1 - slen]) { delta2[patlen-1 - slen] = patlen-1 - p + slen; } }}// Ko‘rsatkichni birinchi o‘yinga qaytaradi.// Shuningdek qarang: glibc memmem () (BM bo‘lmagan) va std :: boyer_moore_searcher (birinchi o‘yin).uint8_t* nilufar (uint8_t *mag‘lubiyat, hajmi_t simli, uint8_t *pat, hajmi_t patlen) { ptrdiff_t delta1[ALPHABET_LEN]; ptrdiff_t delta2[patlen]; // C99 VLA make_delta1(delta1, pat, patlen); make_delta2(delta2, pat, patlen); // Bo‘sh naqsh maxsus ko‘rib chiqilishi kerak agar (patlen == 0) { ozod(delta2); qaytish mag‘lubiyat; } hajmi_t men = patlen - 1; // str-idx esa (men < simli) { ptrdiff_t j = patlen - 1; // pat-idx esa (j >= 0 && (mag‘lubiyat[men] == pat[j])) { --men; --j; } agar (j < 0) { ozod(delta2); qaytish &mag‘lubiyat[men+1]; } ptrdiff_t siljish = maksimal(delta1[mag‘lubiyat[men]], delta2[j]); men += siljish; } ozod(delta2); qaytish NULL;}
|
| |
