RegEx медленно, когда не совпадают

Question

Это регулярное выражение запрос выполняется нормально, когда я не вставляйте никаких признаков того, что не в [,.] перед словом «здесь»:

RegEx.Replace("My products or something/else here ", "My ((?:[a-z']* ??)*?)\s*([,.]|$| here)", "") 

Но это будет очень-очень медленно (замораживать около 3-5 секунд или более), если я вставляю знак, который не находится в [,.] перед словом «здесь». Например я вставить знак '/' перед словом 'здесь':

RegEx.Replace("My products or something/else here ", "My ((?:[a-z']* ??)*?)\s*([,.]|$| here)", "") 

Проблема ушла, когда я добавить/к моему шаблону [,.]:

RegEx.Replace("My products or something/else here ", "My ((?:[a-z']* ??)*?)\s*([/,.]|$| here)", "") 

Но я хочу, чтобы мое регулярное выражение игнорировало знак/вместо соответствия знаку/в конце моего предложения. Почему эта проблема возникает и как ее решить?

Answer 1

Вы являетесь жертвой catastrophic backtracking. Эта часть:

(?:[a-z']* ??)*? 

может соответствовать словам в экспоненциальном количестве возможных комбинаций. Так как пространство не является обязательным, слово в одиночку else могут быть согласованы во всех этих вариаций (где круглые скобки указывают на то, что соответствует одной «например» внутренней группы):

(else) 
(els)(e) 
(el)(se) 
(el)(s)(e) 
(e)(lse) 
(e)(l)(se) 
(e)(ls)(e) 
(e)(l)(s)(e) 

И это взрывает для более длинных слов , и особенно целое предложение. Обычно проблема возникает всякий раз, когда у вас есть вложенное повторение, и неясно, где заканчивается одно повторение, а другое начинается. Затем, если нет совпадения, движок должен пройти через все эти случаи, прежде чем он сможет объявить об отказе. Если есть совпадение, откат обычно не нужен, и проблема остается незамеченной. Наилучшим решением является использование "unrolling-the-loop" pattern, чтобы сделать пространство обязательным в повторении:

"My ([a-z']*(?: [a-z']*)*?)\s*([,.]|$| here)" 

Теперь о том, что пространство является обязательным, каждый «экземпляр» повторяемого должен совпадать слово целиком, который должен решить проблему.