Поиск подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?но текст: Уважаемые граждане России! и выберем алгоритм поиска Бойера-Мура (рис. 2.3).
Рис. 2.3. Выбор алгоритма
После нажатия на кнопку Выполнить поиск поочередно появляются два окна Количество тактов процессора (рис. 2.4) и Результат поиска (рис.2.5).
Рис. 2.4. Количество тактов процессора
Рис. 2.5. Результат поиска
Также открывается файл, в котором был произведен поиск (рис. 2.6).
Рис. 2.6. Текстовый файл Выступление Путина.txt
Если искомый фрагмент отсутствует, то будет выведено сообщение о неудачном поиске (рис. 2.7).
Рис. 2.7. Неудачный поиск
3. Тестирование алгоритмов
В курсовой работе рассмотрено четыре алгоритма поиска подстроки в строке. Была произведена оценка их временной и емкостной сложности. Экспериментальный анализ состоял в измерении количества тактов процессора, за которое выполнялся поиск тем или иным алгоритмом.
Было составлено случайным образом 10 раз три текстовых файла из строчных букв латинского алфавита, длиной в 1000, 10000 и 100000 символов. В каждом из этих файлов выполнялся поиск подстроки, полученной алгоритмом, состоящем из следующих шагов:
Вычисление случайной длины подстроки
Для текстового файла, длиной 1000 символов вычислялась случайная длина искомой подстроки от 10 до 50 символов; для текстового файла, длиной 10000 символов случайная длина подстроки от 100 до 500 символов; и для файла, длиной 100000 символов случайная длина фрагмента вычислялась из диапазона от 1000 до 5000 символов;
Вычисление случайной позиции начала искомой подстроки в файле
Для каждого текстового файла получали случайную позицию подстроки из диапазона от 0 до S.Length-X.Length, где S.Length - длина текстового файла и X.Length - длина искомой подстроки.
Каждый алгоритм выполнял поиск одной и той же подстроки по 10 раз. И в итоге выбирался наилучший результат среди всех попыток.
Так как все алгоритмы находились в равных условиях, то можно провести сравнительный анализ. Заметим, что полученные данные применимы только для данных параметров поиска, и в других условиях могут отличаться.
Среднестатистические результаты экспериментов приведены в Таблице 1 и проиллюстрированы на рис. 3. Полный отчет обо всех экспериментах представлен в Таблице 2, в Приложении Е.
Таблица 1. Среднестатистические результаты тестирования алгоритмов поиска
Алгоритм поискаВремя работы алгоритма, такты процессора1000 символов10 тыс. символов100 тыс. символовПоследовательный16879953101303Рабина-Карпа171810524100300Кнута-Морриса-Пратта1647971092453Бойера-Мура1414580348262
Рис. 3. Результаты тестирования алгоритмов.
Из Таблицы 2 видно, что алгоритм Бойера-Мура справился с экспериментальной задачей быстрее остальных. Однако его эффективность растет с увеличением длины исходной строки и искомой подстроки. Поэтому на входном файле с 1000 символами он показал результат не много лучше остальных алгоритмов.
Алгоритм Кнута-Морриса-Пратта выполнил задачу быстрее Рабина-Карпа и Последовательного поиска, однако существенно уступил Бойеру-Муру. Но к плюсу этого алгоритма можно отнести относительно небольшой разброс времени работы, независимо от входных данных. Что нельзя сказать об алгоритме Бойера-Мура.
Алгоритм Рабина-Карпа, практически не отличается по временным показателям от алгоритма последовательного поиска, но его простота и малые трудозатраты на реализацию, делают его привлекательным для использования в неспециальных программах. Также стоит отметить, что он более эффективно работает на больших алфавитах, где случайные совпадения хеш-функций практически отсутствуют, чего нельзя отметить для данного эксперимента.
Заключение
В курсовой работе были рассмотрены основные алгоритмы поиска подстроки в строке и проведен их сравнительный анализ.
По полученным результатам можно сделать вывод, что алгоритм Бойера-Мура является лучшим по всем показателям. Однако нельзя сделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждый из этих алгоритмов эффективно работает в определенных классах задач. Поэтому выбирать алгоритм поиска для реализации в конкретной задаче нужно только после определения точных целей и функциональности, которые она будет выполнять.
Список использованных источников
1. Ахо А. Алгоритмы поиска подстроки в строке // Структура данных и алгоритмы. - М.: Вильямс, 2000. - С. 384.
. Брайан К. Практика программирования. - СПб: Невский диалект, 2001. - С. 381.
. Вирт Н. Алгоритмы и структуры данных. - М.: Мир, 1989. - С. 360.
. Кнут Д. Алгоритм Кнута-Морриса-Пратта // Искусство программирования на ЭВМ. - М.: Мир, 1978. - т.3. - С. 356.
. Кормен Т., Лейзерсон И., Ривест Л., Штайн. Алгоритмы поиска подстроки // Алгоритмы: построение и анализ - 2-e издание. - М.: Вильямс, 2005. - С. 1019 - 1058.
. Алгоритмы поиска подстроки в строке // MyKod [Эл. ресурс]. URL:
7. Алгоритм Кнута-Морриса-Пратта // Maximal [Эл. ресурс]. URL:
8. Алгоритм Бойера-Мура // Исходники [Эл. ресурс]. URL:
Приложение
Приложение А
Реализация алгоритма последовательного поиска
//Функция последовательного поискаstatic string Posl(string x, string s)
{
//Объявление строки с номерами позиций
string nom = "";
//Если искомая строка больше исходной - возврат пустог