Советы по оптимизации регулярных выражений Java - PullRequest
Новая
       0

Советы по оптимизации регулярных выражений Java

11 голосов
/ 30 сентября 2011

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

Шаблон: ([a-zA-Z0-9]+[ ]?(([_\-][a-zA-Z0-9 ])*)?[_\-]?)+

  1. Вводимый текст должен начинаться с a-zA-Z0-9.
  2. Пробел(один) допускается между словами
  3. "_" и "-" разрешены, но не могут быть последовательными.

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

Exception details                              
============================================                           
Hung thread details, all the same:
[9/28/11 11:40:07:320 CDT] 00000003 ThreadMonitor W   WSVR0605W: Thread "WebContainer : 26" (0000004f) has been active for 709755 mi
lliseconds and may be hung.  There is/are 1 thread(s) in total in the server that may be hung.
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3938)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3801)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3801)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.match(Pattern.java:4307)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$BranchConn.match(Pattern.java:4090)
        at java.util.regex.Pattern$GroupTail.match(Pattern.java:4239)
        at java.util.regex.Pattern$GroupCurly.match0(Pattern.java:4006)
        at java.util.regex.Pattern$GroupCurly.match(Pattern.java:3928)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Branch.match(Pattern.java:4124)
        at java.util.regex.Pattern$Ques.match(Pattern.java:3703)
        at java.util.regex.Pattern$Curly.match0(Pattern.java:3794)
        at java.util.regex.Pattern$Curly.match(Pattern.java:3756)
        at java.util.regex.Pattern$GroupHead.match(Pattern.java:4180)
        at java.util.regex.Pattern$Loop.matchInit(Pattern.java:4323)
        at java.util.regex.Pattern$Prolog.match(Pattern.java:4263)
        at java.util.regex.Matcher.match(Matcher.java:1139)
        at java.util.regex.Matcher.matches(Matcher.java:514)

Ответы [ 6 ]

17 голосов
/ 30 сентября 2011

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

([a-zA-Z0-9]+[ ]?(([_\-][a-zA-Z0-9 ])*)?[_\-]?)+
                                     ^         ^
                                     |         repetition
                                     repetition

Восстановите свое регулярное выражение следующим образом: 

(?i)^(?!.*(?:--|__))[A-Z0-9][\w-]*(?: [\w-]+)*$

Java, с объяснением: 

boolean foundMatch = subjectString.matches(
    "(?ix)      # Case-insensitive, multiline regex:\n" +
    "^          # Start of string\n" +
    "(?!        # Assert that it's impossible to match\n" +
    " .*        # any number of characters\n" +
    " (?:--|__) # followed by -- or __\n" +
    ")          # End of lookahead assertion\n" +
    "[A-Z0-9]   # Match A-Z, a-z or 0-9\n" +
    "[\\w-]*    # Match 0 or more alnums/dash\n" +
    "(?:        # Match the following:\n" +
    " [\\ ]     # a single space\n" +
    " [\\w-]+   # followed by one or more alnums or -\n" +
    ")*         # any number of times\n" +
    "$          # End of string");

Обратите внимание, что строка не должна заканчиваться пробелом в соответствии с вашими требованиями. Если вам интересно, \w это сокращение от [A-Za-z0-9_].

6 голосов
/ 30 сентября 2011

Ваше регулярное выражение учитывает явление, известное как Катастрофическое возвращение назад .

Перейдите по ссылке для получения полного описания, но вкратце у вас есть комбинация необязательного соответствия, которая означает, что оценка должна продолжать повторяться через каждую комбинацию предшествующих символов, что приводит к n! операциям (я довольно уверен насчет n!), который быстро унесет ваш стек.

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

^(?!.*(__|--|  ))[a-zA-Z0-9][\w -]*(?<! )$

Пояснение:

  • ^(?!.*(__|--| )) означает, что весь ввод не должен содержать 2 соседних _ или - или пробела (лучший способ выразить «не более одного пробела между словами» - забудьте о словах - проверьте пробелы)
  • [a-zA-Z0-9][\w -]* означает, что в начале должна быть буква или цифра, остальные могут быть любой комбинацией букв, цифр, подчеркиваний (\w = [a-zA-Z0-9_]), пробелов и тире (с учетом двух приведенных выше условий)
  • [^ ]$ означает, что не заканчивается пробелом (не указано, но кажется разумным - добавьте другие символы в класс символов, например -, как вам нравится - но дефис, если он используется, должен быть первым или последним)

Это регулярное выражение не вызовет катастрофического возврата.

3 голосов
/ 10 октября 2012

комбинация цифр 

^(([\\@|\\-|\\_]*([0-9]+))+)*(([\\@|\\-|\\_])+)*$

