Suffiks avtomat. O (N log N) da qurish va qo‘llash

Информация о документе

Цена	10000UZS
Размер	732.6KB
Покупки	0
Дата загрузки	06 Ноябрь 2026
Расширение	pdf
Раздел	Курсовые работы
Предмет	Педагогика

Suffiks avtomat. O (N log N) da qurish va qo‘llash

Купить

O’ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA -MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
RAQAMLI TEXNOLOGIYALAR FAKULTETI

AMALIY MATEMATIKA YO’NALISHI
201 -GURUH TALABASI
TURSUNMURODOV OG‘ABEK NING
ALGARITM VA MA’LUMOTLAR STRUKTURASI
FANIDAN

Suffiks avtomat. O (N log N) da qurish va qo`llash
mavzusida
KURS ISHI

Ilmiy rahbar: Yusupov Ozod
Tayorladi: Tursunmurodov Og’abek

SAMARQAND – 2022

M undarija
1. Kirish …………………………………………
2. Asosiy qism:
a.Suffix avtomat haqida umumiy tushuncha
b. Suffix massiv haqida umumiy tushuncha
c. Avtomatning qo'shimcha ta'rifi
d. Suffiks avtomatlarini qurish uchun chiziqli vaqt algoritmi
3. Xulosa
4. Foydalanilgan adabiyotlar va web saytlar

Kirish
Bugungi kunda axborot texnologiyalari sohasi respublikamizning
rivojlanishida muhim o‘rin tutib kelmoqda . O ‘tgan yillar mobaynida O ‘zbekiston
Respublikasi hukumati tomonidan yurtimizda axborot texnologiyalarini keng joriy
qilish va rivojlantirish borasida olib borgan siyosati hozirgi kunga kelib o‘z
natijalarini ko ‘rsatmoqda . Bu qatorning qoʻshimcha massivi
{11,8,1,4,6,9,2,5,7,10,3}, chunki “a” qoʻshimchasi 11 -belgidan, “abra” qoʻshimchasi
bilan boshlanadi. 8 -belgi. ket va hokazo, a sl so'zning uchinchi belgisidan
boshlanadigan oxirgi "racadabra" qo'shimchasigacha. Endi ushbu massivdan
foydalanib, barcha pastki qatorlarni osongina topishingiz mumkin. Misol uchun, agar
siz "ab" pastki qatorini topishingiz kerak bo'lsa, "ab" bilan bosh langan barcha
qo'shimchalarni topish kifoya. Alifbo tartibida tartiblash orqali ular bir -birining
yonida joylashgan. Ikkilik qidiruvdan foydalanib, biz qo'shimchalar qatorining 2 va 3
elementlariga mos keladigan "abra" va "abracadabra" 2 va 3 -chi qo'shimch alarini
topamiz (8 va 1). Bu shuni anglatadiki, qidirilayotgan "ab" pastki qatori asl so'zning
birinchi va sakkizinchi belgilarida uchrayd 2019 yilda axborot -kommunikatsiya
texnologiyalari sohasining asosiy ko‘rsatqichlari
Iqtisodiy raqamlarga nazar tashla nadigan bo‘lsak, o‘tgan yildagi natijalarni
ijobiy deb baholasa bo‘ladi. AKT sohasida ko‘rsatilgan jami xizmatlar hajmi 10,6
trillion so‘mgacha yetib, 104% o‘sishini ko‘rsatdi. Aloqa va axborotlashtirish
xizmatlari esa 176 million dollargacha, ya’ni 130 fo izgacha o‘sdi. Internet
tarmog‘ining milliy segmenti “UZ” domenida ro‘yxatdan ơtgan veb -saytlarni
tashkil etish orqali iste'molchilarga qulay xizmatlar ko‘rsatish, yoshlarning onlayn
tarzda bilim olishlari va aholiga elektron savdo tizimlari orqali xizma tlar ko‘rsatish
yơlga qo‘yildi. Onlayn -to‘lov tizimidagi ishlar ham yahshi ko‘rsatqichlar
bilan yakunlandi, ya‘ni 2019 yilda onlayn -to‘lov tizimlari orqali 299,3 million
tranzaktsiyalar amalga oshirildi va jami 6,5 trillion o to‘lov so‘mni tashkil etdi .
Aholi va tadbirkorlik sub’ektlarining davlat organlari bilan kontaktsiz aloqa
shakllarini yanada rivojlantirish maqsadida Yagona interaktiv davlat xizmatlari
portalining yangi versiyasi ishlab chiqildi.

Bugungi kunda Yagona portal orqali 176 ta elektron davlat xizmati taqdim
etilmoqda, ushbu xizmatlardan foydalanish uchun 15,1 mln. ta ariza -buyurtma kelib
tushgan, bu davlat organlari bilan o‘zaro aloqada aholining vaqt va moliyaviy
xarajatlarini kamaytirishga yordam berdi. Yagona interaktiv davlat xizmat lari portali
tizimi orqali hozirgi davrda aholiga 176 ta davlat xizmatlari ko‘rsatiladi. 2019 yil
yakunlari bo‘yicha 15,1 milliona ta ariza -buyurtma bilan ish olib borildi.
Yagona idoralararo ijro intizomi tizimi bo‘yicha hozirgi vaqtda tizimga 4,4 mingdan
ortiq davlat organlari va tashkilotlar, 30 mingdan ortiq foydalanuvchilar ulandi.
Tadbirkorlarning, shu jumladan, chet el investorlari murojaatlari bilan ishlashni
tashkil etish sifati va tezkorligini oshirish, ular bilan ochiq va to‘g‘ridan -to‘g‘ri
muloq otni ta’minlash, ularning qonuniy talablarini amaliy va samarali ro‘yobga
chiqarish va muammoli masalalarini hal etish maqsadida Bosh vazirning tadbirkorlar
murojaatlarini ko‘rib chiqish virtual qabulxonasi “business.gov.uz” portali ishga
tushirildi. Bugun gi kunda ushbu portal orqali 34,7 mingta murojaat kelib tushib,
shulardan 33,6 mingtasi ko‘rib chiqilgan.Tadbirkorlar murojaatlarini ko‘rib chiqish
yagona interaktiv portali faoliyati natijalariga ko‘ra, o‘tgan yili jami 34,7 mingta
murojaat to‘shgan bo‘ls a, ulardan 33,6 mingtasi ko‘rib chiqildi. Saylov jarayonini
boshqarish axborot tizimi (“saylov.gov.uz”) joriy qilindi. Manfaatdor vazirlik va
idoralar bilan hamkorlikda 20,5 mln. dan ortiq fuqarolardan iborat Saylovchilarning
yagona elektron ro‘yxati shakl lantirilib, Saylov jarayonini boshqarish axborot tizimi
bilan integratsiya qilindi.
Hozirda Xitoyning yirik kompaniyalari bilan hamkorlikda 1 bosqichda Toshkent
shahrida to‘g‘ridan -to‘g‘ri xorijiy investitsiyalarni jalb etgan holda “Xavfsiz
shahar” loyihas ining yagona texnologik platformasini yaratish ishlari amalga
oshirilmoqda. O‘zbekiston Respublikasi Prezidentining Oliy Majlisiga
Murojaatnomasida 2020 yilni “Ilm -ma’rifat va raqamli iqtisodiyotni rivojlantirish
yili”, deb e’lon qilinishi hamda shu bo‘yic ha “yo‘l xaritasi” ishlab chiqilgani ham
axborot texnologiyalari sohasiga muhim ahamiyat berilayotganini ko‘rsatmoqda.
Prezidentimizning 2020 yil 2 martdagi farmoni bilan tasdiqlangan Harakatlar
strategiyasining “Ilm, ma’rifat va raqamli iqtisodiyotni rivo jlantirish yili”da amalga

oshirishga oid davlat dasturi ijrosini ta’minlashda eng ustuvor vazifalaridan biri,
ijtimoiy soha ob’ektlari, jumladan, umumta’lim maktablari, maktabgacha ta’lim va
sog‘liqni saqlash muassasalarini tezkor internetga ulash vazifasi qo‘yildi. Bu, o‘z
navbatida, yosh avlodning zamonaviy bilim olishi, bemorlarga sifatli va tezkor
xizmat ko‘rsatish salohiyatini oshirishi bilan ahamiyatlidir. Shundan kelib chiqib,
telekommunikatsiya infratuzilmasini rivojlantirish borasida yirik loyihalar amalga
oshirilmoqda. Bugungi kunda 1 millionta Internet tarmog‘iga keng polosali ulanish
portlari o‘rnatilib, ularning umumiy soni 3 millionga yetkazildi. Bun dan tashqari, 32
ming kilometr optik tolali aloqa liniyalari qurildi.
Ma’lumotlar uzatish tarmog‘ining o‘tkazuvchanlik qobiliyati viloyat
markazlari darajasida 2 barobarga, tuman markazlari darajasida esa 4 barobar oshdi.
Xizmat miqyosini kengaytirish maqs adida 5 mingtadan ortiq mobil aloqa baza
stansiyasi o‘rnatilib, ularning jami soni 32 mingtaga yetkazildi va aholi
maskanlarida uning qamrovi 98 foizga hamda yuqori tezlikdagi yo‘nalishi 90 foizga
yetkazildi. Aholining keng polosali mobil xizmatlariga bo‘l gan ehtiyojini qondirish
maqsadida “O‘zbektelekom” AK “O‘zmobayl” filiali tomonidan mavjud 3 000 dan
ortiq baza stansiyasi modernizatsiya qilindi.

Mavzu: Suffiks avtomat. O (N log N) da qurish va
qo`llash
REJA
1. Suffeks avtomat haqida malumot
2. Suffix massiv h aqida umumiy tushuncha
3. Avtomatning qo'shimcha ta'rifi
4. Suffiks avtomatlarini qurish uchun chiziqli vaqt algoritmi

