導入
正規表現はテキスト処理において強力なツールですが、不用意に記述すると「バックトラッキング（後戻り）」が発生し、プログラムの動作が極端に重くなることがあります。特にWebアプリのバリデーションやログ解析などで、正規表現の選択を誤ると「ReDoS（正規表現DoS攻撃）」と呼ばれる脆弱性に繋がる可能性もあります。今回はJavaのPatternクラスを例に、量指定子の挙動の違いとパフォーマンス最適化の勘所を解説します。
基礎知識
正規表現における「量指定子」には、探索の仕方が異なる3つのタイプがあります。
Greedy（貪欲）: 「」「+」「{n,}」。可能な限り長くマッチしようとし、失敗すると少しずつ戻って再試行します。これがバックトラッキングの主原因となります。
Reluctant（控えめ/非貪欲）: 「?」「+?」「{n,}?」。可能な限り短くマッチしようとし、必要に応じて少しずつ広げていきます。
Possessive（強欲）: 「+」「++」「{n,}+」。マッチしたものを絶対に手放しません。バックトラッキングを行わないため、最も高速です。
実装/解決策
パフォーマンスを最適化する鉄則は、「必要以上のバックトラッキングを避けること」です。
特に、データ構造が確定している場合や、特定の区切り文字までを一気に取りたい場合は、Possessive量指定子を検討してください。また、名前付きグループ（Named Groups）を使用することで、コードの可読性を高めつつ、特定のパターンを効率的に抽出する設計が可能です。
サンプルプログラム
以下のコードでは、同じ文字列に対して異なる量指定子を用いた場合の挙動の違いを示しています。
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class RegexPerformanceDemo {
public static void main(String[] args) {
String input = “ABCDE12345”;
// 名前付きグループを使用して、英字部分をキャプチャする例
// Greedy: . は最後まで読んだ後、数字を見つけるまで1文字ずつ戻る（バックトラッキングが発生）
String greedyRegex = “(?
// Possessive: .+ は最後まで一気に読み込み、絶対に手放さない。
// そのため、次の \d+ がマッチしないと即座に失敗する（バックトラッキングなし）
String possessiveRegex = “(?
Pattern p = Pattern.compile(possessiveRegex);
Matcher m = p.matcher(input);
if (m.find()) {
// 名前付きグループで取得することで、コードの意図が明確になる
System.out.println(“英字部分: ” + m.group(“letters”));
System.out.println(“数字部分: ” + m.group(“digits”));
}
}
}
応用・注意点
1. Possessiveの多用は注意: Possessiveは高速ですが、マッチング条件を厳密に書かないと、本来成功すべきパターンまで「手放さない」ことで失敗させてしまうリスクがあります。
2. 正規表現の複雑化を避ける: 非常に複雑な正規表現が必要な場合は、正規表現で全てを解決しようとせず、StringのsplitメソッドやindexOfメソッド、あるいは小さな正規表現を組み合わせる方が、デバッグしやすく高速な場合があります。
3. バリデーションには要注意: ユーザー入力に対して正規表現を適用する場合、攻撃者は意図的にバックトラッキングを誘発する文字列（「aaaaaaaaaa…!」のようなもの）を投げ込んできます。可能な限りPossessive量指定子や、アトミックグループを活用して、計算量が爆発しないように設計してください。
シニアエンジニアとしては、常に「この正規表現は最悪のケースでどれくらいの計算量になるか」を意識し、保守性とパフォーマンスのバランスを取ることを推奨します。
コメント