Курсовая работа: Алгоритмы поиска подстроки в строке
NextHash(s,i,NowH,LenX); {Вычисление следующего значения хеш-функции}
End;
Search:=Res
End;
Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма. Тогда, время работы алгоритма линейно зависит от размера строки и текста, стало быть программа работает быстро. Ведь вместо того, чтобы проверять каждую позицию на предмет соответствия с образцом, мы можем проверять только те, которые «напоминают» образец. Итак, для того, чтобы легко устанавливать явное несоответствие, будем использовать функцию, которая должна:
1. Легко вычисляться.
2. Как можно лучше различать несовпадающие строки.
3. hash( y[ i+1 , i+m ] ) должна легко вычисляться по hash( y[ i , i+m-1 ].
Во время поиска х будем сравнивать hash( x ) с hash( y[ i, i+m-1 ] ) для i от 0 до n-m включительно. Если обнаруживаем совпадение, то проверяем посимвольно.
Пример (удобной для вычисления функции) [13 ,172]. Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге "окошечка" нужно добавить новое число и вычесть "пропавшее".)
Однако, проблема в том, что искомая строка может быть длинной, строк в тексте тоже хватает. А так как каждой строке нужно сопоставить уникальное число, то и чисел должно быть много, а стало быть, числа будут большими (порядка D*n, где D - количество различных символов), и работать с ними будет так же неудобно. Но какой интерес работать только с короткими строками и цифрами? Разработчики алгоритма придумали, как улучшить этот алгоритм без особых потерь в скорости работы.
Пример (семейства удобных функций) [13, 172-173]. Выберем некоторое число p (желательно простое) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы их кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается своя функция). Сдвиг "окошечка" на 1 соответствует вычитанию старшего члена, умножению на x и добавлению свободного члена. Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же оно является простым, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны - это возможно при p, большем числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, т.е. их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если n много меньше p, то случайному значению x мало шансов попасть в "неудачную" точку.
Строго говоря, время работы всего алгоритма в целом, есть O(m+n+mn/P), mn/P достаточно невелико, так что сложность работы почти линейная. Понятно, что простое число следует выбирать большим, чем больше это число, тем быстрее будет работать программа.
Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными (хотя бы потому, что иногда выполняют явно бесполезную работу, о чем было сказано выше), поэтому мы перейдём к следующему классу алгоритмов. Эти алгоритмы появились в результате тщательного исследования алгоритма последовательного поиска. Исследователи хотели найти способы более полно использовать информацию, полученную во время сканирования (алгоритм прямого поиска ее просто выбрасывает). Рассмотрим алгоритм Кнута – Морриса – Пратта.
1.3. Алгоритм Кнута - Морриса - Пратта(КМП).
Вначале рассмотрим некоторые вспомогательные утверждения. Для произвольного слова X рассмотрим все его начала, одновременно являющиеся его концами, и выберем из них самое длинное (не считая, конечно, самого слова X). Обозначим его n(X). Такая функция носит название префикс – функции [13].
Примеры .
n(aba)=a, n(n(aba))=n(a)=L;
n(abab)=ab, n(n(abab))=n(ab)=L;
n(ababa)=aba, n(n(ababa))=n(aba)=a, n(n(n(ababa)))=n(a)=L; n(abc)=L.
Докажем несколько используемых впоследствии фактов, а именно предложение (по [Шень,1995,с.165-166]):
(1) Последовательность слов n(X),n(n(X)),n(n(n(X))),... "обрывается" (на пустом слове L).
(2) Все слова n(X),n(n(X)),n(n(n(X))),...,L являются началами слова X.
(3) Любое слово, одновременно являющееся началом и концом слова X (кроме самого X), входит в последовательность n(X),n(n(X)),....,L.
Доказательство .
(1) Тривиально, т.к. каждое слово короче предыдущего.
(2) Каждое из них (по определению) является началом предыдущего. По той же причине все они являются концами слова X.
(3) Пусть слово Y является одновременно началом и концом X. Слово n(X) - самое длинное из таких слов, так что Y не длиннее n(X). Оба эти слова являются началами X, поэтому более короткое из них является началом более длинного: Y есть начало n(X). Аналогично, Y есть конец n(X). Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче X, в частности, для слова n(X). Так что слово Y, являющееся концом и началом n(X), либо равно n(X), либо входит в последовательность n(n(X)),n(n(n(X))),...,,L.
Предложение доказано.
Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1 (Листинг 3). Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит
|