1. Suffeks avtomat haqida malumot
Suffiks avtomatlari va omil avtomatlari qatorlar to'plamining to'liq indeksini
ifodalash uchun samarali ma'lumotlar tuzilmasi hisoblanadi. Ular qatorlar
to'plamining barcha qo'shimchalari yoki pastki qatorlari to'plamini ifodalovchi
minimal deterministik avtomatlardir. Ushbu ma qola qatorlar to'plamining avtomat
yoki faktor avtomat qo'shimchasining o'lchamining yangi tahlilini taqdim etadi. Bu
shuni ko'rsatadiki, U qatorlar to'plamining avtomatik qo'shimchasi yoki omil
avtomati ko'pi bilan 2Q -2 holatga ega, bu erda Q - U dagi sa trlarni ifodalovchi
prefiks daraxtining tugunlari soni. Bu chegara 2k U k− 1 dan ko'proq yaxshilanadi. ,
Blumer va boshqalar tomonidan berilgan chegara. (1987), bu erda k U k - U dagi
barcha qatorlar uzunligi yig'indisi. Umuman olganda, biz avtomatning qo' shimchasi
yoki omil avtomatining o'lchami uchun yangi va umumiy chegaralarni asl avtomat
hajmining funktsiyasi sifatida beramiz. va u qabul qiladigan qatorlar tomonidan
bo'lingan qo'shimchaning maksimal uzunligi.

$Shuningdek, biz O(|S|) vaqtida U ning avtom atS qo'shimchasini yoki F omil avtomatini qurish uchun chiziqli vaqt algoritmini batafsil tasvirlab beramiz. Bizning algoritmimiz aslida har qanday kirish qo'shimchasi -noyob avtomatiga taalluqlidir va bitta kirish qatori uchun qo'shimcha avtomatining stand art onlayn qurilishini qat'iy umumlashtiradi. Bizning algoritmimiz satrlar to'plamining oracleor faktor oracle qo'shimchasini yaratish uchun ham to'g'ridan -to'g'ri ishlatilishi mumkin, bu qatorlarni moslashtirishda turli xil foydali xususiyatlarga ega ekan ligi ko'rsatilgan. Bizning tahlilimiz shuni ko'rsatadiki, avtomatlarning omilli avtomatlaridan foydalanish keng ko'lamli ilovalar uchun amaliy bo'lishi mumkin, bu fakt faktor avtomatlarini 15 000 dan ortiq qo'shiqlardan iborat musiqani identifikatsiya qili sh vazifasiga qo'llash bo'yicha tajribalarimiz natijalari bilan qo'shimcha ravishda tasdiqlanadi. Informatika fanida qo'shimchalar qatori qatorning barcha qo'shimchalarining tartiblangan massividir. Bu to'liq matn indekslari, ma'lumotlarni siqish algoritml ari va bibliometriya sohasida qo'llaniladigan ma'lumotlar strukturasidir. Suffiks massivlari Manber va Myers (1990) tomonidan qo'shimcha daraxtlarga oddiy, bo'sh joyni tejaydigan muqobil sifatida kiritilgan. Ular 1987 yilda Gaston Gonnet tomonidan PAT mass ivi nomi bilan mustaqil ravishda kashf etilgan (Gonnet, Baeza - Yates & Snider 1992). Li, Li & Huo (2016) birinchi oʻrinda { \displaystyle { \mathcal {O}}(n)}{ \mathcal {O}}(n) vaqt qoʻshimchasi massivini qurish algoritmini oʻz vaqtida ham, vaqt jihatidan ham o ptimal boʻldi. bo'sh joy, bu erda algoritmga faqat kirish satri va chiqish qo'shimchasi massividan tashqarida qo'shimcha joy kerak { \displaystyle { \mathcal {O}}(1)}} \mathcal {O}}(1) kerak. Kengaytirilgan qo'shimchali massivlar (ESA) bir xil vaqt va xotira murakkabligini saqlagan holda qo'shimchalar daraxtlarining to'liq funksionalligini takrorlaydigan qo'shimcha jadvallarga ega bo'lgan qo'shimchali massivlardir.[1] Satrning barcha qo'shimchalari kichik to'plami uchun qo'shimchalar massivi siyrak qo'shimchal ar massivi deb ataladi.$

