2015年7月30日

正規表現：悪い表現、いい表現、最良の表現

Regexes The Bad, the Better, and the Best

(2015-06-18)by Liz Bennett

本記事は、原著者の許諾のもとに翻訳・掲載しております。

わずかな文字がいかにしてパフォーマンスに大きな違いを生めるかというお話

正規表現は、私たち開発者がことあるごとに駆使する呪文のようなものですが、私たちはそれをどんな時も巧みに使いこなしていると言えるでしょうか。正規表現は繊細で精密な言語です。入念な慎重さで記述してやれば、ボウリングで一瞬にして完璧なストライクを取るような強力なテキストとなり得ます。 しかし、正規表現が精密さに欠ける状態で投げ出されると、さながら酔っ払いがよろよろとつまずきながらテキストの上を歩くがごとく、そのボールはぎこちなくボウリングのレーンを転がり、ピンを1つか2つ倒すだけで終わってしまうのです。 これら2つの正規表現の違いは何なのか。何がいい表現と悪い表現を分けるのか。正規表現に素晴らしい力を与えるメカニズムを、この投稿で明かしてみようと思います。効果的な表現とそうでない表現との大きな違いをきっと分かってもらえるはずです。賢く使えば、あなたの正規表現もより巧みさを増すことでしょう。最初にお断りしておきたいのは、この投稿は読者の皆さんが正規表現の構成や使い方を十分に理解していることを前提としています。正規表現にまだあまりなじみのない方は http://www.rexegg.com/ のサイトをチェックしてみてください。正規表現についての詳細なチュートリアルや豊富なスタートガイドだけでなく、掘り下げたアドバンステクニックなども網羅されています。既に十分な知識がある方でもブックマークしておいて損はないサイトです。

悪い正規表現といい正規表現の比較

次の2つの表現を比べてみましょう。

.* (.*)\[(.*)\]:.*

[12]\d{3}-[01]\d-[0-3]\d (.*)\[(.*)\]:.*

これらの表現は、以下のフォーマットのテキストにマッチするように記述されています。

2014-08-26 app[web.1]: 50.0.134.125 - - [26/Aug/2014 00:27:41] "GET / HTTP/1.1" 200 14 0.0005

抽出される重要な情報は “app” と “web.1” 、つまり最初と2番目のキャプチャグループです。

どちらがいい表現か

どちらがいい正規表現でどちらが悪い表現だと思いますか。きっと皆さんなら正しく答えられるでしょう。では、より難しい質問をしますね。 いい表現に比べて、悪い表現はどれくらい悪いですか。どの入力データが原因で、悪い方はいい方よりも悪くなっているのでしょうか。

通常、長い方がいい正規表現

2つ目︵下︶の方が1つ目︵上︶よりもいい正規表現です。それはなぜでしょうか。いいインジケータは長いものです。いい正規表現は明確な文字・文字クラスを使用し具体的な構造を有しているため、往々にして悪い表現よりも長くなります。これによって精度の高い入力データの予測が可能となり、高速な処理ができるというわけです。マッチしない入力データをより速く特定できれば無駄なサイクルを減らせますよね︵言うまでもありませんが、正規表現の精度が高ければ高いほど、そのつもりもないテキストが誤ってマッチするようなことも少なくなります︶。上の例だと、マッチする入力データは常にタイムスタンプで始まっています。タイムスタンプ自体から何らかの情報が抽出されるわけではありませんが、いい方の正規表現ではそれが符号化されています。

マッチしない入力データの処理は、マッチする入力データよりもはるかに時間がかかる

正規表現のベンチマークの際に念頭に置いてほしいのは、マッチしない入力データの処理は、時にマッチする入力データよりもはるかに時間がかかるということです。マッチする入力データの場合、正規表現は大抵、処理の最中のある時点でマッチしますが、マッチしない入力データの場合、マッチしていないものとして正規表現が確認されるまでに何度も試行されることもあるからです。これを実証するため、上のそれぞれの正規表現が次のマッチしない入力データをどう扱うかを見ていきましょう。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

悪い正規表現はマッチしない入力データに対してどのように実行されるか

悪い正規表現は以下のような感じです。メインのセクションには色付けしています。

.* (.*)\ [ (.*) \]:.*

