- 1: 基本となる8つの正規表現
- 2: 正規表現とは何か/ワイルドカードとの違い
- 3: 冒頭/末尾にマッチするメタ文字とセキュリティ、文字セットの否定と範囲
- 4: 先読みと後読みを極める
- 5（特別編）
|と部分マッチのワナ - 6: 文字セットのショートハンド
- 7: Unicode文字ポイントとUnicode文字クラス
- 8: 対象の構造を意識した「適度にDRYな」書き方
- 9:
.*や.+がバックトラックで不利な理由（本記事） - 10: 危険な「Catastrophic Backtracking」前編
主にRubyを中心としながらも、なるべく一般的な形で正規表現を解説しています。誤りやお気づきの点がありましたら@hachi8833までどうぞ🙇。
⚓.*のバックトラックを視覚的に理解する
百聞は一見にしかずということで、.*のバックトラックを見てみることにしましょう。ひらがなの「いろはに...ひもせすん」に対して/.*ろ/という正規表現を適用したときのバックトラックの様子をregexp101.comの正規表現デバッグ機能で表示しました。最初のものに限り、regexp101を開かなくてもアニメーションGIFで見られるようにしてあります。
- 例: /
.*ろ/というパターン（regex101）
/.*ろ/というシンプルなパターンなのに、マッチが完了するまでのステップが大きいことにお気づきかと思います。ステップ数は画像にもあるとおり「50」です。ここに表れている動作が正規表現のバックトラックです。
⚓バックトラックとは
バックトラックを説明するために、本連載記事で説明したことの中から思い出していただきたいことが2つあります。
以前「参考: |正規表現エンジンのタイプによって挙動が変わる」で、正規表現エンジンに「テキスト制御型」と「正規表現制御型」の2種類があるということを簡単に説明しました。
バックトラック（backtrack）は、後者である「正規表現制御型」エンジンの中核をなす動作です。前者の「テキスト制御型」エンジンではバックトラックは行われません。
なお、後方参照（back reference）は言葉は似ていますが、まったく別の概念です。後方参照については今後説明します。
もうひとつ思い出していただきたいのが、「正規表現はじめの五歩: .」で説明した「+（および*）量指定子はデフォルトで最長一致する」という性質です。
この最長一致（別名: 欲張り一致）という動作は、バックトラックによって実現されます。
上の例を再録します。探索がどのように進むかじっくりご覧ください。リンク先ならマウスやキーボードで1ステップずつ実行できますので、より実感しやすいと思います。
- 例: /
.*ろ/というパターン（regex101）
このバックトラックの動作を順に説明します。
.+というパターンがあると、対象文字列のその地点から末尾まで一気に進む.+の直後にろという文字があるので、対象文字列の末尾から1文字ずつさかのぼる- 対象文字列の中に
ろという文字があれば、対象文字列の.*を開始した地点からろまでをマッチ文字とする
こうすることで、「いろはに...ひもせすん」の中にろという文字が複数あったとしても、末尾に最も近いろまでマッチします。つまり最長一致します。
⚓.+や.*は、使う前に考えよう
私は、本連載記事を通して.+や.*といった正規表現をなるべく避けていますが、その理由のひとつがこれです。つまり無駄なバックトラックにつながる可能性があるからです。常にではありませんが。
.+や.*が単独だったり、正規表現の末尾に置かれている分にはさほど効率は落ちませんが、.*ろなどのように.+や.*の後ろにさらに正規表現が続くと、長い文字列を対象とする正規表現でパフォーマンスが落ちることがあります。
上の例は、バックトラックで効率が落ちるところがわかりやすいよう、極端な正規表現と対象文字列を用いたエッジケースであることにご注意ください。
もちろん.+や.*を使うしかないこともあると思いますので、私のように毛嫌いしなくてもよいと思います。それでも、.+や.*のような正規表現を使う前に、このことをたまに思い出していただければ幸いです。
⚓余分なバックトラックを回避するには
以下はほんの一例であり、他にもいろいろ方法が考えられると思います。.+や.*は最後の手段としてとっておき、原則として避けるのが楽だと思います。
⚓1. .*?で最短一致にする
ここまでの動作を見れば、.*?のように量指定子に最短一致（別名: ものぐさ一致）の?を追加して最長一致をやめれば、バックトラックを抑制できそうです。やってみましょう。
- 例: /
.+?ろ/（regex101）
成功です。50ステップが3ステップにまで激減しました❤️。
⚓2. .をもっと絞り込む
+や*といった量指定子ばかりではなく、.という任意の一文字にも改善の余地があります。あまり実用的な例ではありませんが、.を以下のように[^ろ]に変えてみました。
- 例: /
[^ろ]+ろ/（regex101）
これも成功です。やはり50ステップが3ステップにまで激減しました❤️。
1. 先読み
うすうす予想はついていましたが、先読みを使ったらどうなるかをやってみました。
- 例: /
.+(?=は)/（regex101）
やはり効きませんでした。ステップ数は50のままです👎。
まとめ
- バックトラックが余分に発生すると正規表現のパフォーマンスが落ちることがある
- 正規表現の途中に
.+や.*を使う前に検討しよう - 最小一致の
?はバックトラックの抑制に効果的な場合がある .を絞り込んで、より詳細な別のパターンにすることでバックトラックを抑制できることがある- regex101.comの正規表現デバッグは便利