Алгоритм Кнута-Морриса-Пратта

Алгоритм Кнута - Морриса - Пратта Алгоритм Кнута-Морриса-Пратта КМП получает на вход слово Xx1x2 xn и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел l1 ln, где liдлина слова lx1 хi функция l определена в предыдущем пункте. Словами li есть длина наибольшего начала слова x1 xi, одновременно являющегося его концом. Какое отношение все это имеет к поиску подслова Другими словами, как использовать алгоритм

КМП для определения того, является ли слово A подсловом слова B Решение. Применим алгоритм КМП к слову AB, где - специальная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когда среди чисел в массиве l будет число, равное длине слова A. Описать алгоритм заполнения таблицы l1 ln. Решение. Предположим, что первые i значений l1 li уже найдены.

Мы читаем очередную букву слова т.е. xi1 и должны вычислить li1. Другими словами, нас интересуют начала Z слова x1 xi1, одновременно являющиеся его концами -из них нам надо брать самое длинное. Откуда берутся эти начала Каждое из них не считая пустого получается из некоторого слова Z приписыванием буквы xi1 . Слово Z является началом и концом слова x1 xi.

Однако не любое слово, являющееся началом и концом слова x1 xi, годится - надо, чтобы за ним следовала буква xi1. Получаем такой рецепт отыскания слова Z. Рассмотрим все начала слова x1 xi, являющиеся одновременно его концами. Из них выберем подходящие - те, за которыми идет буква xi1. Из подходящих выберем самое длинное. Приписав в его конец хi1, получим искомое слово

Z. Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции l из предыдущего раздела. Вот что получается i1 110 таблица l1 li заполнена правильно while i n do begin len li len - длина начала слова x1 xi, которое является его концом все более длинные начала оказались неподходящими while xlen1 хi1 and len 0 do begin начало не подходит, применяем к нему функцию l lenllen

end нашли подходящее или убедились в отсутствии if xlen1xi1 do begin х1 xlen - самое длинное подходящее начало li1len1 end else begin подходящих нет li1 0 end ii1 end Доказать, что число действий в приведенном только что алгоритме не превосходит Cn для некоторой константы C. Решение. Это не вполне очевидно обработка каждой очередной буквы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает len по крайней

мере на 1, и в этом случае li1 окажется заметно меньше li. С другой стороны, при увеличении i на единицу величина li может возрасти не более чем на 1, так что часто и сильно убывать она не может - иначе убывание не будет скомпенсировано возрастанием. Более точно, можно записать неравенство li1 l i - число итераций на i-м шаге1 или число итераций на i-м шаге li-li11 Остается сложить эти неравенства по всем i и получить оценку сверху для общего числа

итераций. Будем использовать этот алгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длины m. Как это делать с помощью специального разделителя , описано выше. При этом число действий будет не более Cnm, и используемая память тоже. Придумать, как обойтись памятью не более Cn что может быть существенно меньше, если искомый образец короткий, а слово, в котором его ищут - длинное. Решение.

Применяем алгоритм КМП к слову АВ. При этом вычисление значений l1 l n проводим для слова X длины n и запоминаем эти значения. Дальше мы помним только значение li для текущего i - кроме него и кроме таблицы l1 ln, нам для вычислений ничего не нужно. На практике слова X и Y могут не находиться подряд, поэтому просмотр слова X и затем слова Y удобно оформить в виде разных циклов.

Это избавляет также от хлопот с разделителем. Написать соответствующий алгоритм проверяющий, является ли слово Xx1 xn подсловом слова Yy1 ym Решение. Сначала вычисляем таблицу l1 lnкак раньше. Затем пишем такую программу j0 len0 len - длина максимального качала слова X, одновременно являющегося концом слова y1 jj while len n and j m do begin while xlen1 уj1 and len 0 do begin начало не подходит, применяем к нему функцию l len llen end нашли подходящее или убедились

в отсутствии if xlen1yj1 do begin x1 xlen - самое длинное подходящее начало lenlen1 end else begin подходящих нет len0 end jj1 end если lenn, слово X встретилось иначе мы дошли до конца слова Y, так и не встретив X Алгоритм Бойера - Мура Этот алгоритм делает то, что на первый взгляд кажется невозможным в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть Идея проста. Пусть, например, мы ищем образец abcd.

Посмотрим на четвертую букву слова если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы. Мы приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x1 хn - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором хks. Эти сведения будем хранить в массиве poss если символ

s вовсе не встречается, то нам будет удобно положить poss0 мы увидим дальше, почему. Как заполнить массив pos Решение. положить все poss равными 0 for i1 to n do begin posxii end В процессе поиска мы будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале lastn длина образца, затем last постепенно увеличивается. lastn все предыдущие положения образца уже проверены while last m do begin слово не кончилось if xm ylast then begin последние

буквы разные lastlastn-posylast n - posylast - это минимальный сдвиг образца, при котором напротив ylast встанет такая же буква в образце. Если такой буквы нет вообще, то сдвигаем на всю длину образца end else begin если нынешнее положение подходит, т.е. если xi хnylast-n1 ylast, то сообщить о совпадении lastlast1 end end Знатоки рекомендуют проверку совпадения проводить справа налево, т.е. начиная с последней буквы образца в которой совпадение заведомо есть. Можно также немного сэкономить, произведя вычитание

заранее и храня не poss, а n-poss, т.е. число букв в образце справа от последнего вхождения буквы Возможны разные модификации этого алгоритма. Например, можно строку lastlasti заменить на lastlastn-u, где u - координата второго справа вхождения буквы xn в образец. Как проще всего учесть это в программе Решение. При построении таблицы pos написать for i1 to n-1 do далее как раньше, а в основной программе вместо lastlast1 написать lastlastn-posylast

Приведенный упрощенный вариант алгоритма Бойера-Мура в некоторых случаях требует существенно больше n действий число действий порядка mn, проигрывая алгоритму Кнута-Морриса-Пратта. Пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка mn действий, чтобы это установить. Решение. Пусть образец имеет вид baaa aa, а само слово состоит только из букв а. Тогда на каждом шаге несоответствие выясняется лишь в последний момент.

Настоящий не упрощенный алгоритм Бойера-Мура гарантирует, что число действий не превосходит Cmn в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок Z являющийся концом образца совпал, а затем обнаружилось различие перед Z в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове

В нем обнаружен фрагмент, равный Z, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашего образца. Как говорят знатоки, все это вычисление таблицы сдвигов и ее использование можно уложить в Cm 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 мало шансов попасть в неудачную точку.