LoginSignup
18
4

More than 1 year has passed since last update.

Ruby3.2の正規表現の高速化を、実際にオートマトンを作って体験してみる

Last updated at Posted at 2023-05-11

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回以上という正規表現です。
受理される文字列は空文字、ababaabaなどがあります。

これをオートマトンにするとこのようになります。(少々見にくいですが、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 (今回試したソースコードが転がっています)

18
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
18
4