Алгоритм Кнута-Морриса-Пратта
Алгоритм Кнута - Морриса - Пратта
Алгоритм
Кнута-Морриса-Пратта (КМП) получает на вход слово
X=x[1]x[2]... x[n]
и
просматривает его слева направо буква за буквой, заполняя при этом массив
натуральных чисел l[1]... l[n], где
l[i]=длина слова l(x[1]...х[i])
(функция
l определена в предыдущем пункте). Словами: l[i] есть длина наибольшего начала
слова x[1]...x[i], одновременно являющегося его концом.
Какое отношение все это имеет к поиску подслова?
Другими
словами, как использовать алгоритм КМП для определения того, является ли слово
A подсловом слова B?
Решение. Применим
алгоритм КМП к слову A#B, где # - специальная буква, не встречающаяся ни в A,
ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди
чисел в массиве l будет число, равное длине слова A.
Описать алгоритм заполнения таблицы l[1]...l[n].
Решение. Предположим,
что первые i значений l[1]...l[i] уже найдены. Мы читаем очередную букву слова
(т.е. x[i+1]) и должны вычислить l[i+1].
Другими
словами, нас интересуют начала Z слова
x[1]...x[i+1,
одновременно
являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти
начала? Каждое из них (не считая пустого) получается из некоторого слова Z'
приписыванием буквы x[i+1] . Слово Z' является началом и
концом
слова x[1]...x[i]. Однако не любое слово, являющееся началом и концом слова
x[1]...x[i], годится - надо, чтобы за ним следовала буква x[i+1].
Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова
x[1]...x[i], являющиеся одновременно его концами. Из них выберем подходящие -
те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное.
Приписав в его конец х[i+1], получим искомое слово Z. Теперь пора
воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся
одновременно началами и концами данного слова, можно получить повторными
применениями к нему функции l из предыдущего раздела.
Вот что получается:
i:=1; 1[1]:=0;
{таблица l[1]..l[i] заполнена правильно}
while i <> n do begin
len:= l[i]
{len - длина начала слова x[1]..x[i],
которое является
его концом; все более длинные начала
оказались
неподходящими}
while (x[len+1]<>х[i+1]) and
(len>0) do begin
{начало не подходит, применяем к нему
функцию l}
len:=l[len];
end;
{нашли подходящее или убедились в
отсутствии}
if x[len+1]=x[i+1] do begin
{х[1]..x[len] - самое длинное подходящее
начало}
l[i+1]:=len+1;
end else begin
{подходящих нет}
l[i+1]:= 0;
end;
i:=i+1;
end;
Доказать, что число действий в приведенном только что алгоритме не
превосходит Cn для некоторой константы C.
Решение. Это не вполне
очевидно: обработка каждой очередной буквы может потребовать многих итераций во
внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней мере на
1, и в этом случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при
увеличении i на единицу величина l[i] может возрасти не более чем на 1, так что
часто и сильно убывать она не может - иначе убывание не будет скомпенсировано
возрастанием.
Более точно, можно записать неравенство
l[i+1]<l [i] - (число итераций на i-м шаге)+1
или
(число итераций на i-м шаге)<= l[i]-l[i+1]+1
Остается
сложить эти неравенства по всем i и получить оценку
сверху
для общего числа итераций.
Будем использовать этот алгоритм, чтобы выяснить, является ли слово X
длины n подсловом слова Y длины m. (Как это делать с помощью специального
разделителя #, описано выше.) При этом число действий будет не более C(n+m}, и
используемая память тоже. Придумать, как обойтись памятью не более Cn (что
может быть существенно меньше, если искомый образец короткий, а слово, в
котором его ищут - длинное).
Решение. Применяем
алгоритм КМП к слову А#В. При этом: вычисление значений l[1],...,l [n] проводим
для слова X длины n и запоминаем эти значения. Дальше мы помним только значение
l[i] для текущего i - кроме него и кроме таблицы
l[1]...l[n],
нам для вычислений ничего не нужно.
На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и
затем слова Y удобно оформить в виде разных циклов. Это избавляет также от
хлопот с разделителем.
Написать соответствующий алгоритм (проверяющий, является ли слово
X=x[1]...x[n] подсловом слова Y=y[1]...y[m]
Решение. Сначала
вычисляем таблицу l[1]...l[n]как раньше. Затем пишем такую программу:
j:=0; len:=0;
{len - длина максимального качала слова
X, одновременно
являющегося концом слова
y[1]..j[j]}
while (len<>n) and (j<>m) do
begin
while (x[len+1]<>у[j+1]) and
(len>0) do begin
{начало не подходит, применяем к нему
функцию l}
len: = l[len];
end;
{нашли подходящее или убедились в
отсутствии}
if x[len+1]=y[j+1] do begin
{x[1]..x[len] - самое длинное подходящее
начало}
len:=len+1;
end else begin
{подходящих нет}
len:=0;
end;
j:=j+1;
{если len=n, слово X встретилось; иначе
мы дошли до конца
слова Y, так и не встретив X}
Алгоритм Бойера - Мура
Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной
ситуации он читает лишь небольшую часть всех букв слова, в котором ищется
заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем
образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e,
то нет никакой необходимости читать первые три буквы. (В самом деле, в образце
буквы e нет, поэтому он может начаться не раньше пятой буквы.)
Мы приведем самый простой вариант этого алгоритма, который не гарантирует
быстрой работы во всех случаях. Пусть x[1]...х[n] - образец, который надо
искать. Для каждого символа s найдем самое правое его вхождение в слово X, то
есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве
pos[s]; если символ s вовсе не встречается, то нам будет удобно положить
pos[s]=0 (мы увидим дальше, почему).
Как заполнить массив pos?
Решение.
положить
все pos[s] равными 0
for i:=1 to n do begin
pos[x[i]]:=i;
end;
В
процессе поиска мы будем хранить в переменной last номер буквы в слове, против
которой стоит последняя буква образца. Вначале last=n (длина образца), затем
last постепенно увеличивается.
last:=n;
{все предыдущие положения образца уже
проверены}
while last<= m do
begin {слово не кончилось}
if
x[m]<>y[last] then begin {последние буквы разные}
last:=last+(n-pos[y[last]]);
{n - pos[y[last]] - это
минимальный сдвиг образца,
при котором напротив
y[last] встанет такая же
буква в образце. Если
такой буквы нет вообще,
то сдвигаем на всю длину
образца}
end else begin
если нынешнее положение подходит, т.е.
если
x[i]..х[n]=y[last-n+1]..y[last],
то сообщить о совпадении;
last:=last+1;
end;
end;
Знатоки
рекомендуют проверку совпадения проводить справа налево, т.е. начиная с
последней буквы образца (в которой совпадение заведомо есть). Можно также
немного сэкономить, произведя вычитание заранее и храня не pos[s], а n-pos[s],
т.е.
число букв в образце справа от последнего вхождения буквы Возможны разные
модификации этого алгоритма. Например, можно строку
last:=last+i
заменить
на
last:=last+(n-u),
где
u - координата второго справа вхождения буквы x[n] в образец.
Как
проще всего учесть это в программе
Решение.
При построении таблицы pos написать
for i:=1 to n-1 do...
(далее
как раньше), а в основной программе вместо
last:=last+1
написать
last:=last+n-pos[y[last]];
Приведенный
упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует
существенно больше n действий (число действий порядка mn), проигрывая алгоритму
Кнута-Морриса-Пратта.
Пример
ситуации, в которой образец не входит в слово, но алгоритму требуется
порядка mn действий, чтобы это установить.
Решение. Пусть образец
имеет вид baaa... aa, а само слово состоит только из букв а. Тогда на каждом
шаге несоответствие выясняется лишь в последний момент.
Настоящий
(не упрощенный) алгоритм Бойера-Мура гарантирует, что число действий не
превосходит C(m+n) в худшем случае. Он использует идеи, близкие к идеям
алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со
входным словом, идя справа налево. При этом некоторый кусок Z (являющийся
концом образца) совпал, а затем обнаружилось различие: перед Z в образце стоит
не то, что во входном слове. Что можно сказать в этот момент о
входном
слове? В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в
образце. Эта информация может позволить сдвинуть образец на несколько позиций
вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее
для каждого конца Z нашего образца. Как говорят знатоки, все это (вычисление
таблицы сдвигов и ее использование) можно уложить в C(m+ n) действий.
Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в слове длины m мы
ищем образец длины n. Вырежем окошечко размера n и будем двигать его по
входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным
образцом.
Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию,
определенную на словах длины n. Если значения этой функции на слове в окошечке
и на образце различны, то совпадения нет. Только если значения одинаковы, нужно
проверять совпадение по буквам.
В чем выигрыш при таком подходе. Казалось бы, ничего - ведь чтобы вычислить
значение функции на слове в окошечке, все равно нужно прочесть все буквы этого
слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш
возможен, и вот за счет чего. При сдвиге окошечка слово не меняется полностью,
а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим
данным можно было рассчитать, как меняется функция.
Привести пример удобной для вычисления функции.
Решение. Заменим все
буквы в слове и образце их номерами, представляющими собой целые числа. Тогда
удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое
число и вычесть пропавшее.)
Для каждой функции существуют слова, к которым она применима плохо. Зато другая
функция в этом случае может работать хорошо. Возникает идея: надо запасти много
функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг,
желающий подгадить нашему алгоритму, не будет знать, с какой именно функцией
ему бороться.)
Привести
пример семейства удобных функций.
Решение. Выберем
некоторое число p (желательно простое, смотри далее) и некоторый вычет x по
модулю p. Каждое слово длины n будем рассматривать как последовательность целых
чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты
многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке
x. Это и будет одна из функций семейства (для каждой пары p и x получается,
таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию
старшего члена (хn-1 следует вычислить заранее), умножению на x и
добавлению свободного члена.
Следующее соображение говорит в пользу того, что совпадения не слишком
вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два
различных слова длины n. Тогда им соответствуют различные многочлены (мы
предполагаем, что коды всех букв различны - это возможно, если p больше числа
букв алфавита). Совпадение значений функции означает, что в точке x эти два
различных многочлена совпадают, то есть их разность обращается в 0. Разность
есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и
много меньше p, то случайному x мало шансов попасть в неудачную точку.