комбинация символов 

(([\\@|\\-|\\_]*([a-zA-Z]+))+)*(([\\@|\\-|\\_])+)*$

поле ввода конкурирует с двумя выше для следующих условий * должно иметь хотя бы одну цифру, а char * может иметь только @, _, - как особые символы, не другие

3 голосов
/ 30 сентября 2011

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

(?i)^[A-Z0-9]+(?:[ _-][A-Z0-9]+)*$

Однако ваше регулярное выражение явно разрешено для них на конце строки, а мое - нет.Я предполагаю, что все в порядке, и поступлю так же, как вы: 

(?i)^[A-Z0-9]+(?:[ _-][A-Z0-9]+)*[_-]?$

Попробуйте это последнее регулярное выражение и посмотрите, работает ли оно для вас.

РЕДАКТИРОВАТЬ: Якоря, ^ и $, на самом деле не нужны, если вы используете метод matches(), но они также не причиняют вреда, и они помогают сообщить ваше намерение.

2 голосов
/ 30 сентября 2011

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

    public class CatastrophicBacktrackingRegexRemedy {
    public static void main(String[] args) {
        regexWithNoStackOverflow();
        regexCausingStackOverflow();
    }

    /**
     * Stackoverflow is caused on a specific input, 
     * In this case "A " repeated about 1000 times.
     * This is because of the nested quantifier (?:[\\ ][\\w-]+)*
     */
    private static void regexCausingStackOverflow() {
        StringBuilder subjectStringBuilder = new StringBuilder();
        String subjectString = "A ";
        for (int i = 0; i < 1000; i++) {
            subjectStringBuilder.append(subjectString);
        }
        subjectStringBuilder.append("A");
        //2001 character input
        System.out.println("Input length :" + subjectStringBuilder.length());
        //This causes stackoverflow exception on a string with 2001 characters 
        //on my JVM
        boolean foundMatch = subjectStringBuilder.toString().matches(
                "(?ix)        # Case-insensitive, multiline regex:\n"
                + "^          # Start of string\n"
                + "(?!        # Assert that it's impossible to match\n"
                + " .*        # any number of characters\n"
                + " (?:--|__) # followed by -- or __\n"
                + ")          # End of lookahead assertion\n"
                + "[A-Z0-9]+  # Match A-Z, a-z or 0-9\n"
                + "(?:        # Match the following:\n"
                + " [\\ ]     # a single space\n"
                + " [\\w-]+   # followed by one or more alnums or -\n"
                + ")*         # any number of times\n"
                + "$          # End of string");
        //This will not be printed because of exception in the matches method
        System.out.println("Is match found? " + foundMatch);
    }

    /**
     * Stackoverflow can be avoided by modifying the negative lookahead 
     * and removing the  nested quantifiers as show below.
     */
    private static void regexWithNoStackOverflow(){
        StringBuilder subjectStringBuilder = new StringBuilder();
        String subjectString = "A ";
        for (int i = 0; i < 1000000; i++) {
            subjectStringBuilder.append(subjectString);
        }
        //returns match = true
        subjectStringBuilder.append("A");
        //uncomment following and it will give match = false (space in the end)
        //subjectStringBuilder.append("A A ");
        //uncomment following and it will give match = false (multiple spaces)
        //subjectStringBuilder.append("A  A");
        //2000001 character input
        System.out.println("Input length :" + subjectStringBuilder.length());
        boolean foundMatch = subjectStringBuilder.toString().matches(
        "(?ix)                      # Case-insensitive, multiline regex:\n"
        + "^                        # Start of string\n"
        + "(?!                      # Assert that it's impossible to match\n"
        + " .*                      # any number of characters\n"
        + " (?:--|__|\\s{2,}|\\s+$) # followed by -- or __ or more than a " 
        + "                         # single space or a space in the end\n"
        + ")                        # End of lookahead assertion\n"
        + "[A-Z0-9]+                # Match A-Z, a-z or 0-9\n"
        + "(?:                      # Match the following:\n"
        + " [\\s\\w-]               # followed by a space or alnum or -\n"
        + ")*                       # any number of times\n"
        + "$                        # End of string");
        System.out.println("Is match found? " + foundMatch);
    }
}
0 голосов
/ 30 сентября 2011

Вы не опубликовали код, но я вижу, что вы запускаете его в веб-приложении. Я думаю, что оптимизация шаблона не сильно вам поможет. Помните, что класс Matcher не является потокобезопасным.

Экземпляры этого класса не безопасны для использования несколькими одновременными нити

Попробуйте скомпилировать ваш шаблон в синхронизированном блоке и использовать метод reset () класса Matcher.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...