正規表現で全てのマッチを探すことは、常に O(n²) でした。

検索性能と二次的爆発

あるパターンを文書内で探すのに1秒かかる場合、同じ検索を100倍大きいテキストで繰り返すとほぼ3時間まで拡大します。RE2、Go の

regexp

regex

find_iter

FindAll

「イテレーターの最悪ケース時間計算量は O(m × n²) です … パターンもヒストックも信頼できない場合、すべての一致を列挙するときには二次的な時間計算量に陥ります。これを回避する方法はありません。」

典型例として

.*a|b

b

.*a

a

b

Russ Cox は 2009 年にこれを指摘しており、BurntSushi の rebar ベンチマークは RE2、Go、Rust 全てで入力が倍増するとスループットが半減することを確認しています。

なぜ長い間見逃されていたのか？

多くの学術的正規表現論文は「単一一致問題」に焦点を当てています。理論ではすべてを「マッチする／しない」という yes/no の質問に還元します。これでは一致がどこで起きるか、何個あるか、その長さは無視されます。「マッチするかしない」だけを考えると、全一致問題は見えなくなります。

バックトラッキングエンジンはさらに悪いです：ユーザーが入力したパターンと 50 文字の入力で、宇宙の熱的死よりも長くかかる指数時間に陥ることがあります。Thompson の NFA 構築（1968）はこれを回避しましたが、バックトラッキングは多くのエンジンでデフォルトです。私の GitHub セキュリティアラート（2026 年 3 月）では、npm の glob マッチャー

minimatch

二次的全一致問題はより微妙で、バックトラッキングを避けるように設計されたエンジンにも影響します。ブラウザをクラッシュさせるほどではありませんが、1 秒の検索を 3 時間に変える可能性があります。

歴史的解決策

Aho–Corasick（1975）

固定文字列 のみの場合、Aho–Corasick アルゴリズムは O(n) ですべての出現を見つけます。トライに失敗リンクを構築し、マッチすると正確に終点が分かるため再スキャンが不要です。ただし文字列がリテラルのみの場合に限ります。

Hyperscan / Vectorscan

これらのエンジンは earliest‑match（最初にマッチ状態に入った瞬間を報告）というセマンティクスを採用します。ネットワーク侵入検知では問題ありませんが、

grep

a+

aaaa

REmatch（VLDB 2023）

すべての有効

(start, end)

a+

aaaa

RE# – 二段階線形時間全一致

RE# はパターンや入力に関係なく、すべてのマッチを二つのパスで見つける最初の正規表現エンジンです。セマンティクスは変更しません。

1. 逆 DFA がマッチ開始位置となり得る場所をマークします。
2. 順 DFA が各マークされた位置で最長マッチを解決します。

マッチは再起動せずに後から報告されます。アルゴリズムは任意のパターンに対して機能し、文字列がリテラルのみという制限はありません。

ハードナードモード

二段階で再起動コストを排除したものの、順方向パスではまだ一度に一つのマッチしか解決できません。曖昧な境界を持つ悪質なパターン（例：

.*a|b

ハードナードモード は順方向パスを O(n × S) の走査に置き換えます (

S

通常モードは二次的ですが、ハードナードは線形を保ちます。

ハードナードモードの使用タイミング

• 不正、ユーザー提供パターン：攻撃者が悪質なケースを作成できる場合。
• セキュリティクリティカル環境（例：Web サービス、ログパーサ）。

let re = Regex::with_options(
    pattern,
    EngineOptions::default().hardened(true)
)?;

通常テキストでは、二次的ケースを引き起こす可能性のあるパターンに対して 3〜20 倍程度の遅延が生じます。実際には

[A-Z][a-z]+

Aho–Corasick との比較

RE# のハードナードモードは、マッチ長が事前に分からない完全正規表現へ Aho–Corasick を拡張したものです。逆パスで確認済みの開始位置だけに新しい候補を追加し、アクティブなマッチ候補セットを保持して各文字で全候補を導関数（derivative）で進めます。

ベンチマーク（2 663 語の辞書 vs 約 900 KB のプローズ）：

regex

RE# は派生ベースの DFA が小さく、キャッシュ効率が高いため、二段階であっても高速です。

スキップアクセラレーション & リテラル重視パターン

RE# には AVX2/NEON 用の手書き実装があります：

• レアバイト検索
• テディマルチポジションマッチング
• 文字クラススキャン（範囲ベース）

これにより、リテラル重視のベンチマーク（rebar スイート）で

regex

ストリーミングとその他制限

find_all

.*?

実践例：

re

grep ツール

RE# は多項語 Boolean 検索とスコーピングをサポートする簡易 grep ライクなユーティリティです。

# "unsafe" と "unwrap" の両方が含まれる行を検索
re --near 5 -a unsafe -a unwrap src/

# "serde" と "async" 両方を含むファイル一覧
re --scope file -a serde -a async src/

RE# パターンを直接使用することも可能です。

今後の展望

RE# はまだ開発中で、正式な 1.0 リリースは未定ですが進捗は続いています。PLDI に条件付きで受理された論文があります。今後はキャプチャグループ対応とハードナードモードを lookaround 向けに改善する予定です。