Hatena::ブログ(Diary)

Atzy->getLog() このページをアンテナに追加 RSSフィード

2011年03月09日

[] 欲張り正規表現  欲張り正規表現を含むブックマーク

分かっているようで分かっていない正規表現の欲張り戦略。

欲張りとバックトラック

基本的には正規表現(の実装)は欲張りです。できるだけ長い文字列をマッチしようと心がけます。しかし、それによってマッチに失敗しそうであったときにはしぶしぶ手放します。

と、これが何を意味するのか。

単純な例
 正規表現 A*
 マッチ対象 AAAAAAAAAAAAAAAAAAAAA
 A*のマッチ箇所 AAAAAAAAAAAAAAAAAAAAA (全体にマッチする)

A* というのは、0文字以上のAですから、AAAやらAやら、あるいはAの前の空の部分にさえマッチしますが、欲張って最大限にマッチしようとします。

少しだけ複雑に
 正規表現 \w*\w
 マッチ対象 AAAAA
 \w*\wのマッチ箇所 AAAAA (全体)
 \w*のマッチ箇所 AAAA (4文字分)

\w*\wという正規表現です。この場合は、\w*は1文字分だけ「諦めます」。諦めるというのはどういうことなのか。

つまり、このマッチの処理を考えてみると、まず、\w*は欲張って最大に取得します。つまり全体である「AAAAA」にマッチしようとします。その上で、次の処理として最後の\wをマッチしようと試みますが、既にマッチできるものが存在しません。

したがって、しぶしぶ\w*は「AAAAA」へのマッチを諦めます。そして「じゃあ、1文字だけ譲ってやるよ」と次善の策として「AAAA」へのマッチを実施して、最後の\wを「A」にマッチさせます。このような、一つに失敗した時に次善の策を試みていくのがバックトラックです。

バックトラック

この場合は、一文字諦めただけで済みました。しかし、仮に次の場合はどうなるでしょう。

 正規表現 \w*\w\w\w\w\w
 マッチ対象 AAAAA
 \w*\wのマッチ箇所 AAAAA (全体)
 \w*のマッチ箇所 空 (0文字分)

この場合も\w*は最初に欲張って5文字分獲得します。しかし、以降のマッチで失敗するため、1文字諦めて4文字とします。しかしその場合でも失敗します。(\w\w\w\w\wにAの1文字では足りない。)そうやって次々と諦めていって最終的に\w*がマッチする部分は0文字となり、この場合ようやくにマッチに成功します。したがって6度目の正直でマッチに成功した、つまり5回のバックトラックをしたといえます。

このバックトラックのイメージを頭の中できちんと計算できる人が高速な正規表現をかけます。

最短マッチ(非欲張りマッチ)

Perlその他の正規表現では、欲張らないことが可能です。これは \w*? のように、くり返し演算子に?をつけるものです。

この場合を見てみます。

 正規表現 \w*?\w\w\w\w\w
 マッチ対象 AAAAA
 \w*?\wのマッチ箇所 AAAAA (全体)
 \w*?のマッチ箇所 空 (0文字分)

結果だけ見てみると、\w*と同じです。しかし、内部の処理は全く異なります。\w*?はまず欲張らず、AAAAAの前の最初の空間にマッチを試みます。そしてその後、\w\w\w\w\wをAAAAAにマッチさせて成功します。したがって、バックトラックはこの場合にはありません。したがって高速であるといえます。

この場合はマッチの結果が最短マッチでも同じでした。しかし、以下の例では変わってきます。

 正規表現 \w*\w+
 マッチ対象 AAAAA
 \w*\w+のマッチ箇所 AAAAA (全体)
 \w*のマッチ箇所 AAAA (4文字分)
 \w+のマッチ箇所 A (1文字分)
 バックトラック1回
 正規表現 \w*?\w+
 マッチ対象 AAAAA
 \w*?\w+のマッチ箇所 AAAAA (全体)
 \w*?のマッチ箇所 空 (0文字分)
 \w+のマッチ箇所 AAAAA
 バックトラック0回

最長は保証しない

