Алгоритмы поиска подстроки в строке (работа 1)

Федеральное министерство по образованию

Государственное образовательное учреждение высшего профессионального образования

«Вятский государственный гуманитарный университет»

Факультет информатики

Кафедра информатики и методики обучения информатике

Курсовая работа

Алгоритмы поиска подстроки в строке

Выполнил

студент 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, если найдутся такие строки Z_>1> и Z_>2>, что Y=Z_>1>XZ_>2>. При этом Z_>1> называют левым, а Z_>2> - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение XY.

Пример: слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfro.

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]

Function Search (S: String; X: String; var Place: Byte): Boolean;

{ Функция возвращает результат поиска в слове S }

{ подслова X. Place - место первого вхождения }

var Res: Boolean; i : Integer;

Begin

Res:=FALSE;

i:=1;

While (i<=Length(S)-Length(X)+1) And Not(Res) do

If Copy(S,i,Length(X))=X then

begin

Res:=TRUE;

Place:=i

end

else i:=i+1;

Search:=Res

End;

Листинг 1

Очень просто, но очень неразумно. Ведь максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату.

Следующий метод работает намного быстрее простейшего, но, к сожалению, накладывает некоторые ограничения на текст и искомую строку.

1.2.2. Алгоритм Рабина.

Алгоритм Рабина представляет собой модификацию линейного алгоритма; он основан на весьма простой идее, которую изложим, следуя книге [13 ,172-173].

«Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.» (Листинг 2)

Function Search (S: String; X: String; var Place: Byte): Boolean;

{ Функция возвращает результат поиска в слове S }

{ подслова X. Place - место первого вхождения }

Var Res: Boolean; i: Byte; h,NowH,LenX:Integer; HowMany:Integer;

Begin

Res:=FALSE;

i:=1;

h:=Hash(x); {Вычисление хеш-функции для искомого слова}

NowH:=Hash(Copy(S,1,Length(x)));

HowMany:=Length(S)-Length(X)+1;

LenX:=Length(X);

While (i<=HowMany) And Not(Res) do

If (h=NowH) and (Copy(S,i,Length(X))=X) then

Begin

Res:=TRUE;

Place:=i

End

else

Begin

i:=i+1;

NextHash(s,i,NowH,LenX); {Вычисление следующего значения хеш-функции}

End;

Search:=Res

End;

Листинг 2

Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию, которая должна:

1. Легко вычисляться.

2. Как можно лучше различать несовпадающие строки.

3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ].

Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.

Пример (удобной для вычисления функции) [13 ,172]. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге "окошечка" нужно добавить новое число и вычесть "пропавшее".)

Однако, проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка D*n, где D - количество различных символов), и работать с ними будет так же неудобно. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы.

Пример (семейства удобных функций) [13, 172-173]. Выберем некоторое число p (желательно простое) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы их кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается своя функция). Сдвиг "окошечка" на 1 соответствует вычитанию старшего члена, умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же оно является простым, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно при p, большем числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если n много меньше p, то случайному значению x мало шансов попасть в "неудачную" точку.

Строго говоря, время работы всего алгоритма в целом, есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа.

Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными (хотя бы потому, что иногда выполняют явно бесполезную работу, о чем было сказано выше), поэтому мы перейдём к следующему классу алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм прямого поиска ее просто выбрасывает). Рассмотрим алгоритм Кнута – Морриса – Пратта.

1.3. Алгоритм Кнута - Морриса - Пратта (КМП).

Вначале рассмотрим некоторые вспомогательные утверждения. Для произвольного слова X рассмотрим все его начала, одновременно являющиеся его концами, и выберем из них самое длинное (не считая, конечно, самого слова X). Обозначим его n(X). Такая функция носит название префикс – функции [13].

Примеры.

n(aba)=a, n(n(aba))=n(a)=L;

n(abab)=ab, n(n(abab))=n(ab)=L;

n(ababa)=aba, n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=L; n(abc)=L.

Докажем несколько используемых впоследствии фактов, а именно предложение (по [Шень,1995,с.165-166]):

(1) Последовательность слов n(X),n(n(X)),n(n(n(X))),... "обрывается" (на пустом слове L).

(2) Все слова n(X),n(n(X)),n(n(n(X))),...,L являются началами слова X.

(3) Любое слово, одновременно являющееся началом и концом слова X (кроме самого X), входит в последовательность n(X),n(n(X)),....,L.

Доказательство.

(1) Тривиально, т.к. каждое слово короче предыдущего.

(2) Каждое из них (по определению) является началом предыдущего. По той же причине все они являются концами слова X.

