Мб ОЗУ

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)
Алгоритм		Алгоритм прямого поиска	Алгоритм Рабина		КМП		БМ