3

Android/Java では、Web サイトの 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;
    }
}

残念ながら、これは通常の長さの平均的な Web サイトで約 25 秒間実行されます。何がうまくいかないのですか？私の正規表現は悪いですか？それとも正規表現はとても遅いのでしょうか?

正規表現なしで URL をすばやく見つけることはできますか?

編集：

有効な文字のソースは (大まかに) this answerでした。ただし、URL の最初の文字の文字セットをより限定し、残りのすべての文字の文字クラスをより広くするために、2 つの文字クラス (角括弧) を交換する必要があると思います。これが意図でした。

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+&@#/%?=~_|!:,.;]*一部は文字列全体を消費します。次に、次の文字グループを照合しようとしますが、失敗します (文字列全体が消費されるため)。次に、正規表現の最初の部分の一致で 1 文字バックトラックし、2 番目の文字グループの一致を再度試みます。一致します。次に、ドットの一致を試みますが、文字列全体が消費されるため失敗します。別のバックトラックなど...

本質的に、あなたの正規表現は、何にでも一致するように多くのバックトラッキングを強制しています。また、成功する方法がない試合で多くの時間を浪費します。

単語forestの場合、最初に式の最初の部分で単語全体を消費し、残りの式の一致に失敗した後、繰り返しバックトラックします。膨大な時間の無駄。

また：

  • in 正規表現はエスケープされておらず、任意の.文字に一致します。
  • url.group(0)冗長です。url.group()同じ意味です

正規表現を高速化するには、バックトラッキングの量を減らす方法を見つける必要があります。これは、マッチの開始があまり一般的でない場合にも役立ちます。現在、単語ごとにマッチングが開始され、通常は失敗します。たとえば、通常、html ではすべてのリンクが 2 内にあります"。その場合は、マッチングを開始すると、マッチングが"大幅に高速化されます。式のより適切な開始点を見つけるようにしてください。

于 2013-09-26T07:58:40.747 に答える
1

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...

于 2013-09-29T13:36:32.497 に答える
1

解析に 25 秒かかるほど長い文字列が存在する可能性があるかどうか、疑問がありました。そのため、約 27MB のテキストを使用して、指定された正規表現でそれを解析するのに約 25 秒かかることを試しましたが、今は認めなければなりません。

好奇心が強いので、@FabioDch のアプローチで小さなテスト プログラムを変更しました (どこかに投票したい場合は、彼に投票してください :-)

結果は非常に印象的です: 25 秒の代わりに、@FabioDch のアプローチは 1 秒 (100 ミリ秒から 800 ミリ秒) + 70 ミリ秒から 85 ミリ秒未満で逆転できました!

これが私が使用したコードです。私が見つけた最大のテキスト ファイルからテキストを読み取り、それを 10 回コピーして 27 MB のテキストを取得します。次に、それに対して正規表現を実行し、結果を出力します。

@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 を解析するために regex を使用するのが好きな人がいることは知っていますが、 jsoup の使用を検討したことはありますか?

于 2013-09-29T16:41:46.367 に答える