Mavzu: Matnlar bilan ishlash z-funksiyasi Mundarija: Kirish i-bob. Z algaritmini qo’llash va ishlashi

2.4.Z-algoritm satrini qidirish
Maqsad: Swift-da ma'lum bir naqshning barcha hodisalari indekslarini qaytaradigan oddiy chiziqli vaqt qatorini moslashtirish algoritmini yozing.
Boshqacha qilib aytadigan bo'lsak, biz qidiruv naqshining barcha ko'rinishlari indekslarini ifodalovchi butun sonlar massivini qaytaradigan indexesOf(pattern: String)kengaytmani amalga oshirmoqchimiz yoki agar naqsh satr ichida topilmasa.String[Int]nil
Masalan:
let str = " Salom, o'yin maydonchasi! "
str. indexesOf ( naqsh : " zamin " ) // Chiqish: [11]

yo'l harakati = " 🚗🚙🚌🚕🚑🚐🚗🚒🚚🚎🚛🚐🏎🚜🚗🏍🚒🚲🚕🚓🚌🚑 "

trafik. indexesOf ( naqsh : " 🚑 " ) // Chiqish: [4, 21]
Ko'pgina qatorli qidiruv algoritmlari ketma-ket bosqichda ishlatiladigan jadvalni hisoblash uchun oldindan ishlov berish funktsiyasidan foydalanadi. Ushbu jadval naqsh qidirish bosqichida biroz vaqtni tejashi mumkin, chunki bu keraksiz belgilarni taqqoslashdan qochish imkonini beradi. Z -algoritmi ana shunday funksiyalardan biridir. U naqshni oldindan qayta ishlash funktsiyasi sifatida tug'iladi (bu uning Knuth-Morris-Pratt algoritmidagi roli va boshqalar), lekin biz bu erda ko'rsatganimizdek, uni bitta qatorli qidiruv algoritmi sifatida ham ishlatish mumkin.
Z-algoritmi naqshdan oldingi protsessor sifatida
Aytganimizdek, Z-algoritmi birinchi navbatda o'tkazib yuborish-taqqoslash jadvalini hisoblash uchun naqshni qayta ishlaydigan algoritmdir.
Z-algoritmini naqsh bo'yicha hisoblash butun sonlar Pmassivini ( Zadabiyotda deyiladi) hosil qiladi, bunda har bir element uni , deb ataydi , Z[i]eng uzun pastki qatorning uzunligini ifodalaydi va prefiksga mos keladi . Oddiyroq qilib aytganda, prefiksga mos keladigan eng uzun prefiksni yozadi . Misol tariqasida, ko'rib chiqaylik . Bizda bu bor va .PiPZ[i]P[i...|P|]PP = "ffgtrhghhffgtggfredg"Z[5] = 0 (f...h...)Z[9] = 4 (ffgtr...ffgtg...)Z[15] = 1 (ff...fr...)
Ammo biz qanday hisoblaymiz Z? Algoritmni tasvirlashdan oldin Z-box tushunchasini kiritishimiz kerak. (left, right)Z-box - bu prefiks sifatida ham yuzaga keladigan maksimal uzunlikdagi pastki qatorni qayd qiluvchi hisoblash paytida ishlatiladigan juftlik P. Ikki indeks leftva rightmos ravishda ushbu pastki qatorning chap tomonidagi indeksini va o'ng tomonidagi indeksini ifodalaydi. Z-algoritmining ta'rifi induktivdir va u dan boshlab naqshning
har bir pozitsiyasi uchun massiv elementlarini hisoblaydi . dan keyin quyidagi qiymatlar ( , , ...) hisoblanadi . Algoritmning g'oyasi shundan iboratki, ilgari hisoblangan qiymatlar hisobni tezlashtirishi mumkinkk = 1Z[k + 1]Z[k + 2]Z[k]Z[k + 1], ilgari qilingan ba'zi belgilar taqqoslashlaridan qochish. Ushbu misolni ko'rib chiqing: biz iteratsiyadamiz , shuning uchun biz naqshning k = 100holatini tahlil qilyapmiz . va 100orasidagi barcha qiymatlar to'g'ri hisoblangan va va . Bu shuni anglatadiki , biz ko'rib chiqayotgan naqsh/satr prefiksiga mos keladigan pozitsiyadan boshlanib , pozitsiyada tugaydigan uzunlikning pastki qatori mavjud . Bir oz mulohaza yuritadigan bo'lsak, shuni aytishimiz mumkinki, pozitsiyadan boshlangan uzunlik pastki qatori naqsh pozitsiyasidan boshlanadigan uzunlik qatoriga mos keladi (chunki biz naqsh prefiksiga mos keladigan pastki qator ichidamiz). Shunday qilib, biz hisoblash uchun foydalanishimiz mumkinZ[1]Z[99]left = 70right = 1205170120211002130Z[30]Z[100]qo'shimcha belgilar taqqoslashsiz.
Bu algoritm ortida turgan g'oyaning oddiy tavsifi. Oldindan hisoblangan qiymatlardan foydalanishni to'g'ridan-to'g'ri qo'llash mumkin bo'lmaganda boshqarish uchun bir nechta holatlar mavjud va ba'zi taqqoslashlar amalga oshiriladi.
Mana Z massivini hisoblaydigan funksiya kodi:
func ZetaAlgoritmi ( ptrn : String ) -> [ Int ] ? {

let pattern = Massiv (ptrn. belgilar )

let patternLength : Int = naqsh. hisoblash

guard patternLength > 0 else {

return nil
}

var zeta : [ Int ] = [ Int ]( takrorlash : 0 , hisoblash : naqshUzunlik)

var left : Int = 0

var right : Int = 0
var k_1 : Int = 0
var betaLength : Int = 0
var textIndex : Int = 0
var patternIndex : Int = 0

k uchun 1 ..< patternLength {

if k > o'ng { // Z-box tashqarisida: belgilar mos kelmaguncha solishtiring
naqsh indeksi = 0

k + naqshIndex < naqshUzunlik &&

naqsh[k + naqshIndex] == naqsh[patternIndex] {
patternIndex = patternIndex + 1
}

zeta[k] = naqsh indeksi

agar zeta[k] > 0 {

chap = k
o'ng = k + zeta[k] - 1
}
} else { // Z-box ichida
k_1 = k - chap + 1
betaLength = o'ng - k + 1

if zeta[k_1 - 1 ] < betaLength { // To'liq Z-box ichida: biz avval hisoblangan qiymatlardan foydalanishimiz mumkin

zeta[k] = zeta[k_1 - 1 ]
} else if zeta[k_1 - 1 ] >= betaLength { // To'liq Z-box ichida emas: biz ham solishtirishni davom ettirishimiz kerak
textIndex = betaLength
patternIndex = o'ng + 1

while patternIndex < patternLength && pattern[textIndex] == pattern[patternIndex] {

textIndex = textIndex + 1
patternIndex = patternIndex + 1
}

zeta[k] = naqsh indeksi - k

chap = k
o'ng = patternIndex - 1
}
}
}
zetani qaytarish
}
Keling, yuqoridagi kod bilan misol keltiraylik. Keling, qatorni ko'rib chiqaylik P = “abababbb". Algoritm , bilan k = 1boshlanadi left = right = 0. Shunday qilib, hech qanday Z-box "faol" emas va shuning uchun k > rightbiz belgilarni beetwen P[1]va bilan taqqoslashdan boshlaymiz P[0].
01234567
k: x
abababbb
x
Z: 00000000
left: 0
right: 0
Bizda birinchi taqqoslashda nomuvofiqlik bor va shuning uchun da boshlanadigan pastki qator P[1]prefiksga mos kelmaydi P. Shunday qilib, biz qo'ydik Z[1] = 0va qo'ydik leftva rightteginmasdan. Biz yana bir iteratsiyani bilan boshlaymiz k = 2, bizda bor va yana belgilar bilan 2 > 0taqqoslashni boshlaymiz . Bu safar belgilar mos keladi va shuning uchun biz mos kelmaguncha taqqoslashni davom ettiramiz. Bu pozitsiyada sodir bo'ladi . Belgilar mos keladi , shuning uchun biz qo'yamiz va o'rnatamiz va . Bizda birinchi Z-qutisi bor, bu pastki qator (u ning prefiksiga mos kelishiga e'tibor bering ) pozitsiyasidan boshlanadi .P[2]P[0]64Z[2] = 4left = k = 2right = k + Z[k] - 1 = 5"abab"Pleft = 2
01234567
k: x
abababbb
x
Z: 00400000
left: 2
right: 5
Keyin bilan davom etamiz k = 3. Bizda bor 3 <= 5. Biz ilgari topilgan Z-box ichida va prefiksi ichidamiz P. Shunday qilib, biz oldindan hisoblangan qiymatga ega bo'lgan pozitsiyani izlashimiz mumkin. Biz hisoblaymiz k_1 = k - left = 1, bu prefiks belgisining indeksi ga teng P[k]. Biz tekshiramiz Z[1] = 0va 0 < (right - k + 1 = 3)biz Z-box ichida ekanligimizni aniqlaymiz. Biz ilgari hisoblangan qiymatdan foydalanishimiz mumkin, shuning uchun biz ni qo'yamiz Z[3] = Z[1] = 0va o'zgarishsiz qolamiz. Iteratsiyada biz dastlab tashqi filialni bajaramiz . Keyin ichki bizda bu va . Shunday qilib, pastki qator prefiksli belgilarga mos keladileftright
k = 4elseififk_1 = 2(Z[2] = 4) >= 5 - 4 + 1P[k...r]right - k + 1 = 2Plekin keyingi belgilar uchun bu mumkin emas edi. r + 1 = 6Keyin dan boshlanadigan belgilar bilan boshlanadigan belgilarni solishtirishimiz kerak right - k + 1 = 2. Bizda bor va shuning uchun biz o'rnatishimiz P[6] != P[2]kerak va .Z[k] = 6 - 4 = 2left = 4right = 5
01234567
k: x
abababbb
x
Z: 00402000
left: 4
right: 5
Iteratsiya bilan k = 5biz bor k <= rightva keyin (Z[k_1] = 0) < (right - k + 1 = 1)va shunday qilib o'rnatamiz z[k] = 0. Iteratsiyada 6biz 7tashqi qismning birinchi bo'limini bajaramiz, iflekin bizda faqat nomuvofiqliklar bor, shuning uchun algoritmlar Z-massivni sifatida qaytarishni tugatadi Z = [0, 0, 4, 0, 2, 0, 0, 0].
Z-algoritmi chiziqli vaqtda ishlaydi. PAniqroq qilib aytadigan bo'lsak, o'lchamdagi qator uchun Z-algoritmi ning nishlash vaqtiga ega O(n).
Z-algoritmini satrdan oldingi protsessor sifatida amalga oshirish ZAlgorithm.swift faylida mavjud .
Z-algoritmi qatorni qidirish algoritmi sifatida
Yuqorida muhokama qilingan Z-algoritmi eng oddiy chiziqli vaqt qatorini moslashtirish algoritmiga olib keladi. Uni olish uchun biz naqsh Pva matnni Tsatrda birlashtirishimiz kerak, S = P$Tbu erda na ichida , na $ichida ko'rinmaydigan belgi mavjud . Keyin Z massivini olish algoritmini ishga tushiramiz . Biz qilishimiz kerak bo'lgan yagona narsa Z-massivni skanerdan o'tkazish, unga teng elementlarni izlash (bu naqsh uzunligi). Bunday qiymatni topganimizda, biz hodisa haqida xabar berishimiz mumkin.PTSn
kengaytma satri {

func indexesOf ( naqsh : String ) -> [ Int ] ? {

let patternLength : Int = naqsh. belgilar . hisoblash
/* naqsh va matnni birlashtirish bo'yicha Z-algoritmini hisoblaymiz */
let zeta = ZetaAlgoritm ( ptrn : naqsh + " 💲 " + o'z )

guard zeta != nil else {

return nil
}

var indekslari : [ Int ] = [ Int ]()

/ * Mos naqshlarni topish uchun zeta massivini skanerlang */ i uchun 0 ..< zeta ! . hisoblash {

agar zeta bo'lsa ! [i] == naqsh Uzunligi {
indekslar. qo'shish (i - naqshLength - 1 )
}
}

qo'riqchi ! indekslar. isEmpty else {

nil qaytaradi
}

Qaytish indekslari

}
}

Xulosa
Men bu kurs ishini yozishda Matnlar bilan ishlash Z funksiyasi mavzusini o’rgandim Z algoritmining asosiy ishlashini ko'rib chiqdik .
Shundan so'ng biz Z algoritmining ishlashini yaxshiroq tushunish uchun misolga keldim .
Keyin biz psevdokod/algoritm yordamida Z algoritmi uchun kod yozishni ham o'rganib chiqdim.
Shundan so'ng Z algoritmining vaqt murakkabligi tahlili amalga oshiriladi.
Shundan so'ng biz C++ da Z algoritmini tushuntirish bilan amalga oshirdim
Nihoyat, Z algoritmining ilovalari va misollari muhokama qilindi, shuningdek Z algoritmi unga o'xshash algoritmlar bilan solishtirildi.

<sub>Foydalanilgan adabiyotlar va internet saytlari nomlari
1. Boltayev B.J , Azamatov A.R , Rahimov A.D “Algoritmlash va dasturlash asoslari” kitobi
2. A.M. Po’latov “Algoritmlash va C++ dasturlash asoslari” kitobi
3. A.R. Azamatov “Algoritmlash asoslari” kitobi
4. hozir.org
5. uzvikipediya.org
6. arxiv.uz</sub>