70
47

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

強欲な量指定子(絶対最大量指定子)の使いどころ

Posted at

正規表現の量指定子には「強欲な量指定子」とか「絶対最大量指定子」と呼ばれるものがあります。
この記事では,どのような場合にこれを使うのか,一例を挙げます。

コード例は Ruby で記述しますが,Ruby をご存知ない方にも分かるよう説明を加えます。

強欲な量指定子に至るまでに,ちょっと遠回りをしますが,ご容赦を。

テキスト中から〈数字列+"円"〉を拾う

まずは,テキスト中から,〈数字列+"円"〉をすべて拾い出したいとします。

Ruby では以下のように書けます。

str = "一人250円のお菓子を14個買う"

p str.scan(/\d+円/)

1 行目はローカル変数への文字列代入です。

/\d+円/ は正規表現リテラルです。
正規表現を / / で囲むと正規表現リテラルになります。

str のあとにピリオドを置いて何かを書いているのは str に対するメソッド呼び出しです。
scan は,文字列に対して使えるメソッドです。引数で与えられた正規表現にマッチする部分文字列を検索して,その結果を配列で返します。

p はオブジェクトを表示するメソッドです。配列を与えたときは,配列っぽく見える文字列にフォーマットしたうえで表示してくれます。

結果は以下のようになります。

["250円"]

マッチする部分文字列が一つしか見出されなかったので,1 要素からなる配列が得られました。

後ろに "円" が続く数字列を拾う

今度は,後ろに "円" が続く数字列を拾ってみます。"円" が続く,といっても,"円" 自体は拾わず,数字列だけを拾うようにします。

これは,肯定先読み (?= ) を使って

str = "一人250円のお菓子を14個買う"

p str.scan(/\d+(?=円)/)

と書けます。
結果は

["250"]

となります。

後ろに "円" が来ない数字列を拾う

今度は,後ろに "円" が来ない数字列を拾ってみたいと思います。

否定先読みを使って

str = "一人250円のお菓子を14個買う"

p str.scan(/\d+(?!円)/)

とするとどうなるでしょうか。

結果は

["25", "14"]

となります。

"14" のほうは想定していましたが,"25" のほうは予想外でした。

とはいえ,この "25" は後ろに "円" が来ていないので,確かにマッチします。
我らが正規表現エンジンは,正しく忠実に仕事をこなしたのでした。

正規表現エンジンはどのようにしてこの "25" を拾ったのでしょうか。

正規表現エンジンは,まず \d+ にマッチする文字列を探します。

文字列の先頭から末尾に向かって探すので,"2" で始まる数字列をまず見出すわけですが,量指定子 + は「最長一致」なので,"2""25" ではなく "250" を得ます。

次に,見出した "250" の直後に (?!円) にマッチする部分文字列があるかを検討します。
(?!円) はアンカーなので,「部分文字列」と言っても必ず空文字列ですが,〈直後に "円" が存在しない〉という縛りがあります。

残念ながら直後に "円" が存在するので,失敗。

正規表現エンジンは,\d+ からやり直します。
さきほどは "250" と欲張ってしまったので,1 文字減らして "25" を取り上げます。
そして,直後に (?!円) にマッチする空文字列があるかというと,ありました。

かくして,"25" と空文字列を結合した "25" を拾うことができたのでした。

上述した「やり直し」をバックトラックといいます。

いよいよ強欲な量指定子の出番

前節の結果は正しいのですが,私が意図したものとは違いました。

やりたかったのは,「テキスト中から,最長一致で拾った数字列のうち,後ろに "円" が来ないもの」を拾うことでした。

バックトラックを抑止できれば意図が実現しそうです。

そこで,強欲な量指定子の出番です。
強欲な量指定子は,最長一致で,かつ範囲を縮めるようなバックトラックをしない,というものです。

通常の最長一致の量指定子の後ろに + を付加した形をしています。
つまり,\d+ の強欲版は \d++ となります。

これを使って,

p str.scan(/\d++(?!円)/)

とすれば,期待どおり

["14"]

が得られました。

強欲版を使わなくても

別解として,強欲な量指定子を使わない

p str.scan(/\d+(?!円|\d)/)

も考えられます。

しかし,強欲を使ったほうがシンプルでしょう。

え? 大してシンプルじゃない?
あー,今の場合,\d みたいな単純なやつだったからよかったけれども,もっと複雑な文字クラスだったら大変だぞおっ,ていうことで納得してくれたまえ。

おまけ:パフォーマンスはどうした?

強欲な量指定子はパフォーマンスのために使う,というような説明をよく見ます。
実際,無用のバックトラックによって速度が落ちるケースがあり,強欲版にすることで改善したりします。

しかし,本記事はあえてパフォーマンスをテーマにしませんでした。
機会があればベンチマークテストを含めた記事を書いてみたいと思います。

70
47
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
70
47

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?