3.3.3 Швидкість роботи

Для даного регулярного виразу r і вхідного рядка х існує два методи визначення, чи входить х в L(r). Один підхід складається у використанні алгоритму 3.3 для побудови НКА N з r. Ця побудова може бути виконана за час О(|r|), де |r| — довжина r. N має кількість станів, не більш ніж у два рази переважаюча |r|, і не більше двох переходів для кожного стану. У результаті таблиця переходів N займає обсяг О(|r|). Потім за допомогою алгоритму З.4 за час О(|r|х|х|) можна визначити, чи допускає N рядок х. Таким чином, використовуючи описаний підхід, можна з’ясувати, чи міститься х в L(r) за час, пропорційний довжині r, помноженої на довжину х. Такий підхід застосовується в багатьох текстових редакторах для пошуку шаблонів регулярних виразів, коли рядок не дуже довгий (точніше, для пошуку підрядків рядка х, що .задаються регулярним виразом r).

Другий підхід полягає в створенні ДКА з регулярного виразу r із застосуванням побудови Томпсона, а потім— побудови підмножини (алгоритм 3.2) до отриманого НКА (існують і методи, що дозволяють уникнути явної побудови проміжного НКА). Реалізуючи функцію переходів за допомогою таблиці переходів, можна використати алгоритм 3.1 для моделювання роботи ДКА із вхідним рядком х за час, пропорційний довжині х (незалежно від кількості станів ДКА). Такий підхід частіше використається в програмах пошуку за шаблоном, які переглядають текстові файли в пошуках шаблонів регулярних виразів, Після того, як ДКА побудований, пошук здійснюється дуже швидко, тому такий підхід особливо приємний до дуже довгих рядків, а також для багаторазового пошуку з одним і тим ж регулярним виразом, а значить, з одного разу побудованим ДКА.

Однак існує ряд регулярних виразів, для яких найменші ДКА мають кількість станів, що представляє собою експоненту від розміру регулярного виразу. Наприклад, регулярний вираз (a|b)*a(a|b)(a|b)...(a|b), що завершується n-1 (a|b), не має ДКА з менш чим 2 ⁿ станами. Цей регулярний вираз описує рядок з а й b, на п-м місці від правого кінця якої перебуває символ а. Неважко довести, що будь-який ДКА для цього виразу повинен відслідковувати як мінімум п символів вхідного потоку; у противному випадку може бути дана невірна відповідь. Ясно, що для відстеження всіх можливих послідовностей з п символів а й b потрібно принаймні 2ⁿ стани. На щастя, такого роду вирази зустрічаються в додатках лексичного аналізу не так вже часто, хоча й цілком реальні.

У третьому підході пропонується використати ДКА, але при цьому уникнути побудови всієї таблиці переходів за допомогою технології, називаної "відкладеним обчисленням переходів". При такому методі переходи обчислюються в процесі роботи програми, але тільки в той момент, коли вони дійсно потрібні для роботи. Обчислені в такий спосіб переходи зберігаються в кеші. Щораз при необхідності обчислити деякий перехід відбувається звертання до кешу. Якщо шуканого переходу в ньому немає, він обчислюється й записується в кеш. Якщо кеш переповняється, можна видалити частину раніше обчислених переходів і звільнити місце для нового.

На рис. 3.14 показана пам'ять і час, необхідні в найгіршому випадку при роботі з рядком х і мовою, обумовленою регулярним виразом r з використанням розпізнавачів на базі недетермінованих і детермінованих кінцевих автоматів. "Відкладена" технологія комбінує вимоги до простору для НКА й часу роботи із ДКА. Вимоги до пам'яті зводяться до розміщення регулярного виразу й кеша, а швидкість роботи майже так само висока, як і при звичайній роботі із ДКА. У ряді додатків така технологія за швидкістю перевершує роботу із ДКА, оскільки при цьому не обчислюються переходи, які ніколи не використаються.

	Автомат	Пам'ять	Час
	НКА ДКА	О(|r|) О(2↑ |r|)	О(|r|х|х|) О(|х|)

Рис. 3.14. Пам'ять і час, необхідні для розпізнавання регулярних виразів