Алгоритмы поиска подстроки в строке (стр. 1 из 4)
Федеральное министерство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Вятский государственный гуманитарный университет»
Факультет информатики
Кафедра информатики и методики обучения информатике
Курсовая работа
Алгоритмы поиска подстроки в строке
Выполнил
студент III курса математического факультета
Белов Денис Владимирович
Проверил преподаватель кафедры информатики и методики обучения информатике
Иванов С. Ю.
Киров, 2006 г.
Содержание.
Введение. 3
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке. 5
1.1. Основные понятия. 5
1.1.1 Строка, её длина, подстрока. 5
1.1.2. Понятие о сложности алгоритма. 6
1.2. Алгоритмы основанные на методе последовательного поиска. 7
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm). 7
1.2.2. Алгоритм Рабина. 7
1.3. Алгоритм Кнута - Морриса - Пратта (КМП). 10
1.4. Алгоритм Бойера – Мура и некоторые его модификации. 13
1.4.1. Алгоритм Боейера – Мура. 13
1.4.2. Модификации БМ. 15
1.5. Поиск подстрок с помощью конечного автомата. 17
1.5.1. Структура автомата. 17
1.5.2. Пример построения конечного автомата. 19
Часть 2. Экспериментальный анализ алгоритмов. 21
2.1. Суть эксперимента. 21
2.2. Результаты и анализ эксперимента. 22
Заключение. 24
Библиографический список. 25
Введение
Те, кому приходиться часто работать с текстовыми редакторами, знают цену функции нахождения нужных слов в тексте, существенно облегчающей редактирование документов и поиск нужной информации. Действительно, современные программы обработки текста приучили нас к такой удобной возможности, как поиск и замена фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды.
Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня – чтобы найти строчку в небольшом тексте вы, наверное, используете встроенную функцию. Но если такого рода поиск является ключевой задачей вашей программы, знать принципы организации функций поиска будет совсем нелишне. При этом. в готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html – страницы [9, с. 10]. Работа простейшего спам – фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Все вышесказанное говорит об актуальности проблемы, затрагиваемой работой.
Поставим задачу поиска подстроки в строке. Пусть у нас есть строка, состоящая из некоторого количества символов. Нам нужно проверить, входит ли другая заданная строка в данный текст, и если входит, то начиная с какого символа текста.
В данной работе мы ставим цель, выявить наиболее оптимальный алгоритм, решающий поставленную задачу поиска.
Задачи данной работы:
· рассмотреть основные алгоритмы, решающих задачу поиска;
· систематизировать алгоритмы согласно используемым в них приемам;
· выявить эффективные, с точки зрения времени выполнения, алгоритмы.
Работа содержит две основных части. В первой будут рассмотрены алгоритмы, их теоретическое обоснование, алгоритмическая модель, будет проведена попытка их классификации. Во второй части работы будут приведены данные о практическом применении алгоритмов. В заключении будет сделан вывод о наиболее эффективном (с временной точки зрения) алгоритме.
Часть 1. Теоретические сведения об алгоритмах поиска подстроки в строке.
1.1. Основные понятия.
1.1.1 Строка, её длина, подстрока.
Здесь мы приводим ряд определений, которые будем использовать в изложении материала [5, 11].
Определение 1. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.
Определение 2. Длина строки – количество знаков в строке.
Слова будем обозначать буквами латинского алфавита, напр. X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)=
=n – обозначение длины строки.Определение 3. Слово не содержащее ни одной буквы называется пустым.
Пустое слово обычно обозначают буквой L. Length(L)=0.
Определение 4. Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.
Пример: слово ab является префиксом слова abcfa.
Определение 5. Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.
Пример: слово bfg является суффиксом слова vsenfbfg.
Определение 6.Слово X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называют левым, а Z2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение X
Y.Пример: слова hrf и fhr является подстроками слова abhrfhr, gf
sfdgfro.1.1.2. Понятие о сложности алгоритма.
Целью нашей работы является найти эффективный алгоритм, однако ничего пока не было сказано о методе оценки алгоритмов.
Традиционно в программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, насколько много при этом расходуется память машины? Учет памяти обычно ведется по объему данных и не принимается во внимание память, расходуемая для записи команд программы. Время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой для машин с разной тактовой частотой. [11, с. 38-40]
В данной работе будут рассмотрены две характеристики сложности алгоритмов - временная и емкостная. Мы не будем обсуждать логическую сложность разработки алгоритма - сколько «человеко-дней» нужно потратить на создание программы, поскольку не представляется возможным дать объективные количественные характеристики.
Временную сложность будем подсчитывать в исполняемых командах: количество арифметических операций, количество сравнений, пересылок (в зависимости от алгоритма). Емкостная сложность будет определяться количеством переменных, элементов массивов, элементов записей или просто количеством байт [6, 7, 10, 11].
Эффективность алгоритма также будет оцениваться с помощью подсчета времени выполнения алгоритмом конкретно поставленной задачи, т.е. с помощью эксперимента, подробнее об этом в части 2 данной работы.
1.2. Алгоритмы основанные на методе последовательного поиска.
1.2.1. Алгоритм последовательного (прямого) поиска (The Brute Force Algorithm).
Самый очевидный алгоритм. Обозначим S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция (Листинг 1). [1, 2]
