Jizzax filiali amaliy matematika fakulteti

O`ZBEKISTON RESPUBLIKASI OLIY VA O`RTA MAXSUS TA’LIM VAZIRLIGI
MIRZO ULUG`BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI



AMALIY MATEMATIKA FAKULTETI

«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi

“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN

MUSTAQIL ISH

Mavzu: Suffiks massiv va suffiks avtomat qurish algoritmi

Bajardi: “ Kompyuter ilmlari va dasturlash texnologiyalari ”
yo`nalishi 2-kurs 11-21 guruh talabasi Aliqulov Samariddin

Tekshirdi: Tojiyev Maruf

Jizzax – 2023
Reja:

1. 
   Kirish.
   

Algoritmlar va berilganlar strukturasi haqida.Dasturlash olamidagi o’rni.

2. 
   Asosiy qism.
   

1.Suffiks massiv va suffiks avtomat qurish algoritmi ishlash bosqichi
2.Suffiks massiv algoritmi dastur kodida ishlashi
III. Xulosa.
IV. Foydalanilgan adabiyotlar
Kirish
Suffiks massiv va suffiks avtomat qurish algoritmi, matnlar ichidagi belgilar yoki so'zlarning bitta yoki bir nechta sufikslari bo'yicha ma'lumotni topish uchun ishlatiladigan algoritmlardir. Suffiks massivi, bir matnning barcha suffikslarining uzunligi va indekslari to'plamidir. Ya'ni, bir matnning i-ta belgisidan boshlangan sufikslar uchun indekslar ro'yxati.
Misol uchun, "ababaa" so'zi uchun suffiks massivi 6, 5, 3, 2, 1, 0 bo'ladi. Bu yerda 6-to'liq matnning indeksi.Suffiks avtomati esa belgilangan matnni automata aylantirib, uning qavriqlik funksiyasini yaratadi. Bu funksiya asosida, matndagi har bir so'zning barcha suffikslari uchun avtomatda yagona holat turadi. Masalan, "ababaa" so'zi uchun avtomat quyidagicha bo'ladi:
_{Avtomatning har bir holatiga mos keladigan sufikslar va o'sish yo'llari ham mavjud. Misol uchun "aba" so'zidan keyin "b" harfini qo'shganimizda yangi holat kiritiladi va bu holatga moskeladigan sufikslar ro'yxati "b", "aa" bo'ladi. Suffiks avtomati va suffiks massivi kabi algoritmlar matnlar ichidagi so'zlar va ularning sufikslari bilan ishlash uchun qulaydir. Shu bilan birga, ular o'zaro qo'shimcha ma'lumotlarni topishda ham yordam beradi.
Avtomat qo'shimchasi (yo'naltirilgan asiklik so'z grafigi) - bu siqilgan shaklda saqlash va berilgan satrning pastki qatorlari bilan bog'liq ma'lumotlarni qayta ishlash imkonini beruvchi ma'lumotlar strukturasi. Barcha so'z qo'shimchalarini qabul qiladigan deterministik chekli avtomatni ifodalaydi. {\displaystyle S=s_{1}s_{2}\dots s_{n}} va faqat ular va barcha bunday avtomatlar orasida mumkin boʻlgan eng kichik holatlar soniga ega. Kamroq rasmiy ravishda, avtomat qo'shimchasi ajratilgan boshlang'ich cho'qqi va "yakuniy" cho'qqilar to'plamiga ega bo'lgan yo'naltirilgan asiklik grafik bo'lib, uning yoylari belgilar bilan belgilanadi, shuning uchun har qanday cho'qqi uchun undan chiqadigan yoylardagi belgilar juftlik bilan ajralib turadi va uchun so'zning har qanday qo'shimchasi. S boshlang'ich cho'qqidan ba'zi yakuniy cho'qqigacha bo'lgan yo'l mavjud bo'lib, uning ustidagi belgilar birlashganda berilgan qo'shimchani hosil qiladi. Ushbu tavsifga mos keladigan barcha grafiklar ichida eng kichik cho'qqilar soniga ega bo'lgan avtomat qo'shimchasi hisoblanadi. S va shuningdek, chiziqli ish vaqti bilan qurish uchun onlayn algoritmni taklif qildi. Ushbu mavzu bo'yicha keyingi ishlarda avtomat qo'shimchasi va qo'shimchalar daraxtlari o'rtasidagi chambarchas bog'liqlik aniqlandi va avtomat qo'shimchasi tushunchasi turli xil umumlashmalarni oldi. Shunday qilib, qo'shimcha daraxtini olish uchun bor qo'shimchasiga qo'llaniladigan protseduraga o'xshash protsedura orqali asl nusxadan olingan siqilgan qo'shimchali avtomat, shuningdek, so'zlar to'plami uchun tuzilgan umumlashtirilgan qo'shimcha avtomat kiritildi.}