Курсовая работа: Алгоритмы поиска подстроки в строке

Теорема. Пусть  — функция конечного состояния автомата для поиска подстроки Р[1.. m]. Если Т[1.. n] — произвольный текст, то (Тi) = (Тi) для i=0,1,..., n. [14]

Из изложенного следует, что задача поиска подстроки состоит из двух частей:

построение автомата по образцу (определение функции переходов для заданного образца);

применение этого автомата для поиска вхождений образца в заданный текст.

1.5.2. Пример построения конечного автомата

Построим конечный автомат, допускающий строку ababaca. Поскольку длина образца m = 7 символов, то в автомате будет m + 1 = 8 состояний.

Найдем функцию переходов . В соответствии с определением (1), (q, a) =(Рqа), где   префикс-функция, а — произвольный символ из алфавита , q — номер состояния. Таким образом, необходимо для каждого префикса Pq = P[0..q], q = 0 .. m образца Р и для всех символов а входного алфавита  найти длину максимального префикса Р, который будет являться суффиксом строки Рqа. Длина этого префикса и будет значением функции переходов (q,a). Если а = P[q + 1] (очередной символ текста совпал со следующим символом образца), то Рqа = Рq+1 и (q, a) = q+1.

Такой случай соответствует успешным этапам поиска. Иначе, (q,a)q. Например, для префикса Р[0..5] = ababa и символа b максимальным суффиксом строки Р[0..5]b=ababab, который одновременно является префиксом Р, будет abab. Его длина равна 4, поэтому значение функции переходов (5, b) = 4.

Запишем построенную таким образом функцию переходов в виде таблицы (Табл. 1):

	0	1	2	3	4	5	6	7
a	1	1	3	1	5	1	7	1
b	0	2	0	4	0	4	0	2
c	0	0	0	0	0	6	0	0

Строки соответствуют входным символам, столбцы — состояниям автомата. Ячейки, соответствующие успешным этапам поиска (входной символ совпадает со следующим символом образца), выделены серым цветом.

Построим по таблице граф переходов автомата (Рис. 1), распознающего образец ababaca. Находясь в состоянии q и прочитав очередной символ а, автомат переходит в состояние (q,a). Обратим внимание, что его остов помечен символами образца (эти переходы выделены жирными стрелками).

Рис. 1

Здесь 0 — исходное состояние, 7 — единственное допускающее состояние (зачернено). Если из вершины i в вершину j ведет стрелка, помеченная буквой а, то это означает, что (i,a) = j. Отметим, что переходы, для которых (i,a) = 0, на графе переходов для его упрощения не обозначены. Жирные стрелки, идущие слева направо, соответствуют успешным этапам поиска подстроки Р — следующий входной символ совпадает с очередным символом образца. Стрелки, идущие справа налево, соответствуют неудачам — следующий входной символ отличается от очередного символа образца.

Ниже приведен результат применения автомата к тексту Т = abababacaba. Под каждым символом Т[г] записано состояние автомата после прочтения этого символа (иными словами, значение (Тi)) (Табл. 2).

Найдено одно вхождение образца (начиная с позиции 3). Найденный образец в тексте помечен серым цветом. Черным цветом помечено допускающее состояние автомата (состояние с номером 7).

Часть 2. Экспериментальный анализ алгоритмов.

2.1. Суть эксперимента.

Мы рассмотрели несколько алгоритмов, провели оценку их временной и емкостной сложности. Однако, как уже говорилось, данные критерии оценки не позволяют нам наверняка сказать, какой из алгоритмов будет быстрее работать. Поэтому, для дополнительной оценки проведем их экспериментальный анализ, т.е. измерим время, за которое алгоритм выполняет конкретно поставленную задачу.

Имеется несколько текстовых файлов, содержащих 10000 записей вида:
строка
подстрока (имеющаяся в данной строке)
место вхождения
длина подстроки

с разными максимальными длинами строк и подстрок.

Алфавитом является 66 русских заглавных и строчных букв.

Пусть это будут строки длиной не более 10, 100, 250 символов.

Проведем поиск подстрок в строках для каждого из алгоритмов и измерим время работы программы. При этом будем учитывать следующее:

·           Строки предварительно загружаем в оперативную память (в виде массива), причем время считывания в массив не учитывается. Предобработка (создание таблиц перехода) входит в общее время.

·           Каждый алгоритм запускается 5 раз, время выбирается наименьшее.

Стенд для эксперимента.

Процессор Intel Pentium IV 2,66Ггц

1024 Мб ОЗУ

Компилятор Borland Delphi Enterprise, version 6.0 (Build 6.163)

Фрагмент кода тестируемой программы приведем в листинге 7.

LoadFromFile('C:\String_250.txt'); {Происходит загрузка в массив}   Tick:=GetTickCount; {Запоминаем текцщее значение переменной Tick}   Poisk;  {Процедура в которой происходит поиск 10000 раз}   Tick:=GetTickCount-Tick; {Получаем разницу – время в миллисекундах}   WriteLn('Za vremja ',Tick, ' ms');

 

Понятно, что такой замер времени даст нам весьма расплывчатые результаты, так как напрямую зависит от характеристик и загрузки процессора. Поэтому во время проведения эксперимента, отключались все сторонние и фоновые приложения, которые не влияют на работу программы. При запуске одной и той же задачи мы можем получить разное время, поэтому совершается несколько запусков, из которых выбирается наилучший результат.

2.2. Результаты и анализ эксперимента.

