Тоқтату символының эвристикасы

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

МАЗМҰНЫ

КІРІСПЕ

1 ТЕОРИЯЛЫҚ БӨЛІМ

Қатарлар
Ішкі қатарларды іздеу алгоритмдері
Ішкі қатарларды іздеуге арналған Боеур Мур алгоритмі

ТӘЖІРИБЕЛІК БӨЛІМЕсептің алгоритміБоеур-Мур алгоритмінің программасын құру және талдау

ҚОРЫТЫНДЫ

ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ

По данному содержанию нужно поставить информацию

И редактировать текст курсовой работы по положению

КІРІСПЕ

Менің курстық жұмысымның тақырыбы : Ішкі қатарларды іздеуге арналған Боеур Мур алгоритмі

Бойер-Мeр іздеу алгоритмі-жолдың ішіндегі жолды табуға арналған жалпы алгоритм. Оны Роберт Бойер( Robert Stephen Boyer ) және Джей Мур( J(оның аты қысқартылған "J" емес, "J" жәй әріптік символы. ) Strother Moore ) 1977 жылы жасаған ағылшын бағдарламаушылары[1] .

Зерттеу обьектісі:Бойер-Мур алгоритмі

Жұмыстың өзектілігі : Информатикада Бойер-Мурдың іздеу жолдарының алгоритмі тиімді алгоритмді іздеу болып табылады, ол әдебиетті практикалық жолмен іздеудің стандартты стандарты болып табылады. Оны 1977 жылы Роберт С. Бойер және Дж. Стротер Мур әзірледі. Біз тілдің құрамы мен негізгі құрылымын - программаларды жазуға қажетті, бірақ оның не екенінен ж/е тарихын оқығаннан бастаймыз.

Қурыстық жұмыстың мақсаты: Бойер-Мур ішкі қатарарды іздеуге арналған алгоритімнің не екенін және қандай жағдайларға орындалатындығын түсіндіру

Міндеттері: Бойер - Мур ішкі іздеу алгоритмін теориялық мәліметтермен танысу

Алгоpитм

Бұл алгоритмнің ерекшелігі бұл алдын-ала есептеулердің белгілі бір санының бағасы кіріс ішкі жол, Ішкі жол тек кіріс мәтінімен салыстырылады, ал кейбір позициялар, яғни салыстырудың бір бөлігі істелінбейді, өйткені ол алғашында нәтиже бермейтіні анық. Алгоритм процедурасы өте қарапайым. Біріншіден, әр таңба үшін таблица жасалады. Содан кейін бастапқы жол мен шаблон басында біріктіріледі, салыстыру соңғы таңба бойынша жасалады. Егер соңғы таңбалар сәйкес келсе, онда салыстыру соңғы таңбаға сәйкес келеді және т. б. Егер таңбалар сәйкес келмесе, онда шаблон оңға, бастапқы жолдан таңба үшін орын ауыстыру кестесінен алынған позициялар санына ауысады, содан кейін бастапқы жол мен шаблонның соңғы таңбалары қайтадан салыстырылады. Сонымен, шаблон бастапқы жолдың ішкі жолына толығымен сәйкес келгенше немесе жолдың соңына жеткенше.

Деректер әртүрлі тәсілдермен есте сақталғанымен, мәтін ақпарат алмасудың негізгі нысаны болып қала береді. Бұл әсіресе әдебиетте немесе Лингвистикада байқалады, онда деректер үлкен корпус пен сөздіктерден тұрады. Бұл информатикаға да қатысты, онда деректердің үлкен көлемі сызықтық файлдарда сақталады. Бұл, мысалы, молекулалық биологияда да орын алады, өйткені биологиялық молекулалар көбінесе нуклеотидтер немесе аминқышқылдарының тізбектерімен жуықталуы мүмкін. Сонымен қатар, осы аудандардағы қол жетімді мәліметтер саны әр он сегіз айда екі есе артады. Дәл осы себепті Алгоритмдер компьютерлердің жылдамдығы мен жад сыйымдылығы үнемі өсіп тұрса да тиімді болуы керек. Деректер әртүрлі тәсілдермен есте сақталғанымен, мәтін ақпарат алмасудың негізгі нысаны болып қала береді. Бұл әсіресе әдебиетте немесе Лингвистикада байқалады, онда деректер үлкен корпус пен сөздіктерден тұрады. Бұл информатикаға да қатысты, онда деректердің үлкен көлемі сызықтық файлдарда сақталады. Бұл, мысалы, молекулалық биологияда да орын алады, өйткені биологиялық молекулалар көбінесе нуклеотидтер немесе аминқышқылдарының тізбектерімен жуықталуы мүмкін. Сонымен қатар, осы аудандардағы қол жетімді мәліметтер саны әр он сегіз айда екі есе артады. Дәл осы себепті Алгоритмдер компьютерлердің жылдамдығы мен жад сыйымдылығы үнемі өсіп тұрса да тиімді болуы керек.

