正規表現マッチングの処理時間にも気をつける
本記事は Sansan Advent Calendar 2022 - Adventar の初日の記事です。
正規表現は文字列マッチングにおいて、とても便利な機能です。 基本的に各プログラミング言語でライブラリとして実装されており、利用可能です。
そんな正規表現ですが、例えば貪欲な探索を長い文字列を対象に使うと、もちろん結構遅くなります。
どれくらい処理時間が遅くなるかを調べる簡素なツールを作り、確認してみました。
ツールを作る
ある任意の文字列（string）を含むランダムな任意の長さの文字列（random string）から、正規表現（regex）に一致する表現を取り出す、ということをN回行うツールを作りました。
使い方は以下です。
$ regbench "\d+番" "背番号は10番" --search-target-length=50 --number_of_trials=10 Trying 10/10 {"times": 10, "total_elapsed_sec": 7.191700000001161e-05, "average_search_sec": 7.191700000001161e-06, "method": "search", "pattern": "\\d+番", "string": {"head_of_last_trial_string": "vAboTdcPQs", "length": 50}, "matched": {"head_of_matched": "10番"}}
引数に、正規表現、任意の文字列、その他オプションの順で渡します。
上記の場合だと、「背番号は10番」という文字列をどこかに含んだ50文字の文字列が生成されます。これを対象に正規表現「\d+番」に一致するものがないかを調べます。これを10回繰り返します。 結果、正規表現と一致するものを探す処理に約7.19e-5秒かかっていることがわかります。
マッチ時間の一例
生成する文字列長は50,000文字、試行回数は10回、re.search でマッチする要素を取得します。
以下に、正規表現や検索対象に含める文字列を変更した際の結果を示します。
| 正規表現 | 検索対象に確実に含める文字列 | 平均処理時間 |
|---|---|---|
| test | test | 2.5970899999998993e-05 |
| test | hoge | 4.0716699999999996e-05 |
| .test | test | 0.0001207250000000007 |
| .test | hoge | 0.0003335540999999994 |
| .* test | test | 4.220839999999892e-05 |
| .* test | hoge | 1.4453570459000002 |
| .* test$ | test | 1.4394586875 |
| .* test$ | hoge | 1.4445743792 |
正規表現パターンが単純な文字列や任意の一文字の場合は平均処理時間はかなり短いです。
一方で、任意の一文字以上繰り返しを含めると、結果が異なります。検索対象が確実に含まれる場合と含まれない場合で、処理時間が大きくことなります。
re.search ですので、マッチした時点で終了です。 .*test の場合、検索対象に正規表現が含まれない場合は探索時間が延びています。
これは、探索回数が多い正規表現だったためです。
一回のマッチングに1秒かかることには衝撃を受けました。
正規表現のバックトラック
正規表現で分岐が発生する場合、マッチに失敗した場合は分岐前の状態に戻り、別の分岐にマッチするかを試します。 ここでの分岐前の状態に戻る動作がバックトラックと呼ばれています。 バックトラックにより探索のステップ数が爆発的に増えていくことが、処理時間が長くなる原因です。
以下のサイトを使うと、正規表現のステップ数が確認できます。
これを悪用した正規表現マッチングでの過負荷によるサーバー停止を狙ったReDosというのがあるようです。
とはいえ、実装中に気づくのは難しいので確認する
防ぐために簡単に思いつくのは、理論的に理解して実装しないこと、マッチ時と非マッチ時のステップ数を確認すること、実際のデータで検証してみることかと思います。
