1. 概要

このクイックチュートリアルでは、パターンマッチングエンジンがどのように機能するかを示します。 また、Javaで正規表現を最適化するさまざまな方法を紹介します。

正規表現の使用方法の概要については、こちらの記事を参照してください。

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

The java.util.regex パッケージは、と呼ばれるタイプのパターンマッチングエンジンを使用します非決定性有限オートマトン(NFA)。 特定の文字列の正規表現を照合しようとしているときに、入力の各文字が正規表現のさまざまな部分に対して数回チェックされる可能性があるため、非決定的と見なされます。

バックグラウンドで、上記のエンジンはバックトラッキングを使用します。 この一般的なアルゴリズムは、失敗を宣言するまですべての可能性を使い果たしようとします。  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)メソッドを呼び出すたびに、指定された正規表現が再コンパイルされます。

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 を再利用することにより、正規表現のパフォーマンスを最適化する方法を検討しました。

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

いつものように、完全なソースコードはGitHubにあります。