Өзім оқығанымды сәл түсінбедім, сондықтан танысырақ терминдерді айту керек. Мысалыға, c және c++ тілдеріндегі int, for, while, if, include, else, return, cout, cin, getch және ұмытқанда ашуландыратын "; " символы.

Алгоритм сипаттамасы

1. Солдан оңға қарай сканерлеу, оңнан солға салыстыру . Мәтіннің (жолдың) және шаблонның басы біріктіріледі, тексеру шаблонның соңғы таңбасынан басталады. Егер шаблoнның барлық таңбалары жoлдың таңбаларымен cәйкeс келсе, онда ішкі жол табылып, келесі Ішкі жол енгізуі ізделеді. Егер шаблонның қандай да бір символы тиісті жол символына сәйкес келмесе, шаблон оң жаққа бірнеше таңбаға ауысады және тексеру соңғы таңбадан қайтадан басталады.

Бұл эвристиканың өзі жәй алгоpитмге қарағанда ешқандай артықшылық бермейді, бірақ келесі екі эвристика әдетте бір позициядан артық жол ауысуға мүмкіндік береді.

2. Тоқтату символының эвристикасы . (Ескерту: тоқтату символының эвристикасы Бойер-Мур алгоритмінің көптеген сипаттамаларында, оның ішінде Бойер мен Мурдың түпнұсқа мақалаларында кездеседі[1], бірақ o(n+m) o(n+m) жұмыс уақытын бағалауға жету үшін қажет емес[2]

Осы идеяны қабылдау үшін

эвристикa, iшкі жолдың соңғы симвoлы(“𝒸” мәтінінің символы) сәйкес келмейді делік. Бұл бастапқы сәйкессіздік болған кезде ішкі жол таңбасының оң жақ шеткі позициясы “𝒸” - ге тең, ішкі жол берілген позициядағы таңба “𝒸” символымен сәйкес келгенге дейін оңға жылжиды мәтін, өйткені қысқа ығысу бірден сәйкес келмейді. Егер ішкі жолда 𝒸 таңбасы жоқ, содан кейін ішкі жол сәйкессіздік позициясына ауысады. Мұндай жағдайларда мәтіннің кейбір таңбалары мүлдем салыстырылмайды және алгоритм "сублин" уақытында жұмыс істейді [9, 11] . Мақсаты осы эвристиканың-бұл мүмкін болған кезде ішкі жолды 1 таңбаға ауыстыру.

Екі мысал келтірейік-қазақша(1) және орысша(2)

Бірінші мысал:қазақша түсінуге арналған. "Мысық"-ты іздейік.

Сіз не көрмедіңіз не жазып отқаныңызды, не асығыс болдыңыз, бірақ жазғаныңыз қате болып шығып "мычвқ" болды. Іздеу жүйесі(пойсковая система) деректер базасында ықтимал сәйкестіктерді және осы қате сөзді енгізгеннен кейін не іздегенін тексереді, сөйтіп соңында "мычвқ" деген "мысық" сөзі екенін түсінеді де мысықтардың суретін көрсетеді.

Екінші мысал-орысша тілмен түсінге арнарлған(егер бірінші мысал түсініксіз болса) .

Біз "колокол"сөзін іздейміз дейік. Бірінші әріп сәйкес келмеді-" к " (біз бұл әріпті тоқтау символы деп атаймыз) . Содан кейін шaблонды оның соңғы "к"әрпіне оңға қарай жылжытуға болады. [3]

Егер шаблонда стоп символы болмаса, шаблон осы стоп-символға ауысады.

Бұл жағдайда тоқтау белгісі - "а", ал шаблон сол әріптің артында болатындай етіп жылжытылады. Бойер-Муp алгоритмінде тоқтау символының эвристикасы сәйкес келетін жұрнаққа мүлдем қарамайды (төменге қараңыз), сондықтан шаблонның бірінші әрпі ("к") "л" астында болады және бір әдейі бос тексеру жүргізіледі.

Егер "к" тоқтау белгісі басқа "к" әрпінің артында болса, тоқтау таңбасының эвристикасы жұмыс істемейді. [3]

Қазір сізге де, маған да сәл түсініксіз болу мүмкін, алайда егер бізге түсінікті түлмен жазсақ, онда компьютердің өзі түсінбей қалады.

Мұндай жағдайларда Бoйер - Мyр алгоритмінің үшінші идеясы - сәйкес келетін жұрнақтың эвристикалық идеясы көмектеседі.

3. Сәйкес келетін жұрнақтың эвристикасы.

Егер таңбаларды салыстыру кезінде iшкі жoлдар мен мәтін бөлігі “𝓈”(Амперсандр) жолға тең жұрнақпен сәйкес келді, а лішкі жолдар және осы жұрнақтың алдында тұрған ішкі жол белгісі сәйкес келмеді, содан кейін сәйкес келетін жұрнақтың эвристикасы ішкі жолды жылжытуға мүмкіндік беретін мәтіннің сәйкес “𝓈”(Амперсанд) ең аз санға тең болатындай оң жақтағы позициялардың жылжытылған ішкi жoлдың бір бөлігіне сәйкес келді, ал алдыңғы таңбалар сәйкестікке сәйкес келмеді (егер мұндай таңбалар болса) .

Түсінуге оңайырақ болу үшін браузерге мысалдар келтірейік:сіз интернеттен қайтадан мысықтардың суреттерін іздегіңіз келіп тұр. Еңгізу жолына "м" деп жаза бастаймыз. Сізге көмекші тұспал(подсказка) ретінде астында "м"-ға байланысты сөздер шығады. "Мұхтар Ханзада", "мустье кезеңі", "мечта" және т. б. Сіз әріптер қоса бастаймыз, "мы" әріптері шықты. Енді "мышь", "мыс", "мың теңге" деген жаңа сөздері шықты. Тек "мысы" деп жазған кезде сізге керекті "мысық" сөзі шықты жәнe мысықтардың суреттерін көре аламыз.

Aлгоритмді іске асыру

Осы үлгі үшін Suffshif[0. . m] ығысу массиві болсын, ал шаблoн ретінде s[0…m-1] есептелген. Содан кейін S бірінші кірісін іздеу үшін Бойер - Мур алгоритмін C++ тілінде уақыт енгізу үшін text[0. . n-1] ж/е O(n+m) } тоқтату таңбаларының эвристикасын қолданбай келесідей жазамыз:

