Алгоритм
поиска
|
Время
работы алгоритма, такты процессора
|
|
1000
символов
|
10
тыс. символов
|
100
тыс. символов
|
Последовательный
|
1687
|
9953
|
101303
|
Рабина-Карпа
|
1718
|
10524
|
100300
|
Кнута-Морриса-Пратта
|
1647
|
9710
|
92453
|
Бойера-Мура
|
1414
|
5803
|
48262
|
Рис. 3. Результаты тестирования алгоритмов.
Из Таблицы 2 видно, что алгоритм Бойера-Мура
справился с экспериментальной задачей быстрее остальных. Однако его
эффективность растет с увеличением длины исходной строки и искомой подстроки.
Поэтому на входном файле с 1000 символами он показал результат не много лучше
остальных алгоритмов.
Алгоритм Кнута-Морриса-Пратта выполнил задачу
быстрее Рабина-Карпа и Последовательного поиска, однако существенно уступил
Бойеру-Муру. Но к плюсу этого алгоритма можно отнести относительно небольшой
разброс времени работы, независимо от входных данных. Что нельзя сказать об
алгоритме Бойера-Мура.
Алгоритм Рабина-Карпа, практически не отличается
по временным показателям от алгоритма последовательного поиска, но его простота
и малые трудозатраты на реализацию, делают его привлекательным для
использования в неспециальных программах. Также стоит отметить, что он более
эффективно работает на больших алфавитах, где случайные совпадения хеш-функций
практически отсутствуют, чего нельзя отметить для данного эксперимента.
Заключение
В курсовой работе были рассмотрены основные
алгоритмы поиска подстроки в строке и проведен их сравнительный анализ.
По полученным результатам можно сделать вывод,
что алгоритм Бойера-Мура является лучшим по всем показателям. Однако нельзя
сделать вывод, что какой-то из алгоритмов является самым оптимальным. Каждый из
этих алгоритмов эффективно работает в определенных классах задач. Поэтому
выбирать алгоритм поиска для реализации в конкретной задаче нужно только после
определения точных целей и функциональности, которые она будет выполнять.
Список использованных источников
1.
Ахо А. Алгоритмы поиска подстроки в строке // Структура данных и алгоритмы. -
М.: «Вильямс», 2000. - С. 384.
.
Брайан К. Практика программирования. - СПб: «Невский диалект», 2001. - С. 381.
.
Вирт Н. Алгоритмы и структуры данных. - М.: «Мир», 1989. - С. 360.
.
Кнут Д. Алгоритм Кнута-Морриса-Пратта // Искусство программирования на ЭВМ. -
М.: «Мир», 1978. - т.3. - С. 356.
.
Кормен Т., Лейзерсон И., Ривест Л., Штайн. Алгоритмы поиска подстроки //
Алгоритмы: построение и анализ - 2-e издание. - М.: «Вильямс», 2005. - С. 1019
- 1058.
.
Алгоритмы поиска подстроки в строке // «MyKod» [Эл. ресурс]. URL:
http://www.mykod.ru/
7.
Алгоритм Кнута-Морриса-Пратта // «Maximal» [Эл. ресурс]. URL:
http://e-maxx.ru/algo/prefix_function
8.
Алгоритм Бойера-Мура // «Исходники» [Эл. ресурс]. URL:
http://easylab.net.ua/poisk/algoritm-boyera-mura
Приложение
Приложение А
Реализация алгоритма последовательного поиска
//Функция
последовательного
поискаstatic
string Posl(string x, string s)
{
//Объявление строки с номерами позиций
string nom = "";
//Если искомая строка больше исходной - возврат
пустого поиска
if (x.Length
> s.Length) return nom;
//Цикл
по
исходной
строке
for (int i = 0; i < s.Length
- x.Length+1; i++)
{
bool flag = true; //Флаг
int j = 0;
while ((flag == true)
&& (j < x.Length))
{
if (x[j] != s[i + j]) flag
= false;
j++;
}
//Если искомая строка совпала с частью исходной
if (flag == true)
//Добавление номера позиции в строку номеров
nom
= nom + Convert.ToString(i) + ", ";
}
//Если вхождение найдено
if (nom != "")
{
//Удаление последней запятой и пробела
nom = nom.Substring(0, nom.Length - 2);
}
//Возвращение результата поиска
return nom;
}
Приложение Б
Реализация алгоритма Рабина-Карпа
//Хеш-функция для алгоритма Рабина-Карпа
public static int Hash(string s)
{
int rez = 0;
for (int i = 0; i <
s.Length; i++)
{
rez += (int)(s[i]);//Сложение кодов букв
}
return rez;
}
//Функция поиска алгоритмом Рабина
public static string Rabina(string
x, string s)
{
string nom = "";
//Если искомая строка больше исходной - возврат
пустого поиска
if (x.Length
> s.Length) return nom;
//Вычисление хеш-функции искомой строки
int xhash = Hash(x);
//Вычисление хеш-функции первого слова длины
образца в строке S
int shash =
Hash(s.Substring(0,x.Length));
for (int i = 0; i < s.Length
- x.Length; i++)
{
//Если значения хеш-функций совпадают
if (xhash == shash)
{
bool flag = true; //Флаг
int j = 0;
while ((flag == true)
&& (j < x.Length))
{
if (x[j] != s[i + j])
flag = false;
j++;
}
if
(flag == true)
nom = nom +
Convert.ToString(i) + ", ";
}
//Иначе вычисление нового значения после сдвига
else shash =
shash - (int) (s[i]) +
(int)(s[i + x.Length]);
}
//Если вхождение найдено
if (nom != "")
{
nom = nom.Substring(0,
nom.Length - 2);
}
return nom;
}
Приложение В
Реализация алгоритма Кнута-Морриса-Пратта
//Префикс-функция
для
КМПstatic
int[] PrefFunc(string x)
{
//Инициализация массива-результата длиной X
int[] res = new int[x.Length];
int i = 0;
int j = -1;
res[0] = -1;
//Вычисление префикс-функции
while (i < x.Length - 1)
{
while ((j >= 0) &&
(x[j] != x[i]))
j = res[j];
i++;
j++;
if (x[i] == x[j])
res[i] = res[j];
else
res[i] = j;
}
return res;//Возвращение префикс-функции
}
//Функция
поиска
алгоритмом
КМПstatic
string KMP(string x, string s)
{
//Объявление строки с номерами позиций
string nom = "";
if (x.Length
> s.Length) return nom;
//Вызов префикс-функции
int[] d = PrefFunc(x);
int i=0, j;
while (i < s.Length)
{
for (i = i, j = 0; (i <
s.Length) &&
(j < x.Length); i++, j++)
while ((j >= 0)
&& (x[j] != s[i]))
j = d[j];
if (j == x.Length)
nom = nom +
Convert.ToString(i - j) + ", ";
}
if (nom != "")
{
//Удаление последней запятой и пробела
nom =
nom.Substring(0, nom.Length - 2);
}
return nom;
}
Приложение Г
Реализация алгоритма Бойера-Мура
//Таблица символов искомой строки static char[]
SymbolOfX;
//Таблица смещений для символов static int[]
ValueShift;
//Процедура - формирование смещенийstatic void
ShiftBM(string x)
{
int j;//Счетчик
int k = 0;//Счетчик
bool fl;//Флаг
SymbolOfX = new
char[x.Length];//Инициализация
ValueShift = new
int[x.Length];//Инициализация
//Цикл по искомой строке без последнего символа
for (int i =
x.Length-2; i >= 0; i--)
{
fl = false;//Флаг
j = 0;//Обнуление
while ((j<k+1)&&(fl
== false))
{
if (SymbolOfX[j] == x[i])
fl = true;
j++;
}
if (fl == false)
{
SymbolOfX[k] = x[i];
ValueShift[k] = x.Length -
i - 1;
k++;
}
}
}
//Функция
поиска
алгоритмом
БМstatic
string BM(string x, string s)
{
bool has, have;//Флаги
int l,j,i;//Счетчики
//Вызов процедуры, формирубщей таблицу смещений
Function.ShiftBM(x);
//Объявление строки с номерами позиций
string nom = "";
if (x.Length
> s.Length) return nom;
//Основной цикл по исходной строке
for (i = 0; i < s.Length-x.Length+1;
i++)
{
j = x.Length - 1;
have = true;
//Проверка с последнего символа ((j >=
0)&&(have == true))
{
//Если не совпадает символ искомой и исходной
if
(s[i + j] != x[j])
{
have = false;
//Если это последний символ
if (j == x.Length-1)
{
l = 0;
has = false; //Флаг
//Поиск символа в таблице смещений
while
((l < x.Length)&&(has == false))
{
//Если
символ
есть
if (s[i + j] ==
SymbolOfX[l])
{
has = true; //Изменение флага
//Сдвиг на величину
i
= i + ValueShift[l] - 1;
}
l++;
}
//Если не найден символ в таблице смещений
if (has == false)
//Сдвиг на величину искомой строки
i
= i + x.Length - 1;
}
}
j--;
}
if (have == true)
nom = nom +
Convert.ToString(i) + ", ";
}
//Если строка номеров не пустая
if (nom != "")
{
//Удаление последней запятой и пробела
nom = nom.Substring(0, nom.Length - 2);
}
return nom;//Возвращение результата поиска
}
Приложение Д
Реализация программного кода программы
Код формы:
System;System.Collections.Generic;System.ComponentModel;System.Data;System.Drawing;System.Linq;System.Text;System.Windows.Forms;System.IO;Fuction;System.Diagnostics;System.Threading;
KurgachevND_Kursovaya_1kurs
{
public partial class Form1 : Form
{
public static string str,//Объявление
исходной строки
nom;//Объявление строки с результатами
поиска
public Form1()
{
InitializeComponent();
//Отключение кнопки: "Выполнить поиск"
button3.Enabled = false;
//Отключение кнопок выбора алгоритма
radioButton1.Enabled
= false;
radioButton2.Enabled = false;
radioButton3.Enabled = false;
radioButton4.Enabled = false;
label2.Text
= "";
}
//Событие - клик на кнопку «Выбрать файл поиска»
private void button1_Click(object
sender, EventArgs e)
{
//Очистка исходной строки
str = "";
//Фильтр открываемых файлов
openFileDialog1.Filter
= "Text files (*.TXT)|*.txt";
//Очистка имени открываемого файла
openFileDialog1.FileName = "";
//Если
файл
выбран
if
(openFileDialog1.ShowDialog() == DialogResult.OK)
{
FileStream TextFile = new
FileStream(openFileDialog1.FileName, FileMode.Open);
//Запись имени открываемого файла в элемент
формы
label2.Text
= openFileDialog1.SafeFileName.Substring(0, openFileDialog1.SafeFileName.Length
- 4);
//Закрытие потока данных
TextFile.Close();
using (StreamReader
sr = new StreamReader(openFileDialog1.FileName,Encoding.Default))
{
//Считывание текста в строку
str = sr.ReadToEnd();
}
//Включение кнопок выбора алгоритмов
radioButton1.Enabled = true;
radioButton2.Enabled
= true;
radioButton3.Enabled = true;
radioButton4.Enabled
= true;
}
}
//Событие - клик на кнопку «Выполнить поиск»
private void button3_Click(object
sender, EventArgs e)
{
//Если окно искомого фрагмента пустое -
сообщение об ошибке
if (textBox1.Text == "")
MessageBox.Show("Отсутствует искомый
фрагмент","Ошибка");
//Выполнение поиска искомого фрагмента
else
{
//Если выбран последовательный поиск
if (radioButton1.Checked == true)
{
Stopwatch stopWatch = new
Stopwatch();
//Старт
счетчика
тактов
stopWatch.Start();
//Вызов функции последовательного поиска
nom
= Function.Posl(textBox1.Text, str);
//Остановка счетчика тактов
stopWatch.Stop();
TimeSpan
ts = stopWatch.Elapsed;
string elapsedTime =
Convert.ToString(ts.Ticks);
//Вывод сообщения с количеством тактов
процессора
MessageBox.Show(elapsedTime,
"Количество тактов процессора");
//Если строка номеров не пустая
if (nom != "")
{
//Вывод результата поиска
MessageBox.Show("Данный фрагмент
встречается с " + nom + "-го номера", "Результат
поиска");
//Открываем файл, в котором выполнялся поиск
System.Diagnostics.Process.Start(openFileDialog1.FileName);
}
//Вывод сообщения о неудачном поиске
else MessageBox.Show("Данный
фрагмент не встречается в тексте", "Результат поиска");
}
//Если
выбран
алгоритм
Рабина-Карпа
if (radioButton2.Checked ==
true)
{
Stopwatch stopWatch = new
Stopwatch();
stopWatch.Start();
//Вызов
функции
поиска
алгоритмом
Рабина
nom =
Function.Rabina(textBox1.Text, str);
stopWatch.Stop();
TimeSpan ts =
stopWatch.Elapsed;
string elapsedTime =
Convert.ToString(ts.Ticks);
MessageBox.Show(elapsedTime,
"Количество тактов процессора");
if (nom != "")
{
MessageBox.Show("Данный фрагмент
встречается с " + nom + "-го номера", "Результат
поиска"); //Открываем файл, в котором выполнялся поиск
System.Diagnostics.Process.Start(openFileDialog1.FileName);
}
else MessageBox.Show("Данный
фрагмент не встречается в тексте", "Результат поиска");
}
//Если
выбран
алгоритм
КМП
if (radioButton3.Checked ==
true)
{
Stopwatch stopWatch = new
Stopwatch();
stopWatch.Start();
//Вызов
функции
поиска
алгоритмом
КМП
nom =
Function.KMP(textBox1.Text, str);
stopWatch.Stop();
TimeSpan ts =
stopWatch.Elapsed;
string elapsedTime =
Convert.ToString(ts.Ticks);
MessageBox.Show(elapsedTime,
"Количество тактов процессора");
if (nom != "")
{
MessageBox.Show("Данный фрагмент
встречается с " + nom + "-го номера", "Результат
поиска"); //Открываем файл, в котором выполнялся поиск
System.Diagnostics.Process.Start(openFileDialog1.FileName);
}
else MessageBox.Show("Данный
фрагмент не встречается в тексте", "Результат поиска");
}
//Если
выбран
алгоритм
БМ
if (radioButton4.Checked ==
true)
{
Stopwatch stopWatch = new
Stopwatch();
stopWatch.Start();
//Вызов
функции
алгоритмом
БМ
nom =
Convert.ToString(Function.BM(textBox1.Text,str));
stopWatch.Stop();
TimeSpan ts =
stopWatch.Elapsed;
string elapsedTime =
Convert.ToString(ts.Ticks);
MessageBox.Show(elapsedTime,"Количество
тактов процессора");
if (nom != "")
{
MessageBox.Show("Данный фрагмент
встречается с " + nom + "-го номера", "Результат
поиска"); System.Diagnostics.Process.Start(openFileDialog1.FileName);
}
else MessageBox.Show("Данный
фрагмент не встречается в тексте", "Результат поиска");
}
}
}
//Включение кнопки "Выполнить поиск",
после выбора алгоритма
private void
radioButton1_CheckedChanged(object sender, EventArgs e)
{
button3.Enabled = true;
}
//Включение кнопки "Выполнить поиск",
после выбора алгоритма
private void
radioButton3_CheckedChanged(object sender, EventArgs e)
{
button3.Enabled = true;
}
//Включение кнопки "Выполнить поиск",
после выбора алгоритма
private void
radioButton2_CheckedChanged(object sender, EventArgs e)
{
button3.Enabled = true;
}
//Включение кнопки "Выполнить поиск",
после выбора алгоритма
private void
radioButton4_CheckedChanged(object sender, EventArgs e)
{
button3.Enabled = true;
}
}
}
Код библиотеки
классов:
System;System.Collections.Generic;System.Linq;System.Text;System.Collections;
Fuction
{
public static class
Function
{
//Функция последовательного поиска
public
static string Posl(string x, string s)
{
представлена в Приложении А
}
//Вычисление хеш-функции для алгоритма Рабина
public
static int Hash(string s)
{
представлена в Приложении Б
}
//Функция поиска алгоритмом Рабина
public
static string Rabina(string x, string s)
{
представлена в Приложении Б
}
//Составление префикс-функции для КМП
public
static int[] PrefFunc(string x)
{
представлена в Приложении В
}
//Функция поиска алгоритмом КМП
public
static string KMP(string x, string s)
{
представлена в Приложении В
}
//Таблица смещений для БМ
public
static void ShiftBM(string X)
{
представлена в Приложении Г
}
//Функция поиска алгоритмом БМ
public
static string BM(string X, string S)
{
представлена в Приложении Г
}
}
}
Приложение Е
Результаты экспериментов
Символы
|
№
опыта
|
Алгоритмы
поиска
|
|
|
Простой
|
Рабина-Карпа
|
КМП
|
БМ
|
1000
|
1
|
1681
|
1391
|
1650
|
1404
|
|
2
|
1687
|
1798
|
1632
|
1410
|
|
3
|
1675
|
1693
|
1651
|
1385
|
|
4
|
1699
|
1706
|
1638
|
1391
|
|
5
|
1687
|
1749
|
1644
|
1373
|
|
6
|
1681
|
1810
|
1656
|
1428
|
|
7
|
1687
|
1699
|
1650
|
1502
|
|
8
|
1693
|
1736
|
1638
|
1416
|
|
9
|
1706
|
1816
|
1657
|
1379
|
|
10
|
1675
|
1780
|
1656
|
1453
|
10000
|
1
|
10359
|
11320
|
9583
|
4890
|
|
2
|
10236
|
11135
|
9805
|
7415
|
|
3
|
10372
|
11333
|
9497
|
4551
|
|
4
|
10347
|
10852
|
9596
|
4816
|
|
5
|
10273
|
10994
|
9676
|
6535
|
|
6
|
6319
|
6892
|
9626
|
4871
|
|
7
|
10436
|
11012
|
9805
|
5919
|
|
8
|
10335
|
9981
|
9959
|
7231
|
|
9
|
10483
|
10403
|
9639
|
4921
|
|
10
|
10372
|
11326
|
9922
|
7181
|
100000
|
1
|
100353
|
98760
|
91520
|
36893
|
|
2
|
99587
|
99606
|
92212
|
54706
|
|
3
|
100408
|
98548
|
94902
|
63040
|
|
4
|
99965
|
108937
|
91890
|
39715
|
|
5
|
101217
|
102341
|
91410
|
46206
|
|
6
|
100846
|
99763
|
91871
|
44828
|
|
7
|
100932
|
101016
|
92450
|
37078
|
|
8
|
99989
|
100542
|
93639
|
53210
|
|
9
|
101006
|
104232
|
92370
|
52822
|
|
10
|
98727
|
99262
|
92267
|
54131
|
В Таблице 2 алгоритм Кнута-Морриса-Пратта
обозначен как КМП, и алгоритм Бойера-Мура как БМ.
Курсовая работа «Поиск подстроки в строке»
выполнена мною самостоятельно, и на все источники, имеющиеся в работе, даны
соответствующие ссылки.