Курсовая (1). Программная реализация и анализ алгоритмов поиска в тексте
 Скачать 1.83 Mb.
|
|
Приложение 5 - Реализация алгоритма Бойера-Мура function BMSearch(S, P) { let und = "undefined"; let sl = S.length; let ssl = P.length; if (sl == 0) { console.log("Неверно задана строка\n"); return und; } else { if ( ssl == 0 ) { console.log("Неверно задана подстрока\n"); return und; } else { var ret = []; var k = P.length - 1, o = {}, l = S.length, i = 0, j, c; for (; i < k; i++) o[P.charAt(i)] = k - i; i = 0; while (i < l) { for (j = k; j >= 0; j--) if (P.charAt(j) != S.charAt(i + j)) { break; } if (j < 0) { i++; ret.push(i-1); } else { c = o[S.charAt(i + j)]; if (!c) c = k + 1; c += j - k; if (c <= 0) c = 1; i += c; } } if (ret.length != 0) { return ret; } else { return ("undefined1337"); } } } } 2.5 Анализ алгоритмов В данной главе я хочу произвести сравнение алгоритмов. Сравнения будут производиться путем анализа, за сколько программа нашла всё совпадения, в зависимости от объёма текста и искомых объектов Выполним оценку трудоемкости каждого алгоритма, реализованного в приложении. Для этого разработаем план тестирования и выделим критерии оценки В таблицах предоставлены результаты всех опытов 1) Стих, длинною в 312 символов 2) 1 Том «Война и мир» 3) 1 Том «Война и мир» скопированный 4 раза Голубой цвет – БМ Оранжевый цвет – МПК Синий цвет – Прямой поиск Тест 1. Опыт 1 (По одной букве)  Р  исунок 1.1. Результат работы приложенияОпыт 2 (По одной букве)  Рисунок 1.2. Результат работы приложения  Опыт 3 (По одной букве)  Рисунок 1.3. Результат работы приложения  Тест 2 Опыт 1 (По слову)  Рисунок 2.1. Результат работы приложения  Опыт 2 (По слову)  Рисунок 2.2. Результат работы приложения  Опыт 3 (По слову)  Рисунок 2.3. Результат работы приложения  Тест 3. Опыт 1 (По фрагменту)  Рисунок 3.1. Результат работы приложения  Опыт 2 (По фрагменту)  Рисунок 3.2. Результат работы приложения Опыт 3 (По фрагменту)  Рисунок 3.3. Результат работы приложения  Средние значения: Опыт 1. Поиск по 1 букве
Опыт 2. Поиск по слову
Опыт 3. Поиск по предложению
ЗАКЛЮЧЕНИЕ В процессе выполнения курсовой работы были рассмотрены различные алгоритмы поиска подстроки в строке и проведен их сравнительный анализ Изучив полученные результаты легко можно сделать вывод, что алгоритм «Прямого поиска» справляется достаточно быстро со всеми поставленными задачами, в независимости от объема анализируемого и искомого текста. Алгоритм Бойера – Мура справился задачами, из опытов 1 и 2, хуже остальных. Но следует заметить, что его эффективность значительно возросла, когда мы искали большой фрагмент текста (Опыт 3). Хуже всех справился МКП, так как ни в одном эксперименте он не превзошел алгоритм прямого поиска. Безусловно, если судить по опытам 1 и 2, он в разы лучше БМ. Говорить о том, что какой-либо из алгоритмов является наиболее оптимальным, нельзя. Каждый алгоритм эффективно работает в определенных задачах. Таким образом, какой алгоритм выбрать, следует только после точного изложения проблемы, определения ее целей и функциональности, которую он должен реализовать. Список использованных источников 1) Алгоритмы компьютерной обработки данных: Учеб. пособие / Г. В. Ваныкина, Т. О. Сундукова.– Тула, 2012.– 217 с. 2) Матрос Д. Элементы абстрактной и компьютерной алгебры: Учеб. пособие для студ. педвузов [Текст]. – М.: Издательский центр «Академия», 2004. – 240 с. 3) Основы JavaScript - URL: https://developer.mozilla.org/ru/docs/Learn/Getting_started_with_the_web/JavaScript_basics (Дата обращения 5 января 2020) 4) Академия Microsoft: Структуры и алгоритмы компьютерной обработки данных – URL: https://www.intuit.ru/studies/courses/648/504/lecture/11468?page=3 (Дата обращения 2 февраля 2011) 5) Глушаков С. Программирование Web – страниц [Текст]. – М.: ООО «Издательство АСТ», 2003. – 387 с. 6) Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с 7) Вирт, Н. Алгоритмы и структуры данных [Текст].– М:. Мир, 1989. – 360 с. 8) Студенческая библиотека онлайн. Поиск подстрок с помощью конечного автомата. – URL: https://studbooks.net/2322413/informatika/poisk_podstrok_pomoschyu_konechnogo_avtomata (Дата обращения 28 февраля 2015) 9) Алгоритмы поиска в строке – URL: https://habr.com/ru/post/111449/ (Дата обращения 8 января 2011) 10) Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. - М.: Наука, 1987. - 288 с. |