Федеральноеминистерство по образованию
Государственное образовательное учреждение высшегопрофессионального образования
«Вятский государственный гуманитарный университет»
Факультет информатики
Кафедра информатики и методики обучения информатике
Курсоваяработа
Алгоритмы поиска подстроки в строке
Выполнил
студент III курса математическогофакультета
Белов Денис Владимирович
Проверил преподаватель кафедрыинформатики и методики обучения информатике
Иванов С. Ю.
Киров, 2006г.Содержание.
Введение. 3
Часть 1. Теоретические сведенияоб алгоритмах поиска подстроки в строке. 5
1.1. Основные понятия. 5
1.1.1 Строка, её длина, подстрока. 5
1.1.2. Понятие о сложности алгоритма. 6
1.2. Алгоритмы основанные на методе последовательногопоиска. 7
1.2.1. Алгоритм последовательного (прямого) поиска (TheBrute 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]
Листинг 1
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
If Copy(S,i,Length(X))=X then
begin
Res:=TRUE;
Place:=i
end
else i:=i+1;
Search:=Res
End; />
Очень просто, но очень неразумно. Ведь максимальное, количество сравненийбудет равно O((m-n+1)*n+1), хотя большинство изних на самом деле лишние. Например, найдя строку aabc и обнаруживнесоответствие в четвертом символе (совпало только aab), алгоритм будетпродолжать сравнивать строку, начиная со следующего символа, хотя этооднозначно не приведет к результату.
Следующий метод работает намного быстрее простейшего, но, к сожалению,накладывает некоторые ограничения на текст и искомую строку.1.2.2.Алгоритм Рабина.
Алгоритм Рабина представляет собой модификацию линейного алгоритма; оноснован на весьма простой идее, которую изложим, следуя книге [13 ,172-173].
«Представим себе, что в слове A, длина которого равна m, мы ищем образецX длины n. Вырежем «окошечко» размером n и будем двигать его повходному слову. Нас интересует, не совпадает ли слово в «окошечке» сзаданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторуючисловую функцию на словах длины n, тогда задача сведется к сравнению чисел,что, несомненно, быстрее. Если значения этой функции на слове в«окошечке» и на образце различны, то совпадения нет. Только еслизначения одинаковы, необходимо проверять последовательно совпадение по буквам.»(Листинг 2)
Листинг 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
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; />
Этот алгоритм выполняет линейный проход по строке (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 (j0) And (P[j]P[i-1]) Do j:= Fl[j];
Fl[i]:=j+1;
End;
End; />ответить: почему времяработы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну,во-первых, присвоение префикс-функции происходит четко m раз, остальное времяменяется переменная k. Так как в цикле while она уменьшается (P[k]Листинг 3 А сейчас мыпереходим к самому алгоритму, ищущему подстроку в строке (Листинг 4).
Листинг 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 (j0) 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; />
Доказать что эта программа работает за линейное время, можно точно также, как и для префикс — функции. Стало быть, общее время работы программы есть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).
Листинг 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; />
Теперь напишем функцию,осуществляющую поиск (Листинг 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
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, q0,A, />, />), где:
Q — конечное множество состояний;
q0/>Q — начальноесостояние;
А/>Q — конечноемножество допускающих состояний;
/> — конечный входной алфавит;
/> — функция Q х /> /> Q, называемая функциейпереходов автомата.
Первоначально конечный автомат находится в состоянии q0. Затемон по очереди читает символы из входной строки. Находясь в состоянии q и читаясимвол а, автомат переходит в состояние />(q,a).Если автомат находится в состоянии q />A говорят, что он допускаетпрочитанную часть входной строки. Если q /> А,то прочитанная часть строки отвергнута.
С конечным состоянием М связана функция />,называемая функцией конечного состояния, определяемая следующим образом: />есть состояние, в котороепридет автомат (из начального состояния), прочитав строку w. Автомат допускает строку w тогда и только тогда, когда />/>А
Для каждого образца Р можно построить конечный автомат, ищущий этотобразец в тексте. Первым шагом в построении автомата, соответствующегостроке-образцу Р[1..m], является построение по Р вспомогательнойсуффикс-функциии (как в алгоритме КМП). Теперь определим конечный автомат,соответствующий образцу Р[1..m],следующим образом:
· Его множествосостояний Q = {0,1,..., m}.Начальное состояние q0= 0. Единственное допускающее состояние m;
· Функция переходов/> определена соотношением (q— состояние, /> — символ): /> (q,a) = />(Pqa). (1)
Поясним это соотношение. Требуется сконструировать автомат таким образом,чтобы при его действии на строку Т соотношение
/>(Тi)= />(Тi)
являлось инвариантом (тогда равенство />(Тi) = m будет равносильно тому, что Р входит в Т со сдвигом i — m, и автомат тем самым найдет все допустимые сдвиги). Однако вэтом случае вычисление перехода по формуле (1) необходимо для поддержанияистинности инварианта, что следует из теорем, приведенных ниже.[3]
Теорема. Пусть q = />(х), гдех — строка. Тогда для любого символа а имеет место /> (ха)= />(Pqa).
Теорема. Пусть /> — функцияконечного состояния автомата для поиска подстроки Р[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): 1 2 3 4 5 6 7 a 1 1 3 1 5 1 7 1 b 2 4 4 2 c 6
Строки соответствуют входным символам, столбцы — состояниям автомата.Ячейки, соответствующие успешным этапам поиска (входной символ совпадает соследующим символом образца), выделены серым цветом.
Построим по таблице граф переходов автомата (Рис. 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 ADeclarative Pattern Matching System [Текст]. – Bielefeld:. UniversitätBielefeld, 1995. – 238 с.
2). Lecro, T. Exact string matchingalgorithms [Электронный ресурс]. Режимдоступа 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.