O’zbekiston respublikasi

Landa-vishkin algoritmni amalga oshirish
Landau-Vishkin 89 algoritmining ushbu amalga oshirilishi Java-da Eclipse integratsiyalashgan ishlab chiqish muhiti yordamida dasturlashtirilgan. Landau-Vishkin 89 - satrlarni moslashtirishning taxminiy algoritmi bo'lib, u eng ko'p k farq bilan naqsh-matn moslashuvining barcha hodisalarini topish uchun dinamik dasturlash echimini ta'minlaydi. Bu algoritm yaqin chiziqli vaqtda ishlaydi, xususan O(nk), bu erda n matn uzunligi va k maksimal tahrir masofasi. Landau-Vishkin 89 O(nm) vaqtida ishlaydigan taxminiy satrlarni moslashtirish uchun sodda dinamik dasturlash yechimiga muqobil taqdim etadi, bu erda n matn uzunligi va m - naqsh uzunligi.
Ushbu Landau-Vishkin ilovasi uchta Java faylidan iborat: MatrixL.java, SuffixArray.java va RMQ.java. MatrixL klassi L matritsasini aniqlash, ishga tushirish va hisoblash uchun kodni o'z ichiga oladi. Bu matritsada sodda dinamik dasturlash matritsasining diagonallari boʻylab sakrashlar boʻyicha O(1) ish vaqti hisoblari, D matritsasi mavjud. Landau-Vishkin 89 algoritmi qo'shimchalar qatoridan farqli ravishda qo'shimcha daraxtidan foydalanadi. Biroq, mening amaliyotim qo'shimchalar qatoridan foydalanadi, bu esa qo'shimcha daraxtiga ko'proq makon va vaqtni tejaydigan alternativani taqdim etadi. RMQ.java faylida O(1) sakrashlarini hisoblash uchun lcp massivida foydalaniladigan minimal diapazon so'rovini bajarish uchun kod mavjud.


Xulosa
Landau-Vishkin algoritmi asosan taxminiy matnlar bilan ishlaydi.Hozirgi kunda texnalogiyalar tabora rivojlanayotgan davrda informatika va boshqa texna-logiyalarning asosiy muommosi hisoblanadi. Bu algoritmning tezligi va ustunligi shundaki u qushimcha daraxtlardan foydalanishdir bu algoritmga qushimcha imkoniyatlarni oshiradi.Lekin buning kamchiliklari ham bor ya’ni qushimcha daraxt-lardan foydalanganligi sababli bo’sh joylardan ortiqcha foydalanadi. Landau-vishkin algoritmining qisqartmasini LV algoritmi deb ataladi. Naqsh bilan matnning mos kelishmovchiliklarini Ladau-Vishkin algoritmi bilan aniqlanadi. Bu mos kelish-movchilikda bir necha yani protsedurani uzaytirish va birlashtirish tartibi kabi tushunchalari mavjud bularni birma bir kurib chiqamiz. Protsedura pastki satrlarni solishtiradi, agar mos kelsa, ko’paytiriladi va nomuvofiqliklari jadvali yangilanadi. Bu solishtirish shunday nomuvofiqlik topilmaguncha sodir buladi.Agar bu solishtirishda satrlar orasida tafovutlar topilsa , ilgari olingan malumotlardan foydalanib uni topilgan raqamga tenglashtiradi. Shuni sedan chiqarmaslik kerakki bu nomuvofiqlar naqshning boshlanishiga tug’ri keladi, naqishning joriy holati esa joylashuvdagi farq bilan mos keladi. Algoritm namunani oldindan qayta ishlash bosqichida yaratilgan namunaviy mos kelmasliklarning ikki o’lchovli qatoridan foydalanadi.
Endi dastlabki hisob-kitoblar bosqichida namunaviy nomuvofiqlik jadvalini hisoblashga o'tish kifoya. Umumiylikni yo'qotmasdan, biz buni qandaydir darajada deb taxmin qilishimiz mumkin . Oldindan ishlov berish algoritmi qatorlar to'plamini quyidagi kichik to'plamlarga bo'lishdan foydalanadi:
Algoritm bosqichlardan iborat. Bosqichda , to'plamdagi qatorlar hisoblab chiqila-di.
Ushbu jadvalni hisoblash uchun ishlatiladigan usul matnni tahlil qilish bosqichida qo'llaniladigan usulga asoslanadi. Bosqich uchun algoritmni ko'rib chiqing . Bos-qichda namunani tahlil qilish algoritmi uchun kirishlar namunaning pastki qatorlari va bu erda mos ravishda namuna va matn sifatida ko'rib chiqiladi va oldin-gi bosqichlarning natijalarini o'z ichiga olgan massivdir. Bosqich chiqishlari kiritil-adi . Ular nomuvofiqliklarni topadigan bosqich bundan mustasno, har bir satr uchun bosqichda matnni tahlil qilish algoritmidagi kabi ga qadar emas, balki nomuvofiqliklarni topish talab qilinadi .
Qiyinchilik reytingi Keling, matnni tahlil qilishga sarflangan vaqtni ko'rib chiqaylik. Agar protsedura chaqirilsa va chiqarib tashlansa , matnni tahlil qilish siklining har bir iteratsiyasi belgilangan vaqtni oladi va umumiy vaqtni beradi . Qo'ng'iroqlar paytida protsedura tomonidan bajariladigan operatsiyalarning umumiy soni ga teng , chunki u matnning har bir belgisini ko'pi bilan bir marta tekshiradi. Har bir chaqiruvdagi protsedura jami elementlarga ega bo'lgan va massivni qayta ishlaydi. Ishlash vaqtini ushbu kirishlarning har biri bilan belgilangan vaqtdagi operatsiyalarni bog'lash orqali hisoblash mumkin, bu har bir qo'ng'iroq uchun ga teng bo'lgan hisoblash vaqtini beradi . Shunday qilib, umumiy matnni tahlil qilish vaqti ekanligini ko'rish mumkin . Keling, qurilishni ko'rib chiqaylik . Jarayonning to'g'riligini tekshirishda ishlatiladigan argumentlarga o'xshash argumentlar yordamida shuni ko'rsatish mumkinki, bosqichda mos kelmasliklarning kerakli sonini topish uchun B sharti qondiriladigan pozitsiyalar talab qilinadi va alohida holatda, ya'ni, bosqichda , bunday lavozimlar talab qilinadi.
Landau-Vishkin 89 – satrlarni moslashtirishning taxminiy algoritmi bo'lib, u eng ko'p k farq bilan naqsh-matn moslashuvining barcha hodisalarini topish uchun dinamik dasturlash echimini ta'minlaydi.


Adabiyotlar ro'yxati
[1] Landau, GM va U. Vishkin. "Tez parallel va ketma-ket taxminiy satrlarni moslashtirish." Algoritmlar jurnali 10.2 (1989): 157-69. ACM raqamli kutubxonasi. Veb. 2014 yil 27 noyabr.
[2] De Kastro Miranda, Rodrigo va Maurision Ayala-Rinkon. "Qo'shimcha massivlar orqali eng uzun keng tarqalgan kengaytmalarni hisoblash uchun Landau-Vishkin algoritmining modifikatsiyasi." Bioinformatika va hisoblash biologiyasidagi yutuqlar 3594 (2005): 210-13. Veb. 2014 yil 20 avgust.