(3) Пусть слово Y является одновременно началом и концом X. Слово n(X) - самое длинное из таких слов, так что Y не длиннее n(X). Оба эти слова являются началами X, поэтому более короткое из них является началом более длинного: Y есть начало n(X). Аналогично, Y есть конец n(X). Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче X, в частности, для слова n(X). Так что слово Y, являющееся концом и началом n(X), либо равно n(X), либо входит в последовательность n(n(X)),n(n(n(X))),...,,L.

Предложение доказано.

Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1 (Листинг 3). Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит

Procedure PrefFunc(P:String; Var Fl:TMas);

Var n,i,j:Integer;

Begin

n:=Length(P);

Fl[1]:=0;

For i:=2 To n Do

Begin

j:=Fl[i-1];

While (j<>0) And (P[j]<>P[i-1]) Do j:= Fl[j];

Fl[i]:=j+1;

End;

End;

ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Так как в цикле while она уменьшается (P[k]<k), но не становится меньше 0, то уменьшаться она может не чаще, чем возрастать. Переменная k возрастает на 1 не более m раз. Значит, переменная k меняется всего не более 2m раз. Выходит, что время работы всей процедуры есть O(m) [1, 2].

А

Листинг 3

сейчас мы переходим к самому алгоритму, ищущему подстроку в строке (Листинг 4).

Function KMPSearch(S,P:String):Integer;

{ Алгоpитм Кнута-Моpиса-Пpатта, устанавливающий }

{ вхождение непустой стpоки P в стpоку S }

Var Fl:TMas;

i,j,n,m:Integer;

Begin

n:=Length(S);

m:=Length(P);

PrefFunc(P,Fl);

j:=1;

For i:=1 To n Do

begin

While (j<>0) And (P[j]<>S[i]) do j:=Fl[j];

If j=m Then Break;

j:=j+1

end;

If (j=m) then Result:=i-j+1 Else Result:=0;

End;

Листинг 4

Доказать что эта программа работает за линейное время, можно точно так же, как и для префикс - функции. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

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

1.4. Алгоритм Бойера – Мура и некоторые его модификации.

1.4.1. Алгоритм Боейера – Мура.

Алгоритм Бойера-Мура, разработанный двумя учеными – Бойером (Robert S. Boyer) и Муром (Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Простейший вариант алгоритма Бойера-Мура состоит из следующих шагов. На первом шаге мы строим таблицу смещений для искомого образца. Процесс построения таблицы будет описан ниже. Далее мы совмещаем начало строки и образца и начинаем проверку с последнего символа образца. Если последний символ образца и соответствующий ему при наложении символ строки не совпадают, образец сдвигается относительно строки на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. Если же символы совпадают, производится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с наложенными символами строки, значит мы нашли подстроку и поиск окончен. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, мы сдвигаем образец на один символ вправо и снова начинаем проверку с последнего символа. Весь алгоритм выполняется до тех пор, пока либо не будет найдено вхождение искомого образца, либо не будет достигнут конец строки.

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

Величина смещения для каждого символа образца зависит только от порядка символов в образце, поэтому смещения удобно вычислить заранее и хранить в виде одномерного массива, где каждому символу алфавита соответствует смещение относительно последнего символа образца. Поясним все вышесказанное на простом примере. Пусть у нас есть алфавит из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца “abbad” в строке “abeccacbadbabbad”. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так.

Начало поиска.

Последний символ образца не совпадает с наложенным символом строки. Сдвигаем образец вправо на 5 позиций:

Три символа образца совпали, а четвертый – нет. Сдвигаем образец вправо на одну позицию:

Последний символ снова не совпадает с символом строки. В соответствии с таблицей смещений сдвигаем образец на 2 позиции:

Еще раз сдвигаем образец на 2 позиции:

Теперь, в соответствии с таблицей, сдвигаем образец на одну позицию, и получаем искомое вхождение образца:

Реализуем указанный алгоритм на языке Pascal.

Прежде всего следует определить тип данных «таблица смещений». Для кодовой таблицы, состоящей из 256 символов, определение этого типа будет выглядеть так:

Type

TBMTable = Array [0..255] of Integer;

Далее приводится процедура, вычисляющая таблицу смещений для образца p (Листинг 5).

Procedure MakeMBTable( var Bmt : TBMTable; Const p : string);
Var i : Integer;
Begin
For i := 0 to 255 do Bmt[i] := Length(p);
For i := Length(p) Downto 1 Do
If Bmt[Byte(p[i])] = Length(p) Then
Bmt[Byte(p[i])] := Length(p) – i;
End;

Листинг 5

Теперь напишем функцию, осуществляющую поиск (Листинг 6).

Параметр StartPos позволяет указать позицию в строке s, с которой следует начинать поиск. Это может быть полезно в том случае, если вы захотите найти все вхождения p в s. Для поиска с самого начала строки следует задать StartPos равным 1. Если результат поиска не равен нулю, то для того, чтобы найти следующее вхождение p в s, нужно задать StartPos равным значению «предыдущий результат плюс длина образца».

1.4.2. Модификации БМ.

Быстрый поиск (Классификация Thierry Lecroq [2]).

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

function bmsearch( startpos : integer; const s, p : string;
const bmt : tbmtable) : integer;
var
pos, lp, i : integer;
begin
lp := length(p);
pos := startpos + lp –1;
while pos < length(s) do
if p[lp] <> s[pos] then pos := pos + bmt[s[pos]]
else for i := lp - 1 downto 1 do
if p[i] <> s[pos – lp + i] then
begin
inc(pos);
break;
end
else if i = 1 then
begin
result := pos – lp + 1;
exit;
end;
result := 0;
end;

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

После попытки совмещения x и y [i, i+m-1], длина сдвига - не менее 1. Таким образом, символ y [ i + m ] обязательно будет вовлечен в следующую попытку, а значит, может быть использован в текущей попытке для сдвига плохого символа. Модифицируем функцию плохого символа, чтобы принять в расчет последний символ х:

bc[ a ] = min { j | 0 j m и x[ m - 1 - j ] = a }, если a встречается в x,

bc[ a ] = m в противоположном случае.

Сравнения текста и образца могут производиться в любом порядке.

Т

Листинг 6

урбо БМ (Классификация Thierry Lecroq [2]).

Турбо - БМ является также является улучшением алгоритма Боуера - Мура. Мы будем запоминать сегмент текста, который сошелся с суффиксом образца во время прошлой попытки (и только, если произошел сдвиг хорошего суффикса).

Это даст нам два преимущества:

1. Возможность перескочить через этот сегмент

2. Возможность применения «турбо – сдвига»

«Турбо – сдвиг» может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.

Пусть u - запомненный сегмент, а v - cуффикс, совпавший во время текущей попытки, такой что uzv - суффикс x. Тогда av - суффикс x, два символа а и b встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем «турбо – сдвигом» ).

