Improving Java Regular Expression Compile Time

>

> Should compiled code ran faster than interpreted

> scripts

>

That isn't how it works. The regex in java is 'compiled' when the code runs not when the java code is compiled.

> Any idea, anyone

I suspect you should create a real parser rather than trying to use a regex. It sounds like your regex is going to be hideously hard to maintain. And a parser would probably be faster anyways.

If speed is the only criteria and you don't care about maintainance then use perl.

jschella at 2007-7-15 16:01:27 >

> My regular expression is a very long one and the

> Pattern.compile just take too long. The worst case

> that I experience is 2949342 milliseconds.

Wow, that's pretty pathological. I was going to tell you that you were measuring something wrong, because I had written a test program that could compile a 1 Mb "or" pattern (10,000 words, 100 bytes per) in under 200 ms ... but then I noticed that your patterns have two "or" components, so reran my test, and got over 14 seconds to run with a smaller pattern.

My guess is that the RE compiler, rather than decomposing the RE into a tree, is taking the naive approach of translating it into a state machine, and replicating the second component for each path through the first component.

If you can create a simple hand-rolled parser, that may be your best option. However, it appears that your substrings aren't easily tokenized (some include spaces), so your best bet is to break the regexes into pieces at the "or" constructs, and use Pattern.split() to apply each piece sequentially.

import java.util.Random;

import java.util.regex.Pattern;

public class RegexTest

{

public static void main(String[] argv) throws Exception

{

long initial = System.currentTimeMillis();

String[] words = generateWords(10000);

//String patStr = buildRePortion(words);

//String patStr = buildRePortion(words) + " xxx ";

String patStr = buildRePortion(words) + " xxx " + buildRePortion(words);

long startCompile = System.currentTimeMillis();

Pattern pattern = Pattern.compile(patStr, Pattern.CASE_INSENSITIVE);

long finishCompile = System.currentTimeMillis();

System.out.println("Number of components = " + words.length);

System.out.println("ms to create pattern = " + (startCompile - initial));

System.out.println("ms to compile= " + (finishCompile - startCompile));

}

private final static String[] generateWords(int numWords)

{

String[] results = new String[numWords];

Random rnd = new Random();

for (int ii = 0 ; ii < numWords ; ii++)

{

char[] word = new char[20];

for (int zz = 0 ; zz < word.length ; zz++)

word[zz] = (char)(65 + rnd.nextInt(26));

results[ii] = new String(word);

}

return results;

}

private static String buildRePortion(String[] words)

{

StringBuffer sb = new StringBuffer("(?:");

for (int ii = 0 ; ii < words.length ; ii++)

{

sb.append(ii > 0 ? "|" : "")

.append(words[ii]);

}

sb.append(")");

return sb.toString();

}

}

kdgregorya at 2007-7-15 16:01:27 >

> Any way I am trying to datamine some information from

> many document using RE. But the compilation time

> takes too long.

>

> Any ideas?

Why do you use RE in the first place? RE is for finding patterns in text. From the pieces of your examples, you are not looking for patterns, you are doing dictionary lookup. RE for a dictionary implementation is equivalent to an unordered list. To implement a dictionary, the choice of data structure is HashSet, HashMap or trie.

dingjinga at 2007-7-15 16:01:27 >

> Before jumping on this guy telling him not to do

> do something, it would be good to know what he is

> doing or not. As I see his RE fragment, he is doing a

> frase matcher instead of a dictionary, and he wants

> to match them acording to meaning instead of exact

> words.

The two long long long (...|...|...|...|...|) patterns ARE dictionaries. I am not saying that the code can be implemented with ONE dictionary lookup. It actually needs 2 dictionary lookups and 1 pattern matching.

First, match pattern "(.+) me (.+) java".

Then do 2 dictionary lookups for group(1) and group(2).

Wouldn't it be much slower to do it in 3 steps than just match 1 big pattern? The answer is yes and no. If the (...|...|...|...|...|) sub-patterns are short, yes, 3-step implementation is slower. But we are talking about very very very long sub-patterns. Matching this part is linear complexity O(n). The 3-step implementation is constant complexity O(1).

dingjinga at 2007-7-15 16:01:27 >