正規表現の全マッチ検索、実は「O(n²)」って知ってた？計算量に潜む意外な罠

正規表現を使ってテキスト内からすべてのマッチ箇所を特定する処理は、実はこれまでずっと計算量が O(n²) でした。直感的には線形時間（O(n)）で処理できそうに思えますが、マッチが見つかるたびに検索開始位置をずらして再度スキャンを行う性質上、最悪の場合のパフォーマンスには注意が必要です。大規模なテキスト処理を行うエンジニアが知っておくべき、正規表現のアルゴリズム的な落とし穴についての指摘です。

RE#の2パス・アプローチを他の正規表現エンジンが採用できない理由って何かあるかな？ ああ、最近ここでRE#の詳細と議論についての投稿があったみたいだね、見逃してたよ： https://news.ycombinator.com/item?id=47206647

「実用上重要なことのほとんど：マッチした場所、長さ、数」っていう点についてだけど、ログを掘り返すときとかに実際に使われる正規表現には、パスロジカルなバックトラックを抑える明確な境界があると思うんだよね。特に、記事にある /.*a|b/ みたいな表現の「すべての」マッチを見つける実用的なニーズは想像しにくいかな。現実的には \b.*a|b\b とか、それに近いものを扱うはず。全部のマッチが必要なとき、普通は重なり合うマッチなんて欲しくないからね。つまり、n番目のマッチが終わったところからn+1番目を探したいわけで、 /.a/ みたいな不確定なプレフィックスは使いたくないはず。 逆に言うと、正規表現が信頼できないソースからのもので攻撃的な可能性がある場合には、これは結構使えるヒューリスティックになるかも。/a/ みたいなクリーネ・スターで始まるプレフィックスがないかチェックしたり、各分岐で少なくとも1つのポジティブなマッチを必須にしたりね。もちろん、テキストが「a」の長い連続で「b」以外の文字が混ざってる場合、/a+b|c/ はまだ2次の計算量になっちゃう。でもこれも、個人的には理論上の話って気がするな。

計算量を保証するために正規表現の機能を制限するのは確かに「効く」けど、バックトラックみたいな便利な機能を捨てたり（この記事のケースなら、検索対象の長さに上限を設けたり）しなきゃいけなくなる。 どんな正規表現でもミスや悪意に耐えられるように動かしたいっていう現実的なデプロイ環境なら、他の信頼できないコードを走らせるのと同じ解決策が一番いい。つまり、サンドボックス化だね！ 優れた正規表現APIなら、実行時間やメモリ消費を制限して、上限を超えたらタイムアウトエラーを返すべき。理想を言えば、そういうパラメータはAPIレベルで設定できるのがいい。残念ながら、これがちゃんとできてる正規表現ライブラリで俺が知ってるのは、.NETの標準Regex APIと、Pythonのサードパーティ製regexパッケージくらいかな。

「この投稿で話してる問題（2次の爆発を起こさずにすべての最長マッチを見つけること）」 待って、え？ これって「すべてのマッチ」を見つける話だと思ってたんだけど。最初の例をちょっと変えてみると： 「bbbbbabbbbb」に対して (.*a | b) をマッチさせたいとする。 俺は b を個別に全部検出したいし、bbbbba、bbbba、bbba、bba、ba、それと a も検出したいんだ。それが「すべてのマッチを見つける」ってことだろ。

Perlの革新だった (?:...) が「伝統的な正規表現」って呼ばれるのは違和感あるな。30年以上前とはいえ、当時のPerlはかなり革新的だったんだ。伝統的な正規表現ってのは、その前にあったやつ（一番高度なやつで grep -E とか）を指すだろ。著者の目には何が「非伝統的」に映ってるのか気になるね。

@ievev @bablr/regex みたいな実装は見たことある？ https://github.com/bablr-lang/regex-vm NFAベースのシステムだからスループットで賞を取るようなもんじゃないけど、このケースに限れば複雑度の爆発を完全に回避してるっぽい。ただ、入力がめちゃくちゃデカいとヒープを食いつぶしちゃうけどね。 このエンジンが使ってる戦略は、単に状態を時間の関数として進化させること。マッチが成功しても、他のもっと長いマッチや左側優先のマッチがそれを上書きする可能性があるから、すぐには出力されないんだ。 10,000,000個の数字の後にスペースがないパターンで /d+s+/g を試してみたら、結果なしを返すのに4秒かかった。20,000,000個なら8秒。100,000,000個でヒープ不足になったよ。 テスト環境： https://gist.github.com/conartist6/051838025af1e04d966e03aa95147b7e

ちなみに、nim-regexはキャプチャグループが含まれていても rebar テストで線形時間を達成してるよ。NFAベースだね。 https://github.com/BurntSushi/rebar/pull/20#issuecomment-2562996491

Cursorがこれについて素晴らしいブログ記事を書いてるよ。「高速な正規表現検索：エージェントツール向けのテキストインデックス作成」 https://cursor.com/blog/fast-regex-search

素晴らしい解説記事だね。これがずっと目の前に隠れていたなんて驚きだよ。ほとんどの人は正規表現エンジンはもう十分に最適化されてると思い込んでるけど、重なり合うマッチのケースを2次の挙動なしで扱うのは本当にトリッキーなんだ。最後に触れられてる Thompson NFA のアプローチが正しい方向な気がするけど、現実のパターンの多くはこのケースに当たらないから、誰も優先してこなかった理由はわかる気がするな。