1

CSV ファイルを読み取るために、Java で次の正規表現を使用しています。

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")+|\\\"([^\\\"]|\\\"\\\")+\\\"))*", Pattern.DOTALL);

この式は、このオンライン正規表現テストに合格します。ただし、実行すると常にStackOverflowError.

いくつかの調査の後、解決策は式を次のように置き換えることであることがわかりました

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")++|\\\"([^\\\"]|\\\"\\\")++\\\"))*", Pattern.DOTALL);

ここでは貪欲な量指定子の代わりに所有量指定子を使用します。この場合、それは最適化とも言えます。

私の質問は、Java は多くのバックトラッキングを処理できないため (スタック スペースを消費するため、優れたエンジンはそうではないと私は信じています)、StackOverflowError正規表現が原因であることがわかったときはいつでも最適化を検討する必要があるということです。バックトラッキングを減らす方法は？

4

2 に答える 2

1

はい、Java 正規表現エンジンが壊れています。後方参照をサポートできるようにバックトラッキングを使用しており、その結果、すべての perl ライクな正規表現エンジンに共通する病的な指数空間/時間の問題が発生します。おっしゃるとおり、式を分析して実際に規則的であると判断し、期待した多項式空間/時間アルゴリズムを使用する可能性があります。

このような場合、できればJFlexを介してカスケード正規表現を使用することを常にお勧めしますが、2 つまたは 3 つのレベルに固執する限り、手動で行うことはそれほど苦痛ではありません。それ以上に、レクサーを使用すると、保守がはるかに容易になり、書き込みとデバッグが容易になります。

アイデアは、単純な正規表現を繰り返し適用して行を解析することです。あなたの場合、最初は次のフィールドの開始を識別します。2 番目は、フィールドの終わりを識別します (内容をキャプチャーします)。3 番目は「次のフィールド」をチェックします。繰り返す。

これらは、JFlex を使用して認識する 3 つのトークンとほぼ同じです。唯一の違いはフィールド区切りトークンであり、非常に単純であるため、手動で行うときに「フィールドの終わり」正規表現に含めることができます。

于 2013-02-21T06:47:50.747 に答える
1

Java スローStackOverflowErrorは、マッチングが再帰呼び出しによって内部的に行われることを示しています。これは悪いことですが、正規表現に潜在的な問題があることを示しているため、それ自体が良いことでもあります。

+バックトラッキング地獄は、別の有限多数のマッチング内で有限多数のマッチングを行うという事実によって引き起こされます*: ((A+|B))*(これは正規表現の形式です)。

通常、バックトラックする必要がなく、スタックを必要としない非正規表現ソリューションを作成できる場合 (ブラケット マッチングの問題など)、所有量指定子 (+通常の量指定子の後に追加) を使用して正規表現を作成できます。所有量指定子はバックトラックを (許可) しないため、同じタスクを実行します。これは、非正規表現ソリューションで行うことと似ています。

于 2013-02-21T06:35:53.200 に答える