100% загрузка процессора с регулярным выражением в зависимости от длины ввода

Question

Я пытаюсь придумать регулярное выражение в Python, которое должно соответствовать любому символу, но избегать трех или более последовательных запятых или точек с запятой.Другими словами, допускается только до двух последовательных запятых или точек с запятой.

Итак, вот что у меня в данный момент есть:

^(,|;){,2}([^,;]+(,|;){,2})*$

И, похоже, работает как ожидалось:1007 *

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

>>> r.match('foo, bar, baz,, foo')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, bar, baz,, fooooo, baaaaar')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,')
<_sre.SRE_Match object at 0x7f23af8407e8>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,')
<_sre.SRE_Match object at 0x7f23af840750>
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,')
>>> r.match('foo, bar, baz,, fooooo, baaaaar,,,,')
>>> r.match('foo, bar, baz,, fooooo, baaaaar, baaaaaaz,,,,')

И, наконец, он полностью застревает на этом этапе изагрузка процессора возрастает до 100%.

Я не уверен, можно ли оптимизировать регулярное выражение или что-то еще, любая помощь приветствуется.

Answer 1

Вы сталкиваетесь с катастрофическим возвратом .

Причина этого в том, что вы сделали разделители необязательными, и, следовательно, часть [^,;]+ (которая сама по себе повторяется).группа) вашего регулярного выражения будет пытаться загрузить множество перестановок (из baaaaaaaz), прежде чем, наконец, придется признать ошибку при столкновении с более чем двумя запятыми.

RegexBuddy прерывает попытку сопоставления после 1.000.000 шагов движка регулярных выражений с вашей последней тестовой строкой.Python будет продолжать попытки.

Представьте себе строку baaz,,,:

При попытке вашего регулярного выражения движок регулярных выражений должен проверить все это:

1. baaz,,<failure>
2. baa + z,,<failure>
3. ba + az,,<failure>
4. ba + a + z,,<failure>
5. b + aaz,,<failure>
6. b + aa + z,,<failure>
7. b + a + az,,<failure>
8. b + a + a + z,,<failure>

до объявления общего сбоя.Посмотрите, как это растет экспоненциально с каждым дополнительным символом?

Такое поведение можно избежать с помощью собственнических квантификаторов или атомных групп, которые, к сожалению, не поддерживаются текущим движком регулярных выражений Python.Но вы можете легко выполнить обратную проверку:

if ",,," in mystring or ";;;" in mystring:
    fail()

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

Answer 2

Я думаю, что следующее должно делать то, что вы хотите:

^(?!.*[,;]{3})

Это не удастся, если строка содержит три или более , или ; в строке. Если вы действительно хотите, чтобы он соответствовал символу, добавьте . в конце.

Используется отрицательный прогноз , что приведет к сбою всего совпадения, если регулярное выражение .*[,;]{3} будет соответствовать.

Answer 3

Попробуйте это регулярное выражение:

^([^,;]|,($|[^,]|,[^,])|;($|[^;]|;[^;]))*$

Совпадение повторяется:

• один единственный символ, который не является ни ,, ни ;, ни
• a ,, за которым не следует другой ,, или ,,, за которым не следует другой ,, или
• a ;, за которым не следует другой ;, или ;;, за которым не следует другой ;

пока не будет достигнут конец. Это очень эффективно, так как рано выходит из строя без особого возврата.

Answer 4

Как насчет этой идеи, сопоставьте те, которые имеют шаблон, который вам не нужен ".+,,," В Python оставьте только те, которые не соответствуютДолжно быть быстро