💬 NLP

On the Complexity of the Matching Problem of Regular Expressions with Backreferences

本論文は、SETH および三角形検出の仮定の下で条件付き下限を証明し、かつ 1 回使用のバックリファレンスに対して改良された $O(n \log^2 n)$ アルゴリズムを提示することにより、バックリファレンスを伴う正規表現のマッチングの微細な計算量複雑性を確立する。

原著者： Soh Kumabe, Yuya Uezato

公開日 2026-05-11

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Soh Kumabe, Yuya Uezato

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

以下は、論文「バックリファレンス付き正規表現のマッチング問題の複雑性」の解説を、比喩を用いた日常言語に翻訳したものです。

全体像：「正規表現」の交通渋滞

あなたがクラブ（コンピュータシステム）の警備員だと想像してください。入場できる人々のリスト（正規表現）を持っています。

単純なルール：「赤いシャツを着た人だけ」。これはチェックが簡単です。シャツを見て、「赤い？はい、入って」と言います。列が 10 人であれ 1 万人であれ、かかる時間は同じです。
問題点（ReDoS）：時々、ハッカーが警備員を大量の不要な作業に追い込むように仕組まれた特定の列を作ります。一人をチェックして次に進む代わりに、警備員は A 氏をチェックし、次に B 氏、そして再び A 氏、次に C 氏、そして再び A 氏……とチェックし続け、疲れ果てて倒れてしまいます。これを**サービス不能攻撃（ReDoS）**と呼びます。

現実世界では、これが Stack Overflow や Cloudflare といった巨大なウェブサイトのクラッシュを引き起こしました。論文は、100 人のチェックに 10,000 ステップかかるような「二次関数的」な遅ささえも、システムをクラッシュさせるのに十分であると指摘しています。

悪役：「バックリファレンス」

標準的なルールは単純です。しかし、現代の「正規表現」エンジンにはバックリファレンスと呼ばれる、超強力な機能があります。

比喩：
「単語を見つけ、それを記憶し、その後で全く同じ単語が再び現れることを確認する」というルールだと想像してください。

例：「単語を見つけ、それを'X'と呼ぶ。その後、'X'を再度見つける。」
入力が apple ... apple の場合、成功します。
入力が apple ... banana の場合、失敗します。

この機能はプログラマーにとって非常に役立ちますが、警備員の仕事を大幅に難しくします。警備員は以前に見たものを記憶し、現在見ているものと絶えず比較しなければなりません。論文は問いかけます：これらの複雑なルールを処理し、疲れずに済むほど十分な速度を持つ警備員を構築できるでしょうか？

論文の発見：良いこと、悪いこと、そして醜いこと

著者らは、これらのマッチング問題を解くことがいかに難しいかを正確に調査しました。彼らはそれを難易度（なぜ難しいのか）とアルゴリズム（どう解決するか）の 2 つの側面に分けました。

1. 悪い知らせ：ある種のルールは高速化不可能

論文は、特定の種類の複雑なルールについては、それらを高速にするための「魔法の弾」は存在しないことを証明しています。

「三角形」問題：彼らは、2 つの変数（2 つの異なる単語を記憶し、後でそれらを確認する）を使うルールの場合、それを解くことは巨大なソーシャルネットワークグラフ内で三角形を見つけることと同じくらい難しいことを示しました。もしルールを素早く解けるなら、グラフの問題も素早く解けることになります。グラフの専門家たちはグラフの問題が本質的に遅いと考えているため、ルール問題も遅いはずです。
「直交ベクトル」問題：さらに多くの変数を使うルールについては、必要な時間が変数の数に対して指数関数的に増大することを証明しました。鍵の特定の組み合わせをロックから探すようなものです。鍵の数が増えるほど、それを素早く総当たりで試すことは不可能になります。

要点：ルールが複雑すぎると（多くの「これを記憶せよ」機能を使うと）、高速なエンジンを作ることはできません。必ず壁にぶつかります。

2. 良い知らせ：単純なケースに対する「ほぼ線形」の解決策

しかし、論文はある絶妙なポイントを見つけました。彼らは、特定の一般的なルールタイプに焦点を当てました。

「ABCBD」パターン：「単語（A）を見つけ、次に単語（B）、次に単語（C）、次に全く同じ単語 B を再度、そして単語（D）を見つける。」
- 現実世界の例：「ユーザー名を見つけ、次にパスワード、次にメッセージ、次に同じユーザー名を再度、そして署名を見つける。」

著者らは、これは厄介に見えるが、非常に効率的に解けることを発見しました。

従来の方法：以前の手法は図書館のすべての可能な組み合わせをチェックするようなもので、 $O(n^2)$ の時間（二次関数的）を要しました。本が 1,000 ページなら、1,000,000 ステップかかりました。
新しい方法：著者らは、およそ $O(n \log^2 n)$ $O (n lo g^{2} n)$ の時間がかかる新しいアルゴリズムを構築しました。
- 比喩：図書館が**接尾辞木（Suffix Trees）と因数分解森（Factorization Forests）**を使った魔法の索引システムで整理されていると想像してください。すべてのページを読む代わりに、警備員は関連するセクションに直接ジャンプできます。本が 1,000 ページなら、新しい方法はおよそ 10,000 ステップ（あるいはそれ以下）で済み、これは劇的な改善です。

