Java正则表达式性能

Question

我正在尝试使用Java解析带有正则表达式的链接.

但我认为它变得太慢了.例如,要从以下位置提取所有链接:

• http://news.google.com.ar/nwshp?hl=es&tab=wn

......花了34642毫秒(34秒!!!)

这是正则表达式:

private final String regexp = "<a.*?\\shref\\s*=\\s*([\\\"\\']*)(.*?)([\\\"\\'\\s].*?>|>)";

模式的标志:

private static final int flags = Pattern.CASE_INSENSITIVE | Pattern.DOTALL |Pattern.MULTILINE | Pattern.UNICODE_CASE | Pattern.CANON_EQ;

代码可能是这样的:

private void processURL(URL url){
    URLConnection connection;
    Pattern pattern = Pattern.compile(regexp, flags);
    try {
        connection = url.openConnection();
        InputStream in = connection.getInputStream();
        BufferedReader bf = new BufferedReader(new InputStreamReader(in));
        String html = new String();
        String line = bf.readLine();            
        while(line!=null){
            html += line;
            line = bf.readLine();
        }
        bf.close();
        Matcher matcher = pattern.matcher(html);
        while (matcher.find()) {
            System.out.println(matcher.group(2));
        }
     } catch (Exception e){
     }
 }

你能给我一个提示吗？

额外数据:
1Mbit
Core 2 Duo
1Gb RAM
单线程

Answer 1

提示:不要使用正则表达式进行链接提取或其他HTML"解析"任务!

你的正则表达式中有6个(SIX)重复组.执行它将需要大量的回溯.在最坏的情况下,它甚至可以接近O(N^6)N是输入字符的数量.你可以通过用懒惰匹配替换急切匹配来缓解这一点,但几乎不可能避免病态情况; 例如,当输入数据充分畸形而正则表达式不匹配时.

一个远远好得多的解决方案是使用一些现有的严格或允许的HTML解析器.即使手动编写ad-hoc解析器也会比使用gnarly regex更好.

此页面列出了Java的各种HTML解析器.我听说过TagSoup和HtmlCleaner的好消息.