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

Этот алгоритм выполняет линейный проход по строке (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). Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит

Доказать что эта программа работает за линейное время, можно точно так же, как и для префикс - функции. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

Страницы: 1, 2, 3, 4