Barcha ichki ildiz bo'lmagan tugunlar tarvaqaylab ketganligi sababli, ko'pi bilan
bo'lishi mumkin n - 1 ta shunday tugun va n + (n − 1) + 1 = 2n jami tugunlar (n barglar,
n - 1 ta ichki bo'lmagan tugun, 1 ta ildiz).
Qo'shimchalar eskirgan chiziqli vaqtli qurilish algoritmlari uchun asosiy xususiyatdir,
garchi ko'pchilik yangi algoritmlarga asosl angan bo'lsa ham Farach algoritmi,
qo'shimchali havolalar bilan taqsimlash. To'liq qo'shimchali daraxtda barcha ichki
bo'lmagan ildiz tugunlari boshqa ichki tugunga qo'shilish qo'shimchasiga ega. Agar
ildizdan tugunga yo'l mag'lubiyatni sehrlasa , qayerda bitta belgi va bu mag'lubiyat
(ehtimol bo'sh), uning ichki tugunini ifodalovchi qo'shimchasi mavjud . Masalan,
tugunidagi qo'shimchani ko'ring ANA tuguniga NA yuqoridagi rasmda. Yugurish
havolalari daraxtda ishlaydigan ba'zi algoritmlarda ham qo'llanilad i.
A umumlashtirilgan qo'shimchali daraxt - bu bitta qator o'rniga iplar to'plami uchun
qilingan qo'shimchali daraxt. U ushbu qator qatoridagi barcha qo'shimchalarni
ifodalaydi. Har bir satr boshqa tugatish belgisi bilan tugatilishi kerak.

2. Suffix massiv h aqida umumiy tushuncha
Informatika fanida qo ’shimchalar qatori qatorning barcha qo ’shimchalarining
tartiblangan massividir. Bu to ’liq matn indekslari, ma ’lumotlarni siqish algoritmlari
va bibliometriya sohasida qo ’llaniladigan ma ’lumotlar strukturasidir.
Suffiks massivlari Manber va Myers (1990) tomonidan qo ’shimcha
tarmoqlarga oddiy, bo ’sh joyni tejaydigan muqobil sifatida kiritilgan. Ular 1987 yilda
Gaston Gonnet tomonidan PAT massivi nomi bilan mustaqil ravishda kashf etilgan
(Gonnet, Baeza -Yates & Sni der 1992)
Kengaytirilgan qo ’shimchali massivlar (ESA) bir xil vaqt va xotira
murakkabligini saqlagan holda qo ’shimchalar tarmoqlarining to ’liq funksionalligini
takrorlaydigan qo ’shimcha jadvallarga ega bo ’lgan qo ’shimchali massivlardir.[1]
Satrning barcha qo ’shimchalari kichik to ’plami uchun qo ’shimchalar massivi siyrak
qo ’shi mchalar massivi deb ataladi.

$Qo ’shimcha xotiradan foydalanishni minimallashtirish uchun bir nechta ehtimollik algoritmlari ishlab chiqilgan, shu jumladan optimal vaqt va xotira alg oritmi. S = S [ 1 ] S [ 2 ] bo ’lsin. . . S [ n ] { S=S[1]S[2]...S[n]} S=S[1]S[2]...S[n] an n {\textstyle n} { \textstyle n} -string va S [ i , j ] { S[i,j]} S[i,j] dan i { i}gacha boʻlgan S { S} S ning pastki qatorini bildirsin. I to j { j} j inklyuziv. S { S} S ning A { A} A qoʻshimcha massivi endilikda leksikografik tartibda S { S} S qoʻshimchalarining boshlangʻich oʻrinlarini taʼminlovchi butun sonlar massivi sifatida belgilangan. Bu shuni anglatadiki, A [ i ] { A[i]} A[i] yozuvi S { S} S 10 ag ii { i} i -chi eng kichik qoʻshimchaning boshlangʻich pozitsiyasini oʻz ichiga oladi va shuning uchun hamma uchun 1 < i ≤ n { 1<i \leq n} 1<i \leq n: S [ A [ i – 1 ] , n ] < S [ A [ i ] , n ] { S[A[ i -1],n]<S[A[i],n]} S[A[i -1],n]<S[A[i],n]. S { S} S ning har bir qoʻshimch asi A { A} A da aynan bir marta namoyon boʻladi. Qo‘shimchalar oddiy qatorlardir. Bu satrlar saralanadi (qog ’oz lug ’atdagi kabi), boshlang ’ich pozitsiyalari (butun indekslar) A { A} A da saqlanishidan oldin. Suffiks massivlari qo ’shimcha tarmoqlar bilan c hambarchas bog ’liq: Suffiks massivlari qo ’shimcha tarmoqining chuqurlikdan birinchi o ’tishini bajarish orqali tuzilishi mumkin. Qo ’shimchalar massivi, agar qirralarning birinchi belgilarining leksikografik tartibida tashrif buyurilgan bo ’lsa, o ’tish p aytida tashrif buyurish tartibida berilgan barg belgilariga mos keladi. Suffiks tarmoqi chiziqli vaqtda qo ’shimchalar massivi va LCP massivining kombinatsiyasidan foydalangan holda tuzilishi mumkin. Algoritmning tavsifi uchun LCP massivi maqolasining tegishli bo ’limiga qarang. Har bir qoʻshimcha tarmoqi algoritmini tizimli ravishda qoʻshimcha maʼlumotlar (masalan, LCP massivi) bilan takomillashtirilgan qoʻshimchalar massividan foydalanadigan va bir xil vaqt murakkabligida bir xil muammoni hal qiladiga n algoritm bilan almashti rish mumkinligi koʻrsatilgan.$ $Suffiks massivlarining qo ’shimcha tarmoqlarga nisbatan afzalliklari yaxshilangan bo ’shliq talablarini, oddiy chiziqli vaqtni qurish algoritmlarini (masalan, Ukkonen algoritmiga nisbatan) va yaxshil angan kesh joylashuvini o ’z ichiga oladi. Suffiks massivlari Manber va Myers (1990) tomonidan qo'shimcha tarmoqlarning bo'sh joy talablarini yaxshilash maqsadida kiritilgan: Suffiks massivlari n { n} n butun sonni saqlaydi. Agar butun son uchun 4 { 4 } 4 bayt kerak bo‘lsa, qo‘shimchali massiv uchun jami 4 n { 4n} 4n bayt kerak bo‘ladi. Bu tarmoq qo ’shimchasini ehtiyotkorlik bilan bajarish uchun talab qilinadigan 20 n { 20n} 20n baytdan sezilarli darajada kamroq. Biroq, ba ’zi ilovalarda, qo ’shimchalar massivlarining bo ’sh joy talablari hali ham taqiqlangan bo ’lishi mumkin. Bitlarda tahlil qilinganda, qo‘shimchali massiv O ( n log ⁡ n ) { { \mathcal {O}}(n \log n)} { \mathcal {O}}(n \log n) bo‘sh joyni talab qiladi, asl nusxa esa o ’lchamdagi alifbo ustidagi matn s { \sigma} \sigma faqat O ni talab qiladi ( n log ⁡ s ) { { \mathcal {O}}(n \log \sigma )} { \mathcal {O}}( n \log \sigma ) bitlar. S = 4 { \sigma =4} \sigma =4 va n = 3.4 × 10 9 { n=3.4 \times 10^{9}} n=3.4 \qat 10^{9 boʻlgan inson genomi uchun Shunday qi lib, qo ’shimchalar massivi genomning o ’ziga qaraganda taxminan 16 marta ko ’proq xotirani egallaydi. Suffiks avtomatlari (yo ’naltirilgan asiklik so ’zlar grafigi) ko ’plab qatorli muammolarni hal qilish imkonini beruvchi kuc hli ma’lumotlar strukturasidir. Mas alan, avtomat qo ’shimchasi yordamida ma ’lum bir satrdagi boshqa qatorning barcha holatlarini qidirish yoki turli pastki qatorlar sonini hisoblash mumkin – bu chiziqli bo’lishi mumkin. Vaqt ichida hal qilindi. Intuitiv ravishda, avtomat qo ’shimchasini barch a pastki qatorlarning xulosasi sifatida tushunish mumkin. Muhim fakt shundaki, avtomat qo ’shimchasi siqilgan uzunlikni o ’z ichiga oladi Belgilar qatori haqidagi barcha ma ’lumotlar faqat O(n) bo ’shliqlarini talab qiladi. Va uni O(n) vaqt ichida qurish mumki n (agar biz alifboning k hajmini d oimiy deb hisoblasa k, aks holda O(n*logk)) mavjud.$

Tarixiy jihatdan, Blumer va boshqalar birinchi marta 1983 yilda chiziqli
qo ’shimchali avtomat shkalasini taklif qilishgan va keyin 1985 yildan 1986 yilgacha
odamlar biri nchi chiziqli vaqtinchalik dizaynni taklif qilishgan. Avtomatlarning
suffiks algoritmi (Kroxemor, Blumer va boshqalar). Tafsilotlar uchun maqolaning
oxiridagi havolaga qarang. Avtomat qo ’shimchasi ingliz tilida “suffix automaton”
deb ataladi. “ grafik ” so ’zi ( “DAWG ” deb qisqartirilgan). Men Big O Notation ish
vaqtlari va amortizatsiya vaqtlarini o'rganyapman. Men O (n) chiziqli vaqt
tushunchasini tushunaman, ya'ni kirish hajmi algoritmning o'sishiga mutanosib
ravishda ta'sir qiladi ... va xuddi shu narsa, masalan, kvadratik vaqt O (n2) va
boshqalar uchun ham amal qiladi. Hatto algoritmlar, faktorial o'sadigan O(n!) marta
bilan almashtirish generatorlari kabi. O(n log n): Biz telefon daftarini
shaxsiylashtirmoqchimiz, shuning uchun biz har bir shaxs yoki kompaniyaning
nomini ularning belgilangan nusxasidan topamiz, so‘ngra ularning nomini kitobga
aylantiramiz va homiyligi uchun qisqacha minnatdorchilik xati yozamiz. .
O(n2): Ofisda xatolik yuz berdi va har bir telefon kitobidagi har bir yoz uvda telefon
raqamining oxirida qoʻshimcha “0” bor. Bir oz oq rangni oling va har bir nolni olib
tashlang.
O(n · n!): Biz telefon kitoblarini yuk tashish dokka yuklashga tayyormiz. Afsuski,
kitoblarni yuklashi kerak bo'lgan robot aqldan ozdi: u kitoblarni tasodifiy tartibda yuk
mashinasiga qo'yadi! Bundan ham yomoni, u barcha kitoblarni yuk mashinasiga
yuklaydi, keyin ularning tartibda yoki yo'qligini tekshiradi, agar bo'lmasa, ularni
tushiradi va qaytadan boshlaydi. (Bu dahshatli bogo turi.)
O(nn): Siz ro botni narsalarni to'g'ri yuklashi uchun tuzatasiz. Ertasi kuni
hamkasblaringizdan biri sizga hazil o'ynaydi va yuklash dock robotini
avtomatlashtirilgan bosib chiqarish tizimlariga ulaydi. Robot har safar asl kitobni
yuklash uchun ketganda, zavod printeri barcha telefon kitoblarining dublikatini
qiladi! Yaxshiyamki, robotning xatolarni aniqlash tizimlari etarlicha murakkab bo'lib,
robot yuklash uchun dublikat kitobga duch kelganda undan ham ko'proq nusxalarni
chop etishga urinmaydi, lekin u hali ham chop et ilgan har bir asl va dublikat kitobni
yuklashi kerak.

Suffiks massivi ikkita massivdan iborat:
pos array pos[1,...n]: U barcha S qo‘shimchalarining tartiblangan ro‘yxatini
ifodalaydi. Qo'shimchalar juda katta bo'lgani uchun bo'shliq murakkabligini
kamayti rish uchun massivda faqat qo'shimchalarning boshlang'ich pozitsiyalari
saqlanadi. lcp array lcp[1,...n]: Bu pos massivida saqlangan ketma -ket ikkita
qo‘shimchaning eng uzun umumiy prefiksi uzunligini saqlaydigan n ta butun sonli
massiv. Bolalar jadvali cld tab yuqoriga, pastga va nextlIndex uchta n massivdan
iborat. Tegishli qo'shimcha tarmoqining qirralari haqidagi ma'lumotlar yuqoriga va
pastga massiv tomonidan saqlanadi. NextlIndexarray qo'shimcha tarmoqini
tarmoqlanadigan tugun uchun ishlatiladigan bog 'langan ro'yxatdagi havolalarni
saqlaydi. Yuqori, pastga va nextlIndex massivlari quyidagicha aniqlanadi:
Yuqoriga[i]element i -1 indeksida tugaydigan eng uzun lcp -soniya oralig'ining
boshlang'ich indeksini yozadi.
i indeksidan boshlanadigan eng uzun lcp -intervalning ikkinchi bola oralig'ining
boshlang'ich indeksi pastga[i] elementida saqlanadi
Agar oraliq ota -onasining birinchi bolasi ham, oxirgi bolasi ham bo'lmasa,
nextlIndex[i] elementi i indeksidan boshlab eng uzun lcp -intervalning keyingi
biroda rlik oralig'ining birinchi indeksini o'z ichiga oladi. tarmoqning lcp -intervalining
pastdan yuqoriga o'tishini amalga oshirib, bolalar jadvalini chiziqli vaqtda qurish
mumkin. Yuqori/past qiymatlari va nextlIndex qiymatlarini ikkita alohida algoritm
yordam ida alohida hisoblash mumkin.
Kengaytirilgan qo'shimchalar massivi uchun qo'shimcha havolalarni oldindan
ishlov berish jarayonida har bir [i,..j] oralig'i uchun [1,..,r] qo'shimcha aloqa oralig'ini
yaratish orqali hisoblash mumkin. Intervalning chap va o'n g elementlari l va r [i,..,j]
ning birinchi indeksida saqlanadi. Ushbu interval uchun jadval 0 dan n gacha.
Suffiksli bog'lanish jadvali lcp -interval tarmoqining chapdan o'ngga kengligi -birinchi
o'tish yo'li bilan tuzilgan. Har safar l -interval hisoblanga nda, u l -intervallar ro'yxatiga
qo'shiladi, bu l -ro'yxat deb ataladi. lcp -qiymati > 0 bo'lsa, ro'yxatdagi har bir l -
interval[i,..,j] uchun havola[i] hisoblanadi. [l,..,r] oralig'i (l -1) -ro'yxatda ikkilik
qidiruv orqali hisoblanadi, bu erda l barcha l -1 int ervallari orasidagi eng katta chap

chegara hisoblanadi. [i,..j] ning qoʻshimchali bogʻlanish oraligʻi shu interval [l,..,r]
bilan ifodalanadi. l va r qiymatlari oxir -oqibat [i,..,j] ning birinchi indeksida saqlanadi.
Biz pastki qatorni aniqlashni osonlasht irish uchun umumlashtirilgan
qo'shimcha tarmoqidan foydalanishimiz mumkin. Asosiy g'oya shundan iboratki,
bitta satrdagi har bir kichik satr ushbu qatorning qandaydir qo'shimchasining prefiksi
hisoblanadi. Boshqacha qilib aytadigan bo'lsak, tarmoqga har bir qo'shimchani
qo'yganimizda, shuningdek, qo'shimchaning har bir bosh belgisini tarmoqning
tepasiga (boshlang'ich tugunga ulangan) qo'yamiz. Qo`shimchaning bu boshlang`ich
belgilari ham prefiksning boshidir. Ikki pastki satr faqat qisman tarmoqga mos k elishi
kerak. Eng uzun umumiy pastki qatorni topish algoritmi uch bosqichdan iborat:
T_1 va T_2 uchun umumlashtirilgan qo'shimcha tarmoqini yarating. tarmoqning har
bir ichki tuguniga ushbu tugunda T_1 va T_2 ning har biridan kamida bittadan barg
tugunlari bor -yo'qligi bilan izohlang.
Eng yuqori satr chuqurligi bilan belgilangan tugunni topish uchun tarmoq
bo'ylab birinchi chuqur qidiruvni bajaring.
Bizning misolimizdan foydalanib, biz ikki qatorli, bema'nilik va huquqbuzarlik
bilan umumlash tirilgan qo'shimcha tarmoqini quramiz. Keyin biz har bir tugunga
ushbu filialda faqat 1 -qator, faqat 2 -qator yoki 1,2 bilan ikkala satr bor -yo'qligi bilan
izoh beramiz:

3. Avtomatning qo'shimcha ta'rifi
Ta'riflar. Berilgan s satri uchun avtomat qo'shimcha si s qatorining barcha
qo'shimchalarini qabul qila oladigan minimallashtirilgan chekli holat mashinasidir.
Ushbu ta'rif quyida tushuntiriladi: Avtomat qo‘shimchasi yo‘naltirilgan asiklik grafik
bo‘lib, uning cho‘qqilari holatlar, qirralari esa holatlar ora sidagi o‘tishlarni
ifodalaydi.

Holat t_0 Dastlabki holat chaqiriladi, u barcha boshqa holatlarga yetib borishi
mumkin. Mashinada barcha o'tkazmalar, ya'ni yo'naltirilgan qirralar qandaydir belgi
bilan belgilanadi. Muayyan holatdan boshlangan tarjimalar t urli belgilarga ega
bo'lishi kerak. (Boshqa tomondan, Holatga o'tish har qanday xarakterda bo'lishi
mumkin emas). Bir yoki bir nechta holat tugallangan deb belgilangan.
Agar biz boshlang'ich holatdan chiqsak t_0 Har qanday yo'l bo'ylab ma'lum bir
yakuniy holatga o'ting va barcha o'tgan qirralarni tartibda yozing. Belgilang, natijada
olingan satr ma'lum bir s qo'shimchasiga ega bo'lishi kerak.
Yuqoridagi shartlarni qanoat lantiradigan barcha avtomatlar orasida avtomat
qo'shimchasi shu minimal cho'qqilar soniga ega. (Avtomat qo'shimchasi minimal
qirralarning soniga ega bo'lishi shart emas)
Avtomat qo'shimchasining eng oddiy tabiati
Oddiylik - avtomatik qo'shimchaning eng muhim xususiyati shundaki, u barcha pastki
qator ma'lumotlarini o'z ichiga oladi. Boshqacha qilib aytganda, t_0 boshlang'ich
holatidan boshlanadigan har qanday yo'l uchun, agar biz Yorliqni oldingi chetiga
yozing, yaratilgan pastki qator s ning pastki qato ri bo'lishi kerak. Shunga ko'ra, s ning
har qanday pastki qatori t_0 boshlang'ich holatidan boshlanadigan yo'lga mos keladi.
Ta'rifni soddalashtirish uchun, agar yo'ldagi chekka yorlig'i ushbu pastki qatorni
tashkil qilsa, biz boshlang'ich holatdan yo'lga "mos keladigan" pastki qatorni
chaqiramiz. Shunga ko'ra, biz ixtiyoriy yo'llarni chaqiramiz
Yo'lning chetidagi teglardan iborat bo'lgan ma'lum bir pastki qatorga "mos keladi".
Avtomat qo'shimchasining har bir holati dastlabki holatdan bir yoki bir nechta
yo'llarni olib boradi. Biz bu holatni ushbu yo'llarga mos kelish uchun bir necha usulda
chaqiramiz. Bu manba matni haqida batafsilQoʻshimcha axborot olish uchun manba
matnini kiriting .

3.1 Qurilish qo'shimchasi avtomatlariga misollar
Bu erda oddiy satrlar u chun avtomatik qo'shimchalar yaratishga misollar keltirilgan.
erta Boshlanish holati t0 sifatida yoziladi, chiqish holati yulduzcha (*) bilan
belgilanadi.
s=”“

s=”a”

s=”aa”

s=”ab”

s=”aba”

s=”abb”

s=”abbb”

4. Suffiks avtomatlarini qurish uchun chiziqli vaqt
algoritmi
Qurilish algoritmini ta'riflashdan oldin, avtomatik qo'shimchalar tushunchasini
tushunish uchun juda muhim bo'lgan ba'zi yangi tushunchalar va qisq acha isbotlarni
kiritish kerak. Yakuniy nuqtaning yakuniy pozitsiyasi, u larning tabiati va avtomat ik
qo'shimchalar bilan aloqasi: s satrini ko'rib chiqing t ning har qanday bo'sh bo'lmagan
pastki qatori. Biz oxirgi nuqta to'plamini endpos(t) deb ataymiz: oxirgi nuqta t paydo
bo'la digan s dagi barcha to'plamlar. Ikki pastki qat orni t_1 "Endpoint Equivalent" ga
t_2 deb nomlaymiz, agar ularning so'nggi nuqtalar to'plami mos bo'lsa: endpos(t_1)
= endpos(t_2). Shuning uchun, s ning barcha bo'sh bo'lmagan pastki qatorlari bo'lishi
mumkin
Yakuniy nuqta ekvivalentligi bo'yicha uni bir nechta toifalarga bo'lish mumkin.
Aslida, qo'shimchali avtomatlar uchun so'nggi nuqtaga ekvivalent qator hali ham
xuddi shunday tabiatni saqlab qoladi.

Boshqacha qilib aytganda, avtomat qo'shimchasidagi holatlar soni barcha pastki
qatorlarning chekli ek viv alent sinfiga ekvivalentdir. Raqam va boshlang'ich holat.
Har bir holat bir xil so'nggi nuqtalar to'plamiga ega bir yoki bir necht a pastki
qatorlarga mos keladi. Biz ushbu bayonotni taxmin sifatida ishlatamiz va keyin
chiziqli vaqt ichida avtomatik qo'shim chani qurish uchun ushbu taxminga asoslangan
algoritmni tasvirlaymiz - biz yaqinda ko'rib chiqamiz, Minimaldan (ya'ni, eng kam
cho'qqilar sonidan) tashqari qo'shimcha avtomatlarning barcha kerakli xususiyatlari
bajariladi (minimal NerodeCreated tomonidan b elgilanadi, havolalarga qarang).
Yakuniy nuqtalar to'plamiga kelsak, biz bir nechta oddiy, a mmo muhim faktlarni
keltiramiz. Bu manba matni haqida batafsilQoʻshimcha axborot olish uchun manba
matnini kiriting . Quyida biz ushbu algoritmni tasvirlab beramiz. Algoritm onlayn,
ya'ni. birma -bir belgilar qo'shing va joriy avtom atni mos ravishda o'zgartiring.
Chiziqli fazoning maqsadiga erishish uchun biz faqat har bir holatning liniyasini, mos
yozuvlar qiymatini va uzatish ro'yxatini saqlaymiz.
Biz tugatish holatini belgilas hni qo'llab -quvvatlamaymiz (biz Agar kerak bo'lsa,
avtomat qo'shimchasini yaratgandan keyin ushbu teglarni qanday qo'shishni
ko'rsating).
Dastlab, avtomat t_0 holatiga ega.Tarkibiga ko'ra biz bu holatni 0 deb ataymiz
(qolgan holatlar 1, 2, ... deb nomlanadi). Bu holat uchun len = 0 bo'lsin, qulaylik uchun
havola
Qiymat -1 ga o'rnatiladi (bo'sh holatni ko'rsatadi).
Shuning uchun, hozirgi vazifa c belgisini joriy qatorning oxiriga
qo'shishdir.Operatsiya. Biz ushbu operatsiyani quyida tasvirlaymiz:
1. Oxirgi butun satr holatiga mos kelsin (oxirgi oxirgi = 0, har bir belgi qo'shish
amalidan keyin oxirgi qiymatini o'zgartiramiz).
2. Yangi holat kursini yarating, Let len(cur) = len(last) +1 va link(cur) qiymati
aniqlanmagan.

3. Bi z o'tmishda bo'lganmiz, agar u c belgisini uzatishga ega bo'lmasa, u holda c
belgisini uzatishni qo'shing, cur uchun ishora qiling va keyin uning qo'shimchasi
havolasiga o'ting, aga r yo'q bo'lsa, yana tekshiring. Agar c belgisining uzatilishi
mavjud bo'lsa , uni qo'shing. Agar c belgisi ma'lum bir tugunda uzatilayotgan bo'lsa,
to'xtating va p bu holatning raqami bo'lsin.
4.Agar "tugun allaqachon c belgisiga ega" bo'lsa, uzatish hech qachon sodir
bo'lmagan va biz bo'sh holatga -1 (t_0 ko'rsatkichi orqali) kel gan bo'lsak, biz
shunchaki link(cur) = 0 ni bajardik. sakrab chiqish
5. Aytaylik, biz ma'lum bir q holatda to'xtadik, bu ma'lum bir p holatdan c belgisi
orqali o'tishdir. Endi ikkita holat mavjud: len(p) + 1 = len(q) yoki boshqasi.
6.Agar len(p) + 1 = len (q) bo'lsa, biz shunchaki havola(cur) = q qilamiz va tashqariga
sakrab chiqamiz.
7. Aks holda vaziyat yanada murakkablashadi. Yangi d "Nusxa olish" holatini
yaratish kerak: davlatning yangi klonini yarating, unga q ma'lumotlarini nusxalang
(qo'shimcha ha vola va Transfer), len qiymatidan tashqari: len (klon) = len (p) +1 ni
bajarishingiz kerak.
8.Nusxalashdan so'ng biz klonga bog'lanish nuqtalarini qo'shamiz va q
qo'shimchasini klonga yo'naltiramiz.
9. Oxir -oqibat, biz qilishimiz kerak bo'lgan oxirgi narsa pH dan, qo'shimcha havolaga
amal qilishni boshlang, har bir holat uchun biz q ga o'tish mavju dligini tekshiramiz, c
belgisi, Agar mavjud bo'lsa, uni klonlash uchun yo'naltiring (agar bo'lmasa, tsiklni
yakunlang).
10. Baribir, bu qo'shish operatsiyasi qayerda tugallanganidan qat'i nazar, biz nihoyat
eng so'nggi Assign it to cur dasturini yangilaymiz.
Qaysi tugunlar barg tugunlari ekanligini va qaysilari emasligini bilishimiz kerak
bo'lsa, butun satr uchun avtomat qo'shimchasini qurgandan so'ng barcha b arg
tugunlarini t opishimiz mumkin.

Biz haqimizda Butun satrga mos keladigan tugunni ko'rib chiqing (aniqki, biz uni
lastNode o'zgaruvchisida saqlaymiz), biz uning qo'shimcha havolasini boshla ngunga
qadar kuzatib boramiz va Marshrutdagi har bir tugun yakunl ovchi tugun sifatida
belgilanadi. Buni tushunish oson, shuning uchun biz s qatorining barcha
qo'shimchalarining tegishli holatini belgilaymiz, bu biz aniqlamoq chi bo'lgan tugatish
holatidir. Keyingi bo'limda biz algoritmning har bir bosqichini batafsil ko' rib
chiqamiz va u ning to'g'riligini isbotlaymiz. Bu erda biz faqat bir nuqtaga e'tibor
beramiz: har bir belgi qo'shilishi avtomatga bir yoki ikkita holat qo'shadi. Shuning
uchun shtatlar soni aniq chiziqli. O'tishlar sonining chiziqliligi va algoritmning
chiziqli vaqt murakkabligini tushunish qiyinroq, ular algoritmning to'g'riligini
isbotlagandan so'ng, quyida isbotlanadi.
Algoritm isboti. Agar len (p) + 1 = len (q) bo'lsa, tarjimani (p, q) uzluksiz deb
ataymiz. Aks holda, len(p) +1 < len(q) bo'lganda, biz uni uzluksiz o'tish deb ataymiz.
Algoritm tavsifidan ko'rinib turibdiki, uzluksiz uzatish va uzluksiz uzatish oqim
algoritmining turli tarmoqlariga olib keladi. Uzluksiz uzatish) Shunday nom langan,
chunki birinchidan beri Bitta kirishdan keyin ular o' zgarishsiz qoladi. Aksincha,
uzluksiz tarjima satrga yangisini qo'shishi mumkin Jarayondagi belgilar o'zgaradi
(yon tomonda ko'rsatilgan holatni o'zgartirishi mumkin).
Aniq ma'noga yo'l qo'ymaslik uchun biz buni joriy c belgisini qo'shishga
tayyorlanayotga n biz qurgan avtomatning satri deb ataymiz.
Algoritm boshida biz yangi holat kursini yaratdik.U butun s+c qatoriga mos keladi.
Yangi davlat yaratishimiz sababi aniq - yangi so'zlarni qo'shish
Belgidan so'ng, yangi so'nggi nuqta ekvivalentlik klassi paydo b o'ldi - yangi qatorning
oxiri s + c bilan tugaydigan pastki qator turi.
Yangi holatni yaratgandan so'ng, algoritm butun satrdan boshlanadi sMos holat
qo'shimcha havolani kesib o'tish, cur ga tarjima qo'shishga harakat qilish, yo'lda c
belgisi. Lekin Biz fa qat yangisini qo'shamiz .

$Avtomat qo'shimchasi tushunchasi 1983 yilda Denver universiteti va Kolorado universitetining Boulderdagi Anselm Blumer, Janet Blumer, Devid Xaussler va Ross Makkonneldan tashkil topgan bir guruh olimlari tomonidan kiritilgan, ammo shunga o'xshash tushunchalar ilgari ham mavjud edi. Peter Weiner, Vogan Pratt va Anatole Sliss ishlarida qo'shimcha daraxtlar bilan birga o'rganilgan. enco. O'zlarining asl ishlarida Blumer va boshqalar. S { \displaystyle S} 1 { \displaystyle 1} dan katta boʻlgan satr uchun yaratilgan avtomat qoʻshimchasi koʻpi bilan 2 | S | - 1 {\displaystyle 2| S | -1} holatlar va 3 tadan ko'p bo'lmagan | S | - 4 { \displaystyle 3| S | -4} o'tishlarni amalga oshirdi va avtomatlarni qurish uchun chiziqli algoritmni taklif qi ldi. 1983 -yilda Mu -Tian Chen va Joel Seiferas mustaqil ravishda Weinerning 1973 - yildagi qoʻshimcha daraxtini yasash algoritmini koʻrsatdilar. . 1987 yilda Blumer va boshqalar. qoʻshimchali daraxtlarda qoʻllaniladigan siqish texnikasini qoʻshimcha avtomatga qoʻlladi va siqilgan yoʻnaltirilgan asiklik soʻz grafigi (CDAWG) deb ham ataladigan siqilgan qoʻshimchali avtomatni ixtiro qildi. 1997 yilda Maxime Kroshmore va Renaud Verin CDAWG ni bevosita qurish uchun chiziqli algoritmni ishlab chiqdilar. 2001 yilda Shunsuke Inenaga va boshqalar. trie orqali berilgan soʻzlar toʻplami uchun CDAWG yaratish algoritmini ishlab chiqdi. Avtomat qo'shimchasi (yo'naltirilgan asiklik so'z grafigi) - bu siqilgan shaklda saqlash va berilgan satrning pastki qatorlari bilan bog'li q ma'lumotlarni qayta ishlash imkonini beruvchi ma'lumotlar tuzilmasi . Avtomat qo'shimchasi birinchi marta 1983 yilda Denver va Kolorado universitetlari olimlari tomonidan tasvirlangan, ular shuningdek, avtomatning o'lchami chiziqli ravishda uzunligi {\displaystyle S}S ga bog'liqligini ko'rsatdilar va onlayn algoritmni taklif qilishdi. ] chiziqli ish vaqti bilan qurilishi uchun [ ⇨ ]. Ushbu mavzu bo'yicha keyingi ishlarda avtomat qo'shimchasi va qo'shimchalar daraxtlari [ ⇨ ] o'rtasidagi yaqin bog'liqlik a niqlandi va avtomat qo'shimchasi tushunchasi turli xil umumlashmalarni oldi. Shunday qilib, qo'shimcha daraxtini olish uchun qo'shimcha daraxtiga qo'llaniladigan protseduraga o'xshash protsedura orqali asl nusxadan olingan siqilgan qo'shimchali avtomat, sh uningdek, so'zlar to'plami uchun tuzilgan umumlashtirilgan qo'shimchali avtomat kiritildi .$

Avtomat qo'shimchasi yordamida siz satrdagi pastki qatorni qidirish, ikki yoki
undan ortiq satrlarning eng katta umumiy pastki qatorini aniqlash va boshqalar kabi
ma salalarni samarali hal qilishingiz mu mkin
Burrows -Wheeler konvertatsiyasini (BWT) hisoblash uchun qo'shimchalarni
saralash algoritmlaridan foydalanish mumkin. BWT qatorning barcha siklik
almashtirishlarini saralashni talab qiladi. Agar bu satr leksikografi k jihatdan boshqa
barcha belgilardan (ya'ni, $) kichik bo'lgan maxsus satr oxiridagi belgi bilan tugasa,
unda tartiblangan aylantirilgan BWT matritsasi tartibi qo'shimchalar qatoridagi
qo'shimchalar tartibiga mos keladi. Shuning uchun BWT ni chiziqli vaqtd a
hisoblash mumkin, birinchi navbatda matnning qo'shimchali massivini tuzib, keyin
BWT qatorini chiqarib tashlaydi: BWT [ i ] = S [ A [ i ] - 1 ] { BWT[i]=S[A [i] -1]}
BWT[i]=S[A[i] -1]
Suffiks tarmoqlari kuchli ma'lumotlar tuzilmalari bo'lib, ular naqsh v a
qatorlarni moslashtirish, indekslash va matn statistikasi sohalarida keng qo'llaniladi.
Biroq, u katta hajmdagi joyni egallaydi va shuning uchun genom tahlili kabi
juda katta hajmdagi ma'lumotlarni qayta ishlashni talab qiladigan ko'plab real vaqt
ilova larida kamchilikka ega. Ushbu kamchilikni bartaraf etish uchun kengaytirilgan
qo'shimchalar massivlari ishlab chiqildi, ular qo'shimchalar massivlaridan iborat
ma'lumotlar tuzilmalari va qo'shimchalar tarmoqidagi tugunlar orasidagi ota -bola
munosabatlari haqidagi ma'lumotlarni o'z ichiga olgan bolalar jadvali deb ataladigan
qo'shimcha jadval. Ushbu tarmoq uchun tugunni tarmoqlanuvchi ma'lumotlar
strukturasi bog'langan ro'yxatdir. Kengaytirilgan qo'shimchali tarmoqlar ham makon
samaradorligi, ham vaqt mur akkabligi jihatidan ustundir va ularni amalga oshirish
oson. Bundan tashqari, ular mavhum tushuncha lcp -interval tarmoqlari yordamida
qo'shimcha tarmoqidan foydalanadigan har qanday algoritmga qo'llanilishi mumkin.
Kengaytirilgan qo'shimchalar qatorida n aqsh izlash uchun vaqt murakkabligi O(m|S|)
dir. Ushbu qo'llanmada biz umumlashtirilgan qo'shimcha tarmoqi nima ekanligini va
undan eng uzun umumiy pastki qatorni topish uchun qanday foydalanish
mumkinligini ko'rib chiqamiz.

Eng uzun umumiy pastki qatorni topish umumiy pastki qatorlarni topish orqali
qator o'xshashlik usullarining alohida holatidir. Ushbu usullar sinfidagi "ketma -
ketlik" pastki qatorlardir. Biz eng uzun umumiy pastki qatorni topib,
umumlashtirilgan qo'shimcha tarmoqining qo'llanilishini k o'rsatamiz.
Keyin biz umumiylashtirilgan qo‘shimcha tarmoqini quramiz, avvalo, trie
qo‘shimchasini va Patricia trie qo‘shimchasini (maydon terminologiyasidan
foydalangan holda), so‘ngra bu tarmoqlarga izoh qo‘yib, umumlashgan qo‘shimcha
tarmoqini hosil qilamiz. Birinchi savolga javob berish uchun, yo'q, biz " tarmoq"
so'zini noto'g'ri yozmadik. Qo‘shimchali tarmoqlar tilida trie to‘liq umumlashgan
qo‘shimcha tarmoqini yasash uchun oraliq bo‘lib, bizning vazifalarimiz uchun
ishlatilishi mumkin. Trie qo' shimchasi - bu chekkalari, ya'ni tugunlarni bog'laydigan
chiziqlar qo'shimchalarimiz harflari bilan belgilangan tarmoq. Biz har bir
qo'shimchani kuzatib, yuqori tugundan boshlab har bir belgi uchun chekka hosil qilish
orqali qo'shimcha tarmoqini quramiz. Agar tarmoqga qo'yiladigan yangi qo'shimcha
allaqachon tarmoqda mavjud bo'lgan belgilar to'plamidan boshlansa, biz yangi
shoxcha yaratib, boshqasi bo'lgunga qadar o'sha belgilarga ergashamiz .

Xulosa
Men bu kurs ishini bajarish davomida, o’zim bilmagan ko’plab ma’lumotlarga
ega bo’ldim. Jumladan suffix massivlari bilan qanday ishlash kerakligini va ular
ustida qanday amallar bajarish kerakligini. Suffix massivlar bizga juda ko’p
masalalarda sodda yechi mlar taklif etadi. Suffiks massivlari Manber va Myers (1990)
tomonidan qo'shimcha tarmoqlarga oddiy, bo'sh joyni tejaydigan muqobil sifatida
kiritilgan. Ular 1987 yilda Gaston Gonnet tomonidan PAT massivi nomi bilan
mustaqil ravishda kashf etilgan (Gonnet , Baeza -Yates & Snider 1992)
Kengaytirilgan qo'shimchali massivlar (ESA) bir xil vaqt va xotira
murakkabligini saqlagan holda qo'shimchalar tarmoqlarining to'liq funksionalligini
takrorlaydigan qo'shimcha jadvallarga ega bo'lgan qo'shimchali massivlardir.
Satrning barcha qo'shimchalari kichik to'plami uchun qo'shimchalar massivi siyrak
qo'shimchalar massivi deb ataladi.[2] Qo'shimcha xotiradan foydalanishni
minimallashtirish uchun bir nechta ehtimollik algoritmlari ishlab chiqilgan, shu
jum ladan optimal vaqt va xotira algoritmi.
Shuningdek yanada tushunirliroq bo’lishi uchun bir nechta misollar ham yozib
ishlanish yo’llarini ko’rsatib o’ttim. Shuningdek kurs ishini bajarish davomida suffix
massivlarni tarixi bilan ham tanishib o’tdik.

Foydalanilgan adabiyotlar va web saytlar:
1 Algoritm va ma’lumotlar strukturasi fanidan ma’ruzalar matni – Samarqand Davlat
Unversiteti 2021 -2022 o’quv yili
2 Мусаев М.М. “Компьютер тизимлари ва тармоқлари”. Тошкент.: “ Aloqachi ”
нашриёти, 2013 йил. 8 боб. 394 бет. – Олий ўқув юртлари учун қўлланма.
3.H.T. To‘rayev, I. Azizov; Matematik mantiq va diskret matematika
Toshkent:Tafakkur -Bo‘stoni, 2011.
4. В.Д.Колдаев. Основы алгоритмизации и программирования. Учебное
пособие, Москва ИД “Форум” - ИНФРА -М 2006 г.
5. 11. Narzullaev U .X ., Qarshiev A .B., Boynazarov I.M . Ma ’lumotlar tuzilmasi va
algoritmlar . // O ’quv qo ’llanma . Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
1. www.wix.com
2. www.techCrunch.com
3. www.TheNextWeb.com
4. www.Wired.com
5. www.Mashable.com
6. www.TheVerge.com
7. www.DigitalTrends.com
8. www.TechRadar.com
9. www.Technorati.com
10. Automata, languages and programming pdf
11. Trends in constraint programming pdf

Suffiks avtomat. O (N log N) da qurish va qo‘llash

Купить

Похожие документы
2001-yil sentabr voqealri va uning xalqaro munosabatlarga
1945-1990-yillarda Buyuk Britaniya
1918-1923 yillarda xalqaro munosabatlar, Versal Vashington siyetemasining tuzilishi
Ahmad al-farg‘oniy
Almashlab ekishni loyihalashtirish va joriy etish

Информация о документе

Продавец

Suffiks avtomat. O (N log N) da qurish va qo‘llash

Похожие документы