Ruby 3.2では正規表現の高速化が行われ、ReDoSへの対策が行われています。
https://techlife.cookpad.com/entry/2022/12/12/162023
https://rubykaigi.org/2023/presentations/makenowjust.html#day1 (RubyKaigiでの発表)
Rubyでは正規表現をNFA (非決定性有限状態オートマトン) に変換をし、文字列を入力としたオートマトンを受理するかどうかで文字列が正規表現にマッチするかを判定しているらしいです。
NFAの場合、愚直に処理をすると同じ位置かつ同じ状態をたくさん通ることがあり、計算量が増えてしまうことがあるためRuby3.2ではキャッシュ (メモ化) を行うことで速度改善を実現しています。
さて、この記事では簡単なオートマトンを処理するためのコードを作ってみて、実際に高速化を体験してみます。
今回検証する正規表現
Rubyの公式リリースでも利用されていたa*b?a*で試してみます。
aが0回以上、その後bが0回か1回、最後にaが0回以上という正規表現です。
受理される文字列は空文字、a、b、ab、aa、baなどがあります。
これをオートマトンにするとこのようになります。（少々見にくいですが、1->0と7->6は文字なしでの遷移ができます）
実際に処理するものを作ってみる
require 'benchmark'
str = 'a' * 100000 + 'x'
nodes = [
[[1,'a']], # 0
[[0,'ε'],[5,'ε']], # 1
[[0,'ε'],[5,'ε']], # 2
[[4,'b']], # 3
[[8,'ε']], # 4
[[3,'ε'],[8,'ε']], # 5
[[7,'a']], # 6
[[6,'ε']], # 7
[[6,'ε']], # 8
]
accept_states = [7,8]
states = [2] # Start state
next_states = []
is_accept = false
num = 0
Benchmark.bm 10 do |r|
r.report "実行結果" do
while states != [] && str.length >= num
state = states.pop
nodes[state].each do |node|
if node[1] == 'ε'
if (str.length) == num && accept_states.include?(state)
is_accept = true
break
end
states.push(node[0])
elsif node[1] == str[num]
if (str.length) == (num + 1) && accept_states.include?(state)
is_accept = true
break
end
next_states.push(node[0])
end
end
if states == []
states = next_states
next_states = []
num += 1
end
end
end
end
puts is_accept ? "Accept" : "Reject"
コードに関して簡潔に説明をすると、strが処理したい文字列、nodesがオートマトンを表しています。
nodesでは各状態でどの文字を受理したら、どの状態にいくのかを記述しています。
accept_statesは受理状態の集合で、最後の文字を処理しているときにこの状態に到達できれば受理、ということになります。
n文字目の時、オートマトンで行ける状態を見て、移動するための文字がεであればn文字目として処理し、それ以外の文字ではn+1文字目として処理をするように書いています。Rubyではバックトラックを使うため状態遷移に差異があります。
（直感的にはバックトラックの方が処理は早いしメモリの節約ができそう）
実際に動かしてみる
str = 'a' * 1000 + 'x'
user system total real
実行結果 0.274267 0.000934 0.275201 ( 0.275234)
str = 'a' * 5000 + 'x' の時
user system total real
実行結果 7.143607 0.027188 7.170795 ( 7.184600)
str = 'a' * 10000 + 'x' の時
user system total real
実行結果 27.995554 0.097920 28.093474 ( 28.133852)
文字数に対して、曲線的に増えているのが分かります。($O=n^2$になっている)
改善をしてみる
今回作ったオートマトンでは、一通り処理が終わったら次の文字にいくという処理をしています。
ここに簡易的に出力をを仕込んでみます。
if states == []
p next_states
states = next_states
next_states = []
num += 1
end
それでは実行してみます。
[7, 1, 7]
[7, 7, 1, 7]
[7, 7, 1, 7, 7]
[7, 7, 7, 1, 7, 7]
・・・
7の状態が文字の処理が終了する毎に増えていて、文字が長くなればなるほど処理時間が曲線的($O=n^2$)に伸びていくのが分かります。
それでは改善をしてみます。
本家Rubyではメモ化をしていましたが、今回は一文字ずつ処理をしている都合上、純粋に次の文字に入れるときにuniqを入れたり、next_statesにpushするときに既に入れたい数字が入ってないかをみるだけで良さそうです。
elsif node[1] == str[num]
if (str.length) == (num + 1) && accept_states.include?(state)
is_accept = true
break
end
+ next_states.push(node[0]) unless next_states.include?(node[0])
- next_states.push(node[0])
end
デバッガを仕込んだまま実行してみます。
[7, 1]
[7, 1]
[7, 1]
[7, 1]
なんとなくきちんと動いてそうです。
それでは実際に測ってみましょう。
str = 'a' * 1000 + 'x'
user system total real
実行結果 0.003011 0.000073 0.003084 ( 0.003104)
str = 'a' * 5000 + 'x' の時
user system total real
実行結果 0.013848 0.000085 0.013933 ( 0.013931)
str = 'a' * 10000 + 'x' の時
user system total real
実行結果 0.026625 0.000066 0.026691 ( 0.026700)
str = 'a' * 1000000 + 'x' の時
user system total real
実行結果 2.625518 0.002597 2.628115 ( 2.628164)
計算量が大体$O=n$になっています。同じ位置で同じ状態を通る重複を減らすことで処理を早くすることができました。
まとめ
今回はRuby3.2で入った正規表現の高速化をオートマトンを実際に動作させることで、体験してみることができました。
実際にはバックトラックに実装を書き換えればもっと早くできると思います。
Rubyでは今回の例題よりも、もっと複雑だったり状態数も多い正規表現を処理したりするので、こんな簡単なコードにはならないですが、今回の主題（高速化）に関してのみフォーカスするなら十分でしょう。
正規表現様々な場所で使われており、ここが早くなることでRubyを使ったアプリケーションの処理速度も変わってくるので、今後も高速化を期待したいところです。
REF
https://github.com/Umekawa/automaton-rb (今回試したソースコードが転がっています)