Почему регулярное выражение "[^ <] * <\\?" показывать экспоненциальное время, когда текст не имеет «<»?

Question

Используя библиотеку регулярных выражений ICU 4.0, я обнаружил, что следующее регулярное выражение показывает экспоненциальное время:

actual: "[^<]*<\?"
C code: "[^<]*<\\?"

Цель: найти "<?" где нет другого "<" перед ним </p>

При выполнении этого регулярного выражения на обычном тексте без символов «<», кажется, что оно занимает экспоненциальное время. Если в тексте есть хотя бы одно «<», то это быстро. Я не понимаю почему. </p>

Разве не должен совпадать требуемый символ "<?" предотвратить это от необходимости отказаться? Я бы подумал, что он попытается найти первое «<», а затем проверить остальное выражение. Если он не может найти «<», то он сдастся, потому что шаблон, очевидно, не может соответствовать. </p>

Это ошибка в регулярном выражении ICU или ожидается?

Answer 1

Вы найдете объяснение на Сопоставление регулярных выражений может быть простым и быстрым .
Как сказал MizardX, если совпадение не выполняется в позиции 0, двигатель попытается снова в позиции 1, 2 и т. Д. Если текст длинный, будьте готовы подождать некоторое время ...

Решение - закрепить выражение: "^[^<]*<\?"

Answer 2

Здесь вступают в игру собственнические квантификаторы и атомные группы. На Java я бы сделал это:

String regex = "[^<]*+<\\?";

или это:

String regex = "(?>[^<]*)<\\?";

В любом случае, после того, как часть [^<]* соответствует всем, что может, она отказывается возвращаться назад. Если следующая часть не может совпадать на следующей позиции, совпадение не выполняется. У Java и PHP есть и функции, и у .NET есть атомарные группы; Я не знаю о других языках.

Answer 3

К сожалению, это ожидается. От RegularExpressions.info

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

При применении регулярного выражения к строке, двигатель запускается с первого символа строки. Он попробует все возможные перестановки регулярного выражения в первом характер.
Только если все возможности были опробованы и найдены сбои, двигатель продолжит работу со вторым символом в тексте.
Опять же, он попробует все возможные перестановки регулярного выражения, в точности в том же порядке.
В результате механизм, направленный в регулярные выражения, вернет крайнее левое совпадение.

Итак, на ABC он пытается «ABC», терпит неудачу, пытается «BC», терпит неудачу, затем пытается «C» и терпит неудачу. Это не было бы так неприятно, если бы не тот факт, что жадный "[^ <]" на самом деле добился успеха до самого конца, где он не находит <? </p>

Answer 4

Движок регулярных выражений не настолько умен. Он будет пытаться сопоставить с каждую позицию и каждый поиск времени для <? с конца и возвращаться обратно до начала попытки сопоставления. Это дает квадратичную временную сложность, O ( n ² ).

Answer 5

Я не эксперт в том, как на самом деле работают движки регулярных выражений, но я знаю, что некоторые (все?) Являются жадными и постараются найти как можно больше совпадений как можно раньше. Предположим, у вас есть строка s, которую вы пытаетесь сопоставить, в которой нет символов '<'. Сначала он будет соответствовать части [^<]* регулярного выражения, по существу совпадая со всем от s[0] до s[n-1] (s имеет нулевой индекс и не имеет тонкостей c-строки, так что это вся строка). Затем произойдет сбой следующего элемента в шаблоне (символ '<'). Затем он вернется к совпадению [^<]* с s[0] до s[n-2], попытается сопоставить '<' и снова потерпит неудачу. Это будет повторяться до тех пор, пока не будет соответствовать строке длины 0 в позиции 0 (примечание * соответствует нулю или более повторений, и этот последний случай равен нулю повторений). Таким образом, таким образом, он определит, что запуск в позиции 0 не может привести к успешному совпадению, поэтому он будет повторять вышеизложенное, на этот раз начав диапазон совпадающих символов с s[1], и снова потерпит неудачу после исчерпания всех таких диапазонов. Затем он начнёт с позиции 2 и так далее, пока не попытается найти совпадение после последнего символа. Тогда он сдастся.

Edit: Ваше регулярное выражение будет по существу соответствовать любой части строки, которая заканчивается на <? и не содержит другой <, например, в <<? она соответствует <? и в ba<abc<?def, она соответствует abc<?. Некоторые из других предложенных предложений будут вести себя по-другому. В частности, ^[^<]*<\? не будет ничего совпадать в этих двух примерах.

Answer 6

Perl re dump

Извините за такой длинный пост. Примеры выходных данных были отредактированы для ясности.

Двигатель Perl regex использует ярлыки. Так что мой первый прогон не принес ничего такого полезного.

perl -Mre=debug -e' "abcdefghijklm" =~ /[^<]*<[?]/; '

Compiling REx "[^<]*<[?]"
Final program:
   1: STAR (13)
   2:   ANYOF[\0-;=-\377{unicode_all}] (0)
  13: EXACT <<?> (17)
  17: END (0)
floating "<?" at 0..2147483647 (checking floating) minlen 2 
Guessing start of match in sv for REx "[^<]*<[?]" against "abcdefghijklm"
Did not find floating substr "<?"...
Match rejected by optimizer
Freeing REx: "[^<]*<[?]"

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

