Tools + Simulatorsnanase.cc / tools

正規表現

オプション

例

照合の手順

比較中不一致・後戻り追跡中の状態照合中の範囲一致
0 / 0 手順
速さ 速さ

回/秒

方式文字の比較後戻り同時に追跡した状態の最大DFA の状態一致使われている所

文字の比較
0
一致
0 件
後戻り
0
スタックの深さ
0

動作原理と式

正規表現と有限オートマトン

正規表現は文字列の集合（言語）を表します。連接・選択・繰り返しの 3 つで組める言語を正規言語と呼びます。

L(rs)=L(r)L(s)L(r|s)=L(r)∪L(s)L(r*)=⋃k≥0L(r)k

Kleene の定理によると、正規表現で書ける言語と有限オートマトンが受理する言語は一致します [1]。有限オートマトンには有限個の状態があり、1 文字読むごとに状態を移ります。同じ文字で行き先が複数ある NFA も、行き先が 1 つに決まる DFA も、受理できる言語は同じです [2]。

パターンから NFA を組む

Thompson の構成では、パターンの部品ごとに入口と出口が 1 つずつの小さな NFA を作り、つなぎ合わせます [3]。ε は文字を読まずに進む矢印です。

  • 文字 a: 2 つの状態を a の矢印でつなぐ
  • 連接 rs: r の出口を s の入口につなぐ
  • 選択 r|s: 新しい入口から r と s へ ε で分かれ、両方の出口を新しい出口へまとめる
  • 繰り返し r*: 入口から r と出口へ分かれ、r の出口から入口へ戻る
  • r+ は rr*、r? は r|ε、r{2,3} は rr(r|ε) と同じ形

1 つの部品で増える状態は 2 個までなので、パターンの長さを m とすると状態は 2m 個以下です。{'{m,n}'} は部品を複製するので、そのぶん長くなります。

NFA の同時シミュレーション

今いる状態の集合 Si を持ち、文字 ci を読むたびに全部の状態を同時に進めます [3]。E は ε の矢印だけでたどれる状態を足す操作です。

Si+1=E({δ(q,ci)∣q∈Si})

集合の大きさは 2m 以下で、文章は 1 回しか読みません。文章の長さを n とすると手間は O(𝑚𝑛) で、後戻りはありません [4]。

Pike VM は集合の各状態にキャプチャの位置を持たせます [5]。集合を優先順に並べ、同じ状態に 2 本たどり着いたら先のほうだけ残します。これでバックトラックと同じく、左に書いた選択肢を優先した一致が得られます。

NFA から DFA へ

部分集合構成では、NFA の状態の集合 1 つを DFA の状態 1 つにします [2]。DFA は 1 文字につき表を 1 回引くだけで進みます。ただし集合の数だけ状態ができうるので、最悪で指数個になります。

|QDFA|≤2|QNFA|

(a|b)*a(a|b){k} は最後の k+1 文字を覚えておく必要があり、a と b だけの文章でも 2k+1 個の状態が要ります。

遅延 DFA は文章で実際にたどった状態だけを作り、キャッシュに残します。1 回の検索で新しくできる状態は n+1 個までです。RE2 はキャッシュがあふれると全部捨てて作り直し、それが続くと NFA に切り替えます [6]。

バックトラックの手間

バックトラックは分かれ道で 1 つを選んで進み、失敗すると後戻りして次を試します [4]。(a+)+b を a が n 個の文章に当てると、外側の + が a の並びをいくつに分けるかを全部試します。隣り合う a の間ごとに「切る・切らない」があるので、分け方は次の数です。

2n−1∑k=1n2k−1=2n−1

b がないのでどれも失敗し、開始位置を 1 つずらして同じことを繰り返します。右の式が開始位置すべての合計です。a が 12 個では文字の比較が約 24,547 回になります。メモ化と NFA は同じ (状態, 位置) を 1 回しか調べないので約 60 回です。

破滅的バックトラック（ReDoS）への対策

