Boyer-Mur algoritmi va xossalari

Boyer-Mur algoritmi va xossalari

Bajardi: 404-19 guruh magistranti

Bobojonov Murodjon.

Tekshirdi: Nishonov. A.

Reja

4

BOYER-MUR ALGORITMINING QIYOSIY TAHLILI

1

2

3

BOYER –MUR ALGORITMINING XOSSALARI VA DASTURIY YECHIMI

Boyer –Mur algoritmiga doir dasturiy misollar

XULOSA

BOYER-MUR ALGORITMINING QIYOSIY TAHLILI

Kruskal , pufakli, genetik va boshqa algoritmlarning Boyer-Mur algoritmi bilan o`xshash jihatlari. Algoritmlashning asosiy shartlaridan biri bu – dasturning ishlash tezligi. Kod qanchalik optimal bo`lsa, dastur shuncha tez ishlaydi. Algoritmlar juda ko`p turlarga va nomlarga ega. Biror masalani yechishni oson, qulay va umuman algoritmlash talablariga mos keluvchi usulni ishlab chiqqan olim algoritmga o`z nomini bergan. Yoki aksincha, o`quvchilarning o`zi shu nom atay boshlashgan. Shunday algoritmlarga “pufakli saralash”, “Prim algoritmi”, ”Xorspul algoritmi”, “Kruskal algoritmi”, “Roevoy algoritmi” ushbu ketma-ketlikni ko`p davom ettirish mumkin. Prima algoritmi - og'irlik bilan bog'liq bo'lgan nostandart grafikaning minimal spanning daraxtini yaratish algoritmidi.

• Algoritmlash va algoritmning asosiy xossalari

Algoritm dеganda, bеrilgan masalani yеchish uchun ma`lum tartib bilan bajarilishi kеrak bo`lgan chеkli sondagi buyruqlar kеtma-kеtligini tushuniladi.

Biror masalani kompyutеrda yеchishda eng muhim va ma`suliyatli ishlardan biri qo`yilgan masalani yеchish algoritmini yaratish bo`lib, bu jarayonda bajarilishi kеrak bo`lgan hamma bo`lajak buyruqlar kеtma-kеtligi aniqlanadi.

Algoritm quyidagi asosiy xossalarga ega:

• uzluklilik,
• aniqlik,
• natijaviylik
• ommaviylik.

Blok-sxemalarni tuzishda foydalaniladigan asosiy sodda geometrik figuralar quyidagilardan iborat:

• Algoritm uchta fikrga asoslangan:

Chapdan o'ngga, o'ngdan chapga taqqoslash. Matnning boshi (qatorlar) va shablon birlashtirilib, tekshirish shablonning oxirgi belgisidan boshlanadi. Agar belgilar mos keladigan bo'lsa, shablonning oxiridan bitta oldingi simvoli va undan keyin qolganlari taqqoslanadi. Agar barcha shablon simvollari qo`shilgan simvollar satri bilan mos kelsa, naqshning barcha belgilar satrining ustki belgilariga mos keladigan bo'lsa, bunday xolda ostsatr topiladi va pastki chiziqning keyingi ko'rinishi izlanadi.

Agar shablondagi qaysidir belgi satrda mos keladigan simvolga mos kelmasa, shablon bir nechta belgi o'ngga siljiydi va test oxirgi belgidan yana boshlanadi.

Stop simvollar: Keling, "kolokol" so'zini izlaylik. Birinchi harfga mos kelmadi - "k" (ushbu harfni to'xtash belgisi deb nomlaylik). So'ng shablonni o'ngdan oxirigacha "k" harfi bilan surishingiz mumkin.

Строка: * * * * * * к * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Shablonda da hech qanday to'xtash belgisi bo'lmasa, shablon bu to'xtash belgisidan tashqariga o'tadi.

Строка: * * * * * а л * * * * * * * *Шаблон: к о л о к о лСледующий шаг: к о л о к о л

 

Bunday holatda, stop simvoli "a" hisoblanadi. Shablon esa to`g`ridan to`g`ri bu harfni ko`rsatgani uchun siljiydi. Boyer-Moor algoritmida stop simvoli mos keladigan qo'shimchaga umuman qaramaydi, Shuning uchun shablonning birinchi harfi ("k") "l" ostida bo'ladi va ma'lum bo'lgan bo'shliq bajariladi. Agar to'xtash belgisi "k" boshqa harfdan keyin "k" bo'lsa, stop simvoli ishlamaydi.

Строка: * * * * к к о л * * * * *Шаблон: к о л о к о л

Следующий шаг: к о л о к о л ?????

• Ushbu algoritmni C++ da amlaga oshirish quyidagicha:

Boyer-Mur algoritmining 1-modifikasiyasi. BM algoritmida foydalaniladigan yomon simvol siljishi kichik bo’lgan alifbo uchun uncha samarali emas, lekin alifbo o’rtasi namuna uzunligiga qaraganda katta bo’lsa, bu ASCII jadvali bilan bo’lgan holda va matn muharririda oddiy izlashda, u juda foydali. Algoritmda faqat uning bittasidan foydalanish juda samarali bo’ladi.

x va y [i, i+m-1]larni mos tushirishga urinishlardan so’ng, siljish uzunligi birdan kam emas. Shunday qilib, y[i+m] albatta navbatdagi urinishga kiritiladi, demak, joriy urinishda yomon simvolni siljitish uchun foydalanishi mumkin. Yomon simvol funksiyani oxirgi simvol x ni hisobga qabul qilish uchun o’zgartiramiz:

Agar a x da uchrasa, bc[a]=min{j|0j mva x [m-1-j]=a} bc[ a ] = qarama – qarshi holda. Matn va namunani taqqoslash ixtiyoriy tartibda amalga oshirishi mumkin.

XULOSA

Hozirgi axborotlashgan jamiyatda axborot va uning oqimi tez sur`atlarda o`sib bormoqda. Internetda ko`plab axborot manbalari, ya`ni megadatalar, bigdatalar o`lchami oshib bormoqda. Bularni saqlash, saralash, foydalanish muammolarni keltirib chiqarishi mumkin. Axborotlarning bir vaqtda bir kanalda bo`lishi, bir vaqtda uzatilishi muammolarni keltirib chiqarishi mumkin. Shu sababli ularni tartibga solishni ma`lum bir usulni, ya`ni tartiblash va saralash usulini talab etadi. Bular esa o`z navbatida algoritmni, vazifalar hamda malalarni bosqichma-bosqich yechishni ko`zda tutadi. Ayni damda axborotlarni izlash, dasturlarda turli masalarni yechish maqsadida turli algoritmlar ishlab chiqarildi. Yuqorida xuddi shunday algoritmlardan Boyer-mur algoritmi tahlil qilindi. Ushbu usul axborotlarni izlash va saralash soxasida eng samarali usul hisoblanadi. Boyer-Mur algoirtmi izlashda satr bo`yicha kerakli axborotni uzatishni taklif etadi. Yuqorida shunga doir misollar ham keltirilgan. Algoritmlar doim ham bir-biridan tubdan farq qilmaydi. Ze`ro, turli algoritm bir masalani yechishga qaratilgan bo`lishi mumkin.