1.5. Поиск подстрок с помощью конечного автомата.

1.5.1. Структура автомата.

По определению, конечный автомат представляет собой пятерку М = (Q, q_>0>, A, , ), где:

Q — конечное множество состояний;

q_>0>Q — начальное состояние;

А_>>Q — конечное множество допускающих состояний;

— конечный входной алфавит;

— функция Q х Q, называемая функцией переходов автомата.

Первоначально конечный автомат находится в состоянии q_>0>. Затем он по очереди читает символы из входной строки. Находясь в состоянии q и читая символ а, автомат переходит в состояние (q,a). Если автомат находится в состоянии q A говорят, что он допускает прочитанную часть входной строки. Если q А, то прочитанная часть строки отвергнута.

С конечным состоянием М связана функция , называемая функцией конечного состояния, определяемая следующим образом: есть состояние, в которое придет автомат (из начального состояния), прочитав строку w. Автомат допускает строку w тогда и только тогда, когда А

Для каждого образца Р можно построить конечный автомат, ищущий этот образец в тексте. Первым шагом в построении автомата, соответствующего строке-образцу Р[1..m], является построение по Р вспомогательной суффикс-функциии (как в алгоритме КМП). Теперь определим конечный автомат, соответствующий образцу Р[1..m], следующим образом:

Его множество состояний Q = {0,1,..., m}. Начальное состояние q_>0> = 0. Единственное допускающее состояние m;

Функция переходов определена соотношением (q — состояние, — символ): (q,a) = (P_>q>a). (1)

Поясним это соотношение. Требуется сконструировать автомат таким образом, чтобы при его действии на строку Т соотношение

(Т_>i>) = (Т_>i>)

являлось инвариантом (тогда равенство (Т_>i>) = m будет равносильно тому, что Р входит в Т со сдвигом i — m, и автомат тем самым найдет все допустимые сдвиги). Однако в этом случае вычисление перехода по формуле (1) необходимо для поддержания истинности инварианта, что следует из теорем, приведенных ниже.[3]

Теорема. Пусть q = (х), где х — строка. Тогда для любого символа а имеет место (ха) = (P_>q>a).

Теорема. Пусть — функция конечного состояния автомата для поиска подстроки Р[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 — номер состояния. Таким образом, необходимо для каждого префикса P_>q> = 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.