RegEx to find URLs in HTML takes 25 seconds in Java/Android

Question

In Android/Java, given a website's HTML source code, I would like to extract all XML and CSV file paths.

What I am doing (with RegEx) is this:

final HashSet<String> urls = new HashSet<String>();
final Pattern urlRegex = Pattern.compile(
        "[-a-zA-Z0-9+&@#/%?=~_|!:,.;]*[-a-zA-Z0-9+&@#/%=~_|].(xml|csv)");
final Matcher url = urlRegex.matcher(htmlString);
while (url.find()) {
    urls.add(makeAbsoluteURL(url.group(0)));
}

public String makeAbsoluteURL(String url) {
    if (url.startsWith("http://") || url.startsWith("http://")) {
        return url;
    }
    else if (url.startsWith("/")) {
        return mRootURL+url.substring(1);
    }
    else {
        return mBaseURL+url;
    }
}

Unfortunately, this runs for about 25 seconds for an average website with normal length. What is going wrong? Is my RegEx just bad? Or is RegEx just so slow?

Can I find the URLs faster without RegEx?

Edit:

The source for the valid characters was (roughly) this answer. However, I think the two character classes (square brackets) must be swapped so that you have a more limited character set for the first char of the URL and a broader character class for all remaining chars. This was the intention.

Answer 1

Your regex is written in a way that makes it slow for long inputs. The * operator is greedy.

For instance for input: http://stackoverflow.com/questions/19019504/regex-to-find-urls-in-html-takes-25-seconds-in-java-android.xml

The [-a-zA-Z0-9+&@#/%?=~_|!:,.;]* part of the regex will consume the whole string. It will then try to match the next character group, which will fail (since whole string is consumed). It will then backtrack in match of first part of the regex by one character and try to match the second character group again. It will match. Then it will try to match the dot and fail because the whole string is consumed. Another backtrack etc...

In essence your regex is forcing a lot of backtracking to match anything. It will also waste a lot of time on matches that have no way of succeeding.

For word forest it will first consume whole word in the first part of expression and then repeatedly backtrack after failing to match the rest of expression. Huge waste of time.

Also:

• the . in regex is unescaped and it will match ANY character.
• url.group(0) is redundant. url.group() has same meaning

In order to speed up the regex you need to figure out a way to reduce the amount of backtracking and it would also help if you had a less general start of the match. Right now every single word will cause matching to start and generally fail. For instance typically in html all the links are inside 2 ". If that's the case you can start your matching at " which will speed it up tremendously. Try to find a better start of the expression.

Answer 2

I've nothing the say in the theoretical overview that U Mad did, he highlighted everything I'd noticed.

What I would like to suggest you, considering what are you look for with the RE, is to change the point of view of your RE :)

You are looking for xml and csv files, so why don't you reverse the html string, for example using:

new StringBuilder("bla bla bla foo letme/find.xml bla bla").reverse().toString()

after that you could look for the pattern:

final Pattern urlRegex = Pattern.compile(
    "(vsc|lmx)\\.[-a-zA-Z0-9+&@#/%=~_|][-a-zA-Z0-9+&@#/%?=~_|!:,.;]*");

urlRegex pattern could be refined as U Mad has already suggested. But in this way you could reduce the number of failed matches.

Answer 3

Would suggest only using the regex to find file extensions (.xml or .csv). This should be a lot faster and when found, you can look backwards, examining each character before and stop when you reach one that couldn't be in a URL - see below:

final HashSet<String> urls = new HashSet<String>();
final Pattern fileExtRegex = Pattern.compile("\\.(xml|csv)");
final Matcher fileExtMatcher = fileExtRegex.matcher(htmlString);

// Find next occurrence of ".xml" or ".csv" in htmlString
while (fileExtMatcher.find()) {
    // Go backwards from the character just before the file extension
    int dotPos = fileExtMatcher.start() - 1;
    int charPos = dotPos;
    while (charPos >= 0) {
        // Break if current character is not a valid URL character
        char chr = htmlString.charAt(charPos);
        if (!((chr >= 'a' && chr <= 'z') ||
              (chr >= 'A' && chr <= 'Z') ||
              (chr >= '0' && chr <= '9') ||
              chr == '-' || chr == '+' || chr == '&' || chr == '@' ||
              chr == '#' || chr == '/' || chr == '%' || chr == '?' ||
              chr == '=' || chr == '~' || chr == '|' || chr == '!' ||
              chr == ':' || chr == ',' || chr == '.' || chr == ';')) {
            break;
        }
        charPos--;
    }

    // Extract/add URL if there are valid URL characters before file extension
    if ((dotPos > 0) && (charPos < dotPos)) {
        String url = htmlString.substring(charPos + 1, fileExtMatcher.end());
        urls.add(makeAbsoluteURL(url));
    }
}