1.　正規表現は .* で始まりますが、 * が貪欲なため、最初にできるだけ多くのテキストを取得するべく全てのイベントをスキャンします。 ^(1)

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

2.　最後まで行くと、最初のスペースに到達するまでバックトラックします。求めているのは左角括弧の前にある（長さ0のこともありますが可能な限り長い）文字列(.*)[です。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

3.　0.0005をスキャン後、左角括弧に遭遇しない限り、バックトラックを続けて前のスペースを探します。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

4.　このスキャニングと再スキャニングは、イベント内の3番目のスペースに到達するまで各スペースで続きます。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                          

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                               

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                             

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                             

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

5.　左角括弧の前の長さ0の文字列を見つけると（この場合、最初のキャプチャグループは空です）、先に進んで \[.*\]: を照合します。ここに別の .* があるため、再びイベント全体を消費しますが、今回は右角括弧を探します。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

6.　右角括弧を見つけました。しかし、求めていたコロンが見当たらずに失敗したため、再びスキャンに戻って他に右角括弧がないか探します。右角括弧が他になければ、バックトラックに戻りスペースを探します。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

7.　2番目のスペースまで行き、少しバックトラックをして、やっと先頭に戻ります。

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
            

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005
                                                                       

50.0.134.125 - - [26/Aug/2014 00:27:41] \"GET / HTTP/1.1\" 200 14 0.0005

8.　他にできることはなく、マッチングは失敗に終わります。この正規表現では、スキャニングと再スキャニングのほとんどが徒労に終わりました。このようなテキスト処理を防ぐ方法はいくらでもあります。その一部を後ほどカバーしたいと思います。

いい正規表現はマッチしない入力データに対してどのように実行されるか

次は2つ目の正規表現を検討してみましょう。こちらでは数字の1か2で始まることが予期されます。なぜなら、入力テキストはタイムスタンプで始まるべきだからです。実際に見ると、入力は5で始まっているためマッチしないことが分かります。簡単ですね。

悪い正規表現といい正規表現のパフォーマンス

ここまでで、マッチしない入力データに対して悪い正規表現がどうして悪く、いい表現がどうしていいのかがお分かりいただけたでしょう。2つ目の正規表現はマッチしない入力データをすぐに特定できましたが、1つ目の表現は入力がマッチしていないことを確定するまでに多くの無駄足を踏んでいます。私はそれぞれの正規表現 ^(2) で、交互に100万行のマッチしないテキストによるパフォーマンステスト ^(3) を行ってみました。 その結果はというと、悪い正規表現では100万行全ての処理時間が平均1万100ミリ秒に対し、いい表現ではたったの240ミリ秒です。悪い方はかなり悪いですね。約42倍も多く時間がかかっています。

悪い正規表現といい正規表現はマッチするテキストに対してどのように実行されるか

マッチしないテキストについては、もういいでしょう。次はマッチするテキストを見ていきます。この投稿の最初からマッチするテキストに対して同じ100万行テストを行ったところ、入力データのマッチング処理結果は、悪い正規表現で平均1万7800ミリ秒、いい正規表現では4700ミリ秒でした。悪くない数字です。ただ、もっとよくできます。

最良の正規表現

ここで、 最良の ^(4) 正規表現を紹介せてください。

[12]\d{3}-[01]\d-[0-3]\d ([^ \[]*?)\[([^\]]*?)\]:.*

最良の正規表現といい正規表現を分けるものは何か

この3つ目の正規表現では、前述した2つの正規表現における不必要なスキャニングをほとんど全て回避することができます。その実現のためにやることは次の2点です。 (一)量指定子を含める ことで、アスタリスクが何文字を消費するべきかを指定する。私は最後の 以外、全て?に置き換えました。 (二)単にピリオドを使うではなく、 どの文字がマッチするか ︵マッチしないか︶ を明示する 。私は最後のピリオド以外、全て否定文字クラスにしました。︵ほとんどないものの︶時には .＊ が︵3つ目の正規表現の最後に︶適切な場合もありますが、上で見たような入力テキストの過度なスキャニングのため、通常はそんなことはありません。3つ目の正規表現では、最後以外の全ての＊を＊?に置き換えたことで、アスタリスクはある意味、怠惰になりました。できるだけ少ないテキストを消費するようになり、スキャンの方法も入力データの端の右から左ではなく、現在のインデックスの左から右に変わっています。また、ピリオドについても最後の.以外の全てを否定文字クラス、すなわち [^ \]] に変更しました。これら2つの変更により、正規表現は左から右へとスキャンしつつスペース区切りや括弧閉じのない文字を探すことになり、マッチする／しない入力データのスキャン量が大幅に減ることになるのです。

