Практическая реализация кода

Оглавление

Введение        3

Глава 1. Теоретический обзор алгоритмов и структур данных.        4

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

1.2. Алгоритм Боуера-Мура        4

1.3. Алгоритм Боуера-Мура-Хорспула        6

1.5. Нечеткий поиск в строке        7

1.6. Классификация алгоритмов поиска подстроки в строке        8

Глава 2. Практическая реализация кода.        10

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

2.2. Описание методов, используемых в программе.        11

2.3. Пример использования алгоритма нечеткого поиска в строке.        13

2.4. Пример использования алгоритма Кнута-Морриса-Пратта.        14

2.5. Пример использования алгоритма Боуера-Мура.        14

Заключение        15

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

Приложение        17

Введение

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

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

Для решения поставленной задачи разработано консольное приложение, используя средства разработки языковой среды Си++, имеющее понятный русифицированный интерфейс.

Глава 1. Теоретический обзор алгоритмов и структур данных.

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

Алгоритм Кнута-Морриса-Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки(образа) в строке.

Работа алгоритма делится на 2 основных этапа:

1. Создание префикс-функции для образа.

Префикс-функция для i-го символа образа возвращает значение, равное максимальной длине совпадающих префикса(символы в начале) и суффикса(символы в конце) подстроки в образе, которая заканчивается i-м символом. Это значение удобно хранить в массиве π (табл.1).

                        Табл.1.Пример создания массива π.

1. Поиск образа в строке.

Далее посимвольно сравниваются символы в строке и образе. Как только зафиксируется несовпадение, то идет обращение к массиву π. Указатель на символы в образе становиться равным значению π[указатель-1].  Это место — ключ к эффективности КМП. Если очередные символы строки и образца не совпали, мы не двигаем образец на 1 символ и не сравниваем его со строкой с самого начала (как в примитивном поиске). Мы сдвигаем образец на несколько символов и делаем одно сравнение str[i] и obr[j]. Если не совпало — опять сдвиг образца, пока символы не совпадут или не дойдем до начала образца.

Говоря о временной сложности алгоритма КМП, можно сказать, что его временная сложность будет равна O(n+m), где n-длина образа, m-длина строки.

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

Алгоритм Бойера-Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над образом (но не над строкой, в которой ведётся поиск) образ сравнивается с исходным текстом не во всех позициях, т.к. часть проверок пропускаются как заведомо не дающие результата.