Java regular expression optimization tips

Question

I am new to Java Regular expression. We are using a pattern for matching a string. We are using this for validating a text field and it meets our requirements. But there is a performance issue in the matching.

Pattern : ([a-zA-Z0-9]+[ ]?(([_\-][a-zA-Z0-9 ])*)?[_\-]?)+

Input text should start with a-zA-Z0-9.
Space(single) is allowed between words
"_" and "-" are allowed but cannot be consecutive.

Our problem is, for certain input strings the CPU time goes high and causes hanging the threads. Also we get exceptions. Can anyone please help me to optimize the Pattern or suggest a new pattern to solve my issue.

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)

Are you pre-compiling (javalobby.org/forums/thread.jspa?threadID=16822&tstart=0) the regex? — Aravind Yarram
– Aravind Yarram, Commented Sep 30, 2011 at 7:34
@Pangea: pre-compiling the regex only saves the cost of creating a new Pattern object every time; the problem here is with the performance of the regex itself. (Anyway, it looks like the OP is already doing that; the exception is originating in Matcher's matches(), not String's.) — Alan Moore
– Alan Moore, Commented Sep 30, 2011 at 8:01
@dpkcv, is a_- _-z acceptable? In other words, can a hyphen be followed immediately by an underscore, or vice versa? Can a space be right next to a hyphen or underscore? — Alan Moore
– Alan Moore, Commented Sep 30, 2011 at 8:09

Tim Pietzcker · Accepted Answer · 2011-09-30 19:21:28Z

18

Your problem is catastrophic backtracking which you're getting because you have nested quantifiers. This starts becoming a problem when the text doesn't match the requirements because of the exponentially increasing number of permutations the regex engine has to go through to declare failure.

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

Reconstruct your regex like this:

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

Java, with explanation:

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");

Note that the string must not end in a space as per your requirements. In case you're wondering, \w is a shorthand for [A-Za-z0-9_].

edited Sep 30, 2011 at 19:21

answered Sep 30, 2011 at 7:43

Tim Pietzcker

337k59 gold badges520 silver badges572 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

michael667 Over a year ago

+1 for comments in regexp. I was not aware of that feature and will use it, too!

Narendra Yadala Over a year ago

stackoverflow.com/questions/7607250/…

Bohemian · Accepted Answer · 2011-09-30 10:38:31Z

6

Your regex allows for a phenomenon known as Catastrophic Backtracking.

Follow the link for a complete description, but briefly you have a combination of optional matching that means the evaluation must keep going back through every combination of preceding characters, leading to n! operations (I pretty sure about n!), which will quickly blow your stack.

Try this regex instead:

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

Explanation:

^(?!.*(__|--| )) means the entire input must not contain 2 adjacent _ or - or space (a better way of expressing "at most one space between words" - forget about words - check the spaces)
[a-zA-Z0-9][\w -]* means must have letter or number at start, the rest can be any combo of letters, numbers, underscores (\w = [a-zA-Z0-9_]), spaces and dashes (given the above two proviso)
[^ ]$ means doesn't end in a space (not stated, but seems reasonable - add other chars to the character class like - as you like - but dash if used must be first or last)

This regex won't cause catastrophic backtracking.

edited Sep 30, 2011 at 10:38

answered Sep 30, 2011 at 7:42

Bohemian♦

427k103 gold badges604 silver badges750 bronze badges

7 Comments

Tim Pietzcker Over a year ago

Um, your regex only checks if the first two characters aren't - or _, (or two spaces) and it also disallows -_. Then it requires that the string start exactly with a-zA-Z0-9. Furthermore, it allows any number of spaces between words.

Tim Pietzcker Over a year ago

Not quite. You forgot the character class, and the string may still end in spaces. Also, -_ is still not allowed (where I understand only __ and -- shouldn't be allowed, but my interpretation may be wrong - @dpkcv, please clarify). Oh, and better put the - at the end of the character class.

Bohemian Over a year ago

I see now that OP meant not __ or --, so I fixed it. Now my regex is way smaller, and I think better, than yours :) Nothing mentioned by OP not ending in spaces, but fine - I've prevented that

