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

<span Times New Roman",«serif»; color:blue"> Алгоритм Кнута — Морриса — Пратта

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Алгоритм Кнута-Морриса-Пратта (КМП)получает на  вход слово

<span Times New Roman",«serif»">X=x[1]x[2]…x[n]

<span Times New Roman",«serif»">и просматривает его слева направо букваза буквой, заполняя при этом массив натуральных чисел l[1]… l[n], где

<span Times New Roman",«serif»">l[i]=длинаслова l(x[1]… х[i])

<span Times New Roman",«serif»">(функция l определена в предыдущемпункте). Словами: l[i] есть длина наибольшего начала слова x[1]...x[i],одновременно являющегося его концом.

<span Times New Roman",«serif»">   Какое отношение все это имеетк поиску подслова?

<span Times New Roman",«serif»">Другими словами, как использоватьалгоритм КМП для определения того, является ли слово A подсловом слова B? 

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Применим алгоритм КМП к слову A#B, где # — специальная буква, не встречающаясяни в A, ни в B. Слово A является подсловом слова B тогда и только тогда, когдасреди чисел в массиве l будет число, равное длине слова A.

<span Times New Roman",«serif»">   Описать алгоритм заполнениятаблицы l[1]...l[n].

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Предположим, что первые i значений l[1]...l[i] уже найдены. Мы читаем очереднуюбукву слова (т.е. x[i+1]) и должны вычислить l[i+1].

<span Times New Roman",«serif»"><img src="/cache/referats/495/image001.gif" v:shapes="_x0000_i1025">

<span Times New Roman",«serif»">Другими словами, нас интересуют начала Zслова

