Разработка комплекса программ и реализация алгоритмов поиска подстроки - Курсовая работа

АТД - массив структур struct line, содержит int id - идентификатор строки, char str[255] - строка. line *arr - указатель на сам массив. Добавить строку: Вход: String^ str - строка для добавления; Пусть заданы массивы символов типа char: строка S как размером N,подстрока P размером M (см. блок 2). В этом алгоритме подстрока (образ) размером N сравнивается со строкой S размером M и если встречается несовпадение, следующее сравнение начинается с первой несовпадающей позиции в строке. Помимо основных функций АТД в программе присутствуют функции обработки нажатий на кнопки: private:System::Void Form1_Load (System::Object^sender, System::EVENTARGS^ e) - функция открытия формы. private: System::Void button1_Click(System::Object^ sender, System::EVENTARGS^ e) - функция поиска. private: System::Void button2_Click(System::Object^ sender, System::EVENTARGS^ e) - функция загрузки из файла массива структур. private: System::Void button3_Click(System::Object^ sender, System::EVENTARGS^ e) - функция удаления массива структур и закрытия формы. private:System::Void button4_Click(System::Object^ sender, System::EVENTARGS^ e) - функция добавления строки в массив структур. private:System::Void button5_Click(System::Object^ sender, System::EVENTARGS^ e) - функция удаления строки из массива структур. private:System::Void ОЧИСТИТЬМАССИВСТРУКТУРTOOLSTRIPMENUITEM_Click(System::Object^ sender, System::EVENTARGS^ e) - функция очищения всех полей и удаления массива структур. private:System::Void ОТКРЫТЬTOOLSTRIPMENUITEM_Click(System::Object^ sender, System::EVENTARGS^ e) - функция выбора файла для чтения.В результате написания курсового проекта мною были разработаны и реализованы: алгоритмы поиска подстроки в тексте, АТД - массив структур, программа тестирования трудоемкости для алгоритма прямого поиска. После чего, были приведены график эффективности алгоритмов поиска и график зависимости трудоемкости прямого поиска от размера текста. Комплекс программ разработан на языке программирования С в среде Visual Studio.

Оглавление

Введение

Постановка задачи

Описание структуры данных

Разработка детальных алгоритмов решения

Разработка структуры программы

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

Экспериментальная часть

Заключение

Список литературы

Приложение А. Графическая часть

Приложение Б. Исходный код программы

В процессе выполнения курсового проекта должен быть реализован комплекс программ поиска подстроки в тексте алгоритмом прямого поиска и алгоритмом Кнута-Морриса-Пратта. Должен быть разработан АТД или с представлением описания. Должна быть разработана программа тестирования трудоемкости операций. Эффективность работы алгоритмов должна быть представлена на графиках. Должен быть выполнен сравнительный анализ теоретических и экспериментальных оценок эффективности алгоритмов. Работа алгоритмов должна быть представлена скриншотами интерфейса программы. ПО должно быть разработано на языке программирования С .

Постановка задачи

Быстрый поиск точно заданной подстроки в строке является одной из самых простейших задач поиска информации. Однако эта задача является чрезвычайно важной. Данная функция встроена в различные текстовые редакторы и базы данных, что существенно ускоряет процесс поиска информации и редактирование (замену) фрагментов.

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

Описание структуры данных.

АТД - массив структур struct line, содержит int id - идентификатор строки, char str[255] - строка. line *arr - указатель на сам массив. Массив сразу создается с размером n = 0. Размер n изменяется при последующем добавлении элементов. АТД - список имеет компонентные функции: загрузка данных из файла, добавление элемента, удаление элемента. Вызов функций АТД реализован в пользовательском интерфейсе программы. Исходный код АТД см. приложение 1.

Данные: Параметры: int id - идентификатор элемента массива структур;

char str[255] - строка.

Структура данных: Массив структур размером n.

Операции: Загрузка из файла: Вход: имя файла с входными данными wchar_t file[255];

Процесс: формирование массива из файла;

Выход: новый размер списка n;

Добавить строку: Вход: String^ str - строка для добавления;

Процесс: включение полученной строки в массив, выполняется функцией Addline();

Выход: новый размер массива n 1;

Удалить строку: Вход: int number - идентификатор удаляемой строки;

Процесс: поиск идентификатора строки и присваивание ему значения -10;

Выход: новый размер size-1;

Удаление массива структур: Процесс: удаление массива структур;

Конец АТД.

Разработка детальных алгоритмов решения

Алгоритм прямого поиска подстроки.

Пусть заданы массивы символов типа char: строка S как размером N,подстрока P размером M (см. блок 2). Поиск завершается после поиска подстроки P во всех строках S , это позволяет получить результат о всех найденных вхождениях P в S. Поиск считается удачным, если количество совпавших символов будет равно длине подстроки (см. блоки 7-9). Алгоритм содержит условие, предотвращающее выход за пределы строки (см. блок 10). Проход по каждому символу строки осуществляется счетчиками (см. блок 4, блок 6).

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

В этом алгоритме подстрока (образ) размером N сравнивается со строкой S размером M и если встречается несовпадение, следующее сравнение начинается с первой несовпадающей позиции в строке. Если совпадения вообще нет, то сравнение начинается со следующей позиции в строке.

