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
酷睿 2 双核
1Gb 内存
单线程

Answer 1

提示:不要将正则表达式用于链接提取或其他 HTML“解析”任务!

您的正则表达式中有 6 (6) 个重复组。执行它需要大量的回溯。在最坏的情况下，它甚至可能接近 O(N^6)，其中 N 是输入字符的数量。您可以通过将急切匹配替换为惰性匹配来稍微缓解这种情况，但是几乎不可能避免病态情况；例如当输入数据严重畸形以至于正则表达式不匹配时。

一个好得多的解决方案是使用一些现有的严格或宽松的 HTML 解析器。即使手动编写一个临时解析器也比使用粗糙的正则表达式要好。

This page列出了 Java 的各种 HTML 解析器。我听说过有关 TagSoup 和 HtmlCleaner 的好消息。