Українські рефератиучбові матеріали на українській мові

RefBaza.com.ua пропонує студентам та абітурієнтам найбільшу базу з рефератів! Також ви можете ділитися своїми рефератами для поповнення бази.

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

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

Алгоритм Кнута-Морриса-Пратта (КМП) отримує на вхід слово

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].

Рішення. Припустимо, перші і значень 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 і <> 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 для деякою константи З.

Рішення. Не цілком очевидний: обробка кожної чергової літери вимагатиме багатьох ітерацій у внутрішньому циклі. Проте кожна така ітерація зменшує len по крайнього заходу на 1, й у разі l[i+1] виявиться помітно менше l[i]. З іншого боку, зі збільшенням і на одиницю величина l[i] може підвищитися лише на 1, тож і дуже убувати вона може - інакше убування нічого очікувати скомпенсировано зростанням.

Більше точно, можна записати нерівність

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] для поточного і - окрім неї та, крім таблиці

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+(n-u),

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

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

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

for i:=1 to n-1 do .

(далі як раніше), а основну програму замість

last:=last+1

написати

last:=last+n-pos[y[last]];

Наведений спрощеному варіанту алгоритму Бойера-Мура деяких випадках вимагає значно більше n дій (число дій порядку mn), програючи алгоритму Кнута-Морриса-Пратта.


Схожі реферати

Статистика

[1] 2