Tim Pietzcker Over a year ago

But it's still wrong. Spaces are only allowed between words, and you're still matching a-zA-Z0-9 literally. Oh, and the end anchor is missing... :)

Bohemian Over a year ago

@Ti what are you talking about a-zA-Z0-9? That's in the question as the first char definition

|

Alan Moore · Accepted Answer · 2011-09-30 14:54:09Z

3

I think this will be a lot easier to understand if you start with a smaller problem. The simplest way to match several words separated by spaces is this:

^\w+(?:[ ]\w+)*$

To enforce the rule about no consecutive hyphens or underscores, all you have to do is add them to the existing character class:

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

However, your regex explicitly allowed for them at the end of the string too, and mine doesn't. I'll assume that's okay and deal with it the same way you did:

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

Try that last regex and see if it works for you.

EDIT: The anchors, ^ and $, aren't really necessary if you use the matches() method, but they don't hurt either, and they do help communicate your intent.

edited Sep 30, 2011 at 14:54

answered Sep 30, 2011 at 9:29

Alan Moore

75.6k13 gold badges110 silver badges161 bronze badges

1 Comment

ridgerunner Over a year ago

+1 Best answer so far. Although it does not allow words to start or end on - or _, the OP was not at all clear about what is needed in this regard.

Brad Larson · Accepted Answer · 2012-10-11 18:03:37Z

3

digit pattern

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

char pattern

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

input field is compered with above two for below conditions * must have atleast one digit and char * can have only @,_,- as special chars not others

edited Oct 11, 2012 at 18:03

Brad Larson

170k45 gold badges401 silver badges574 bronze badges

answered Oct 10, 2012 at 7:15

divya

311 bronze badge

Comments

Narendra Yadala · Accepted Answer · 2011-09-30 14:03:16Z

I wanted to post this as a comment to Tim Pietzcker's answer but figured there won't be enough space there. While the regex given by Tim avoids catastrophic backtracking to some extent, it still has nested quantifiers which can cause a problem with a specific input text and cause StackOverflowException as shown below. I want to repeat that this answer is just a demonstration of the weird StackOverflowException and it is not supposed to be a rant on anyone's answer.

    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);
    }
}

Interesting. I was able to reproduce the stack overflow with my Java (Win32 build 1.6.0_24-b07). But there is nothing wrong with the (?:[ ][\w-]+)* expression - it does NOT result in catastrophic backtracking. In fact, in RegexBuddy, Tim's regex matches the 2001 count: "A A...A" test string in fewer steps than the non-SO version you provide here. Looks to me like a bug in the Java regex engine. Once again - Interesting!
It is possible that it is a problem with Java regex engine. Non-SO version will take more steps than the normal one because it does a lot of negative lookahead. I did measure the time using System.currentTimeMillis() and the non-SO version did well on 2 million character input ...it took around 500ms for completion.

Kris · Accepted Answer · 2011-09-30 07:44:00Z

0

You haven't posted any code but I can see that you run it in a web application. I guess optimization of the pattern won't help you much. Remember that the Matcher class is not thread safe.

Instances of this class are not safe for use by multiple concurrent threads

Try to compile your pattern in synchronized block and use reset() method of the Matcher class.

answered Sep 30, 2011 at 7:44

Kris

5,7923 gold badges29 silver badges47 bronze badges

1 Comment

Alan Moore Over a year ago

I don't think this has anything to do with concurrency. It's just a very poorly crafted regex (no offense intended, @dpkcv).

Collectives™ on Stack Overflow

Java regular expression optimization tips

6 Answers 6

2 Comments

7 Comments

1 Comment

Comments

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

7 Comments

1 Comment

Comments

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related