この記事の途中に、以下の記事の引用を含んでいます。
Regular Expression Matching Can Be Simple and Fast
1. “正規表現は遅い”は本当か？驚きの比較が示す現実
まず、多くの開発者にとって正規表現（regex）は日常的な道具です。
「表現力豊かで便利だけど、ときどき妙に遅い…」と感じたことのある人も少なくないでしょう。
実際、絶大な人気を誇るPerl、Python、PHP、Ruby、Java…どの言語でも「正規表現がボトルネックになった」という体験談は後を絶ちません。
この記事で取り上げられているのは、一見すると地味で古典的な話題。
しかし、内容を噛み砕いて言えば「現在主流の正規表現実装の多くは、理論的には遥かに高速化できる余地があるのに、事実上“致命的な遅さ”を抱えたまま使われ続けている」という実態です。
著者が冒頭で次のように語っています。
Perl requires over sixty seconds to match a 29-character string. The other approach, labeled Thompson NFA for reasons that will be explained later, requires twenty microseconds to match the string. That’s not a typo. … the Thompson NFA implementation is a million times faster than Perl when running on a miniscule 29-character string.
(Regular Expression Matching Can Be Simple and Fast)
つまり、正規表現によっては100万倍以上の速度差すら現実になりうるのです。
2. “遅い理由”はアルゴリズムの選択にあり――2つの流派を徹底比較！
では、なぜ世の中の多くのRegexエンジンはそこまで非効率なのでしょうか。
記事では2種類の正規表現マッチング戦略に注目します。
- バックトラッキング実装（大半の現代言語が採用）
- 有限オートマトン（特にThompson NFA）ベース（grepやawkなどUnix系の一部ツール）
ここが最重要ポイントです。
バックトラッキング型
これは、「選択肢が複数ある正規表現（例えばa?など）」の場合、すべての組み合わせルートをなめ尽くして答えを探す戦略です。
実装はシンプルで柔軟ですが、“パスワースケース（病的な正規表現）”だと組合せ爆発を起こし、指数関数的な時間がかかります。
有限オートマトン型（Thompson NFA）
一方、Thompsonの手法は「選択肢を同時にすべて進めてしまう」仕組み。
要するに1文字読むごとに現在到達可能な状態を全部追いかけ、一度の走査のみで済むのが特徴です。
どんなパターンでも常に「線形時間」か、それに近い高速性を保てます。
“there are no regular expressions that are pathological for the Thompson NFA implementation.”
(Regular Expression Matching Can Be Simple and Fast)
この差が生み出すパフォーマンス格差は圧倒的です。
3. 理論 vs 現実、なぜ“速い理論”が現実世界で普及しなかったのか？
ここで気になるのが、「なぜ非効率なバックトラッキング実装が主流になったのか？」という点。
Unix黎明期には理論を理解していたはずの研究者たち（Ken ThompsonやDennis Ritchieら）がツールに正規表現の理論を持ち込んだにもかかわらず、今日ではその恩恵が意外なほど実装に生かされていないのです。
記事歴史パートをかみ砕くと、こうなります。
- grep/sed/ed系：バックトラッキング（ただし初期は言語仕様がシンプルで大きな問題なし）
- egrep/awk/GNU grep系：原理通りの有限オートマトン（DFA/NFA）方式
- Perl全盛以降、ほとんどの言語で再びバックトラッキング型が支配的に
この転換点には“便利な機能が後付けで追加、バックトラッキングを前提とすると楽に実装できた”など、歴史上の偶然や開発コミュニティの選好が絡んでいるようです。
実際、記事ではこう指摘されています：
“Regular expressions have also become a shining example of how ignoring good theory leads to bad programs. The regular expression implementations used by today’s popular tools are significantly slower than the ones used in many of those thirty-year-old Unix tools.”
(Regular Expression Matching Can Be Simple and Fast)
つまり「過去のほうがよくできてた」パターンすらあるのです。
4. “backreference（後方参照）”問題と設計のジレンマ
なぜ言語は今になっても“遅い”アルゴリズムを使い続けているのでしょうか？
最大の要因はbackreference（後方参照）の存在です。
後方参照とは「(ab)\1」などのように、括弧で括った値を後で再利用する機能。
この機能をサポートしようとすると、理論的には正規表現よりも遥かに表現力が高くなり、指数時間アルゴリズム（NP完全問題）の呪縛から逃れられません。
バックトラッキングは柔軟にこれをサポートできるが、NFA/DFAベースでは不可能です。
とはいえ、日常的な検索や置換パターンはbackreferenceを使わないケースも多く、その場合はNFA/DFA方式で十分対応可能、かつ劇的な高速化が現実的なのです。
記事では次のように述べています。
“…they could employ much faster algorithms when presented with regular expressions that don’t have backreferences, like the ones considered above. This article is about those faster algorithms.”
(Regular Expression Matching Can Be Simple and Fast)
つまり「backreferenceを含まない場合は自動的に速いアルゴリズムへ切り替えるべき」なのに、それすら満足に実装されていない現状が指摘されています。
5. 「実践的な正規表現エンジン」とは？NFA/DFAシミュレーションの実装ポイント
では、NFA/DFA方式はどれだけ実装が大変なのか？
記事では400行程度のCコード例を交えて、Thompsonアルゴリズムの実装方法も解説されています。
この実装は：
- 正規表現をNFA（非決定性有限オートマトン）に変換
- 入力文字列を1文字ずつ走査し“到達可能な状態集合”を管理
- 実行中に部分的DFA状態をキャッシュすることで更なる高速化も可能
- 様々な最適化や現代的要請（サブマッチ抽出、UTF-8対応など）も追加容易
となっています。
NFA/DFA方式は「パターンが複雑でも大きな組合せ爆発を起こさない」「どんな入力でも“最悪計算量”が一定で予測しやすい」という点で非常に実践的です。
病的パターンへの耐性
実際、記事が示すベンチマークによれば、典型的な“病的正規表現”で
– Perl等：入力文字数30程度で秒～分レベル、それ以上で“数年”オーダー
– Thompson NFAやDFA実装：数ms以下で処理完了
現実逃避ではなく、実際に計測するだけでこの差が明確になることが重要です。
6. 私の視点：なぜ“最もよい理論”が普及しないのか？そしてこの問題をどう見るべきか
私見として、この問題の根底には
– 互換性重視（既存コードの維持）
– 実装コストや人材リソースの問題
– ユーザビリティと表現力（flexibility）のトレードオフ
の3点があると考えます。
特にPerlやPCRE、Javaなどのエンジンは“誰でも使える応用範囲の広さ”を追い求めた結果、「バックトラッキング型で応急処置的に多機能を詰め込む」設計にシフトしやすい。
結果、パフォーマンス上のリスクや、不規則な“突然重くなる”状況が放置されたままとなるケースが多いわけです。
バックレファレンスも国際化（Unicode）対応もニッチな要求に見えて、グローバルなユーザー規模では無視できません。
そこに正規表現エンジンの“絶妙なジレンマ”が潜んでいます。
しかし、記事が指摘する通り「大半の実際的な使い方ならNFA/DFAで十分。しかも圧倒的に速い」のは間違いない。
例えばGoやRust、最近のRE2、PGGREPといったエンジンでは、NFA/DFA志向が復権してきつつあります。
今後は「パターンを自動的に“難しい部分”と“高速部分”に分割し、賢く最適なアルゴリズムをミックスする」そんなハイブリッド型エンジンが増えると考えます。
7. まとめ：“正規表現は遅い”を常識にしないために
最後に、この記事から得られる示唆を箇条書きします。
- 正規表現の“遅さ”は避けられない宿命ではない。適切な理論と実装で驚くほど速くできる。
- バックトラッキング実装は便利だが、悪意ある or 病的なパターンで指数時間爆発が起きる。これを無視しては開発現場で痛い目に遭う。
- NFA/DFAベース（Thompson流）の技法は、半世紀以上前からあったベストプラクティス。現代でも十分に実用可能。
- backreferenceなど一部機能は例外的に遅くてもやむを得ないが、それ以外は自動的に最善手法に振り分ける設計が理想。
- 新しい実装（Go/Rust/RE2など）はすでにこの方向に舵を切りつつある。
- 正規表現の使い方も実装も“理論に学ぶ”ことが、結果的に安全で、保守しやすいシステムへの第一歩と言える。
自分の使っているツールや言語の正規表現エンジンがどの戦略で動いているか、一度調べてみてはいかがでしょうか。
「正規表現は便利だけど、遅くて重い」という“都市伝説”に騙されず、適切な実装や使い方を身につけることで、生産性や品質を大きく向上させることができるでしょう！
categories:[technology]
コメント