手間が指数的に増えるパターンに長い文章を渡すと、サーバーが長く応答しなくなります。これが ReDoS で、公開のパッケージにも多く見つかっています [7]。

  • Ruby 3.2: 分かれ道で (命令, 位置) の組を覚え、同じ組を 2 度調べない [8][9]
  • Ruby 3.2 のメモ化の範囲: 後方参照・先読み・後読みを含むパターンでは使わない。それ以外の備えとして Regexp.timeout を足した [8]
  • RE2・Rust の regex: 後方参照と先読み・後読みを捨て、文章の長さに比例する時間を保証する [10][11]
  • .NET: 照合に時間の上限を付けられ、超えると RegexMatchTimeoutException を出す。既定は上限なし [12]
  • .NET 7 以降: RegexOptions.NonBacktracking で線形時間の照合を選べる。後方参照・先読み・後読み・アトミックグループは使えない [13]
  • V8: 試験的な線形時間のエンジンがあり、フラグを付けたときだけ動く。後戻りが 50,000 回を超えたら切り替える設定もある [14]

メモ化の表は命令の数と位置の数の積で、時間もメモリも O(𝑚𝑛) です。

後方参照が NFA・DFA で扱えない理由

後方参照 \1 は、キャプチャした文字列と同じものをもう一度求めます。^(a*)b\1$ に一致する文章は次の集合です。

{akbak∣k≥0}

b の前の a の数を覚えるには無限個の状態が要るので、この言語は正規言語ではありません。有限個の状態しか持たない NFA と DFA では表せません。後方参照つきの照合は NP 完全で [15]、効率のよい方法は知られていません。

計算量

n は文章の長さ、m はパターンの長さです。照合は文章を 1 回調べる最悪の手間、前処理は照合の前に作るものの大きさです。

照合前処理後方参照使われている所出典
バックトラックO(2𝑛) など指数O(𝑚)使えるJavaScript・Python・Perl・Java・PCRE[4]
バックトラック＋メモ化O(𝑚𝑛)、メモリも O(𝑚𝑛)O(𝑚)あるとメモ化を止めるRuby 3.2 以降[8][9]
NFA シミュレーションO(𝑚𝑛)O(𝑚)使えないThompson 1968・Pike VM（RE2・Go）[3][5]
遅延 DFAO(𝑚𝑛)、状態がそろえば O(𝑛)O(𝑚)使えないRE2・Rust の regex・GNU grep[6][11]
DFAO(𝑛)O(2𝑚)使えないlex・flex[2]

出典

  1. 正規表現と有限オートマトンの対応S. C. Kleene, “Representation of Events in Nerve Nets and Finite Automata,” in C. E. Shannon, J. McCarthy (eds.), Automata Studies, Annals of Mathematics Studies 34, Princeton University Press, pp. 3–42, 1956
  2. NFA と部分集合構成M. O. Rabin, D. Scott, “Finite Automata and Their Decision Problems,” IBM Journal of Research and Development, vol. 3, no. 2, pp. 114–125, 1959
  3. NFA の組み方と同時シミュレーションK. Thompson, “Programming Techniques: Regular expression search algorithm,” Communications of the ACM, vol. 11, no. 6, pp. 419–422, 1968
  4. バックトラックと NFA の比較、DFA の状態のキャッシュR. Cox, Regular Expression Matching Can Be Simple And Fast, 2007
  5. Pike VM とキャプチャR. Cox, Regular Expression Matching: the Virtual Machine Approach, 2009
  6. RE2 の DFA のキャッシュR. Cox, Regular Expression Matching in the Wild, 2010
  7. ReDoS の実態J. C. Davis, C. A. Coghlan, F. Servant, D. Lee, “The impact of regular expression denial of service (ReDoS) in practice: an empirical study at the ecosystem scale,” ESEC/FSE 2018, pp. 246–256
  8. Ruby 3.2 のメモ化とタイムアウトRuby, Ruby 3.2.0 Released, ruby-lang.org, 2022
  9. メモ化で ReDoS を防ぐJ. C. Davis, F. Servant, D. Lee, “Using Selective Memoization to Defeat Regular Expression Denial of Service (ReDoS),” 2021 IEEE Symposium on Security and Privacy
  10. RE2Google, RE2, README, GitHub
  11. Rust の regexregex crate documentation, docs.rs
  12. .NET のタイムアウトMicrosoft, Best Practices for Regular Expressions in .NET, Microsoft Learn
  13. .NET の NonBacktrackingMicrosoft, Options for regular expression, Microsoft Learn
  14. V8 の線形時間のエンジンM. Bidlingmaier, An additional non-backtracking RegExp engine, V8 blog, 2021
  15. 後方参照つきの照合は NP 完全A. V. Aho, “Algorithms for Finding Patterns in Strings,” in J. van Leeuwen (ed.), Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, Elsevier, pp. 255–300, 1990

関連ツール

すべてのツール