<span Times New Roman",«serif»">x[1]...x[i+1,

<span Times New Roman",«serif»">одновременно являющиеся его концами -изних нам надо брать самое длинное. Откуда берутся эти начала? Каждое из них (несчитая пустого) получается из некоторого слова Z' приписыванием буквы x[i+1].Слово Z' является началом и

<span Times New Roman",«serif»">концом слова x[1]...x[i]. Однако нелюбое слово, являющееся началом и концом слова x[1]...x[i], годится — надо,чтобы за ним следовала буква x[i+1].

<span Times New Roman",«serif»">    Получаем такой рецепт отыскания слова Z. Рассмотрим все начала словаx[1]...x[i], являющиеся одновременно его концами. Из них выберем подходящие — те, за которыми идет буква x[i+1]. Из подходящих выберем самое длинное.Приписав в его конец х[i+1], получим искомое слово Z. Теперь поравоспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиесяодновременно началами и концами данного слова, можно получить повторнымиприменениями к нему функции l из предыдущего раздела.

<span Times New Roman",«serif»">   Вот что получается:

<span Times New Roman",«serif»">        i:=1; 1[1]:=0;

<span Times New Roman",«serif»">{таблицаl[1]..l[i] заполнена правильно}

<span Times New Roman",«serif»">while i<> n do begin

<span Times New Roman",«serif»">len:= l[i]

<span Times New Roman",«serif»">{len — длинаначала слова x[1]..x[i], которое является

<span Times New Roman",«serif»">его концом;все более длинные начала оказались

<span Times New Roman",«serif»">неподходящими}

<span Times New Roman",«serif»">while(x[len+1]<>х[i+1]) and (len>0) do begin

<span Times New Roman",«serif»">{начало неподходит, применяем к нему функцию l}

<span Times New Roman",«serif»">len:=l[len];

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">{нашлиподходящее или убедились в отсутствии}

<span Times New Roman",«serif»">ifx[len+1]=x[i+1] do begin

<span Times New Roman",«serif»">{х[1]..x[len]- самое длинное подходящее начало}

<span Times New Roman",«serif»">l[i+1]:=len+1;

<span Times New Roman",«serif»">end else begin

<span Times New Roman",«serif»">{подходящихнет}

<span Times New Roman",«serif»">l[i+1]:= 0;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">i:=i+1;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">      Доказать, что число действийв приведенном только что алгоритме не превосходит Cn для некоторой константы C.

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Это не вполне очевидно: обработка каждой очередной буквы может потребоватьмногих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает lenпо крайней мере на 1, и в этом случае l[i+1] окажется заметно меньше l[i]. Сдругой стороны, при увеличении i на единицу величина l[i] может возрасти неболее чем на 1, так что часто и сильно убывать она не может — иначе убывание небудет скомпенсировано возрастанием.

<span Times New Roman",«serif»">    Более точно, можно записать неравенство

<span Times New Roman",«serif»">       l[i+1]<l [i] — (число итераций на i-м шаге)+1

<span Times New Roman",«serif»">или

<span Times New Roman",«serif»">      (число итераций на i-м шаге)<= l[i]-l[i+1]+1

<span Times New Roman",«serif»">Остается сложить эти неравенства по всемi и получить оценку

<span Times New Roman",«serif»">сверху для общего числа итераций.

<span Times New Roman",«serif»">      Будем использовать этоталгоритм, чтобы выяснить, является ли слово X длины n подсловом слова Y длиныm. (Как это делать с помощью специального разделителя #, описано выше.) Приэтом число действий будет не более C(n+m}, и используемая память тоже.Придумать, как обойтись памятью не более Cn (что может быть существенно меньше,если искомый образец короткий, а слово, в котором его ищут — длинное).

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Применяем алгоритм КМП к слову А#В. При этом: вычисление значений l[1],...,l[n] проводим для слова X длины n и запоминаем эти значения. Дальше мы помнимтолько значение l[i] для текущего i — кроме него и кроме таблицы

<span Times New Roman",«serif»">l[1]...l[n], нам для вычислений ничегоне нужно.

<span Times New Roman",«serif»">    На практике слова X и Y могут не находиться подряд, поэтому просмотрслова X и затем слова Y удобно оформить в виде разных циклов. Это избавляеттакже от хлопот с разделителем.

<span Times New Roman",«serif»">    Написать соответствующийалгоритм (проверяющий, является ли слово X=x[1]...x[n] подсловом словаY=y[1]...y[m]

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Сначала вычисляем таблицу l[1]...l[n]как раньше. Затем пишем такую программу:

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">j:=0; len:=0;

<span Times New Roman",«serif»">{len — длинамаксимального качала слова X, одновременно

<span Times New Roman",«serif»">           являющегося концом слова y[1]..j[j]}

<span Times New Roman",«serif»">while(len<>n) and (j<>m) do begin

<span Times New Roman",«serif»">while(x[len+1]<>у[j+1]) and (len>0) do begin

<span Times New Roman",«serif»">{начало неподходит, применяем к нему функцию l}

<span Times New Roman",«serif»">len: = l[len];

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">{нашлиподходящее или убедились в отсутствии}

<span Times New Roman",«serif»">ifx[len+1]=y[j+1] do begin

<span Times New Roman",«serif»">{x[1]..x[len]- самое длинное подходящее начало}

<span Times New Roman",«serif»">len:=len+1;

<span Times New Roman",«serif»">end else begin

<span Times New Roman",«serif»">{подходящихнет}

<span Times New Roman",«serif»">len:=0;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">j:=j+1;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">{если len=n,слово X встретилось; иначе мы дошли до конца

<span Times New Roman",«serif»">слова Y, так ине встретив X}

<span Times New Roman",«serif»">

<span Times New Roman",«serif»; color:blue">Алгоритм Бойера — Мура

<span Times New Roman",«serif»">  Этот алгоритм делает то, что на первый взгляд кажется невозможным: втипичной ситуации он читает лишь небольшую часть всех букв слова, в которомищется заданный образец. Как так может быть? Идея проста. Пусть, например, мыищем образец abcd. Посмотрим на четвертую букву слова: если, к примеру, этобуква e, то нет никакой необходимости читать первые три буквы. (В самом деле, вобразце буквы e нет, поэтому он может начаться не раньше пятой буквы.)

<span Times New Roman",«serif»">  Мы приведем самый простой вариант этого алгоритма, который негарантирует быстрой работы во всех случаях. Пусть x[1]… х[n] — образец,который надо искать. Для каждого символа s найдем самое правое его вхождение вслово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить вмассиве pos[s]; если символ s вовсе не встречается, то нам будет удобноположить pos[s]=0 (мы увидим дальше, почему).

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">  Как заполнить массив pos?

<span Times New Roman",«serif»">Решение.

<span Times New Roman",«serif»">положить все pos[s] равными 0

<span Times New Roman",«serif»">for i:=1 to ndo begin

<span Times New Roman",«serif»">    pos[x[i]]:=i;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">В процессе поиска мы будем хранить впеременной last номер буквы в слове, против которой стоит последняя букваобразца. Вначале last=n (длина образца), затем last постепенно увеличивается.

<span Times New Roman",«serif»">last:=n;

<span Times New Roman",«serif»">{всепредыдущие положения образца уже проверены}

<img src="/cache/referats/495/image002.gif" v:shapes="_x0000_s1026"><span Times New Roman",«serif»">whilelast<= m do begin {слово не кончилось}

<img src="/cache/referats/495/image003.gif" v:shapes="_x0000_s1027"><span Times New Roman",«serif»">      if x[m]<>y[last] then begin{последние буквы разные}

<span Times New Roman",«serif»">         last:=last+(n-pos[y[last]]);

<span Times New Roman",«serif»">        {n — pos[y[last]] — это минимальныйсдвиг образца,

<span Times New Roman",«serif»">               при котором напротив y[last]встанет такая же

<span Times New Roman",«serif»">               буква в образце. Если такойбуквы нет вообще,

<span Times New Roman",«serif»">               то сдвигаем на всю длинуобразца}

<span Times New Roman",«serif»">      end else begin

<span Times New Roman",«serif»">если нынешнееположение подходит, т.е. если

<span Times New Roman",«serif»">            x[i]… х[n]=y[last-n+1]..y[last],

<span Times New Roman",«serif»">            то сообщить о совпадении;

<span Times New Roman",«serif»">            last:=last+1;

<span Times New Roman",«serif»">      end;

<span Times New Roman",«serif»">end;

<span Times New Roman",«serif»">Знатоки рекомендуют проверку совпаденияпроводить справа налево, т.е. начиная с последней буквы образца (в которойсовпадение заведомо есть). Можно также немного сэкономить, произведя вычитание заранееи храня не pos[s], а n-pos[s],

<span Times New Roman",«serif»">т.е. число букв в образце справа отпоследнего вхождения буквы Возможны разные модификации этого алгоритма.Например, можно строку

<span Times New Roman",«serif»">last:=last+i

<span Times New Roman",«serif»">заменить на

<span Times New Roman",«serif»">last:=last+(n-u),

<span Times New Roman",«serif»">где u — координата второго справавхождения буквы x[n] в образец.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">Какпроще всего учесть это в программе

<span Times New Roman",«serif»">Решение. При построении таблицы posнаписать

<span Times New Roman",«serif»">for i:=1 ton-1 do...

<span Times New Roman",«serif»">(далее как раньше), а в основнойпрограмме вместо

<span Times New Roman",«serif»">last:=last+1

<span Times New Roman",«serif»">написать

<span Times New Roman",«serif»">last:=last+n-pos[y[last]];

<span Times New Roman",«serif»">Приведенный упрощенный вариант алгоритмаБойера-Мура в некоторых случаях требует существенно больше n действий (числодействий порядка mn), проигрывая алгоритму Кнута-Морриса-Пратта.

<span Times New Roman",«serif»"> Примерситуации, в которой образец не входит в слово, но алгоритму требуетсяпорядка mn действий, чтобы это установить.

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Пусть образец имеет вид baaa… aa, а само слово состоит только из букв а.Тогда на каждом шаге несоответствие выясняется лишь в последний момент.

<span Times New Roman",«serif»">Настоящий (не упрощенный) алгоритмБойера-Мура гарантирует, что число действий не превосходит C(m+n) в худшемслучае. Он использует идеи, близкие к идеям алгоритма Кнута-Морриса-Пратта.Представим себе, что мы сравнивали образец со входным словом, идя справаналево. При этом некоторый кусок Z (являющийся концом образца) совпал, а затемобнаружилось различие: перед Z в образце стоит не то, что во входном слове. Чтоможно сказать в этот момент о

<span Times New Roman",«serif»">входном слове? В нем обнаружен фрагмент,равный Z, а перед ним стоит не та буква, что в образце. Эта информация можетпозволить сдвинуть образец на несколько позиций вправо без риска пропустить еговхождение. Эти сдвиги следует вычислить заранее для каждого конца Z нашегообразца. Как говорят знатоки, все это (вычисление таблицы сдвигов и ееиспользование) можно уложить в C(m+ n) действий.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»; color:blue">Алгоритм Рабина

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">   Этот алгоритм основан на простой идее. Представим себе, что в словедлины m мы ищем образец длины n. Вырежем окошечко размера n и будем двигать егопо входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным

<span Times New Roman",«serif»">образцом. Сравнивать по буквам долго.Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Еслизначения этой функции на слове в окошечке и на образце различны, то совпадениянет. Только если значения одинаковы, нужно проверять совпадение по буквам.

<span Times New Roman",«serif»">     В чем выигрыш при таком подходе. Казалось бы, ничего — ведь чтобывычислить значение функции на слове в окошечке, все равно нужно прочесть всебуквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менеевыигрыш возможен, и вот за счет чего. При сдвиге окошечка слово не меняетсяполностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы,чтобы по этим данным можно было рассчитать, как меняется функция.

<span Times New Roman",«serif»">   Привести пример

<span Times New Roman",«serif»">удобной для вычисления функции.

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Заменим все буквы в слове и образце их номерами, представляющими собой целыечисла. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужнодобавить новое число и вычесть пропавшее.)

<span Times New Roman",«serif»">    Для каждой функции существуют слова, к которым она применима плохо. Затодругая функция в этом случае может работать хорошо. Возникает идея: надозапасти много функций и в начале работы алгоритма выбирать из них случайную. (Тогда враг, желающий подгадить нашемуалгоритму, не будет знать, с какой именно функцией ему бороться.)

<span Times New Roman",«serif»"> Привести пример семейства удобныхфункций.

<span Times New Roman",«serif»">Решение

<span Times New Roman",«serif»">.Выберем некоторое число p (желательно простое, смотри далее) и некоторый вычетx по модулю p. Каждое слово длины n будем рассматривать как последовательностьцелых чисел (заменив буквы кодами). Эти числа будем рассматривать каккоэффициенты многочлена степени n-1 и вычислим значение этого многочлена помодулю p в точке x. Это и будет одна из функций семейства (для каждой пары p иx получается, таким образом, своя функция). Сдвиг окошка на 1 соответствуетвычитанию старшего члена (хn-1 следует вычислить заранее), умножениюна x и добавлению свободного члена.

<span Times New Roman",«serif»">      Следующее соображение говорит в пользу того, что совпадения не слишкомвероятны. Пусть число p фиксировано и к тому же простое, а X и Y — дваразличных слова длины n. Тогда им соответствуют различные многочлены (мыпредполагаем, что коды всех букв различны — это возможно, если p больше числабукв алфавита). Совпадение значений функции означает, что в точке x эти дваразличных многочлена совпадают, то есть их разность обращается в 0. Разностьесть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если имного меньше p, то случайному x мало шансов попасть в неудачную точку.

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">

<span Times New Roman",«serif»">

еще рефераты
Еще работы по программированию, базе данных