perl -Mre=debug -e' "ab<?" =~ /[^<]*(?!<)<[?]/; '

Compiling REx "[^<]*(?!<)<[?]"
Final program:
   1: STAR (13)
   2:   ANYOF[\0-;=-\377{unicode_all}] (0)
  13: UNLESSM[0] (19)
  15:   EXACT <<> (17)
  17:   SUCCEED (0)
  18: TAIL (19)
  19: EXACT <<?> (23)
  23: END (0)
floating "<?" at 0..2147483647 (checking floating) minlen 2 
Guessing start of match in sv for REx "[^<]*(?!<)<[?]" against "ab<?"
Found floating substr "<?" at offset 2...
Guessed: match at offset 0
Matching REx "[^<]*(?!<)<[?]" against "ab<?"

# Start at first pos()
#      |
#      V
   0 <> <ab<?>               |  1:STAR(13)
                                  ANYOF[\0-;=-\377{unicode_all}] can match 2 times out of 2147483647...
   2 <ab> <<?>               | 13:  UNLESSM[0](19)
   2 <ab> <<?>               | 15:    EXACT <<>(17)
   3 <ab<> <?>               | 17:    SUCCEED(0)
                                      subpattern success...
                                    failed...
# try with one fewer [^<]*
   1 <a> <b<?>               | 13:  UNLESSM[0](19)
   1 <a> <b<?>               | 15:    EXACT <<>(17)
                                      failed...
# try with one fewer [^<]* again
   1 <a> <b<?>               | 19:  EXACT <<?>(23)
                                    failed...
# try with zero [^<]*
   0 <> <ab<?>               | 13:  UNLESSM[0](19)
   0 <> <ab<?>               | 15:    EXACT <<>(17)
                                      failed...
   0 <> <ab<?>               | 19:  EXACT <<?>(23)
                                    failed...
                                  failed...

# Start at second pos()
#       |
#       V
   1 <a> <b<?>               |  1:STAR(13)
                                  ANYOF[\0-;=-\377{unicode_all}] can match 1 times out of 2147483647...
   2 <ab> <<?>               | 13:  UNLESSM[0](19)
   2 <ab> <<?>               | 15:    EXACT <<>(17)
   3 <ab<> <?>               | 17:    SUCCEED(0)
                                      subpattern success...
                                    failed...
   1 <a> <b<?>               | 13:  UNLESSM[0](19)
   1 <a> <b<?>               | 15:    EXACT <<>(17)
                                      failed...
   1 <a> <b<?>               | 19:  EXACT <<?>(23)
                                    failed...
                                  failed...

# Start at third and final pos()
#        |
#        V
   2 <ab> <<?>               |  1:STAR(13)
                                  ANYOF[\0-;=-\377{unicode_all}] can match 0 times out of 2147483647...
   2 <ab> <<?>               | 13:  UNLESSM[0](19)
   2 <ab> <<?>               | 15:    EXACT <<>(17)
   3 <ab<> <?>               | 17:    SUCCEED(0)
                                      subpattern success...
                                    failed...
                                  failed...
Match failed
Freeing REx: "[^<]*(?!<)<[?]"

Если вы пропустили его, он пытается найти соответствие '[^<]*' всеми возможными способами, прежде чем потерпеть неудачу. Представьте, что вы пытались запустить это сопоставление с большим файлом, только чтобы узнать, что последние два символа не были '<?'.

Лучше использовать максимальное совпадение и начало строки, утверждение нулевой ширины.

^ - это BOL (начало строки) в следующем тексте.

perl -Mre=debug -e' "abcdefghijklm<?" =~ /^[^<]*+(?!<)<[?]/; '

Compiling REx "^[^<]*+(?!<)<[?]"
Final program:
   1: BOL (2)
   2: SUSPEND (18)
   4:   STAR (16)
   5:     ANYOF[\0-;=-\377{unicode_all}] (0)
  16:   SUCCEED (0)
  17: TAIL (18)
  18: UNLESSM[0] (24)
  20:   EXACT <<> (22)
  22:   SUCCEED (0)
  23: TAIL (24)
  24: EXACT <<?> (28)
  28: END (0)
floating "<?" at 0..2147483647 (checking floating) anchored(BOL) minlen 2 
Guessing start of match in sv for REx "^[^<]*+(?!<)<[?]" against "abcdefghijklm<?"
Found floating substr "<?" at offset 13...
Guessed: match at offset 0
Matching REx "^[^<]*+(?!<)<[?]" against "abcdefghijklm<?"
   0 <> <abcdefghij>         |  1:BOL(2)
   0 <> <abcdefghij>         |  2:SUSPEND(18)
   0 <> <abcdefghij>         |  4:  STAR(16)
                                    ANYOF[\0-;=-\377{unicode_all}] can match 13 times out of 2147483647...
  13 <defghijklm> <<?>       | 16:    SUCCEED(0)
                                      subpattern success...
  13 <defghijklm> <<?>       | 18:UNLESSM[0](24)
  13 <defghijklm> <<?>       | 20:  EXACT <<>(22)
  14 <defghijklm<> <?>       | 22:  SUCCEED(0)
                                    subpattern success...
                                  failed...
Match failed
Freeing REx: "^[^<]*+(?!<)<[?]"

Обратите внимание, что это не удалось намного быстрее, чем в предыдущем примере.