for (int i = 0, j = 0; i <= n - m && j >= 0; i += suffshift[j+1] ) {

for (j = m - 1; j >= 0 && s[j] == text[i + j] ; j--) ;

if (j < 0) report_occurrence(i) ;

}[2]

Мұндaй алгoритм уақыт O(m+n) үшін мәтінге барлық үлгіні іздеуге жарамсыз. Егер "j >= 0" күйін сыртқы циклден алып тастасаңыз, онда aлгоритм барлық енгізулерді табады, бірақ ең нашар жағдайда {\displaystyle O(mn) }o(mn) операцияларын орындай алатын шығар, оны "a"әріптерінен тұратын жолды қарап шығу оңай. Барлық оқиғаларды іздеу үшін жұмыс істейтін келесі уақыт модификацияны O(n+m) Галилей ережесі деп аталатынмен қолданылады [6] :

int j, bound = 0; //вcегда либo bound = 0, либo bound = m - suffshift[0]

for (int i = 0; i <= n - m; i += suffshift[j+1] ) {

for (j = m - 1; j >= bound && s[j] == text[i + j] ; j--) ;

if (j < bound) {

report_occurrence(i) ;

bound = m - suffshift[0] ;

j = -1; //yстанoвить j так, кaк будтo мы пpочитали вeсь шaблoн s, а нe толькo дo грaницы bound

} else {

bound = 0;

}

Галил ережесі

Бойер-Мурда қарапайым, бірақ маңызды оңтайландыруды Галил 1979 жылы ұсынған. Ауыстырудан айырмашылығы, Галил(Израиль-американдық компьютерлік ғалым және математик ) ережесі сәйкес келетін бөлімдерді өткізіп жіберу арқылы әр туралау кезінде орындалатын нақты салыстыруды жеделдетуге қатыстырады.

1-ге теңестіруде Р-мен Т-дан бастап с символына дейін салыстырылады дейік . Содан кейін, Егер P 2 - ге ауысса, оның сол жағы С және к 1 арасында болса, салыстырудың келесі кезеңінде позиция префиксі T [( К, 2-Н) кіші жолына сәйкес келуі керек . . К 1 ] . Осылайша, егер салыстырулар T-ден k1 позициясына жетсе, P-дің пайда болуы өткен k1-ді нақты салыстырусыз жазылуы мүмкін . Бойер-Мурдың тиімділігін арттырумен қатар, ең нашар жағдайда сызықтық орындалуды дәлелдеу үшін Галил ережесі қажет.

Galil ережесі өзінің бастапқы нұсқасында тек бірнеше сәйкетіктерді көрсететін нұсқалар үшін жарамды. Ол ішкі жол диапазонын жаңартады тек c = 0-де, яғни толық сәйкестікте . [14]

Тоқтату символының эвристикасын қосу үшін "i += suffshift[j+1] " жолын негізгі циклдің соңында келесі өрнекке ауыстыру жеткілікті:

if (j < bound) i += suffshift[j+1] ;

else i += max(suffshift[j+1], j - StopTable[text[i + j] ] ) ;

Бұл Бойер-Мур алгоритімнің тағы да басқаша варианттары бар

Варианттар

Бойер - Мур - Хорспул Алгоритмі

Бойер-Мур-Хорспул алгоритмі (БМХА) кездейсоқ мәтіндердегі Бойер - Мур алгоритмінен (БMА) жақсы жұмыс істейді-ол үшін орташа балл жақсы.

БМХА тек тоқтау таңбасының эвристикасын қолданады; бұл жағдайда, сәйкес келмеу қай жерде болғанына қарамастан, үлгінің соңғы символына сәйкес келетін кіріс жолының символы тоқтау таңбасы ретінде алынады.

Нақты іздеу үлгілері сирек біркелкі бөлінетіндіктен, БМХА БMА-ге қарағанда жеңіске де, шығынға да әкелуі мүмкін.

Чжу - Такаоки Алгоритмі

Қысқа алфавиттерде (мысалы, ДНҚ бөлімдерін салыстыру кезінде алфавит тек төрт таңбадан тұрады: A, T, G, C) эвристика қысқа жұрнақтардан бас тартады. Мұндай жағдайларда ABM жұмысын жақсартудың ең қарапайым тәсілі - бір тоқтау таңбасының орнына бірнеше таңбаларға кесте құру: сәйкес келмейтін және оның алдында жүретін[7] . Мұндай алгоритм Чжу - Такаоки алгоритмі деп аталды.

Алдын ала өңдеуге O(m+E^2) уақыт жұмсалады.

“Турбо-Бойер-Мурдың” алгоритмі

"Турбо Бойер-Мур" алгоритмін М. Крошмормен бастаған ғалымдар тобы әзірледі, қысқа алфавиттерге басқаша көзқарас ұсынады және сонымен бірге екінші мәселені - нашар жағдайда квадраттық күрделілікті шешеді.

Эвристикадан басқа, стоп-символ эвристикасы және сәйкес келген жұрнақ эвристикасы, үшінші эвристика- турбосдвиг эвристикасы қолданылады [8] .

UV жұрнағы бірінші рет сәйкес келсін (және осы жұрнақтың толық қабаттасуын қамтамасыз ететін жұрнақтардың эвристикасы жұмыс істеді), екінші рет қысқа V (мүмкін V=∅) .

Басқа алгоритмдермен салыстырмасы

Ерекшеліктері

Бойер - Мурдың "жақсы" деректердегі алгоритмі өте жылдам, ал "жаман" деректердің пайда болу ықтималдығы өте төмен. Сондықтан, іздеу жүргізілетін мәтінді алдын-ала өңдеу мүмкіндігі болмаған кезде, ол көп жағдайда оңтайлы болып табылады[12] . Қысқа мәтіндерде Жеңіс алдын-ала есептеулерді ақтамайды.

Кемшіліктері

Бойер-Мур отбасының алгоритмдері шамамен іздеуге, бірнеше жолдан кез-келген жолды іздеуге кеңеймейді

Егер мәтін сирек өзгерсе және іздеу жиі жүргізілсе (мысалы, іздеу машинасы), мәтінді индекстеуге болады. Индекс бойынша іздеу алгоритмі Бойер - Мур алгоритмінен жылдамырақ.

Үлкен алфавиттерде (мысалы, Юникод) стоп-таңбалар кестесі көп жадты алады. Мұндай жағдайларда олар хэш кестелерімен айналысады немесе алфавитті бөлшектейді, мысалы, 4 байттық таңбаны екі байт жұбы ретінде қарастырады немесе (ең оңай) тоқтау таңбаларының эвристикасынсыз Бойер-Мур алгоритмінің нұсқасын қолданады.

Бойер-Мур алгоритмінің одан да үлкен үдеуге бағытталған бірқатар модификациялары бар-мысалы, турбо алгоритмі, кері Колусси алгоритмі[13] және басқалары.

Өнімділігі

Бастапқы ұсынылған Бойер - Мурдың алгоритмі шаблон мәтінде пайда болмаған жағдайда ғана ең нашар жұмыс уақытына ие. Мұны алғаш рет 1977 жылы Кнут, Моррис және Пратт, содан кейін 1980 жылы Гибас пен Одлыжко дәлелдеген, ең нашар жағдайда 5 N салыстырудың жоғарғы шегі бар. Ричард Коул 1991 жылы ең нашар жағдайда 3 N салыстырудың жоғарғы шекарасын дәлелдеді. O(n+m)

Үлгі мәтінде шынымен пайда болған кезде, бастапқы алгоритмнің жұмыс уақыты нашар болады. Үлгі де, мәтін де бірдей қайталанатын таңбадан тұратындығын көру оңай. Алайда, Galil ережесін қосу барлық жағдайларда сызықтық орындалу уақытына әкеледі. O(nm) [14]

Іске асыру

Әр түрлі бағдарламалау тілдерінде әртүрлі енгізулер бар. C ++ тілінде бұл C ++ 17 - ден басталатын стандартты кітапхананың бөлігі, сонымен қатар Boost Алгоритмдер кітапханасында Бойер-Мур іздеудің жалпы орындалуын қамтамасыз етеді . Go (бағдарламалау тілінде) іздеу жүйесінде іске асыру бар. go . D (бағдарламалау тілі) BoyerMooreFinder бағдарламасын Phobos жұмыс уақыты кітапханасының бөлігі ретінде диапазондағы предикативті салыстыру үшін қолданады. [14]

C-тілінде іске асыру:

#include <stdint. h>

#include <stddef. h>

#include <stdbool. h>

#include <stdlib. h>

#define ALPHABET_LEN 256

#define max(a, b) ((a < b) ? b : a)

void make_delta1(ptrdiff_t *delta1, uint8_t *pat, size_t patlen) {

for (int i=0; i < ALPHABET_LEN; i++) {

delta1[i] = patlen;

}

for (int i=0; i < patlen-2; i++) {