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

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

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

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

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

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

Type

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

Реализация процедуры, вычисляющая таблицу смещений для образца p, представлена в приложении 5.

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

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

Глава 2. Практическая часть.

Дан некоторый текст, в котором следует найти фрагмент этого текста.

Данную задачу можно интерпретировать как поиск подстроки в строке.

Эту задачу я реализовал при помощи алгоритма последовательного (прямого) поиска. Программный код задачи реализовал на языке программирования Turbo Pascal 7.1 и он представлен в приложении 7.

Описание работы программы.

После запуска программа запрашивает ввод текста:

Например, введём следующий текст: ”алгоритм рабина представляет собой модификацию линейного алгоритма.”

Далее программа запрашивает ввод строки(подстроки) для поиска:

Например, вводим фрагмент текста: ”алгоритм”

После ввода, программа ищет строку в тексте, если строка существует то программа выводит текст на экран, выделяет строку красным цветом и выдает с какого символа начинается строка:

Если фрагмента нет в тексте, то программа выдаст сообщение о том, что данной строки в тексте не существует:

Глава 3. Анализ алгоритмов

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

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

-    строка

-    подстрока (имеющаяся в данной строке)

-    место вхождения

-    длина подстроки,

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

Алфавит кириллицы содержит 32 буквы, поэтому длина строки будет не более 10, 100, 250 символов.

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

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

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

Эксперимент проходил на ПК:

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

1024 Мб ОЗУ

Компилятор Turbo Pascal 7.1

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

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

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

Таблица 1

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

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

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

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

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

Заключение

В процессе выполнения курсовой работы были рассмотрены различные алгоритмы поиска подстроки в строке и проведен их сравнительный анализ, результаты которого представлены в таблице 2 (см. приложение 9).

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

Только после этого этапа необходимо переходить к реализации программного кода.

В связи с глобализацией информации в сети internet был разработан интеллектуальный поиск. Который позволяет найти документ по смыслу содержащейся в нем информации, то есть документы по заданной теме. В системе реализован алгоритм с использованием компьютерной обработки документа. Согласно гипотезе Ципфа смысл документа зависит от частоты терминов, встречающихся в документе. Однако гораздо важнее не сама частота слова, а то, насколько часто в текущем документе это слово встречается относительно других слов.

Список используемой литературы:

1) Альсведе Р., Вегенер И. "Задачи поиска" , 1982г, Издательство "Мир"

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

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

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

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

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

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

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

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

Электронные источники.

1) http://www.ipkro.isu.ru/informat/methods/findsort/

2) http://www.delphikingdom.com/asp/viewitem.asp?catalogid=65

3) http://revolution./programming/00013926_0.html

4) http://ric.uni-altai.ru/fundamental/pascal1/lab15/l15-teor.htm

5) http://www.rsdn.ru/article/alg/textsearch.xml

Приложение 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<=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;

Приложение 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;

Приложение 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;

Приложение 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;

Приложение 5

 

Алгоритм Бойера-Мура

 

Реализация процедуры, вычисляющая таблицу смещений для образца p.

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

 

Алгоритм Бойера-Мура

Функция, осуществляющая поиск.

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;

Приложение 7

 

Реализация программного кода

program Poisk;         uses crt;          var          t,s,tex,t2:string; p,i,d1,d2,d3,x:integer; text:array [1..100] of string; begin      clrscr;  { }      textcolor(10);      writeln('Введите текст');      textcolor(15);      readln(t);                       writeln;      textcolor(10);      writeln(‘Введите строку’);      textcolor(15);      readln(s);                       writeln;       d3:=0;         repeat                textcolor(10);                p:=pos(s,t);                    if p=0 then                if x>1 then                 begin                 writeln;                writeln('Конец поиска. Для выхода нажмите Enter.')                end                else             writeln('Такой строки в тексте не существует. Для выхода нажмите Enter.')                 else begin               tex:=tex+text[x];               d3:=length(tex);                writeln;               writeln('Образец входит в текст с  ',p+d3,'-ого символа ');                 writeln;              d1:=length(s);            textcolor(15);            write(tex);            for i:=1 to p-1 do            write(t[i]);                 for i:=1 to d1 do                 begin                     textcolor(12);                     write(s[i]);                 end;

 

	d2:=length(t);                        for i:= d1+p to d2 do                          begin                            textcolor(15);                            write(t[i]);                          end;                     readln;                  x:=x+1;                  text[x]:=copy(t,1,p+d1-1);                  delete(t,1,p+d1-1);           end;          until p=0;      readln; end.

Приложение 8

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

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

Приложение 9

Общие результаты с анализов рассмотренных алгоритмов

	Таблица 2

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