StackOverflowError при сопоставлении большого ввода с использованием RegEx

Я получил StackOverflowError при сопоставлении результата с использованием шаблона RegEx.

Шаблон (\d\*?(;(?=\d))?)+. Это регулярное выражение используется для проверки ввода:

12345;4342;234*;123*;344324

Вход представляет собой строку, состоящую из значений (только цифры), разделенных ;. Каждое значение может включать один * в конце (используется в качестве подстановочного знака для других совпадений). В конце строки нет ;.

Проблема в том, что это регулярное выражение отлично работает с небольшим количеством значений. Но когда количество значений слишком велико (более 300), это вызовет StackOverflowError.

final String TEST_REGEX = "(\\d\\*?(;(?=\\d))?)+";

// Generate string
StringBuilder builder = new StringBuilder();
int number = 123456;
for (int count = 1; count <= 300; count++) {
    builder.append(Integer.toString(number).concat(";"));
    number++;
}
builder.deleteCharAt(builder.lastIndexOf(";"))

builder.toString().matches(TEST_REGEX); //<---------- StackOverflowError

И трассировка стека:

java.lang.StackOverflowError
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    ...

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

Я очень ценю любое предложение, так как у меня нет опыта работы с RegEx.


java regex stack-overflow lookahead
person Genzer    schedule 26.02.2013    source источник

Ответы (3)


arrow_upward
7
arrow_downward

Прежде чем решить проблему с StackOverflowError...

  1. #P2# <блочная цитата> #P3# #P4#

  2. Ваше регулярное выражение будет делать ненужный возврат на несоответствующий ввод.

  3. Java использует один кадр стека для каждого повторения группы (\d\*?(;(?=\d))?) (которая повторяется 1 или более раз +).

Правильным регулярным выражением будет:

\d+\*?(?:;\d+\*?)*

Обратите внимание, что это отклонит *, что не слишком ясно из вашего требования, хотите ли вы принять или отклонить это.

Это не устраняет проблему StackOverflow, поскольку каждое повторение группы (?:;\d+\*?) также будет использовать стек. Чтобы исправить это, сделайте все квантификаторы притяжательными, поскольку нет необходимости в возврате, поскольку грамматика не является двусмысленной:

\d++\*?+(?:;\d++\*?+)*+

Ввод в строковый литерал:

"\\d++\\*?+(?:;\\d++\\*?+)*+"

Я протестировал приведенное выше регулярное выражение с совпадающими и несовпадающими входными данными, которое содержит более 3600 токенов (разделенных ;).

Сноска

1: регулярное выражение 101 использует вариант PCRE, который немного отличается от варианта регулярного выражения Java. Однако функции, используемые в вашем регулярном выражении, являются общими для них, поэтому не должно быть расхождений.

Приложение

  • На самом деле, из моего тестирования с вашим регулярным выражением (\d\*?(;(?=\d))?)+ (которое неверно в соответствии с вашими требованиями), кажется, что внешнее наиболее + притяжательное ++ решает проблему StackOverflowError, по крайней мере, в моем тестировании с примерно 3600 токенами ( разделенные ;, длина строки составляет около 20 тыс. символов). Это также не вызывает длительного времени выполнения при тестировании несовпадающей строки.

  • В моем решении сделать квантификатор * для группы (?:;\d+\*?) притяжательным достаточно, чтобы разрешить StackOverflowError.

    "\\d+\\*?(?:;\\d+\\*?)*+"

    Тем не менее, я делаю все собственником, чтобы быть в безопасности.

person nhahtdh    schedule 26.02.2013
comment
Я знал те случаи, которые пропускает мой исходный шаблон, поскольку я не добавлял эти случаи в тесты. - person Genzer; 26.02.2013
comment
Удивительно, ваше предложение только что прошло все мои тесты, включая тест для StackOverflowError. Я не знал о possessive материале. Не могли бы вы предложить какие-либо ссылки на RegEx, которые я могу улучшить? - person Genzer; 26.02.2013
comment
@Genzer: docs.oracle.com/javase/tutorial/essential/regex /quant.html объясняет притяжательный квантификатор, но чтобы понять, вы должны понимать, как выполняется сопоставление. Если это не помогает, проверьте это: regular-expressions.info/possessive.html . Притяжательный квантификатор особенно полезен, когда вы выполняете сопоставление, которое не требует возврата, если вы пишете обычный код. - person nhahtdh; 26.02.2013

arrow_upward
1
arrow_downward

Ваше регулярное выражение немного неэффективно и не соответствует вашему описанию. У вас есть '\d\*?' - это одна цифра, за которой следует необязательный *. Затем необязательно ';(?=\d)' - ';' с опережающей цифрой. Строка '1*2*3*' будет соответствовать вашему регулярному выражению, но не вашему описанию. Вы можете использовать следовать регулярному выражению. Он соответствует вашему вводу и немного более эффективен.

final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+";

Он пройдет тест, когда количество ‹ 300, но все еще не пройдено для больших значений. Используйте операцию с простой строкой, например indexOf и substring, чтобы проверить ввод.

person ijrandom    schedule 26.02.2013
comment
Спасибо за ваше регулярное выражение. Да, я только что обнаружил некоторые ошибки в своем регулярном выражении. Но настоящая проблема в том, что StackOverflowError все еще возникает. - person Genzer; 26.02.2013

arrow_upward
0
arrow_downward

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

По сути, вы начинаете свою программу с опцией -Xss. Например, -Xss4m Когда я начал ваш код с -Xss4m, ваша программа работала без переполнения стека для меня (она возвращает true).

person Daniel Kaplan    schedule 26.02.2013
comment
Спасибо за предложение. Но на самом деле я не хочу настраивать параметры JVM, но я рассмотрю это как последнее средство. - person Genzer; 26.02.2013