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

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

МАЗМҰНЫ

КІРІСПЕ
1 ТЕОРИЯЛЫҚ БӨЛІМ
Қатарлар
Ішкі қатарларды іздеу алгоритмдері
Ішкі қатарларды іздеуге арналған Боеур Мур алгоритмі

ТӘЖІРИБЕЛІК БӨЛІМ
Есептің алгоритмі
Боеур-Мур алгоритмінің программасын құру және талдау
ҚОРЫТЫНДЫ
ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ

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

КІРІСПЕ
Менің курстық жұмысымның тақырыбы : Ішкі қатарларды іздеуге арналған Боеур Мур алгоритмі
Бойер-Мeр іздеу алгоритмі-жолдың ішіндегі жолды табуға арналған жалпы алгоритм. Оны Роберт Бойер( Robert Stephen Boyer ) және Джей Мур( J(оның аты қысқартылған "J" емес, "J" жәй әріптік символы.) Strother Moore ) 1977 жылы жасаған ағылшын бағдарламаушылары[1].
Зерттеу обьектісі:Бойер-Мур алгоритмі
Жұмыстың өзектілігі : Информатикада Бойер-Мурдың іздеу жолдарының алгоритмі тиімді алгоритмді іздеу болып табылады , ол әдебиетті практикалық жолмен іздеудің стандартты стандарты болып табылады. Оны 1977 жылы Роберт С. Бойер және Дж. Стротер Мур әзірледі.Біз тілдің құрамы мен негізгі құрылымын - программаларды жазуға қажетті, бірақ оның не екенінен же тарихын оқығаннан бастаймыз.
Қурыстық жұмыстың мақсаты: Бойер-Мур ішкі қатарарды іздеуге арналған алгоритімнің не екенін және қандай жағдайларға орындалатындығын түсіндіру
Міндеттері: Бойер - Мур ішкі іздеу алгоритмін теориялық мәліметтермен танысу

Алгоpитм
Бұл алгоритмнің ерекшелігі бұл алдын-ала есептеулердің белгілі бір санының бағасы кіріс ішкі жол, Ішкі жол тек кіріс мәтінімен салыстырылады,ал кейбір позициялар, яғни салыстырудың бір бөлігі істелінбейді,өйткені ол алғашында нәтиже бермейтіні анық.Алгоритм процедурасы өте қарапайым. Біріншіден, әр таңба үшін таблица жасалады. Содан кейін бастапқы жол мен шаблон басында біріктіріледі, салыстыру соңғы таңба бойынша жасалады. Егер соңғы таңбалар сәйкес келсе, онда салыстыру соңғы таңбаға сәйкес келеді және т.б. Егер таңбалар сәйкес келмесе, онда шаблон оңға, бастапқы жолдан таңба үшін орын ауыстыру кестесінен алынған позициялар санына ауысады, содан кейін бастапқы жол мен шаблонның соңғы таңбалары қайтадан салыстырылады. Сонымен, шаблон бастапқы жолдың ішкі жолына толығымен сәйкес келгенше немесе жолдың соңына жеткенше.
Деректер әртүрлі тәсілдермен есте сақталғанымен, мәтін ақпарат алмасудың негізгі нысаны болып қала береді. Бұл әсіресе әдебиетте немесе Лингвистикада байқалады, онда деректер үлкен корпус пен сөздіктерден тұрады. Бұл информатикаға да қатысты, онда деректердің үлкен көлемі сызықтық файлдарда сақталады. Бұл, мысалы, молекулалық биологияда да орын алады, өйткені биологиялық молекулалар көбінесе нуклеотидтер немесе аминқышқылдарының тізбектерімен жуықталуы мүмкін. Сонымен қатар, осы аудандардағы қол жетімді мәліметтер саны әр он сегіз айда екі есе артады. Дәл осы себепті Алгоритмдер компьютерлердің жылдамдығы мен жад сыйымдылығы үнемі өсіп тұрса да тиімді болуы керек. Деректер әртүрлі тәсілдермен есте сақталғанымен, мәтін ақпарат алмасудың негізгі нысаны болып қала береді. Бұл әсіресе әдебиетте немесе Лингвистикада байқалады, онда деректер үлкен корпус пен сөздіктерден тұрады. Бұл информатикаға да қатысты, онда деректердің үлкен көлемі сызықтық файлдарда сақталады. Бұл, мысалы, молекулалық биологияда да орын алады, өйткені биологиялық молекулалар көбінесе нуклеотидтер немесе аминқышқылдарының тізбектерімен жуықталуы мүмкін. Сонымен қатар, осы аудандардағы қол жетімді мәліметтер саны әр он сегіз айда екі есе артады. Дәл осы себепті Алгоритмдер компьютерлердің жылдамдығы мен жад сыйымдылығы үнемі өсіп тұрса да тиімді болуы керек.
Өзім оқығанымды сәл түсінбедім,сондықтан танысырақ терминдерді айту керек.Мысалыға,c және c++ тілдеріндегі int,for,while,if,include,else,retur n,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 ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.