Эксперимент проводился для четырех алгоритмов – представителей классов алгоритмов. Так как все алгоритмы ставились в одинаковые условия, то можно провести их сравнительный анализ. Заметим, что данный анализ применим только для данных параметров поиска, и при иных условиях может отличаться.

Результаты эксперимента занесем в таблицу (Табл. 3).

Алгоритм	Время выполнения
	Длина ≤10	Длина ≤100	Длина ≤250
Послед. поиск	15	93	234
Алгоритм Рабина (Хеш – сумма кодов)	15	63	93
КМП	5	30	50
БМ	31	31	32

Как и предполагалось, алгоритм Бойера Мура справился с экспериментальной задачей быстрее остальных. Следует, однако, заметить, что его эффективность растет лишь с увеличением длины строки и, соответственно, длины образца. Так при длине строки меньшей или равной 10 символов, он показал себя хуже, чем последовательный поиск. Аналогичные результаты показывает и алгоритм КМП, как для коротких, так и для длинных слов. Его можно использовать как универсальный, когда неизвестны длины строки и образца.

Алгоритм Рабина, при его схожести с последовательным работает быстрее, а его простота и малые трудозатраты на реализацию, делают его привлекательным для использования в неспециальных программах.

Наихудший результат показал алгоритм последовательного поиска. Как предполагалось лишь при небольшом увеличении длины строки, он работает в разы медленнее остальных алгоритмов.

В данный эксперимент не включен алгоритм поиска с помощью конечного автомата, т.к. мы используем алфавит, состоящий из 66 букв русского алфавита, и построенный автомат был бы слишком громоздок. Эффективность этого алгоритма возрастает при малом количестве букв в алфавите.

Заключение.

Мы рассмотрели различные алгоритмы поиска подстроки в строке, сделали их анализ. Результаты можно представить в таблице (Табл. 4).

Алгоритм	Время на пред. обработку	Среднее время поиска	Худшее время поиска	Затраты памяти	Время работы (мс) при длине строки ≤250	Примечания
Алгоритмы основанные на алгоритме последовательного поиска
Алгоритм прямого поиска	Нет	O((m-n+1)*n+1)/2	O((m-n+1)*n+1)	Нет	234	Mалые трудозатраты на программу, малая эффективность.
Алгоритм Рабина	Нет	O(m+n)	O((m-n+1)*n+1)	Нет	93
Алгоритм Кнута-Морриса-Пратта
КМП	O(m)	O(n+m)	O(n+m)	O(m)	31	Универсальный алгоритм, если неизвестна длина образца
Алгоритм Бойера-Мура
БМ	O(m+s)	O(n+m)	O(n*m)	O(m+s)	32	Алгоритмы этой группы наиболее эффективны в обычных ситуациях. Быстродействие повышается при увеличении образца или алфавита.

Исходя из полученных результатов, видно, что алгоритм Бойера – Мура является ведущим по всем параметрам, казалось бы, найден самый эффективный алгоритм. Но, как показывает эксперимент, алгоритм Кнута – Мориса - Пратта, превосходит алгоритм БМ на небольших длинах образца. Поэтому я не могу сделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждый алгоритм позволяет эффективно действовать лишь для своего класса задач, об этом еще говорят различные узконаправленные улучшения. Алгоритм поиска подстроки в строке следует выбирать только после точной постановки задачи, которые должна выполнять программа.

Сделав такой вывод, мы выполнили цель данной работы, т.к. для различных классов задач был выделен свой эффективный алгоритм.

Библиографический список.

1). Kurtz, St. Fundamental Algorithms For A Declarative Pattern Matching System [Текст]. – Bielefeld:. Universität Bielefeld, 1995. – 238 с.

2). Lecro, T. Exact string matching algorithms [Электронный ресурс]. Режим доступа http://algolist.manual.ru/

3). Ахметов И. Поиск подстрок с помощью конечных автоматов [Текст]: Курсовая работа.- С-П государственный университет информационных технологий, механики и оптики.

4). Ахо, Альфред Структура данных и алгоритмы [Текст]. М.: Издательский дом «Вильямс», 2000. - 384 с.

5). Белоусов А. Дискретная математика [Текст]. – М.: Издательство МГТУ им. Н.Э. Баумана, 2001. – 744 с.

6). Брайан, К. Практика программирования [Текст].- СПб:. Невский диалект, 2001. - 381 с.

7). Вирт, Н. Алгоритмы и структуры данных [Текст]. М:. Мир, 1989. – 360 с.

8). Гилл, Арт. Введение в теорию конечных автоматов [Текст]. – М., 1966. - 272 с.

9). Глушаков С. Программирование Web страниц [Текст]. – М.: ООО «Издательство АСТ», 2003. – 387 с.

10). Кнут, Д. Искусство программирования на ЭВМ [Текст]: Том 3. – М:. Мир, 1978. – 356 с.

11). Матрос Д. Элементы абстрактной и компьютерной алгебры: Учеб. пособие для студ. педвузов [Текст]. – М.: Издательский центр «Академия», 2004. – 240 с.

12). Успенский В. Теория алгоритмов: основные открытия и приложения [Текст]. – М.: Наука, 1987. – 288 с.

13). Шень, А. Программирование: теоремы и задачи [Текст]. – М.: Московский центр непрерывного математического образования, 1995.

14). Кормен, Т. Алгоритмы: построение и анализ [Текст]/ Т. Кормен, Ч. Лейзерсон, Р. Ривест - М.: МЦНМО, 2002.  М.: МЦНМО, 2002.