Small disclaimer: I used part of your original regex for valid URL characters: [-a-zA-Z0-9+&@#/%?=~_|!:,.;]. Haven't verified if this is comprehensive and there are perhaps further improvements that could be made, e.g. it would currently find local file paths (e.g. C:\TEMP\myfile.xml) as well as URLs. Wanted to keep the code above simple to demonstrate the technique so haven't tackled this.

EDIT Following the comment about effiency I've modified to no longer use a regex for checking valid URL characters. Instead, it compares the character against valid ranges manually. Uglier code but should be faster...

Answer 4

I had my doubts, if there can be a String really long enough to take 25 seconds for parsing. So I tried and must admit now, that with about 27MB of text, it takes around 25 seconds to parse it with the given regular expression.

Being curious I changed the little test program with @FabioDch's approach (so, please vote for him, if you want to vote anywhere :-)

The result is quite impressing: Instead of 25 Seconds, @FabioDch's approach needed less then 1 second (100ms to 800ms) + 70ms to 85ms for reversing!

Here's the code I used. It reads text from the largest text file I've found and copies it 10 time to get 27MB of text. Then runs the regex against it and prints out the results.

@Test
public final void test() throws IOException {
    final Pattern urlRegex = Pattern.compile("(lmx|vsc)\\.[-a-zA-Z0-9+&@#/%=~_|][-a-zA-Z0-9+&@#/%?=~_|!:,.;]*");
    printTimePassed("initialized");

    List<String> lines = Files.readAllLines(Paths.get("testdata", "Aster_Express_User_Guide_0500.txt"), Charset.defaultCharset());
    StringBuilder sb = new StringBuilder();
    for(int i=0; i<10; i++) { // Copy 10 times to get more useful data 
        for(String line : lines) {
            sb.append(line);
            sb.append('\n');
        }
    }
    printTimePassed("loaded: " + lines.size() + " lines, in " + sb.length() + " chars");
    String html = sb.reverse().toString();
    printTimePassed("reversed");

    int i = 0;
    final Matcher url = urlRegex.matcher(html);
    while (url.find()) {
        System.out.println(i++ + ": FOUND: " + new StringBuilder(url.group()).reverse() + ", " + url.start() + ", " + url.end());
    }
    printTimePassed("ready");
}

private void printTimePassed(String msg) {
    long current = System.currentTimeMillis();
    System.out.printf("%s: took %d ms\n", msg, (current - ms));
    ms = current;
}

Answer 5

I know people love to use regex to parse html, but have you considered using jsoup?

Answer 6

For sake of clarity I created a separate answer for this regex:

Edited to escape the dot and remove reluctant quant.

(?<![-a-zA-Z0-9+&@#/%=~_|])[-a-zA-Z0-9+&@#/%?=~_|!:,.;]*[-a-zA-Z0-9+&@#/%=~_|]‌\\​.(xml|csv)

Please try this one and tell me how it goes.

Also here's a class which will enable you to search a reversed string without actually reversing it:

    public class ReversedString implements CharSequence {
    public ReversedString(String input) {
        this.s = input;
        this.len = s.length();
    }
    private final String s;
    private final int len;
    @Override
    public CharSequence subSequence(final int start, final int end) {
        return new CharSequence() {
            @Override
            public CharSequence subSequence(int start, int end) {
                throw new UnsupportedOperationException();
            }

            @Override
            public int length() {
                return end-start;
            }

            @Override
            public char charAt(int index) {
                return s.charAt(len-start-index-1);
            }
            @Override
            public String toString() {
                StringBuilder buf = new StringBuilder(end-start);
                for(int i = start;i < end;i++) {
                    buf.append(s.charAt(len-i-1));
                }
                return buf.toString();
            }
        }; 
    }

    @Override
    public int length() {
        return len;
    }

    @Override
    public char charAt(int index) {
        return s.charAt(len-1-index);
    }

}

You can use this class as such:

pattern.matcher(new ReversedString(inputString));