Проверка регулярного выражения занимает слишком много времени c #

Question

У меня есть сценарий использования регулярных выражений для проверки.

Вот текстовый формат, который мне нужно проверить, выглядит примерно так:

Допустимый текст

проверка имени + компания abc def + телефон 3434 + проверка транспортного средства + заинтересованный ггг + приглашенный zzz

Неверный текст:

имя te% st + компания + телефон 3434 + проверка транспортного средства + заинтересованный ггг + приглашенный zzz

Правила

1. В тексте не должно быть других символов, таких как%в выше.
2. Кроме того, первое слово должно следовать за пробелом, после него должен быть какой-то текст, а затем знак +.

Вот регулярное выражение, которое я написал:

^(([a-z]*[A-Z]*\s?)+(\w*\s*)*\+)*$

Проблема, с которой я сталкиваюсь, заключается в том, что когда текст действителен, Regex.Match(text) немедленно возвращает true.Но когда я добавляю в текст какой-то другой символ, который недопустим, это занимает слишком много времени, и отладчик никогда не возвращается.

Answer 1

недействительно, это занимает слишком много времени и отладчик никогда не возвращается.

Вы просите синтаксический анализатор рассмотреть слишком много сценариев, и он должен исключить все из них, прежде чем вернуться; отсюда и медлительность.

---

Предложение

Использование *, что означает ноль или более вхождений заставляет анализатор регулярных выражений переосмыслить (возврат) о других возможных совпадениях.

С точки зрения шахмат, существуют буквально миллионы возможных комбинаций. Использование * - это все равно что сказать, дай мне каждый возможный ход. Но нам нужны только подходящие шаги ... То же самое верно и в отношении кузнечных операций в регулярных выражениях; держи его до минимума.

1. С * вместо этого предпочитайте использовать +, если вы действительно знаете, что будет 1 или более предметов, а не ноль. Он сводит backtracking к минимуму и ускоряет разбор.

2. Для ваших сценариев неудач, вместо того, чтобы пытаться сопоставить мир, почему бы не провалить совпадение, проверив сначала инвалидов? Это можно сделать, например, ^(?! ) шаблон. Итак, в вашем правиле упоминается сбой не найденных символов, поэтому сначала укажите это ^(?!.+%). Это говорит о том, что если в тексте есть % где-то , то совпадение будет неудачным.

3. Как только # 2 закончен, просто сосредоточьтесь на правильных шаблонах, которые дают наилучший сценарий.

---

Ваш пример данных проблематичен, но в духе того, что вы хотите в качестве отправной точки, я бы начал с этого паттерна:

^(?!.+%)(\w+\s\w+\s\+\w+\s?)+

Что говорит о неудаче на %, тогда должен быть 1 или более шаблонов (пространство слов пространство слов + слово и возможный пробел)

Answer 2

Почему не простой парсер? Разделите на символ '+', затем оцените каждую фразу. Я предполагаю, что первое слово перед пробелом является ключом, а остаток - значением. Есть также регулярное выражение, которое проверяет правильность символов; не буквенно-цифровой вызовет исключение.

var working = "name test +company abc def +phone 3434 +vehicle test + interested yyy +invited zzz";

if (System.Text.RegularExpressions.Regex.IsMatch(working, "[^a-zA-Z0-9 +]"))
{
    throw new InvalidOperationException();
}

var values = working.Split('+').Select(x => x?.Trim() ?? string.Empty);

foreach (var phrase in values)
{
    string left, right;

    var space = phrase.IndexOf(' ');
    if (space > 0)
    {
        left = phrase.Substring(0, space)?.Trim() ?? string.Empty;
        right = phrase.Substring(space + 1, phrase.Length - space - 1)?.Trim() ?? string.Empty;

        Console.WriteLine("left: [" + left + "], right: [" + right + "]");
    }
}

Выход на консоль:

left: [name], right: [test]
left: [company], right: [abc def]
left: [phone], right: [3434]
left: [vehicle], right: [test]
left: [interested], right: [yyy]
left: [invited], right: [zzz]

Запуск вышеуказанного с недопустимым символом вызывает исключение:

var working = "na%me test +company abc def +phone 3434 +vehicle test + interested yyy +invited zzz";  

...

Operation is not valid due to the current state of the object.

Answer 3

Вместо того, чтобы пытаться придумать выражение "всегда работает", почему бы вам вообще не перефразировать решение без регулярных выражений.обрабатывать большие объемы текста, но в противном случае это должно быть хорошо.