Пошук з поверненням в регулярних виразах

Пошук з поверненням відбувається, якщо шаблон регулярного виразу містить змінні квантіфікатори або конструкції зміни. і обробник регулярних виразів повертається в попереднє збережений стан, щоб продовжити пошук збіги. У пошуку з поверненням укладена сила регулярних виразів. Завдяки йому вирази можуть бути потужними і гнучкими, а також збігатися зі складними шаблонами. З іншого боку, ці можливості дорого обходяться. Часто саме пошук з поверненням істотно знижує продуктивність обробника регулярних виразів. На щастя, розробник може управляти роботою обробника регулярних виразів і тим, як він використовує пошук з поверненням. У цьому розділі описано, як функціонує пошук з поверненням, і як нею можна управляти.

В цілому, при використанні NFA-машини (недетермінірованного кінцевого автомата), такий як обробник регулярних виразів .NET Framework, відповідальність за створення ефективних і швидко виконуваних регулярних виразів лежить на розробнику.

Цей розділ містить такі підрозділи.

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

Це ілюструє наступний приклад.
Регулярний вираз e \ w \ b шукає наступний рядок: два входження літери «e», потім символ слова, потім межа слова.

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

Положення в шаблоні

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

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

Наприклад, розглянемо шаблон регулярного виразу. * (Es). збігається з символами "es" та будь-яким попереднім символам. Як показано в наступному прикладі, якщо взяти вхідні рядок "Essential services are provided by regular expressions.", Збігатися з шаблоном буде вся рядок до букв "es" в слові "expressions" включно.

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

Оброблювач виявляє збіг частини виразу. * (Що відповідає будь-якому числу будь-яких символів) з усією вхідний рядком.

Потім обробник шукає збіг для символу "e" шаблону регулярного виразу. Однак у вхідному рядку немає більше символів для пошуку збігу.

Оброблювач повертається до місця останнього успішного збігу, "Essential services are provided by regular expressions", і порівнює символ "e" з точкою в кінці речення. Збіг відсутня.

Оброблювач продовжує повертатися до попередніх успішним збігів, відступаючи по одному символу, поки імовірно підходящої підрядком не стає подстрока "Essential services are provided by regular expr". Потім обробник порівнює символ "e" шаблону з другої буквою "e" в слові "expressions" і виявляє збіг.

Потім він порівнює символ "s" шаблону з символом "s" після символу "e" в рядку (перша буква "s" в слові "expressions"). Збіг успішно.

При використанні пошуку з поверненням пошук збігу шаблону регулярного виразу з вхідною рядком довжиною 55 символів вимагає 67 операцій порівняння. Цікаво, що якщо шаблон регулярного виразу включає ледачий квантіфікатор, *? (Es). пошук збігу зажадає додаткових операцій порівняння. У цьому випадку замість зворотного пошуку від кінця рядка до символу "r" в слові "expressions" оброблювачу регулярних виразів доведеться виконати зворотний пошук до початку рядка в пошуках "Es", що зажадає 113 порівнянь. Як правило, якщо в шаблоні регулярного виразу є один змінний квантіфікатор або одна конструкція зміни, число порівнянь, необхідних для пошуку у вхідному рядку збіги з шаблоном регулярного виразу, більш ніж удвічі перевищує число символів у вхідному рядку.

Кількість порівнянь, необхідне для пошуку у вхідному рядку збіги з шаблоном регулярного виразу, може збільшуватися експоненціально, якщо шаблон включає велику кількість конструкцій зміни або вкладені конструкції зміни, або, що трапляється частіше, вкладені змінні квантіфікатори. Наприклад, шаблон регулярного виразу ^ (a +) + $ повинен збігатися з рядком, що складається з одного і більше символів "a". У прикладі показані дві вхідні рядки однакової довжини, тільки одна з яких збігається з шаблоном. Клас System.Diagnostics. Stopwatch використовується для визначення часу виконання операції пошуку збігу.

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

Він перевіряє, що знаходиться на початку рядка, після чого перевіряє перші п'ять символів рядка на збіг з шаблоном a +. Потім перевіряє, що в рядку немає інших груп символів "a". Потім виконується перевірка до кінця рядка. Оскільки в рядку міститься один додатковий символ, перевірка виявляється невдалою. Цей негативний результат вимагає 9 порівнянь. Оброблювач регулярних виразів також зберігає інформацію про стан при збіги "a" (збіг 1), "aa" (збіг 2), "aaa" (збіг 3) і "aaaa" (збіг 4).

Потім він повертається до попередньо збереженого збігом 4. Далі встановлюється наявність додаткового символу "a", який призначається додаткової захопленої групі. Потім виконується перевірка до кінця рядка. Оскільки в рядку міститься один додатковий символ, перевірка виявляється невдалою. Цей негативний результат вимагає 4 порівнянь. Таким чином, всього виконано 13 порівнянь.

Потім він повертається до попередньо збереженого збігом 3. Він встановлює наявність двох додаткових символів "a", які призначаються додаткової захопленої групі. Однак перевірка на наявність закінчення рядка не проходить. Оброблювач повертається до збігу 3 і намагається зіставити два додаткових символу "a" з двома додатковими захопленими групами. Перевірка на наявність закінчення рядка не проходить. Для отримання цих неуспішних збігів потрібно 12 порівнянь. Таким чином, всього виконано 25 порівнянь.

Порівняння вхідного рядка з регулярним виразом триває таким же чином, поки обробник регулярних вирази не перебере всі можливі комбінації збігів, уклавши, що збігів немає. Через наявність вкладених квантіфікаторов це порівняння є операцією експоненційної складності O (2 n) де n - кількість символів вхідного рядка. Це означає, що в гіршому випадку вхідний рядок, що складається з 30 символів, вимагає за приблизними підрахунками 1 073 741 824 порівнянь, а вхідний рядок довжиною 40 символів посилання - 1 099 511 627 776 порівнянь. При використанні рядків такого або більшого розміру методи, які виконують регулярні вирази, можуть виконуватися дуже довго, перш ніж буде встановлено, що вхідні рядок не збігається з шаблоном регулярного виразу.

Починаючи з .NET Framework 4.5, можна задавати значення часу очікування, яке дорівнює значенню найдовшого інтервалу, необхідного оброблювачу регулярних виразів для виконання пошуку до першого збігу, поки він не припинить спроби знайти відповідність і не викличе виключення RegexMatchTimeoutException. Щоб задати інтервал очікування, вкажіть значення TimeSpan в конструкторі Regex. Regex (String, RegexOptions, TimeSpan) регулярних виразів примірника. Крім того, кожен статичний метод порівняння з шаблоном має перевантажену версію з параметром TimeSpan. який дозволяє вказати значення часу очікування. За замовчуванням інтервал часу очікування задається в Regex. InfiniteMatchTimeout і час очікування обробника регулярних виразів чи не закінчується.

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

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

Наприклад, наступний код викликає конструктор Regex. Regex (String, RegexOptions, TimeSpan) для створення екземпляра об'єкта Regex зі значенням часу очікування, рівним одній секунді. Шаблон регулярного виразу (a +) + $. який зіставляється з послідовністю з одного або декількох символів "a" в кінці рядка, відноситься до шаблонів з надмірним використанням пошуку з поверненням. Якщо створюється виняток RegexMatchTimeoutException. то інтервал часу очікування в даному прикладі збільшується до максимального значення, рівного трьом секундам. Після цього спроби знайти відповідність шаблону будуть перервані.