しばしば、正規表現は(非欲張りを使わない場合は)最左最長(longest of leftmost)と呼ばれます。しかし多くの正規表現実装は最長を保証しません。これはどういうことなのか。

詳説正規表現では次のような例が出ていました。

 正規表現 one(self)?(selfsufficient)?
 マッチ対象 oneselfsufficient
 one(self)?(selfsufficient)?のマッチ箇所 oneself
 (self)?のマッチ箇所 self
 (selfsufficient)? 空(selfの後の0文字)

これは(self)?が最初に欲張って、selfとマッチしてしまったため、後ろの (selfsufficient)? が割を食ったという例です。それでもマッチ自体には成功するため、selfはマッチを手放すことをしません。しかし、仮に手放しておけば、(selfsufficient)? がselfsufficientにマッチできるはずですから、最長マッチは oneselfsufficient です。

なお、選択の場合も最長を保証しません。つまり (abc|abcde)をabcdeにマッチさせたときは、abcで満足します。

どうしてそのようなことになっているのか。これは実装上の理由といえるでしょう。仮に最長を保証したければ、マッチに成功しても、他の全ての可能性を求めて全てのバックトラックをくり返し、その上で最長であるものを見つけてくるという実装が必要です。(もっと賢い実装もありえる?)

そのような計算コストをかけてまで最長を見つける意味はあまりないわけですから、PerlにしろJavaにしろ最長を保証することはありません。(なお、保証している正規表現実装もあります。)

強欲マッチ

欲張りマッチに加えて強欲マッチというものがあります。これはJavaPerl(5.10以降!)、あるいは鬼車でも実装されています。

繰り返しの量指定子の後ろに+をつけるというもので、\w++とか\d*+といった記述となります。

強欲なマッチは、一度つかんだ最長マッチを手放さず、繰り返し内でのバックトラックを禁止します。例えば \w++ はAAAに対して複数のマッチ可能性がありますが、AAAにマッチさせてしまえば、AAやAといった別の可能性を振り返ることはありません。

したがって、\w++\wは必ずマッチに失敗します。(\w++は、必ず\wの分をマッチさせ、\wのために残すことをしないから。)

最短(非欲張り)マッチと最長(欲張り)マッチはマッチ箇所の違いはあっても、最終的なマッチ成功・失敗については必ず一致します(試す可能性の順序が異なるだけ)。しかし、強欲マッチの場合には、試さないバックトラックが存在するため、マッチ結果自体が変わりうるのです。

で、それが何なのか、何に使えるのかということですが、正規表現の高速化で私は使います。

例えば、数値に対するマッチを考えます。

 ^[-+]?\d+(\.\d+)?$

この正規表現で、-100とか10.45といったものにマッチすることができます。で、ここで小数点以下の部分(\d+)に注目します。仮に10.4aとか小数点以下の部分に数字以外が来たら、マッチ失敗に決まっています。改めて別の可能性を試すまでもありません。ですから、\d+は過剰機能ですから、\d++で十分といえます。そうでなければ、0.00000000000000000aという文字列について、\d+は0の個数分くらいのバックトラックを繰り返して無駄な努力をするわけです*1

(\.\d+)?については、(\.\d++)?+のようにここも強欲にすることができます。(なぜなら、マッチ末尾なので一度マッチしてしまえば、他の可能性を試す意味がないから。)

強欲とは関係ありませんが、無駄なバックトラックの回数を少なくするためには、先頭部分についても、[-+]?\d+ をやめて、[-+\d]\d*と記述するという手があります。これは賢い手法ですね。(と書いたけど、よく考えると-だけの一文字とかにマッチしちゃうじゃないか。)

Perl5.8まででは、強欲マッチは使えませんが、アトミックグループというものは使えます。これも同様にバックトラック抑止が可能です。これは (?:>正規表現) のような記法です。\w++と(?:>\w+)は同等の意味ですので、こちらで同様の高速化が可能です。

*1:少なくとも最適化の有無によってはそのような無駄な努力をする可能性がある。

トラックバック - http://d.hatena.ne.jp/atzy/20110309/p1