Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

Очевидно, що Д1) = 0. Далі міркуємо так. Нехай усі значен­ия /(1),..., f(j - 1) уже обчислено, причому ВІДОМО, що f(j -l) = k, тобто у випадку збігання х[1] ... x[j - 1] із s[i - у - 1] ... s[i - 2] наступний зсув у рядку треба зробити на у - k елементів віднос-но s[i — j — 1] (мал. 50).

Мал. 50

Розглянемо тепер, яким може бута значения /(у). Нага-даемо, як треба тлумачити значения /(у). По-перше, це означав, що ми продовжили розгляд фрагмента підрядка від його почат­ку ще на один елемент: х[1]... x\j]. Але якщо розглянути попе-редне «прикладання» х[1] ... x[k] до x\j - k] ... x[j - 1], яке ми визнали таким, що збігається, то тепер треба провести порів-няння наступних двох елементів: x[j] i x[k + 1] (мал. 51).

137

Мал. 51

Тут можливі два варіанти.

Якщо x[j] = x[k + 1], то кінець рядка х[1] ... x[j - l]x\j] збі-гається з його початком довжини ft + 1, тому логічно, що f(j) =

= Г0-1) + 1 = л + 1.

Якщо ж x[j] =■= x[k + 1], то треба спробувати підібрати інший такий фрагмент х[1]... x[ftl], що х[1]... x[ftj = x[j^;- ft, + 1]... x\j] при ft, < ft. Як же знайти значения ft,? Давайте перелічимо ті факти, які нам на даний час відомі:

• фрагмент підрядка д:[1] ... x[k] збігається з його ж фраг­ментом x\j - ft]... x[j - 1];

• x[k + 1] * x[j], тобто збігання наступних двох елементів тих фрагментів підрядка, які розглядаються, відсутнє.

Це означає, що якщо фрагмент підрядка х[1] ... x\j - 1] = = s[i - ft]... s[i - 2], x[j] * s[i - 1] i для цього випадку відоме зна­чения ft для наступного зсуву підрядка по рядку, то відповідно виконується і таке твердження: д:[1]... x[k] = s[i - ft]... s[i - 2], x[k + 1] * s[i - 1] (див. мал. 49). Який висновок з цього можна зробити? А висновок такий, що знову маемо справу зі старто­вого ситуацією і переходимо до початку наших міркувань, ви-значивши j - 1 = ft (ft < j - 1). А що було зроблено для того, щоб визначити, на яку кількість символів у x[lj... x[k] треба змісти-тися, щоб деякий його початок збігався з його кінцем? Оскіль-ки ft < j - 1, то ця інформація вже відома і є значениям елемен-та масиву /(ft).

Отже, «наступним кандидатом у кінці» рядка х[1] ... ... x{j — l]x[j] є рядок х[1~\ ... x[f(k)]x[f(k) + 1], оскільки саме х[1] ... x[f(k)] є найдовшим кінцем х[1] ... x[k]. Якщо і він не придатний, то наступним є д:[1]... x[f{f(k)) + 1] тощо. Таким чи­ном, ми або знайдемо початок довжинир такий, що х[1]... х[р] є кінцем дг[1]... x\j], і тоді f(j) = p, або не знайдемо, і тоді f(j) = 0.

Описаний алгоритм, як бачимо, є рекурентним. Запишемо його у вигляді тексту Pascal-програми, де значения функції f будемо записувати у масив:

f[1]:=0; forj := 2ton do begin

k:=f[j-1];

while (x[j] <> x[k + 1]) and (k > 0) do k := f[k];

138

If (x[j]<>x[k+1])and(k = 0) thenffj] :=0 elsef[j]:=k+1; end;

Однак рекурентність досить часто можна замінити рекур-сією. Тому слід запропонувати й такий варіаит цього самого ал­горитму обчислення значень функції переходів для заданого підрядка х:

procedure КМР (k: word); begin if к = О

then f[j] := О elseifx[f[k-1] + 1] = x[j]

then fШ := f [k - 1] + 1 elseKMP(f[k]); end;

Побудова функції переходів здійснюється таким фрагмен­том алгоритму:

f[1]:=0;

forj := 2 torn do

KMP(j);

Побудова функції переходів за доиомогою рекурсивного ал­горитму може виглядати і так:

procedure КМР; var k, j: word; begin

f[1]:=0; forj := 2 to n do begin k:=f[j-1];

while (x[j] о x[k + 1]) and (k > 0) do к := f[k]; if (x[j]ox[k+ 1])and(k = 0) then f[j] := 0 elsef[j] :=k+ 1; end; end;

У цьому разі виклик процедури буде найпростішим: КМР;

