Файл: Реализация алгоритмов поиска по тексту.docx

Федеральное агентство морского и речного транспорта

Воронежский филиал

Федерального государственного бюджетного образовательного

учреждения высшего образования

«Государственный университет морского и речного флота

имени адмирала С.О. Макарова»

Отчёт о выполнении лабораторной работы №1
По дисциплине: «Теория обработки информации»

На тему: «Реализация алгоритмов поиска по тексту»

Выполнил:	Давлетшин Б.А.
	(Фамилия, Имя, Отчество)
Принял:	Скрипников О. А.
	(Фамилия, Имя, Отчество)

ВОРОНЕЖ 2022 г.

Задание

Научиться реализовывать на выбранном языке программирования алгоритмы поиска по тексту: прямой поиск, алгоритм Кнута, Морриса, Пратта; алгоритм Бойера-Мура.

Выполнение

Прямой поиск

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

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

Поэтому в худшем случае алгоритм будет малоэффективен

---

, так как его сложность будет пропорциональна О((n-m+1) *m), где n и m – длины строки и подстроки соответственно.

Для начала выполнения работы необходимо выбрать язык программирования. Выбран был язык программирования c# в интерфейсе Visual Studio.

Для реализации меню был выбран метод switch (см. рис. 1):



Рисунок 1 – switch конструкция

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



Рисунок 2 – Условия отбора

Чтобы вычислить количество тиков на выполнение поиска по тексу, использован тип Stopwatch.

Для использования StreamReader/Writer была добавлена библиотека IO.

Поиск реализован через посимвольное сопоставление с подстрокой, с использованием циклов for и условий if (см.рис.3).

Листинг

using System;

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics;

using System.Text;

using System.IO;

using System.Threading.Tasks;

using AlghoritmsSearch;
static void Main(string[] args)

{

string text;

Console.WriteLine("Введите текст для поиска");

text = Console.ReadLine();

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

Console.WriteLine("Введите подстроку");

string user = Convert.ToString(Console.ReadLine());

if (text.Length
{

Console.WriteLine("Ошибка! Введите данные заного!");

Console.WriteLine("Введите текст для поиска");

text = Console.ReadLine();

Console.WriteLine("Введите подстроку");

user = Convert.ToString(Console.ReadLine());

}

string s = text;

bool ok = false;

int a = 0;

int b = 0;

string k = "";

for (int i = 0; i < s.Length; i++)

{

if (s[i] == user[0])

{

a = 0;

k = "";

int h = i;

for (int j = 0; j < user.Length; j++)

{

if (user[j] == s[h])

{

a++;

k = k + Convert.ToString(s[h]);

if (k == user)

{

b = a;

ok = true;

}

}

else

{

break;

}

h++;

}

}

}

if (ok == true)

{

stopwatch.Stop();

int g = Convert.ToInt32(stopwatch.ElapsedTicks);

Console.WriteLine(g + " Тиков ушло на поиск", "Количество времени");

Console.WriteLine("Первое вхождение: " + (b + 1));

}

}

Алгоритм Кнутта, Марисса, Пратта

Основным отличием алгоритма является в том, что сдвиг подстроки выполняется не на один символ на каждом шаге, а на некоторое переменное количество символов.

Решение

Было создано консольное приложение, при запуске которого появляется надпись: «Вставьте файл и нажмите Enter», это подразумевает напрямую перетаскивание файла в консоль, тем самым указывается путь до данного файла, либо можно просто напрямую письменно задать путь к этому же файлу (см. рис. 4):

---

Рисунок 4 – Выбор файла

Затем выводится надпись: «Напишите искомую строку», как следует из написанного, необходимо написать искомую строку (см. рис. 5):



Рисунок 5 – Искомая строка

После проделанных операций нужно нажать кнопку «Enter» на клавиатуре и сработает написанный алгоритм, который выведет первое вхождение с соответствующим подписанием, а также количество тиков отсчитанных сначала работы алгоритма (см. рис. 6):




Рисунок 6 – Результат поиска

Листинг

using System;

using System.Collections.Generic;

using System.Linq;

using System.Diagnostics;

using System.Text;

using System.IO;

using System.Threading.Tasks;

using AlghoritmsSearch;

static void Main(string[] args)

{

string text;

int x=1;

Console.Clear();

Console.WriteLine("Введите текст для поиска");

text = Console.ReadLine();

Consle.WriteLine("Введите подстроку");

string user = Convert.ToString(Console.ReadLine());

if (text.Length
{

Console.WriteLine("Ошибка! Введите данные заного!");

Console.WriteLine("Введите текст для поиска");

text = Console.ReadLine();

Console.WriteLine("Введите подстроку");

user = Convert.ToString(Console.ReadLine());

}

Stopwatch stopwatch = new Stopwatch();

stopwatch.Start();

string s = text;

bool ok = false;

int a = 0;

int b = 0;

string k = "";

for (int i = 0; i < s.Length; i++)

{

if (s[i] == user[0])

{

a = 0;

k = "";

int h = i;

for (int j = 0; j < user.Length; j++)

{

if (user[j] == s[h])

{

a++;

k = k + Convert.ToString(s[h]);

if (k == user)

{

b = a;

ok = true;

}

}

else

{

break;

}

h++;

}

}

}

if (ok == true)

{

stopwatch.Stop();

int g = Convert.ToInt32(stopwatch.ElapsedTicks);

Console.WriteLine(g + " Тиков ушло на поиск", "Количество времени");

Console.WriteLine("Первое вхождение: " + (b + 1));

g = 0;

}

---