3

在 Android/Java 中，给定网站的 HTML 源代码，我想提取所有 XML 和 CSV 文件路径。

我正在做的（使用 RegEx）是这样的：

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

不幸的是，对于一个正常长度的普通网站来说，这大约需要 25 秒。出了什么问题？我的正则表达式很糟糕吗？还是正则表达式太慢了？

如果没有 RegEx，我能否更快地找到 URL？

编辑：

有效字符的来源（大致）是这个答案。但是，我认为必须交换两个字符类（方括号），以便为 URL 的第一个字符设置更有限的字符集，为所有剩余字符设置更广泛的字符集。这是本意。

4

6 回答 6

4

您的正则表达式的编写方式使得长输入速度变慢。*操作员很贪心。

例如输入： http://stackoverflow.com/questions/19019504/regex-to-find-urls-in-html-takes-25-seconds-in-java-android.xml

正则表达式的[-a-zA-Z0-9+&@#/%?=~_|!:,.;]*一部分将消耗整个字符串。然后它将尝试匹配下一个字符组，这将失败（因为消耗了整个字符串）。然后它将回溯匹配正则表达式的第一部分一个字符并尝试再次匹配第二个字符组。它会匹配。然后它将尝试匹配点并失败，因为整个字符串都被消耗了。另一个回溯等...

从本质上讲，您的正则表达式会强制进行大量回溯以匹配任何内容。它还会在无法成功的比赛上浪费大量时间。

对于单词forest，它将首先在表达式的第一部分消耗整个单词，然后在匹配其余表达式失败后重复回溯。极大的浪费时间。

还：

  • in 正则.表达式未转义，它将匹配任何字符。
  • url.group(0)是多余的。url.group()具有相同的含义

为了加快正则表达式的速度，您需要找到一种减少回溯量的方法，如果您的比赛开始不太普遍，这也会有所帮助。现在每个单词都会导致匹配开始并且通常会失败。例如，通常在 html 中，所有链接都在 2 内"。如果是这种情况，您可以开始匹配，"这将大大加快速度。尝试找到更好的表达开头。

于 2013-09-26T07:58:40.747 回答
3

在 U Mad 所做的理论概述中，我没有发言权，他强调了我注意到的所有内容。

考虑到您对 RE 的要求，我想建议您的是改变您对 RE 的看法 :)

您正在寻找 xml 和 csv 文件，那么为什么不反转 html 字符串，例如使用：

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

之后你可以寻找模式：

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

urlRegex 模式可以按照 U Mad 的建议进行改进。但是通过这种方式，您可以减少失败匹配的数量。

于 2013-09-29T10:07:40.920 回答
1

建议仅使用正则表达式查找文件扩展名（.xml或.csv）。这应该会快很多，找到后，您可以向后看，检查之前的每个字符，并在到达无法在 URL 中的字符时停止 - 见下文：

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

小免责声明：我将您原始正则表达式的一部分用于有效的 URL 字符：[-a-zA-Z0-9+&@#/%?=~_|!:,.;]. 尚未验证这是否全面，可能还有进一步的改进，例如它目前可以找到本地文件路径（例如C:\TEMP\myfile.xml）以及 URL。想要保持上面的代码简单以演示该技术，所以没有解决这个问题。

编辑在关于效率的评论之后，我已经修改为不再使用正则表达式来检查有效的 URL 字符。相反，它手动将字符与有效范围进行比较。更丑陋的代码，但应该更快......

于 2013-09-29T13:36:32.497 回答
1

我怀疑是否有一个足够长的字符串需要 25 秒来解析。所以我尝试并且现在必须承认，对于大约 27MB 的文本，使用给定的正则表达式解析它大约需要 25 秒。

出于好奇，我用@FabioDch 的方法更改了小测试程序（所以，如果你想在任何地方投票，请投票给他 :-)

结果令人印象深刻：@FabioDch 的方法不是 25 秒，而是需要不到 1 秒（100 毫秒到 800 毫秒）+ 70 毫秒到 85 毫秒的反转！

这是我使用的代码。它从我找到的最大文本文件中读取文本并将其复制 10 次以获得 27MB 的文本。然后针对它运行正则表达式并打印出结果。

@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;
}
于 2013-09-29T16:58:33.147 回答
0

我知道人们喜欢使用正则表达式来解析 html，但是您考虑过使用jsoup吗？

于 2013-09-29T16:41:46.367 回答
0

为了清楚起见，我为此正则表达式创建了一个单独的答案：

编辑以逃避点并删除不情愿的量化。

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

请试试这个，告诉我它是怎么回事。

这里还有一个类，它可以让您搜索一个反转的字符串，而无需实际反转它：

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

}

您可以这样使用此类：

pattern.matcher(new ReversedString(inputString));

于 2013-10-07T11:55:27.583 回答