Оцінимо загальну кількість порівнянь символів, виконува-них за цим алгоритмом. Позначимо через w(j) кількість вико-нань тіла циклу для відповідного значения ;' = 2, ..., т. Неваж-ко побачити, що кожне виконання тіла циклу while зменшує

139

значения k не менше як на 1. Звідси f[f\ <= f[j - 1] - w(j) + 1, тоб-то w(j) <- f[j - 1] - /[/] + 1. Тоді:

ш(2) + ш(3) + ... + ш(/п) <= Я1] - Я2] + 1 + Я2] - ЯЗ] + 1 + .« + + Я"і - 1] - Л>] + 1 = Я1] + т-1 <-j»-l.

Для кожного у відбувається порівнянь символів на 2 більше, ніж виконань тіла циклу: одне додаткове порівняння під час обчислення умови в заголовку циклу і одне - в умовному опера-торі. Звідси загальна кількість порівнянь символів не більша за 3(т - 1), тобто пропорційна т. Таким чином, загальну кіль-кість порівнянь символів під час побудови функції відступів можна оцінити як 0{т).

Тепер, нарешті, наведемо алгоритм пошуку входжень по­рядка х у рядок s. Причому будемо шукати всі можливі вхо­дження.

Нехай через t позначимо номер поточної позиції в рядку, j -номер поточної позиції у підрядку. їх початкові значения до-рівнюють 1.

Далі, поки t <- п, виконуємо наступні дії. Порівнюємо сим-воли x{j] і s[t]. Якщо вони рівні, то маємо входження х[1]... x[f\ у кінці рядка s[l]... s[t]. Якщо при цьому j = т., то можна пові-домити про входження підрядка х, почйнаючи з позиції t — j + 1, i приступати до пошуків наступного його входження, поклавши / = f(m). Якщо ж у < т, то переходимо до наступної пари символів, збільшивши t i у на 1. Якщо s[t] i x{j\ нерівні при j > 1, то міняємо значения у на f[j — 1] + 1, а при у = 1 — збіль-шуємо t на 1. Проте зміни у" не мають сенсу, коли t = п. Ось i все.

Наведемо описаний алгоритм також мовою Pascal:

i := 1; j := 1;flag :=true; while (i <= n) and flag do begin

ifx[j] = s[i] then if j = m then begin write(f_out, 'Text has found at the position: #'); writeln(f_out, i - j + 1); flag := false; end else begin i:=i + 1; j:=j + 1 end else

140

if i <= n - m + 1 then begin ifj>1

theni:=i-f[j-1] else i := i + 1;

j:=1; end end; if flag then writeln(f_out, 'Text hasn"t found');

Оцінимо тепер кількість порівнянь символів під час вико-нання цього алгоритму. Нескладно помітити, що під час кож­ного виконання тіла циклу значения t збільшується на 1 або значения j зменшується прииаймні на 1 присвоюванням /[/'] чи f[j - 1] + 1. Позначимо через b(t) початкове значения / під час чергового значения t = 1, 2, ..., n, а через w(t) — кількість змен-шень j під час відповідного значения t. Оскільки під час збіль-шення t значения у або не змінюється, або збільшується на 1, то маемо, що b(t) <= b(t - 1) - w(t) + 1 при t> 1.

Звідси w(t) <- b(t - 1) - b(t) + 1. Тоді:

w(l) + w(2) + ... + w(n) <= 1 + fe[l] - b[2] + 1 + 6[2] - b[3] + 1 + + ... + b[n - I] - b[n] + 1 - n + b[l] - b[n] <- n + 1.

3 алгоритму очевидно, що порівнянь символів відбувається рівио стільки, скільки збільшень t і зменшеньу' разом. Оскільки t збільшується п - 1 разів, загальна кількість порівнянь сим-волів не більша за 2п, тобто пропорційна п, і оцінюється як 0(л).

3 урахуванням побудови функції переходів загальна кіль-кість порівнянь символів для будь-яких рядків довжини п і т оцінюеться як О(т) + О(л), або 0(п + т).

Оскільки описаний метод є не дуже простим щодо його усві-домлення, то дозволимо собі ще раз зробити остаточний висновок у вигляді таких основных постулатів методу КМП-пошуку:

1. для пошуку наступного входження підрядка довжиною т у рядок довжиною п можна робити зсув лише на k позищй, де 1 <= k <- т;

2. якщо знайдено кількість позицій зсуву k для підрядка, то цеозначав, щох[1] = х[п -k +1], х[2] = х[т -k + 2],..., x[k] = х\т\, тобто існує такий початок підрядка в h символів, що збігається з його кінцем довжиною також у k символів. Це означав, що можна визначити наперед, на скільки позицій треба зсунути підрядок у межах від 1 до т, якщо попередне його повне накла-дання не збігається;

3. при накладанні з деякої позиції на рядок шуканого під-рядка незбігання можна визначити раніше, не переглядаючи

141

весь підрядок. Наприклад, незбігання відбулося на символі / заданого підрядка. Посилаючись на п. 1, можна зробити висно-вок, що тепер зсув можна робити лише в межах / символів по­рядка, де j < т. Посилаючись на п. 2, можна знайти таке ft., що визначає такий початок підрядка в ft. символів, що збігається з його кінцем.

/ Запитання для самоконтролю

1.Хто є авторами методу пошуку підрядка у рядку, який розгля-даеться?

2. Чому метод КМП-пошуку можна віднести до методу, що вико-ристовує скінченний автомат?

3. Поясніть поетапно ідею методу КМП-пошуку на конкретному прикладі, супроводжуючи свої пояснения мапюнками.

2. Що являє собою функція переходів для методу КМП-пошуку?

2. Який вміст елементів функції переходів для методу КМП-по­шуку?

3. Наведіть рекурентний алгоритм побудови функції переходів для методу КМП-пошуку.

4. Запишіть наведений у пункті 6 алгоритм у вигляді фрагмента тексту Pascal-програми.

5. Наведіть рекурсивний алгоритм побудови функціі переходів для методу КМП-пошуку.

6. Запишіть наведений у пункті 8 алгоритм у вигляді тексту Pascal-процедури.

10. Запишіть алгоритм пошуку входження підрядка у рядок з вико-ристанням побудованоі функції переходів у вигляді фрагмента тексту Pascal-програми.

11. Сформулюйте основні постулати методу КМП-пошуку.

12. Якою є оцінка ефективності роботи методу КМП-пошуку? Обгрунтуйте цю оцінку.

Завдання

1. Реалізувати алгоритм пошуку підрядка х у рядку s, засто-сувавши метод КМП-пошуку. Для побудови функції переходів використати рекурентний алгоритм.

2. Реалізувати алгоритм пошуку підрядка х у рядку в, засто-сувавши метод КМП-пошуку. Для побудови функпд переходів використати рекурсивний алгоритм.

3. Протестувати алгоритм, реалізований у завданні 1, для конкретного прикладу.

4. Протестувати алгоритм, реалізований у завданні 2, для конкретного прикладу.

5- Порівняти результати виконання алгоритмів у завдан-нях 1, 2 стосовно кількості порівнянь символів підрядка і ряд­ка з алгоритмом лінійного пошуку.

6. Зробити письмовий аналіз виконання завдання 5.

142

Пошук у мережі

Мережею будемо називати множину вершин Р і множину дуг R, що їх з'єднують, та функцію d, яка задана на R у мно­жит дійсних чисел. Можна сказати, що d задає залежність між окремими вершинами, визначеними на дугах.

Далі мережу будемо визначати так:

S = (P,R,d).

Інколи d(x, у) інтерпретують як довжину дуги (х, у) Є R.

Для кращого розуміння поняття мережі та з'ясування, чому ми її розглядаємо в темі «Пошукові алгоритми», наведемо ти-пові приклади існування інформації, яку можна представити у вигляді мережі.

Наприклад, це може бути задача про взаємини щодо визна-чення обсягу постачання сировини в мережі, яку утворюють N підприємств одного відомства. А саме, на яку загальну суму підприємство х отримує сировину від інших підприємств, якщо відома інформація про постачання сировини підприєм-ства х, деякому підприємству у. на суму d.. (1 < і, j < N).

Ще одна подібна задача про банки. Нехай відома інформація про те, яку грошову суму винен кожний із банків іншим. Треба визначити, яку суму винен деякий банк х іншим банкам і яким саме, а також яку суму винні йому інші банки та які саме.

Отже, перейдемо до суті задачі в термінах мережі. Розгляне-мо приклад деякої мережі, яка мае т вершин (т = 9) і п дуг (п " 15), що з'єднують ці вершини (мал. 52).

Мал. 52

Сформулюємо дві задачі, які найчастіше доводиться роз-в'язувати у зв'язку з мережею:

1) для фіксованої вершини х Є Р визначити всі дуги мережі вигляду (х, у) (виходи з х);

143

2) для фіксованої вершини хЄР визначити всі дуги мережі вигляду (у, х) (входи в х).

Будемо говорити про багатократний пошук необхідної ін-формації в мережі, стан якої не змінюється протягом ви конин-ня алгоритму.

Найпростіше, але найменш ефективно, застосовувати в кож­ному з випадків лінійний пошук. Але існують і ефективніші методи. Розглянемо деякі з них і визначимо, чому вони мають безпосереднє відношевня до скінченних автоматів.

Пред ставимо мережу S у вигляді таблиці, де окремі рядки є записами про конкретні дуги (табл. 14).

Таблиця 14