Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash


O’ZBEKISTON RESBUPLIKASI OLIY TA’LIM FAN VA INNOVATSIYALAR VAZIRLIGI SHAROF RASHIDOV NOMIDAGI SAMARQAND DAVLAT UNIVERSITETI INTELLEKTUAL TIZIMLAR VA KOMPYUTER TEXNOLOGIYALARI FAKULTETI sun’iy intellekt yo’nalishi Ma’lumotlar tuzulmasi fanidan 1-MUSTAQIL ISHI Bajardi: Abduvaitova O’g’iloy 2 -bosqich 201-guruhi talabasi Tekshirdi: Rabbimov G’ Samarqand 2024
Aho-Korasik algoritmi va Shiber-Vishkin algoritmi ning strukturasini o‘rganish va ularning murakkabligini baholash : 1. Aho-Korasik algoritmi Aho-Korasik algoritmi va Shiber-Vishkin algoritmi — bu matnni qidirish va tahlil qilish bilan bog‘liq bo‘lgan ikkita muhim algoritmdir. Har biri turli vazifalar uchun optimallashtirilgan va o‘ziga xos strukturalarga ega. Keling, ularning strukturasi va murakkabliklarini batafsil ko‘rib chiqamiz. 1. Aho-Korasik algoritmi Struktura: Aho-Korasik algoritmi ko‘p qismli qidirish algoritmidir va asosan "trie" (prefix tree) va "fail" (ko‘rsatgichlar) strukturalariga asoslanadi. Uning maqsadi bir nechta qidiruv so‘zlarini matnda samarali tarzda qidirishdir. Trie: Trie — bu so‘zlar yoki satrlarni saqlash uchun ishlatiladigan daraxt shaklidagi ma'lumotlar tuzilmasidir. Har bir tugun (node) so‘zning biror belgisini ifodalaydi, va yo‘lni davom ettirish orqali butun so‘zni topish mumkin. Fail: Aho-Korasik algoritmi "fail" deb ataladigan qo‘shimcha ko‘rsatgichlar qo‘shadi. Fail har bir tugun uchun qidiruvning "qayta davom etish" imkoniyatini beradi, ya'ni agar qidiruv to‘xtab qolsa, fail yordamida keyingi mos keladigan holatga o‘tish mumkin. Algoritmning ish tartibi: 1.Trie qurilishi: Dastlab, qidirilayotgan so‘zlarning barcha prefikslarini o‘z ichiga olgan trie daraxti quriladi. 2.Fail qurilishi: Har bir tugun uchun fail ko‘rsatgichlari hisoblanadi, bu ko‘rsatgichlar qidiruv davomida qachon va qanday qilib keyingi holatlarga o‘tishni aniqlashga yordam beradi. 3.Qidiruv: Matnda har bir belgi bilan qidiruv olib boriladi. Agar qidiruv tugunida davom eta olmasa, fail ko‘rsatgichiga asoslanib boshqa tugunga o‘tiladi. Murakkablik: Tayyorlash: Trie daraxtini qurishning va fail ko‘rsatgichlarini yaratishning vaqti O(mn) , bu yerda m — so‘zlar soni, n — har bir so‘z uzunligi. Qidiruv: Har bir belgi uchun qidiruv davomida O(N) , bu yerda N — matn uzunligi. Aho-Korasik algoritmi bir necha so‘zni matnda samarali tarzda qidirishga yordam beradi va qidiruvning vaqt murakkabligi O(N) ga tushadi. 2. Shiber-Vishkin algoritmi Struktura: Shiber-Vishkin algoritmi asosan ikki matnni taqqoslash uchun ishlatiladi va matnni qidirish jarayonida eng qisqa o‘zgartirishlar (edit distance) hisoblashga asoslangan.
Dynamic Programming (DP): Algoritm o‘zining dinamik dasturlash metodini ishlatadi. Har bir qadamda ikki matn orasidagi minimal masofani hisoblashga harakat qiladi. DP matritsasi (yoki jadvali) yordamida har bir holatni hisoblashda optimal qaror qabul qilinadi. Algoritmning ish tartibi: 1.Matritsa yaratish: Matnlarning har bir belgisini taqqoslash uchun n × m o‘lchamdagi matritsa yaratiladi (bu yerda n va m — ikki matn uzunliklari). 2.Taqqoslash: Har bir juft belgi o‘rtasidagi farq hisoblanadi va matritsa orqali eng qisqa yo‘l (edit distance) aniqlanadi. Har bir qadamda qo‘shish, o‘chirish yoki almashtirish kabi operatsiyalarni hisoblash kerak bo‘ladi. 3.Tashlash: Algoritm yakunida minimal tahrirlar (operatsiyalar) soni (masofa) chiqadi. Murakkablik: Tayyorlash: DP matritsasini qurishning vaqti O(nm) , bu yerda n va m — matn uzunliklari. Qidiruv: DP jadvalini to‘ldirishning vaqti ham O(nm) bo‘ladi. Shiber-Vishkin algoritmi ikki matn orasidagi farqni topish va ularni moslashtirish uchun eng yaxshi yechimlardan biridir. Taqqoslash Xulosa Aho-Korasik algoritmi ko‘p so‘zli matnni qidirish uchun juda samarali, ayniqsa bir nechta so‘zlarni izlashda juda tezkor ishlaydi. Shiber-Vishkin algoritmi esa ikki matnni tahrir masofasi orqali taqqoslashga mo‘ljallangan va matnlar o‘rtasidagi o‘zgarishlarni aniqlash uchun juda foydalidir. Har ikki algoritm ham o‘zining maxsus vazifalarida samarali ishlaydi, ammo ularning murakkabligi va ishlash sharoitlari turlicha.
Murakkablikni baholash: Vaqt murakkabligi : Aho-Korasik algoritmining vaqt murakkabligi asosan matn va naqshlar uzunligiga bog‘liq bo‘ladi. Har bir belgi uchun faqat bir marta qidiruv amalga oshiriladi, shuning uchun umumiy vaqt murakkabligi: O(n+m+z)O(n + m + z)O(n+m+z) n — matn uzunligi. m — naqshlar umumiy uzunligi. z — topilgan mosliklar soni. Xotira murakkabligi : Trie daraxti va fail pointerlarining xotira talabiga bog‘liq. Trie daraxti har bir naqshning uzunligi bo‘yicha joy talab qiladi, shuning uchun xotira murakkabligi: O(m)O(m)O(m) Bu yerda m — naqshlarning umumiy uzunligi. 2. Shiber-Vishkin algoritmi Shiber-Vishkin algoritmi (1989) — bu algoritm eng yaqin mosliklarni qidirish va qidiruvda kiritish, o'chirish va almashtirish operatsiyalarini amalga oshirish uchun ishlatiladi. Algoritm asosan parallel qidiruv va dinamik dasturlashdan foydalanadi . Algoritm strukturasini o ‘ rganish : Shiber - Vishkin algoritmi asosan quyidagi bosqichlardan iborat : 1. Dinamik dasturlash : Algoritmda dinamik dasturlash orqali qidirilayotgan naqsh va matnning mosliklarini kiritish , o ' chirish va almashtirish operatsiyalarini amalga oshirish uchun yaqinlik matritsasini hisoblash kerak bo ' ladi . Yaqinlik matritsasi har bir pozitsiyani va ularning o'zaro mosliklarini hisoblab chiqadi. 2.Parallelizatsiya : Shiber-Vishkin algoritmi parallel ishlov berish orqali samaradorlikni oshiradi. Algoritmda har bir bo‘lakni parallel tarzda ishlov berish imkoniyati mavjud. Bu katta matnlarni va naqshlarni parallel tarzda tezda qidirish imkonini beradi.