3

サンプルコード:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Regex {
    public static void main(String[] args) {
        String data = "Shyam and you. You are 2.3 km away from home. Lakshmi and you. Ram and you. You are Mike. ";
        Pattern pattern = Pattern.compile(
                "\\s*((?:[^\\.]|(?:\\w+\\.)+\\w)*are.*?)(?:\\.\\s|\\.$)",
                Pattern.DOTALL);
        Matcher matcher = pattern.matcher(data);
        while (matcher.find()) {
            System.out.println(matcher.group(0));
        }
    }
}

出力：

You are 2.3 km away from home. 

You are Mike.

上記のコードを実行すると、期待される出力が得られます。しかし、問題は、同じ正規表現をより大きな string でテストすると、オーバーフロー エラーが表示されることです。同じことを調べてみたところ、正規表現の (A|B)* のような変更が問題の原因であることがわかりました。この問題を解決する方法はありますか? 助けてください。

4

2 に答える 2

3

バックトラッキングを避けるために、正規表現をリファクタリングしようとしました。この正規表現を試すことができますか:

Pattern pattern = Pattern.compile("(?>[^.]|(?:\\w+\\.)+\\w)+\\sare\\s.*?(?>\\.\\s|\\.$)",
                  Pattern.DOTALL);

(?>group)アトミック グループ化と呼ばれます。

ごとに: http://www.regular-expressions.info/atomic.html

アトミック グループ

アトミック グループとは、正規表現エンジンが終了したときに automatically throws away all backtracking positions remembered by any tokens inside the group. アトミック グループは非キャプチャです。構文は(?>group).

于 2013-08-28T15:14:37.610 に答える
1

Pshemo がコメントで賢明に指摘したように、問題は、入力文字列の長さとは関係なく、壊滅的なバックトラッキング(ネストされたすべての量指定子による) の結果である可能性があります。上記のリンクは、StackOverflowErrors短い入力文字列と単純に見える正規表現でも取得できる理由の非常に良い例を提供します。

簡単に言うと、特定の状況では、パターン マッチャーが (入力の長さと比較して) 指数関数的な数のステップを実行して、一致/不一致を判断できることを意味します。これが発生すると、パターン マッチングの再帰が深くなりすぎるため、スタックが「オーバーフロー」します。上記のリンクやパターン(x+x+)+yの (いくつかの例の 1 つ) のように、ネストされた量指定子で特に一般的です。((?:\\w+\\.)+\\w)*

何のために正規表現を書こうとしているのかを説明していただければ、不運または悪意のある入力を与えても爆発しない正規表現を思いつくのを手助けできる可能性が非常に高いです。

要件に関するコメントを考えると、正規表現をまったく使用しない場合は、頭痛の種を減らすことができます。入力を区切り文字 (この場合は". ") で分割し、各結果をキーワードで検索します。何人かのコメンターが言及しているように、特にサイズが不明な場合は、とにかくデータを分割する方が一般的に安全です。

String[] sentences = data.split("\\. ");
for (String sentence : sentences) {
    if (sentence.contains("are")) {
        System.out.println(sentence.concat(". "));
    }
}
于 2013-08-28T14:46:40.433 に答える