Sirtqi bo‘lim Fanidan MUSTAQIL ISH Mavzu: Suffiks massiv va suffiks avtomat qurish algoritmi
BAJARDI: _____ guruh talabasi ______________
QABUL QILDI: ______________
Jizzax_2023
Suffiks massiv va suffiks avtomat qurish algoritmi
Reja: Kirish. Algoritmlar va berilganlar strukturasi haqida.Dasturlash olamidagi o’rni.
Asosiy qism. 1.Suffiks massiv va suffiks avtomat qurish algoritmi ishlash bosqichi
2.Suffiks massiv algoritmi dastur kodida ishlashi
3. Massiv
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.