最良の正規表現のパフォーマンス

最良の正規表現でテストを再実行した時、マッチしない入力データのテストではかかる時間に変わりはありませんでしたが、マッチする入力データの時は平均で800ミリ秒でした。いい正規表現で4700ミリ秒、悪い正規表現だと1万7000ミリ秒程度なので、これは大きな違いです。 同じ入力テキストから同じ情報をマッチするのに20倍強の開きがあるわけですからね。すごいことです。

今回のお話の教訓

もしあなたが速度の必要なでアプリケーションを作成しており、そこで正規表現を頻繁に使っているようなら、可能な限り正確な正規表現を作り上げることで多くの計算サイクル数を省くことができるようになります。ここに挙げた例は、正規表現と入力データの潜在的な広がりに比べればその適用は非常に限られたものです。ただ、ボウリング王者のボールと酔っ払いのボールの軌道、つまりよく練り上げられた正規表現と未熟な正規表現の違いの大きさは示せたと思います。ご自身の使用目的に合わせるため、何をマッチしようとしているかを、入念に、そして正確に検討しましょう。 正規表現を具体的にすれば、仮に長くなったとしても、パフォーマンスに違いを生み出せます。 マッチを確定するスキャン文字数が少ないほど、正規表現は速くなるのです。正規表現を驚くほど速くするのに効果的な方法はいくつかあります。次の投稿では、それらについて、1つずつ見ていきたいと思いますので、楽しみにしていてくださいね。

全ての正規表現のエンジンがここで説明したとおりに動くわけではありません。この投稿のステップスルーはJavaやRuby、PerlやPython、そしてPHPが使う（最適化されていない）アルゴリズムを示したもので、再帰的なバックトラックアルゴリズムです。AwkやgrepはThompson NFAアルゴリズムを使っています。実際のところ、それはどのような点においてもかなり高速ですが、サポートしている機能は制限されます。この2つのアルゴリズムについて、 https://swtch.com/~rsc/regexp/regexp1.html のサイトに詳細な説明があるので、ご興味のある方はご覧ください。 ↩
それぞれの正規表現は事前にコンパイルされています。正規表現を繰り返し使う場合、使用前にコンパイルすることでもパフォーマンスを大幅に向上させることが可能です。 ↩
パフォーマンステストは、正式な基準値取得を目指したものではなく、ちょっとした実証に過ぎません。テスト環境は2014年のMacbook、OpenJDK 1.7上で行いました。テスト用のコードについては https://github.com/zzbennett/RegexPerfTest/blob/master/Main.java をご覧ください。 ↩
技術的には、この正規表現はいまだ”最良”とは言えません。最適化できる点が残されているからです。ただ、その最適化は正規表現のパフォーマンスをぐっと引き上げはするものの、私の意見では正規表現をかなりの度合いで複雑にし、また時間がかかる上、作成には専門知識も必要とされます。この投稿で説明した最適化はパフォーマンスの点で間違いなく大きな改善をもたらしてくれつつ、同時に読みやすさも維持したものです。更なる最適化についてもっと知りたい方は http://www.rexegg.com/regex-quantifiers.html#explicit_greed をご覧ください。 ↩

古川陽介
株式会社リクルート　プロダクト統括本部　プロダクト開発統括室　グループマネジャー株式会社ニジボックス　デベロップメント室室長 Node.js 日本ユーザーグループ代表

複合機メーカー、ゲーム会社を経て、2016年に株式会社リクルートテクノロジーズ(現リクルート)入社。現在はAPソリューショングループのマネジャーとしてアプリ基盤の改善や運用、各種開発支援ツールの開発、またテックリードとしてエンジニアチームの支援や育成までを担う。 2019年より株式会社ニジボックスを兼務し、室長としてエンジニア育成基盤の設計、技術指南も遂行。 Node.js 日本ユーザーグループの代表を務め、Node学園祭などを主宰。

Twitter: @yosuke_furukawa
Github: yosuke-furukawa