1.概要

このクイックチュートリアルでは、パターンマッチングエンジンの仕組みを説明します。 Javaで「正規表現」を最適化するさまざまな方法も紹介します。


正規表現

の使い方の紹介については、https://www.baeldung.com/regular-expressions-javaを参照してください。

2.パターンマッチングエンジン


java.util.regex

パッケージは、**

Nondterministic Finite Automaton

(NFA)と呼ばれるパターンマッチングエンジンの一種を使用します。与えられた文字列に正規表現をマッチさせようとしている間、入力の各文字が正規表現の異なる部分に対して何度かチェックされるかもしれないので、それは

nondterministic

と考えられています。

バックグラウンドでは、上記のエンジンは

backtracking

を使用します。この一般的なアルゴリズムはそれが失敗を宣言するまですべての可能性を使い果たすことを試みます。

NFA

をよりよく理解するために、次の例を検討してください。

"tra(vel|ce|de)m"

入力

String



travel

”を指定すると、エンジンは最初に“

tra

”を探してすぐに見つけます。

その後、4文字目から「

vel

」に一致させるようにします。これは一致するので、先に進み、「

m

」と一致するように試みます。

これは一致しません。そのため、4文字目に戻って「

ce

」を検索します。繰り返しになりますが、これは一致しません。4番目のポジションに戻って「

de

」を試してみます。その文字列はどちらにも一致しないため、入力文字列の2番目の文字に戻り、別の ”

tra

“を検索します。

最後の失敗では、アルゴリズムは失敗を返します。

最後の簡単な例では、入力

String

を正規表現に一致させようとしている間に、エンジンは何度かバックトラックしなければなりませんでした。

そのため、** バックトラックを最小限に抑えることが重要です。

3.最適化する方法

正規表現

3.1. 再コンパイルを避ける

Javaの正規表現は、内部データ構造にコンパイルされています。このコンパイルは時間がかかるプロセスです。


__String.matches(String regex)

__methodを呼び出すたびに、指定された正規表現が再コンパイルされます。

if (input.matches(regexPattern)) {
   //do something
}

ご覧のとおり、条件が評価されるたびに、正規表現がコンパイルされます。

最適化するには、最初にパターンをコンパイルしてから

Matcher

を作成して値の一致を見つけることができます。

Pattern pattern = Pattern.compile(regexPattern);
for(String value : values) {
    Matcher matcher = pattern.matcher(value);
    if (matcher.matches()) {
       //do something
    }
}

上記の最適化に代わる方法は、同じ

Matcher

インスタンスをその

reset()

メソッドで使用することです。

Pattern pattern = Pattern.compile(regexPattern);
Matcher matcher = pattern.matcher("");
for(String value : values) {
    matcher.reset(value);
    if (matcher.matches()) {
     //do something
    }
}

__Matcherはスレッドセーフではないため、このバリエーションの使用には注意が必要です。マルチスレッドのシナリオではおそらく危険かもしれません。

要約すると、いつでも

Matcher

を使用しているユーザーが1人だけであると確信しているすべての状況で、

reset

を使用して再利用することは問題ありません。

それ以外の場合は、プリコンパイル済みファイルを再利用すれば十分です。

3.2. 交代で作業する

最後のセクションで確認したように、不適切な交代の使用はパフォーマンスに悪影響を与える可能性があります。より早くマッチできるように、起こりそうなオプションを前面に配置することが重要です。

また、それらの間に共通のパターンを抽出する必要があります。置くことは同じではありません:

(travel | trade | trace)

より:

tra(vel | de | ce)

後者の方が速いのは、

NFA

が「

tra

」と一致しようとし、見つからない場合は他の方法を試しないためです。

3.3. グループをキャプチャする

グループを占領するたびに、少しのペナルティが発生します。

テキストをグループ内に取り込む必要がない場合は、取り込まないグループの使用を検討する必要があります。 “

(M)

”の代わりに“

(?:M)

”を使用してください。

4.まとめ

この簡単な記事では、

NFA

のしくみについて簡単に説明しました。次に、パターンをプリコンパイルして

Matcher

を再利用することによって、正規表現のパフォーマンスを最適化する方法を探りました。

最後に、私たちは交替やグループで作業する際に留意すべきいくつかの考慮事項を指摘しました。

いつものように、完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/core-java-8[GitHubに載っています]。