Boyer-Mur algoritmi va xossalari

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.

http://fayllar.org