|
Python dasturida ishlash prinsipi
|
| bet | 5/7 | | Sana | 16.12.2023 | | Hajmi | 137,71 Kb. | | #120571 |
Bog'liq Bayer va mur algoritimlari2.1 Python dasturida ishlash prinsipi
Ushbu versiya ingliz alifbosiga ASCII-da sezgir mos keltirish uchun sezgir.# Ushbu funktsiyani olib tashlash uchun alf_dexini ord (c) deb belgilang va "26" ning o‘rnini almashtiring# "256" yoki istalgan maksimal kod nuqtasi bilan. Unicode uchun siz UTF-8 ga mos kelishingiz mumkin0x10FFFF o‘lchamdagi jadval yaratish o‘rniga # bayt.ALPHABET_SIZE = 26def alfavit_indeks(v: str) -> int: "" "Berilgan belgi indeksini ingliz alifbosida 0 dan boshlab qaytaring. val = ord(v.pastroq()) - ord("a") tasdiqlash val >= 0 va val < ALPHABET_SIZE qaytish valdef match_length(S: str, idx1: int, idx2: int) -> int: "" "Idx1 va idx2 dan boshlanadigan S satrlarining mos uzunligini qaytaring." "" agar idx1 == idx2: qaytish len(S) - idx1 match_count = 0 esa idx1 < len(S) va idx2 < len(S) va S[idx1] == S[idx2]: match_count += 1 idx1 += 1 idx2 += 1 qaytish match_countdef fundamental_preprocess(S: str) -> Ro‘yxat[int]: "" "Qaytish Z, S ning asosiy qayta ishlanishi. Z [i] - bu I dan boshlanadigan pastki satr uzunligi va u ham S ning prefiksi. Ushbu oldindan ishlov berish O (n) vaqtida amalga oshiriladi, bu erda n - S ning uzunligi. """ agar len(S) == 0: # Bo‘sh satrni boshqaradi qaytish [] agar len(S) == 1: # Bitta simvolli qatorni boshqaradi qaytish [1] z = [0 uchun x yilda S] z[0] = len(S) z[1] = match_length(S, 0, 1) uchun men yilda oralig‘i(2, 1 + z[1]): # 1-5 mashqdan optimallashtirish z[men] = z[1] - men + 1 # Z-boxning pastki va yuqori chegaralarini belgilaydi l = 0 r = 0 uchun men yilda oralig‘i(2 + z[1], len(S)): agar men <= r: # i mavjud z-qutiga tushadi k = men - l b = z[k] a = r - men + 1 agar b < a: # b mavjud z-box ichida tugaydi z[men] = b boshqa: # b z-box tugagandan keyin yoki tugagandan so‘ng tugaydi, biz z-boxning o‘ng tomoniga aniq mos kelishimiz kerak z[men] = a + match_length(S, a, r + 1) l = men r = men + z[men] - 1 boshqa: # i mavjud z-box ichida yashamaydi z[men] = match_length(S, 0, men) agar z[men] > 0: l = men r = men + z[men] - 1 qaytish zdef bad_character_table(S: str) -> Ro‘yxat[Ro‘yxat[int]]: """ S uchun R hosil qiladi, bu ba'zi bir belgilar c ning ichida joylashganligi bilan indekslangan massivdir Ingliz alifbosi. R-dagi indeksda har biri uchun belgilanadigan | S | +1 uzunlik massivi mavjud S-dagi indeks (plyuskadan keyingi indeks) qachon paydo bo‘lgan c belgilarining keyingi joylashuvi i dan boshlab S dan o‘ngga chapga o‘tish. Bu doimiy ravishda qidirish uchun ishlatiladi Boyer-Mur satrlarni qidirish algoritmidagi yomon belgilar qoidasi uchun bo‘lsa ham doimiy bo‘lmagan vaqt echimlariga qaraganda ancha katta hajm. """ agar len(S) == 0: qaytish [[] uchun a yilda oralig‘i(ALPHABET_SIZE)] R = [[-1] uchun a yilda oralig‘i(ALPHABET_SIZE)] alfa = [-1 uchun a yilda oralig‘i(ALPHABET_SIZE)] uchun men, v yilda sanab o‘tish(S): alfa[alfavit_indeks(v)] = men uchun j, a yilda sanab o‘tish(alfa): R[j].qo‘shib qo‘ying(a) qaytish Rdef yaxshi_suffix_table(S: str) -> Ro‘yxat[int]: """ Kuchli yaxshi qo‘shimchalar qoidasini amalga oshirishda ishlatiladigan massiv S uchun L hosil qiladi. L [i] = k, S ning eng katta pozitsiyasi, S [i:] (i-dan boshlanadigan S qo‘shimchasi) mos keladi S [: k] qo‘shimchasi (k bilan tugaydigan S satri). Boyer-Murda ishlatilgan, L miqdori beradi T-ga nisbatan P-ni siljiting, chunki T-dagi P holatlari o‘tkazib yuborilmasligi va P-ning qo‘shimchasi [: L [i]] oldingi o‘yin urinishida P qo‘shimchasi bilan mos keladigan T substringiga mos keladi. Xususan, agar mos kelmaslik P-da i-1 holatida bo‘lsa, siljish kattaligi berilgan len (P) - L [i] tenglamasi bo‘yicha. L [i] = -1 bo‘lgan taqdirda, to‘liq siljish jadvali ishlatiladi. Faqatgina tegishli qo‘shimchalar muhim bo‘lgani uchun L [0] = -1. """ L = [-1 uchun v yilda S] N = fundamental_preprocess(S[::-1]) # S [:: - 1] S ni teskari yo‘naltiradi N.teskari() uchun j yilda oralig‘i(0, len(S) - 1): men = len(S) - N[j] agar men != len(S): L[men] = j qaytish Ldef to‘liq_shift_table(S: str) -> Ro‘yxat[int]: """ Boyer-Murda yaxshi qo‘shimchalar qoidasining maxsus holatida ishlatiladigan massivni S uchun F hosil qiladi satrlarni qidirish algoritmi. F [i] - S [i:] ning eng uzun qo‘shimchasining uzunligi, u ham a S.ning prefiksi, u ishlatilgan holatlarda, P naqshining, ga nisbatan siljish kattaligi i-1da yuzaga keladigan nomuvofiqlik uchun T len (P) - F [i]. """ F = [0 uchun v yilda S] Z = fundamental_preprocess(S) eng uzun = 0 uchun men, zv yilda sanab o‘tish(teskari(Z)): eng uzun = maksimal(zv, eng uzun) agar zv == men + 1 boshqa eng uzun F[-men - 1] = eng uzun qaytish Fdef string_search(P, T) -> Ro‘yxat[int]: """ Boyer-Mur satrlarni qidirish algoritmini amalga oshirish. Bu $ P $ ning barcha hodisalarini topadi T-da va optimalni aniqlash uchun naqshni oldindan qayta ishlashning ko‘plab usullarini o‘z ichiga oladi qatorni siljitish va taqqoslashni o‘tkazib yuborish uchun miqdor. Amalda u O (m) da ishlaydi (va hatto) sublinear) vaqt, bu erda m - T ning uzunligi. Ushbu dastur kichik harflar bilan bajariladi bo‘shliqlarga kiritilmagan ASCII alifbo belgilaridan qidirish. """ agar len(P) == 0 yoki len(T) == 0 yoki len(T) < len(P): qaytish [] gugurt = [] # Oldindan ishlov berish R = bad_character_table(P) L = yaxshi_suffix_table(P) F = to‘liq_shift_table(P) k = len(P) - 1 # P uchining T ga nisbatan hizalanishini anglatadi oldingi_k = -1 # Oldingi bosqichda hizalanishni anglatadi (Galil qoidasi) esa k < len(T): men = len(P) - 1 # Pda solishtirish uchun belgi h = k # Tda taqqoslanadigan belgi esa men >= 0 va h > oldingi_k va P[men] == T[h]: # P oxiridan boshlanadigan o‘yinlar men -= 1 h -= 1 agar men == -1 yoki h == oldingi_k: # Match topildi (Galilning qoidasi) gugurt.qo‘shib qo‘ying(k - len(P) + 1) k += len(P) - F[1] agar len(P) > 1 boshqa 1 boshqa: # Mos kelmaydi, yomon xarakterga va yaxshi qo‘shimchalar qoidalariga qarab siljiting char_shift = men - R[alfavit_indeks(T[h])][men] agar men + 1 == len(P): # Muvofiqlik birinchi urinishda sodir bo‘ldi qo‘shimchani almashtirish = 1 elif L[men + 1] == -1: # Mos keluvchi qo‘shimchalar P ning hech bir joyida ko‘rinmaydi qo‘shimchani almashtirish = len(P) - F[men + 1] boshqa: # Uyg‘unlashtiruvchi qo‘shimchada P ko‘rinadi qo‘shimchani almashtirish = len(P) - 1 - L[men + 1] siljish = maksimal(char_shift, qo‘shimchani almashtirish) oldingi_k = k agar siljish >= men + 1 boshqa oldingi_k # Galilning qoidasi k += siljish qaytish gugurt
The Boyer-Mur-Xorspool algoritmi Boyer-Mur algoritmini faqat yomon belgilar qoidasi yordamida soddalashtirishdir.
The Apostoliko - Giankarlo algoritmi belgining aniq taqqoslanishini o‘tkazib yuborish orqali berilgan kelishuvda mos kelish yoki yo‘qligini tekshirish jarayonini tezlashtiradi. Bunda naqshni oldindan qayta ishlash jarayonida yig‘ilgan ma'lumotlar har bir o‘yin tashabbusida qayd etilgan qo‘shimchalarning mos kelish uzunliklari bilan birgalikda ishlatiladi. Qo‘shimchalarning mos uzunliklarini saqlash uchun qidirilayotgan matnga teng hajmdagi qo‘shimcha jadval kerak.
The Raita algoritmi Boyer-Mur-Horspool algoritmining ish faoliyatini yaxshilaydi. Berilgan satrda ma'lum bir sub-stringni qidirish tartibi Boyer-Mur-Horspool algoritmidan farq qiladi.
|
| |
