Бінарна алгебраїчна операція
Химия

Реферат — Алгоритм Кнута-Морріса-Пратта — завантажити безкоштовно


Реферат - Алгоритм Кнута-Морріса-Пратта - завантажити безкоштовно

Завантажити реферат: Алгоритм Кнута-Морріса-Пратта

Алгоритм Кнута-Морріса-Пратта (КМП) отримує попередження.

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]

або

(число ітерацій на i-му кроці)<= l[i]-l[i+1]+1

Залишається скласти ці нерівності по всіх і отримати оцінку зверху для загального числа ітерацій.

Використовуватимемо цей алгоритм, щоб з’ясувати, чи є слово 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;

end;

{якщо 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+(nu),

де u — координата другого справа входження літери x[n] в зразок.

Як найпростіше врахувати це у програмі

Рішення. При побудові таблиці написати

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 мало шансів потрапити до невдалої точки.

© Реферат плюс



Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *