Цель курсовой работы: Изучить и проанализировать алгоритмы поиска подстроки в строке, и рассмотреть ряд практических задач на данную тематику.

Задачи курсовой работы: изучить задачи связанные с проблемой поиска подстроки в строке, дать основные определения; рассмотреть применение различных алгоритмов поиска подстроки в строке на практике; написать программный код, реализующий один из алгоритмов поиска подстроки в строке.

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

Конечно, сейчас функции поиска инкапсулированы во многие языки программирования высокого уровня, поэтому чтобы найти строчку в небольшом тексте используется встроенная функция. Но если такого рода поиск является ключевой задачей программы, знать принципы организации функций поиска будет полезным. В готовых подпрограммах далеко не всегда все написано лучшим образом. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что понадобится изменить стандартное поведение этих функций (например, предусмотреть возможность поиска по шаблону). Наконец, область применения функции поиска не ограничивается одними лишь текстовыми редакторами. Следует отметить использование алгоритмов поиска при индексации страниц поисковым роботом, где актуальность информации напрямую зависит от скорости нахождения ключевых слов в тексте html. Работа простейшего спам–фильтра, заключается в нахождении в тексте письма фраз таких, как «Миллион за час» или «Раскрутка сайта». Это всё говорит об актуальности проблемы поиска.

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

Глава 1. Теоретические сведения об алгоритмах поиска подстроки в строке

1.1. Основные понятия

Возможно вы искали - Курсовая работа: Алгоритмы сжатия данных

Определение. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.

Определение . Длина строки – количество знаков в строке.

Слова обозначаются буквами латинского алфавита, напр. X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)==n – обозначение длины строки.

Определение . Слово не содержащее ни одной буквы называется пустым.

Пустое слово обычно обозначается буквой L. Length(L)=0.

Похожий материал - Курсовая работа: Алгоритмы сжатия данных

Определение . Слово X называется префиксом слова Y, если есть такое слово Z, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.

Пример: слово ab является префиксом слова abcfa.

Определение . Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.

Пример: слово bfg является суффиксом слова vsenfbfg.

Определение . Слово X называется подстрокой строки Y, если найдутся такие строки Z₁ и Z₂ , что Y=Z₁ XZ₂ . При этом Z₁ называется левым, а Z₂ - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение XY.

Очень интересно - Курсовая работа: Алгоритмы сортировки, поиска длиннейшего пути во взвешенном графе и поиска покрытия, близкого к кратчайшему

Пример: слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfro.

В программировании понятие сложности алгоритма связано с использованием ресурсов компьютера: насколько много процессорного

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

Существует две характеристики сложности алгоритмов - временная и емкостная.

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

Вам будет интересно - Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

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

1.2. Алгоритм последовательного (прямого) поиска

Самый очевидный алгоритм. Обозначеное S - слово, в котором ищется образец X. Пусть m и n - длины слов S и X соответственно. Можно сравнить со словом X все подслова S, которые начинаются с позиций 1,2,...,m-n+1 в слове S; в случае равенства выводится соответствующая позиция. Реализация этого алгоритма представлена в приложении 1.

Это не эффективный алгоритм т.к. максимальное, количество сравнений будет равно O((m-n+1)*n+1), хотя большинство из них на самом деле лишние. Оценим скорость работы этого программного кода. В ней присутствуют два цикла (один вложенный), время работы внешнего большей степенью зависит от n, а внутренний в худшем случае делает m операций. Таким образом, время работы всего алгоритма есть O((n-m+1)m). Для маленьких строк поиск проработает быстро, но если в каком-то многомегабайтном файле будет искаться последовательность длинной 100 Кб, то придется ждать ну очень долго. Впрочем многим хватает и этого. Например, найдя строку aabc и обнаружив несоответствие в четвертом символе (совпало только aab), алгоритм будет продолжать сравнивать строку, начиная со следующего символа, хотя это однозначно не приведет к результату.

1.3. А лгоритм Рабина

Алгоритм Рабина представляет собой модификацию линейного алгоритма.

В слове A, длина которого равна m, ищется образец X длины n. Вырежем "окошечко" размером n оно двигается по входному слову. Совпадает ли слово в "окошечке" с заданным образцом? Фиксируется некоторая числовая функция на словах длины n, тогда задача сводится к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.

Похожий материал - Контрольная работа: Алгоритмы численного решения задач

Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом не учитывается временная сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, можно проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будет использоваться функция, которая должна:

1. Легко вычисляться.

2. Как можно лучше различать несовпадающие строки.

3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ].