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

R

131

Мабуть, варто пояснити деякі значения функцій переходів у наведеній таблиці.

Для стану g_t характерно те, що введения будь-якого сим­волу, крім «s», «і» та *п», призводить до переходу до цього самого стану д, із значениям функції виходу 0, коли введения інформації ще не завершено, та 1, коли завершено. У випадку введения символу «s» перехід відбувається лише до стану q₂ із значениям функції виходу 0, тобто введения продовжується далі, або ж 1, коли цей символ є останнім. У випадку введения символів «і» та «п» виробляеться значения функції виходу 1, і робота автомата припиняється, оскільки за умовою задачі ці символ и не можуть передувати символу «s».

Для стану q₂ введения будь-якого символу, крім «і», є по­милковим, тому значения функції виходу дорівнює 1 і перехід до іншого стану не мае ніякого значення, а при введенні сим­волу «і» перехід відбувається до стану q₃ відповідно із значен­иям функції виходу 0, коли введения символів продовжується, і 1, коли припиняється.

Стан q₃ передбачає перехід до стану g, лише при введенні символу «п» відповідно із значениям функції переходу 0/1, а в усіх інших випадках функщя виходу дае значення 1, тобто будь-яке значення символу, крім «п», є помилковим, і робота автомата припиняється.

Як і в попередньому прикладі за такою таблицею переходів нескладно розробити алгоритм, що контролює правильність за-пису функції синус в математичному виразі.

Спробуємо відповісти на запитання: коли варто формулю-вати алгоритми у термінах скінченних автоматів? Зрозуміло, що коли алгоритм є досить прозорим і в ньому небагато пере-творень, то у створенні таблиці переходів немає потреби. Якщо ж умова задачі передбачає багато перетворєнь або ж ці пере-творення є досить склад ними, залежними одні від одних, то зручніше побудувати таблицю переходів і при цьому реалізація алгоритму стане набагато прозорішою.

А зрештою, використання скінченних автоматів треба роз-глядати як один із підходів до побудови алгоритмів.

Слушним є запитання, чому елементи теорії автоматів ми розглядаємо в розділі пошукових алгоритмів. Справа в тому, що деякі алгоритми, які можна представити у вигляді таблиці переходів, і є пошуковими. Адже задачі, які ми розглянули, підтверджують це.

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

1. Які питания інформатики вирішує теорія автоматів?

2. Як тлумачиться в інформатиці поняття «автомат»?

3. Які основні поняття входять до формування поняття «автомат»?

132

4. Зобразіть схематично роботу автомата.

5. Чому автомати, які розглядаються в інформатиці, називаються скінченними?

6. Дайте означения сличенного автомата в термінах алгоритмізації.

7. Наведіть приклад задачі та сформулюйте її в термінах теорії ав-томатів. Побудуйте для неї таблицю переходів і функції виходу.

8. Обґрунтуйте значения таблиці переходів у наведеному в пункті 7 прикладі.

9. Коли варто формулювати алгоритми у термінах скінченних ав­томате?

Завдання

1. Реалізувати у вигляді алгоритму побудований скінченний автомат для задачі заміни на 7 усіх значень, що перевищують 7 у заданій послідовності натуральних чисел а[і], I = 1, 2,..., п.

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

3. Реалізувати у вигляді алгоритму побудований скінченний автомат для задачі перевірки правильності розставлення круг-лих дужок в математичному виразі.

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

5. Реалізувати у вигляді алгоритму побудований скінченний автомат для задачі перевірки правильності визначення імені функції синус в математичному виразі.

6. Протестувати алгоритм, реалізований у завданні 5.

Пошук підрядків за допомогою скінченних автоматів.

КМП-пошук

Цей метод уперше описано Д. Кнутом, Д. Морісом і В. Прат-том у 1970 р. Його особливістю є те, що він базується на ство-ренні функції перетворень.

Сформулюємо спочатку задачу, яку будемо розв'язувати. Нехай треба знайти перше входження підрядка х, який скла-даеться з т символів, у рядок s, у якому міститься п символів {т < п).

Подібну задачу ми вже розглядали, але ЇЇ розв'язування зво-дилося до лінійного пошуку, тобто ми покроково зміщували підрядок х у рядку s, перевіряючи збігання їх символів. Такий метод мае право на існування, але він не є досить ефективним, оскільки вимагає п ■ т порівнянь збігання символів.

Розглянемо інший підхід до пошуку розв'язання поставле­но! задачі.

Почнемо порівнювати символ и підрядка х - х[1] ... х[т] із символами рядка s - s[l]... s[n] із початку. Нехай s[l] - х[1],..., «[/-!] = хЦ ~ 1]. s[j] * x\j], де / < т (мал. 43).

133

Ііадалі на малюыках ті елементи підрядка х і рядка s, що збі-гаються, будемо позначати світло-сірим кольором, а ті, що не збігаються, — темно-сірим.

Мал. 43

Зрозуміло, що підрядок не входить у рядок із першої пози-ції, оскільки відбулося його незбігання у ;'-й позиції. Можна, звичаино, спробувати почати перевірку з другої за порядком позиції у рядку, як це робилося раніше при лінійному пошуку, але виявляеться, так діяти зовсім не обов'язково.

Розглянемо такий приклад: х = 'ababb' i s = 'ababababbab¹ (мал. 44).

123456789 10 11

12 3 4 5

Мал. 44

3 малюнка видно, що після того як виявилося, що s[5] = 'а' * * 'Ь' = х[5], є сенс починати наступну перевірку лише з s[3], ос-кільки саме там є наступне входження початку підрядка х. Можна також помітити, що символами s[3]s[4] - 'ab' водночас закінчується й починається частина тдрядка лг[1]л:[2]д:[3]д:[4]-Тому можна також казати, що наступне входження підрядка х можливе, коли д:[1]х[2] займуть місце дг[3]х[4] (мал. 45). Таким чином, підрядок «зсунеться» відносно рядка відразу на дві по-зиції'!

123456789 10 11

12 3 4 5

Мал. 45

134

Тепер виявляється, що s[7] * х[5] і підрядок х можна знову зсунути відразу на дві позиції, щоб х[1]х[2] знову зайняли міс-це д:[3]дг[4], збігаючись при цьому з s[5]s[6] (мал. 46).

123456789 10 11

12 3 4 5

Мал. 46

Тепер s[7] = x[3], s[8] ■ x[4], s[9] = x[5] i входження, почи-наючи з позиції 5, знайдено.

Спробуємо узагальнити помічені особливості при відшукан-ні позиції зміщення підрядка х у рядку s.

Отже, нехай перевіряється входження зразка від позиції і — j, х[1] ... х[і] = s[i — ;']... s[i — 1], a x\j + 1] не збігається з чер-говим символом рядка s[i] (мал. 47).

Мал. 47

Виділимо i розглянемо окремо ту частину рядка s і цідряд-ка х, які збіглися (мал. 48).

Мал. 48

Нагадаємо, що в розглянутому вище прикладі х = 'ababb' і s = 'ababababbab' ми намагалися відшукати найоптимальніший зсув нашого підрядка у рядку і такий зсув знайшли, змістивши на другому кроці наш підрядок х зразу на дві позиції у рядку s. Таким чином, ми помітили, що при такому зсуві перші два еле-менти підрядка збігаються з кінцем тієї її частини, що збіглася

135

за значениями з елементами рядка (див. мал. 45): х[1]д:[2] ■ = х[3]*[4] ('ab' - 'ab').

Узагальнюючи наведений приклад, можна дійти висновку, лцо в загальному випадку, коли збіглися частини шдрядка х[1] ... x\j] iрядкаs[i — /]... s[i - 1], требавідшукатитакий най-довший початок х[1]... x[k] підрядка, який водночас є і кінцем фрагмента підрядка х[1]... x[f], що у цій частині з деякої пози-ції збігається і з фрагментом заданого рядка s (мал. 49).

Мал. 49

Це можна пояснити так:

- по-перше, зсув підрядка по рядку може відбуватися лише в межах тієї частини х, що збіглася, тобто у проміжку від 1-го до у-го елемента;

- по-друге, при такому зсуві деякий початок підрядка х (перші k елементів) накладаємо на таку саму кількість його ос- танніх j елементів, і вони при цьому повинні збігатися.

Шдіб'ємо підсумок наведених вище міркувань: перехід від перевіреного початку підрядка довжини ;' до перевіреного по­чатку довжини k (1 < k < j) означав зсув підрядка відносно ряд­ка s відразу на jI — k позицій. Але на меншу кількість позицій зсувати підрядок немає сенсу, оскільки х[1]... х[Щ - це найдов-ший початок підрядка х, що збігається з кінцем фрагмента рядка s[l] ... s[i - 1].

Продовжимо наші міркування далі. Збігання елементів х[1] ... x[k] з елементами s[i - j - к + 1] ... s[i - 1] не припиняє процес порівняння далі, оскільки елементи підрядка х ще не вичерпано. А саме, якщо x[k + 1] - s[i], то можна продовжува-ти порівняння від символу s[i + 1]. Якщо x[k + 1] X s[i], то треба відшукати найдовший початок х[1] ... x[AJ підрядка, що збі-гається з кінцем х[1] ... x[k] (і з кінцем s[l]... s[i - 1]), і порів-няти x[k_x + 1] із s[i]. Описаний алгоритм потрібно застосовува-ти далі аналогічним чином.

Наприклад, якщо s - 'abababc', ал» 'ababc', то за спроби «прикласти» підрядок, починаючи з першого символу рядка, маемо х[1] - s[l], х[2] - в[2], х[3] = в[3], х[4] = s[4], х[5] * s[5], тобто j = 4. Відповідним значениям k буде 2, оскільки 'ab' є най-довшим початком рядка 'abab', що є водночас його кінцем. Звідси випливає, що немає сенсу пробувати «прикласти» під-

136

рядок до рядка, починаючи з його другої позиції, а слід «пе­ресунута» його відразу на у' — k = 2 позиції. При цьому гаран-тується рівність х[1] ... x[k] i s[i — k] ... s[i - 1], тобто назад від позиції s[i] у рядку можна не повертатися.

Отже, можна зробити висновок, що для заданого підрядка х існує строго визначена залежність і вона полягає в такому: для кожної позиції у підрядка відома найбільша довжина f(j) < j такого початку підрядка x[l] ... x[f(j)], що збігається з кінцем х[1] ... x{j].

Оскільки підрядок х задається на самому початку алго­ритму пошуку і не змінюється протягом виконання пошуково-го алгоритму, то можна для кожної позиції у (1 < у < т) задано­го підрядка визначити такі значения k (1 < k < у), для яких х[1] ... x[k] збігається з x{j - k + 1]... x\J]. Значения k i буде ca-ме тим зсувом, який повністю задовольняє оптимальні вимоги пошуку входження підрядка х у рядок s. Значения функції f(j) = k для l<ft<y<mie фактично функцією переходу при кожному конкретному стані розгляду фрагмента підрядка д:[1] ... x[j], де 1 <у'< т.

Перейдемо до алгоритму побудови функції переходу f(j), яка виражає довжину такого найдовшого початку рядка х[і]... x[j], що є водночас його кінцем. У літературі така функція ще нази-вається функцією відступів для методу КМП-пошуку.