|
Galil qoidasi va ishlash prinsipi
|
| bet | 5/8 | | Sana | 17.11.2023 | | Hajmi | 50,67 Kb. | | #100256 |
Bog'liq Samarqand davlat universiteti raqamli texnologiyalar fakulteti d-hozir.org 8007254, 2 5273916464473058944Galil 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;}
|
| |
