厳密な正規表現による高速化

著者:杉浦

厳密な正規表現による高速化

 正規表現は文字列の集合を一つの文字列で表せる便利な手法で、様々な言語、アプリに実装されています。
 大体の正規表現の行いは文字列の前方から正規表現とのマッチを順に探して弾かれたら終了というわかりやすいものです。また、正規表現のマッチングにはループが行われることが少なくないです。このため厳密に書かれた正規表現は雑に書かれた正規表現より格段高速に動きやすいです。極端な例として次の正規表現があります。

(.*),(.*),(.*),(.*)\r\n

 この正規表現中の()は変数に代入する目的の()です。$1に一つ目のカッコの中身が、$2に二つ目の…といった具合です。正直なところ、csvファイルを読み取る時に私が書いてしまったことのある正規表現です。実際は40列以上のフォーマットでしたのでもっとろくでもない正規表現になっていました。(想定した数以上の列があっても正しいとしてしまうため、速度以外でもろくでもないです)この正規表現は、一行の終わり近くまでを任意文字として読み取っては”,”の数が足りずに最初に戻って、また任意文字として長大な読み取りを行っては”,”の数が足りずに最初に戻って…と繰り返します。こんなことをすれば実行時間が長くなって当然でしたね。この例の()の中の様な部分を厳密に記述することによって、試行されるマッチングがすぐに破棄されるようになり、結果高速化が実現します。例えば

(\d\d),(\d\d),(\d\d),(\d\d)\r\n

とすれば.*によって引き起こされたループすら行われなくなります。

  • この記事いいね! (0)

著者について

杉浦 administrator