1. scivola

    Posted

    scivola
Changes in title
+強欲な量指定子(絶対最大量指定子)の使いどころ
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,155 @@
+正規表現の量指定子には「強欲な量指定子」とか「絶対最大量指定子」と呼ばれるものがあります。
+この記事では,どのような場合にこれを使うのか,一例を挙げます。
+
+コード例は Ruby で記述しますが,Ruby をご存知ない方にも分かるよう説明を加えます。
+
+強欲な量指定子に至るまでに,ちょっと遠回りをしますが,ご容赦を。
+
+# テキスト中から〈数字列+"円"〉を拾う
+
+まずは,テキスト中から,〈数字列+`"円"`〉をすべて拾い出したいとします。
+
+Ruby では以下のように書けます。
+
+```rb
+str = "一人250円のお菓子を14個買う"
+
+p str.scan(/\d+円/)
+```
+
+1 行目はローカル変数への文字列代入です。
+
+`/\d+円/` は正規表現リテラルです。
+正規表現を `/ /` で囲むと正規表現リテラルになります。
+
+`str` のあとにピリオドを置いて何かを書いているのは `str` に対するメソッド呼び出しです。
+`scan` は,文字列に対して使えるメソッドです。引数で与えられた正規表現にマッチする部分文字列を検索して,その結果を配列で返します。
+
+`p` はオブジェクトを表示するメソッドです。配列を与えたときは,配列っぽく見える文字列にフォーマットしたうえで表示してくれます。
+
+結果は以下のようになります。
+
+```rb
+["250円"]
+```
+
+マッチする部分文字列が一つしか見出されなかったので,1 要素からなる配列が得られました。
+
+# 後ろに "円" が続く数字列を拾う
+
+今度は,後ろに `"円"` が続く数字列を拾ってみます。`"円"` が続く,といっても,`"円"` 自体は拾わず,数字列だけを拾うようにします。
+
+これは,肯定先読み `(?= )` を使って
+
+```rb
+str = "一人250円のお菓子を14個買う"
+
+p str.scan(/\d+(?=円)/)
+```
+
+と書けます。
+結果は
+
+```rb
+["250"]
+```
+
+となります。
+
+# 後ろに "円" が来ない数字列を拾う
+
+今度は,後ろに `"円"` が来ない数字列を拾ってみたいと思います。
+
+否定先読みを使って
+
+```rb
+str = "一人250円のお菓子を14個買う"
+
+p str.scan(/\d+(?!円)/)
+```
+
+とするとどうなるでしょうか。
+
+結果は
+
+```rb
+["25", "14"]
+```
+
+となります。
+
+`"14"` のほうは想定していましたが,`"25"` のほうは予想外でした。
+
+とはいえ,この `"25"` は後ろに `"円"` が来ていないので,確かにマッチします。
+我らが正規表現エンジンは,正しく忠実に仕事をこなしたのでした。
+
+正規表現エンジンはどのようにしてこの `"25"` を拾ったのでしょうか。
+
+正規表現エンジンは,まず `\d+` にマッチする文字列を探します。
+
+文字列の先頭から末尾に向かって探すので,`"2"` で始まる数字列をまず見出すわけですが,量指定子 `+` は「最長一致」なので,`"2"` や `"25"` ではなく `"250"` を得ます。
+
+次に,見出した `"250"` の直後に `(?!円)` にマッチする部分文字列があるかを検討します。
+`(?!円)` はアンカーなので,「部分文字列」と言っても必ず空文字列ですが,〈直後に `"円"` が存在しない〉という縛りがあります。
+
+残念ながら直後に `"円"` が存在するので,失敗。
+
+正規表現エンジンは,`\d+` からやり直します。
+さきほどは `"250"` と欲張ってしまったので,1 文字減らして `"25"` を取り上げます。
+そして,直後に `(?!円)` にマッチする空文字列があるかというと,ありました。
+
+かくして,`"25"` と空文字列を結合した `"25"` を拾うことができたのでした。
+
+上述した「やり直し」をバックトラックといいます。
+
+# いよいよ強欲な量指定子の出番
+
+前節の結果は正しいのですが,私が意図したものとは違いました。
+
+やりたかったのは,「テキスト中から,最長一致で拾った数字列のうち,後ろに `"円"` が来ないもの」を拾うことでした。
+
+バックトラックを抑止できれば意図が実現しそうです。
+
+そこで,強欲な量指定子の出番です。
+強欲な量指定子は,最長一致で,かつ範囲を縮めるようなバックトラックをしない,というものです。
+
+通常の最長一致の量指定子の後ろに `+` を付加した形をしています。
+つまり,`\d+` の強欲版は `\d++` となります。
+
+これを使って,
+
+```rb
+p str.scan(/\d++(?!円)/)
+```
+
+とすれば,期待どおり
+
+```rb
+["14"]
+```
+
+が得られました。
+
+# 強欲版を使わなくても
+
+別解として,強欲な量指定子を使わない
+
+```rb
+p str.scan(/\d+(?!円|\d)/)
+```
+
+も考えられます。
+
+しかし,強欲を使ったほうがシンプルでしょう。
+
+え? 大してシンプルじゃない?
+あー,今の場合,`\d` みたいな単純なやつだったからよかったけれども,もっと複雑な文字クラスだったら大変だぞおっ,ていうことで納得してくれたまえ。
+
+
+# おまけ:パフォーマンスはどうした?
+
+強欲な量指定子はパフォーマンスのために使う,というような説明をよく見ます。
+実際,無用のバックトラックによって速度が落ちるケースがあり,強欲版にすることで改善したりします。
+
+しかし,本記事はあえてパフォーマンスをテーマにしませんでした。
+機会があればベンチマークテストを含めた記事を書いてみたいと思います。