Eyal Schneider による投稿: 2009 年 5 月 21 日 java.util.regex パッケージは、バージョン 1.4 の Java に追加されました。これは非常に強力なツールであり、正しく使用するにはマスターになる必要があります。
正規表現が trueの場合でも、インテリジェントに記述されていない場合、非常に遅くなる可能性があります。問題の原因を理解したい場合は読み続けてください。ページの最後までスクロールすると、Java の正規表現のパフォーマンスを向上させるための 10 の役立つヒントが見つかります。
本当にそんなに遅いのでしょうか？
一連の文字「a」と「b」を含む行のみを選択するとします。正しい解決策は次のようになります。
(a*b*)* ただし、たとえば文字列 “aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaax” を使用して式を実行すると、終了して一致が報告されないまでに数分かかります。もちろん、この場合の最適な正規表現は次のようになります。
(a|b)* 同じ文字列を使用した場合、私のマシンでは 1 ミリ秒もかかりません。ここには明らかにパフォーマンスの問題があります。
なぜこうなった？
ほとんどの正規表現エンジンと同様に、Java は NFA (非決定的有限オートマトン) アプローチを使用します。エンジンは正規表現コンポーネントを 1 つずつスキャンし、それに応じて入力文字列を処理します。そして、「行き止まり」に陥った場合には、最初に戻って適切な代替案を見つけることができます。代替結果は、量指定子 (
*、+、? ) や代替 (例:
a|b|c|d ) などの通常の構造を使用して取得されます。この調査手法はバックトラッキングと呼ばれます。上記のひどい例では、エンジンは実際に、一致するものが存在しないことが分かるまで、記号「a」のすべての系列をより小さな系列に分解します。この例は、バックトラッキング アルゴリズムにより、(入力文字列の長さに応じて) 指数関数的な時間推定値がどのように得られるかを示します。これは、NFA の重要な特性も示しています。つまり、パターンにほぼ一致する最悪のケースが常に存在します。一致するものが見つかった場合、検索は停止します。正規表現で使用されるもう 1 つの主なアプローチは、DFA (Deterministic Finite Automaton) です。このアプローチでは、正規表現は実際に、バックトラックせずに入力文字列を 1 文字ずつ走査するために使用されるオートマトンを構築します。これにより、正規表現の複雑さに関係なく、入力全体に線形時間が与えられます。(NFA のように) 一致する文字列を順番にスキャンする代わりに、DFA は並列スキャンをシミュレートします。では、なぜ Java (および .NET、Perl、Python、Ruby、PHP など) は、動作がはるかに優れている DKA ではなく NKA を使用するのでしょうか? その理由は、NKA には多くの重要な利点があるためです。
- コンパイルが高速になり、必要なメモリが大幅に少なくなります
- いくつかの便利な機能が可能になります (詳細についてはSun のチュートリアルを参照してください)。
- グループキャプチャとバックリンク
- 位置確認
- 拡張量指定子 (Greedy および Lazy)
一般的な用語 NKA および DKA は、正規表現のコンテキストで使用すると不正確になることに注意することが重要です。理論的には、これら 2 つのモデルの計算能力は同じです。これは、あるオートマトン モデルでは、別のオートマトン モデルでは表現できない正規表現を記述することはできないことを意味します。実際には、2 つのタイプの実装のセマンティクスが異なるように、さらに多くの機能が必要です。NKA エンジンは柔軟性が高く、コンピューティング能力において DKA よりも優れています。DFA の速度と NFA の独自の機能により、正規表現を実装する「事前に作成された」方法がさらに 2 つあります。両方のタイプを使用する実装 (実行時に特定のエンジンを選択する GNU egrep など) もあれば、すべての利点を備えた真のハイブリッド バージョン (Tcl 正規表現など) を実装できる実装もあります。
アドバイス
以下は、Java での正規表現の効率性の問題を回避する方法に関するヒントです。その多くは利益を減らすことを目的としています。
1) プリコンパイル
ありきたりですが、言及する価値があります。正規表現を複数回使用する場合は、必ず事前にコンパイルしてください。
// компиляция p = Pattern.compile(regex, flags); … // использование Matcher a = p.matcher(input);
2)遅延量子化子と貪欲な量子化子
デフォルトでは、量指定子 (
* + ? ) は貪欲です。これは、可能な限り長いシーケンスとのマッチングを開始し、必要に応じて徐々に元に戻すことを意味します。通常、一致が短いことが事前にわかっている場合は、遅延量指定子を使用する必要があります。最小の一致から開始し、必要に応じてさらに進みます。「hello」というシーケンスに一致する行のみを検索したいとします。通常の
.*hello.* はすべてを正しく実行しますが、「hello」が通常テキストの先頭近くに表示されることがわかっている場合は、
.*?hello.* の方が平均して高速に動作します。
3)可能な限り、非常に貪欲な数量指定子を使用する
パフォーマンスには影響しますが、通常の動作には影響を与えない遅延量指定子とは異なり、超貪欲量指定子は実際に正規表現の意味を変更する可能性があります。
*の代わりに
*+を使用すると、最初の一致は貪欲になります (つまり、単に * であるかのように可能な限り最大の一致) が、失敗した場合、たとえ検索全体が失敗したとしてもフォールバックはありません。これはいつ役立つでしょうか? 引用符で囲まれたテキストを検索する必要があるとします。通常の
\"[^\"]*\" は問題なく機能します。ただし、否定的な場合 (たとえば、「bla bla bla」) には不必要なインデントが作成されます。
\"[^\"]*+\"を使用すると、式の意味を変更せずにロールバックします。独立したグループ化でも同じ効果が得られ、さらに詳細な制御が可能になります (
Sun のチュートリアルを参照)。
4) 集団捕獲を避ける
デフォルトでは、括弧内の式はすべてグループとみなされます。これはパフォーマンスにわずかな影響を与えます。可能な限りグループを「キャプチャ不能」にするには、
(の代わりに
(?:)でグループを開始します。
5) インターリーブを賢く使用する
インターリーブが使用されている場合 (例:
Paul|Jane|Chris )、エンジンがオプションを照合しようとする順序は、オプションが表示される順序と同じです。この機能を利用して、最も一般的なオプションを先頭近くに配置できます。これにより、平均陽性応答時間が改善されます。
6) 曖昧さを避ける
入力文字列内の異なる一致の数を最小限に抑えるような方法で正規表現を作成します。たとえば、記事の冒頭にある正規表現
(a*b*)* では、文字列「aabb」をさまざまな方法で解釈できます。 一方、
(a2b2) (a1)(a1)(b1)(b1) (a2)(b2) (a1)(a1b2) etc… 正規表現
(a|b)* は一意の解釈のみを行います。積極的に組み合わせます。
これは、ニアマッチの場合のリターンを減らすために非常に重要です。
7) プレビュー
プレビューを使用すると、現在の位置の左/右にシーケンスに制限を追加できます。特に、否定先読みを使用すると、シーケンスを含まない行を検索できます (これがなければどうなるでしょうか!)。これはどのように生産性の向上に役立つでしょうか? リンクタグから URL を取得したいとします。次の正規表現を考慮してください。
a .* href=(\S*).*/ 通常のタグの場合、この式は、テキストに「href」属性が含まれている場合にのみアドレスと一致します (区切り文字を除くすべての文字には \S が使用されます)。ただし、たとえば、一部の異常なタグではロールバックが発生します。例: 「a href= href=href=…。href=何か。」次の正規表現は、式内の「.*」を「href」に一致しないものに置き換えるときにこの問題が発生するのを防ぎます。
a ((?!href).)* href=(\S*)((?!href).)*/
8) 長さを指定します
Java には、入力文字列の長さを正規表現から取得した最小長および最大長と比較してチェックする正規表現オプティマイザーが含まれています。これにより、場合によっては検索をすぐに停止できます。このメカニズムを支援するには、可能な限り繰り返しの数を指定する必要があります (たとえば、
[01]{6}は 6 文字長のすべてのバイナリ文字列に一致します)。
9) 同一の行を選択します
場合によっては、同じ文字列がグループまたは代替の中に隠されていることがあります。
(hello|hell|heel) この式は次のように簡略化できます。
he(llo|ll|el) これにより、正規表現オプティマイザにより多くの情報が与えられます。
10) 正規表現をテストする
パフォーマンスが重要なアプリケーションで正規表現を使用する場合は、最初に正規表現をテストすることが賢明な場合があります。さまざまな入力データで式をテストするマイクロベンチマークを作成します。必ずさまざまな長さのデータ、およびサンプルによく一致するデータでテストしてください。
リンク:
http://java.sun.com/docs/books/tutorial/essential/regex/index.html http://www.javaworld.com/javaworld/jw-09-2007/jw-09-optimizingregex.html?page =1 http://www.softec.st/en/OpenSource/DevelopersCorner/ RegularExpressions/ RegularExpressionEngines.html http://www.devarticles.com/c/a/Java/NFA-DFA-POSIX-and-the-Mechanics -of-Expression-Processing/
GO TO FULL VERSION