Для работы алгоритма вводится дополнительный массив для вычисления сдвига на очередном шаге - D. Этот массив может быть получен на основе анализа образа Р и зависит только от содержимого подстроки. До начала самого поиска подстроки в строке можно вычислить значения сдвигов, которые используются в дальнейшем поиске. Причем в массив D помещается значение = -1, если производится сдвиг на целый образ. Чем меньше значение D, тем на большее число позиций производится сдвиг по строке. Сдвиг для ячейки j вычисляется как j-d[j]. Основным отличием КМП-алгоритма от алгоритма прямого поиска является осуществления сдвига слова не на один символ на каждом шаге алгоритма, а на некоторое переменное количество символов. Таким образом, перед тем как осуществлять очередной сдвиг, необходимо определить величину сдвига. Для повышения эффективности алгоритма необходимо, чтобы сдвиг на каждом шаге был бы как можно большим.

Блок схемы алгоритмов представлены см. приложение А.

Разработка структуры программы алгоритм поиск подстрока

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

Разработанная программа состоит из 4 основных функций: void SHOWSTRUCT() - функция вывода массива на экран;

int LINEFIND(array^ fstr,int m) - функция прямого поиска подстроки. Вход: искомая подстрока, размер искомой строки.

Выход: Возвращает 1 если поиск успешен, 0 - если не успешен. int algorithm_KMP(array^ fstr,int l) - функция поиска алгоритма Бойера-Мура. Вход: искомая подстрока, адрес строки в массиве строк. Выход: возвращает адрес строки. int Addline() - функция добавления строки в массив структур. Выход: возвращает 1 - если добавление успешно, 0 - если добавление неудачно.

Помимо основных функций АТД в программе присутствуют функции обработки нажатий на кнопки: private:System::Void Form1_Load (System::Object^sender, System::EVENTARGS^ e) - функция открытия формы. private: System::Void button1_Click(System::Object^ sender, System::EVENTARGS^ e) - функция поиска. private: System::Void button2_Click(System::Object^ sender, System::EVENTARGS^ e) - функция загрузки из файла массива структур. private: System::Void button3_Click(System::Object^ sender, System::EVENTARGS^ e) - функция удаления массива структур и закрытия формы. private:System::Void button4_Click(System::Object^ sender, System::EVENTARGS^ e) - функция добавления строки в массив структур. private:System::Void button5_Click(System::Object^ sender, System::EVENTARGS^ e) - функция удаления строки из массива структур. private:System::Void ОЧИСТИТЬМАССИВСТРУКТУРTOOLSTRIPMENUITEM_Click(System::Object^ sender, System::EVENTARGS^ e) - функция очищения всех полей и удаления массива структур. private:System::Void ОТКРЫТЬTOOLSTRIPMENUITEM_Click(System::Object^ sender, System::EVENTARGS^ e) - функция выбора файла для чтения.

Структурная схема программы представлена в приложении А. Исходный код см. приложение Б.

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

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

Работа алгоритмов представлена скриншотами.

Для заполнения списка строками можно воспользоваться возможностью загрузки текста из файла: для начала нужно выбрать файл (Файл - открыть) см. Рис1.

Рис1. Пример выбора файла

Рис2. Добавление строки

Затем заполнить массив структур с помощью кнопки «Заполнить массив». Присутствует возможность ввести строки вручную используя кнопку «Добавить строку». Кнопка добавления также предоставляет пользователю возможность добавить строку к загруженному из файла тексту, см. Рис2.

Кнопка «Удалить строку» реализует возможность удаления строки из текста, см. Рис3.

Рис3. Удаление строки

Рис4. Поиск и вывод результатов работы.

Рис5.Поиск и вывод результатов работы

Экспериментальная часть

Исследование эффективности алгоритмов

Тестирование программы проводилось на входных данных различного размера. В качестве входной информации были использованы текстовые файлы содержащие английский текст. Зависимость времени поиска от размера для каждого алгоритма представлено в Таблице 1 и Рис 6.

Время

Количество символов Прямой поиск Алгоритм КМП

2033 0.01393 0.01272

4560 0.039 0.02970

6593 0.04723 0,03294

13186 0,097 0,1

Таблица1.

Рис 6. График зависимости времени от колва символов.

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

Исследование трудоемкости.

Для алгоритма прямого поиска была подсчитана трудоемкость операций, под которой подразумевается количество элементарных операций необходимое для решения определенной задачи. График зависимости трудоемкости от размерности см. Рис 7.

Рис 7. Зависимость трудоемкости от размера.

График Рис 7 показывает, что чем больше количество символов в списке строк, тем больше потребуется произвести операций для получения результата. В коде программы за количество элементарных операций отвечает счетчик kol.

В результате написания курсового проекта мною были разработаны и реализованы: алгоритмы поиска подстроки в тексте, АТД - массив структур, программа тестирования трудоемкости для алгоритма прямого поиска. После чего, были приведены график эффективности алгоритмов поиска и график зависимости трудоемкости прямого поиска от размера текста. Также пояснительная записка содержит описание АТД - список и структуры программы. Работоспособность программы показана на рисунках. Комплекс программ разработан на языке программирования С в среде Visual Studio.

В разработанной программе реализованы следующие возможности: Формирование массива строк из файла;

Добавление строки в массив;

Удаление строки из массива;

Очистка массива;

Прямой поиск;

Поиск алгоритмом Кнута-Морриса-Пратта;

Вывод результатов работы программы в отдельное поле.

1. Д. Макконнел. Основы современных алгоритмов. М.: Техносфера, 2010. 368 с.

2. Н. Вирт. Алгоритмы и структуры данных. М.: Невский Диалект, 2009. 352 с.

3. Р. Седжвик. Фундаментальные алгоритмы C . Части 1-4. М.: Диасофт,