Поиск подстроки в строке
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
делает операцию и в худшем операций. Таким образом, в лучшем случае алгоритм производит сравнений, но в худшем случае это сравнений. Причем, большинство этих сравнений явно лишние. Например, при поиске подстроки aabbc, обнаружено несоответствие в пятом символе (совпало только первые четыре), алгоритм продолжит сравнение со следующего символа исходной строки, что явно не приведет к результату. На небольших входных данных этот алгоритм проработает быстро, но если в большом многомегабайтном файле будет искаться последовательность объемом в несколько килобайт, то ждать придется довольно долго.
.2.2 Алгоритм Рабина-Карпа
Алгоритм Рабина-Карпа представляет собой модифицированную версию алгоритма последовательного поиска. Его отличительной чертой является применение хеширования - преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины [5].
Пусть - строка, в которой выполняется поиск, а - искомое слово. И и . Представим окошечко длины , которое двигается последовательно по строке , начиная с первого символа. Будем вычислять хеш-функцию для каждого слова длины . Тогда задача сводится к сравнению чисел, что, несомненно, быстрее. И если значение хеш-функции слова из окошечка не совпадает со значением хеш-функции искомого образца, то однозначно эти две строки не совпадают, в противном случае выполним посимвольное сравнение.
Этот алгоритм выполняет линейный проход по искомому фрагменту ( шагов) и линейный проход по всему тексту ( шагов), стало быть, общее время работы есть . Здесь не учитывается время на вычисление хеш-функции. Потому что сама идея алгоритма построена на условии, что хеш-функция будет легко вычисляться, и время этого вычисления не будет влиять на работу алгоритма. Примером такой легко вычисляемой хеш-функции может быть функция, которая считает сумму кодов символов слова в окошечке. Таким образом, при сдвиге окошечка на один элемент вправо не нужно заново считать всю сумму. Достаточно просто вычесть код первого символа до сдвига и добавить код нового символа, попавшего в диапазон. Совпадение подсчитанного значения суммы со значением хеш-функции искомого слова при их посимвольном несоответствии не слишком вероятно, однако, в худшем случае время работы будет . Широкое распространение алгоритм Рабина не получил, однако, он часто используется в программах поиска плагиата [2].
.3 Эффективные алгоритмы поиска подстроки в строке
Алгоритм последовательного поиска и алгоритм Рабина-Карпа являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее эффективными и оптимальными. Как говорилось раньше, они зачастую выполняют ненужную работу. Поэтому будет рассматриваться следующий класс алгоритмов, которые появились в результате тщательного исследования алгоритма последовательного поиска. Исследователи хотели найти способы более полно и полезно использовать информацию, полученную во время сканирования. В отличие от простейших алгоритмов, которые данную информацию не используют вовсе.
Однако эти алгоритмы используют чуть больше трудозатрат и имеют время предварительной обработки. Но операций сравнения становится в разы меньше, и мы можем говорить о линейной зависимости этих алгоритмов от величины строки . [5]
.3.1 Алгоритм Кнута-Морриса-Пратта
Данный алгоритм был предложен в 1977 году учеными Кнутом, Праттом и независимо от них Моррисом. Предложенный ими метод выполняет предварительную обработку искомой строки. На её основе создается префикс-функция, которая инкапсулирует сведения о том, в какой мере образец совпадает сам с собой после сдвигов. Т.е. префиксной функцией заданного образца называется функция , такая что
. (1)
Другими словами, равно длине наибольшего префикса образца , который является истинным суффиксом строки . В качестве примера приведем полную префиксную функцию для образца ababababca, продемонстрированную на рис. 1.
Рис.1. Иллюстрация для образца P = ababababca и q = 8.
Смысл префикс-функции в том, что можно отбросить заведомо неверные варианты, т.е. если при поиске совпала подстрока abcasdqtabc (следующий символ не совпал), то имеет смысл продолжать проверку уже с четвертого символа (первые три и так совпадут). Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной больше одного символа, то он одновременно и префикс подстроки длинной . Таким образом, проверяется префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находится наибольший искомый префикс [4, 5, 7].
Время работы данной префикс-функции линейно. Т.к. присвоение префикс-функции происходит раз, следовательно, работа этой функции . Время работы самого алгоритма также линейно и равно .
1.3.2 Алгоритм Бойера-Мура
Алгоритм Бойера-Мура, разработанный двумя учеными - Бойером и Муром в 1977 году, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Преимущество этого алгоритма в том, что при помощи некоторой предобработки искомой строки, образец сравнивается с исходным текстом не во всех позициях - часть проверок пропускаются как заведомо не дающие результата.
Оригинальный вариант алго