新しいアルゴリズムの仕組み（「魔法のトリック」）

この速度を達成するために、著者らは論文で説明するいくつかの巧妙な技法を使用しました。

接尾辞木（マップ）：入力文字列の巨大なマップを作成しました。このマップは文字列のすべての可能な末尾を示します。これにより、警備員は瞬時に「ああ、この単語'B'はここにも、あそこにも現れている」と確認できます。
Heavy-Light Decomposition（sorting hat）：マップを「重い」パス（非常に一般的なパス）と「軽い」パス（稀なパス）に分割しました。彼らは重い作業を稀なパスでのみ行い、時間を節約しました。
周期性（リズム）：単語が繰り返される場合（「B...B」など）、文字列にはしばしばリズムやパターンが存在することに気づきました。彼らはすべての文字をチェックする代わりに、数学を使ってこれらのパターンを予測しました。
因数分解森（索引）：これは超高速な索引として機能するデータ構造であり、警備員がテキストの長さに関係なく、一定時間でテキストのチャンクがルールに一致するかどうかを確認できるようにします。

結論のまとめ

すべての ReDoS 攻撃を止められるか？ いいえ。ルールが複雑すぎると（「これを記憶せよ」変数が多すぎると）、数学的に遅いことが証明されています。
最も一般的な複雑なルールを修正できるか？ はい！ある単語を記憶し、後で一度だけそれを確認する特定のケース（「ABCBD」パターン）については、著者らは単純なルールとほぼ同じ速度の新しいエンジンを作成しました。
なぜこれが重要なのか？ ソフトウェアエンジニアに伝えます。「バックリファレンスを多用するな、そうすれば遅くなる。しかし、この特定の一般的な方法で使用するなら、新しい手法を使ってシステムを安全かつ高速に保つことができる。」

論文は本質的に、砂に線を引いています：ここが速度制限を破れない場所であり、ここが私たちがより速く走る方法を見つけた場所です。

技術的概要：バックリファレンスを伴う正規表現のマッチング問題の複雑性

1. 問題定義と動機

本論文は、バックリファレンスを伴う正規表現マッチング問題（REWB）の微細な計算複雑性を調査する。古典的な正規表現（Regex）は、Thompson 構成法を用いて入力文字列の長さ $|w|$ に対して線形時間でマッチング可能であるが、実用的なエンジンではバックリファレンス（例：部分文字列を捕捉する (E)x と、それを再利用する \x）がサポートされている。この機能は Regex の表現力を厳密に拡張し（ $\{ww \mid w \in \Sigma^*\}$ のような非正規言語の認識を可能にする）、しかしながら重大なアルゴリズム的リスクをもたらす。

動機は、正規表現によるサービス拒否（ReDoS）攻撃に由来する。敵対者はマッチングエンジンで最悪の挙動を誘発するよう入力を工作する。Stack Overflow（2016 年）や Cloudflare（2019 年）での注目すべき事案は、バックトラッキングベースのエンジンにおける二次時間挙動（ $O(|w|^2)$ ）でさえ、壊滅的なサービス停止を引き起こし得ることを示した。著者らは、根本的な問いを提起する：線形時間または準線形時間で実行される ReDoS 安全な REWB エンジンを構築することは可能か？

本論文は、 $k$ 個の異なる変数を持ち、任意の計算におけるバックリファレンス実行の総数が $r$ に制限される「 $r$ -use $k$ -REWB」に焦点を当てる。

2. 手法と技術的アプローチ

本論文は、条件付き下限（困難性）の確立と、特定の部分クラスに対する効率的なアルゴリズムの設計という二重のアプローチを採用する。

2.1 困難性の結果

著者らは、既知の困難な問題を REWB マッチングに帰着させることで、以前の複雑性結果を強化する：

W[2]-困難性: $k$ -Dominating Set 問題を帰着させることで、REWB マッチングが式サイズ $|E|$ をパラメータとして W[2]-困難であることを証明する。これは既知の W[1]-困難性結果を強化するものである。
条件付き下限（三角形検出）: 三角形検出に対する「準線形時間仮説の不存在（No-Almost-Linear-Time Hypothesis）」を仮定し、極めて制限された2-use 2-REWB問題でさえ、任意の $\delta > 0$ に対して $O(|w|^{1+\delta})$ 時間で解くことはできないことを示す。
条件付き下限（k-OV）: $k$ -直交ベクトル（k-OV）仮説（SETH より弱い）の下で、 $k$ -REWB マッチングは $O(|w|^{2k-\epsilon})$ 時間では解けないことを証明する。これは、一般的な $k$ に対して準線形時間はあり得ないことを意味する。

2.2 アルゴリズム的結果

主要なアルゴリズム的貢献は、1-use REWB（変数が 1 つあり、それが正確に 1 回参照される式）に焦点を当てている。

標準形への変換: 著者らは、任意の 1-use REWB が、 $A, B, C, D$ が古典的な正規表現であるような $A (B)_x C \backslash x D$ の項の和を含む標準形に変換可能であることを証明する。これをABCBD 問題と呼ぶ。
分解戦略: ABCBD 問題は 2 つの部分問題に分解される：
1. XYYZ 問題: $B$ の 2 つの出現が隣接している場合（ $w = w_A w_B w_B w_D$ ）。これは、遷移モノイドから導かれる最終的に周期的集合の性質とCrochemore の最大局所冪数え上げを用いて解かれる。
2. 分岐 ABCBD 問題: $B$ の 2 つの出現が空でない $C$ によって分離され、かつ 2 つの $B$ の直後の文字が異なる場合。
サフィックス木と Heavy-Light 分解: 分岐ケースにおいて、アルゴリズムは入力文字列 $w$ のサフィックス木を利用する。探索空間を分割するためにHeavy-Light 分解を採用する。
データ構造:
- 因数分解フォレスト: 線形前処理後に部分文字列に対する正規表現の所属性を定数時間で評価するために使用される。
- 遷移モノイド: 正規表現 $A, B, C, D$ の状態を効率的に追跡するために活用される。
- カスタム数え上げ器: 著者らは、遷移数え上げを処理するための specialized なデータ構造（RightEnumerator、LeftEnumerator、AuxiliaryEnumerator）を設計する。これらの構造は、部分文字列 $w_B$ の長さによって変化する制約を管理するために、遅延更新と**互いに素な集合の和集合（DSU）**戦略を使用する。

3. 主要な結果

困難性

定理 3: REWB マッチングは、式サイズをパラメータとして W[2]-困難である。
定理 4: 三角形検出仮説を仮定すると、2-use 2-REWB マッチングは超線形時間（具体的には $O(|w|^{1+\delta})$ ではない）を必要とする。
定理 5: $k$ -OV 仮説の下では、 $k$ -REWB マッチングは $\Omega(|w|^{2k-\epsilon})$ 時間を必要とする。

アルゴリズム

定理 7（主要結果）: ABCBD 問題は、 $O(|w| \log^2 |w|)$ 時間のアルゴリズムを許容する。隠れた定数は正規表現 $A, B, C, D$ のサイズに指数関数的に依存する（ $2^{O((|A|+|B|+|C|+|D|)^2)}$ ）。
定理 8: したがって、1-use REWB マッチング問題は、 $O(|w| \log^2 |w|)$ 時間のアルゴリズムを許容する。
定理 9: XY $\alpha$ Z 問題（XYYZ を $\alpha$ 回繰り返しに一般化したもの）は、 $O(|w| \log |w|)$ 時間のアルゴリズムを許容する。

これらの結果は、ABCBD 問題に対する Nogami と Terauchi（MFCS 2025）による以前の最良既知の $O(|w|^2)$ アルゴリズムに対する大幅な改善を表す。

4. 意義と主張

本論文は、REWB マッチングの複雑性ランドスケープに対する根本的な理解を提供すると主張する：

ReDoS 安全性: 一般的な REWB マッチングは準線形時間に対して非現実的である可能性が高いが、実用的に関連する部分クラス（1-use REWB）は準線形時間でマッチング可能であることを確立する。これは、1-use バックリファレンスをサポートするエンジンが理論的に ReDoS 安全にできる可能性を示唆する。
微細な複雑性: 本作業は、処理可能と非処理可能のケースの境界を明確にする。バックリファレンスの使用数を 1 から 2 に増やすこと（変数が 2 つしかない場合でも）は、問題を準線形領域から外れる可能性が高いことを示す。
アルゴリズム的革新: 本論文は、以前は二次時間を必要すると考えられていた問題を解決するために、サフィックス木、因数分解フォレスト、遷移モノイドを組み合わせた複雑だが極めて非自明なアルゴリズム的枠組みを導入する。

著者らは明示的に、自らのアルゴリズムが一様であることを述べている。つまり、固定された式に依存する非一様な助言なしに、式と入力文字列を一緒に処理するものである。彼らは、式サイズ $|E|$ に対する指数関数的依存性が非常に大きな式にとっては依然として制限要因であることを認め、真の線形時間アルゴリズム（ $O(|w|)$ ）が存在するか、あるいは対数因子を除去できるかどうかという問いは未解決のまま残している。

5. 制限と未解決問題

本論文は、いくつかの未解決の方向性を特定する：

$r$ -use 1-REWB の複雑性: $r \ge 2$ である $r$ -use 1-REWB の複雑性は未解決のままである。
線形時間: $O(|w| \log^2 |w|)$ の限界を $O(|w|)$ に改善できるかどうか。
式依存性: $|w|$ に対する準線形依存性を維持しつつ、 $|E|$ に対する指数関数的依存性を多項式に削減すること。
より広範な機能: ルックアラウンド、アトミックグルーピング、貪欲/遅延スターなどの他の実用的な正規表現機能へのこれらの結果の拡張。