[正規表現] 連続する貪欲マッチ、どっちが優先される？

正規表現の貪欲マッチ.*や最短マッチ.*?を使っていて、
「あれ…？なんでこんな出力になるの…？」
ってことありませんか？

突然ですが、問題

以下の２つのケース、どんな出力になるか、わかるでしょうか？
ぜひ少し考えてみてください。

import re
s = 'aaabbb'
# 連続する貪欲マッチ
re.findall(r'^(.*)(b*)$', s)
# 連続する最短マッチ
re.findall(r'^(.*?)(b*?)$', s)

答え

# re.findall(r'^(.*)(b*)$', s)
('aaabbb', '')
# re.findall(r'^(.*?)(b*?)$', s)
('aaa', 'bbb')

前者のケース、(b*)の貪欲マッチが優先されれば、('aaa', 'bbb')になりそうにも思えます。
また、後者のケースも同様に、(b*?)の最短マッチが優先されれば、('aaabbb', '')となってもおかしくないように思えます。

結論： より前方の貪欲/最短マッチが優先される

結論を聞くと、まぁそうだよね感はあるかと思いますが、より前方にある貪欲/最短マッチが優先されます。

なぜそうなるのか、貪欲/最短マッチのアルゴリズムとともに、説明していきたいと思います。

貪欲マッチ

アルゴリズム

まず、貪欲マッチは、以下のようなアルゴリズムで動いています。
（なお、こちらのサイト→貪欲と怠惰な量指定子に、図付きでわかりやすく解説されているので、以下の説明で「？？？」という方はこちらもご参照ください。）

1. 開始位置を決定する
2. 該当の条件がマッチしなくなるまで、終了位置を後方に進める
3. 後続の条件がマッチするまで、終了位置を前方に戻す

挙動

aaabbbに対する^(.*)(b*)$は、以下のような動作になります。

1. 行頭を表す^があるため、(.*)の開始位置は[ココ]aaabbbになります
2. .は任意の文字なので、続く文字は全てマッチします。結果、(.*)の終了位置はaaabbb[ココ]まで進みます
3. 後続の条件は(b*)$で「行末の0個以上のb」です。「行末の空文字列」はこれを満たします。よって、終了位置を前方に戻す必要はなく、処理終了です

したがって、

• (.*)には、'aaabbb'
• （b*）には、''（空文字列）

がそれぞれ該当するという結果になる訳です。

最短マッチ

アルゴリズム

続いて、最短マッチのアルゴリズムです。

1. 開始位置を決定する
2. 終了位置を1文字進め、該当の条件がマッチするかを確認。マッチしない場合は処理終了
3. その終了位置で、後続の条件がマッチするかを確認。マッチする場合は処理終了
4. 2と3を繰り返す

貪欲マッチでは、2の部分で該当の条件がマッチする限り終了位置を後方に進めて、そこから前方に遡る形で、後続の条件がマッチするかを見ていきました。一方で、最短マッチでは、終了位置を1文字進める度に、後続の条件がマッチするかと見るという形になっています。

挙動

最短マッチについても、aaabbbに対する^(.*)(b*)$の動作を見ていきます。

1. 行頭を表す^があるため、(.*)の開始位置は[ココ]aaabbbになります
2. 終了位置を[ココ]aaabbbとして条件を確認します
   1. 該当の条件(.*)は、空文字列にマッチします（→処理継続）
   2. 後続の条件(b*)$は、aaabbbにはマッチしません（→処理継続）
3. 終了位置を1文字進めて、a[ココ]aabbbとして条件を確認します
   1. 該当の条件は、aにマッチします（→処理継続）
   2. 後続の条件は、aabbbにはマッチしません（→処理継続）
4. （少し飛ばして）終了位置を更に進め、aaa[ココ]bbbとして条件を確認します
   1. 該当の条件は、aaaにマッチします（→処理継続）
   2. 後続の条件は、bbbにマッチします（→処理 終了）

したがって、

• (.*)には、'aaa'
• （b*）には、'bbb'

という結果になります。

結論

ということで、正規表現との一致の確認が前方から行われていくため、より前方の貪欲/最短マッチが、後方の貪欲/最短マッチより優先されるということになります。

こんなん気にする場面ある？

実際のところ、出現頻度は低い気はしますが、私が遭遇した実例を紹介しておきます。

言語処理100本ノックという、東北大学の研究室が公開している言語処理の問題集があり、その中の第３章 25.テンプレートの抽出の中で、この記事の問題に出会しました。

少し問題を簡略化しますが、

こんにちは = Hello
おはよう=Good morning
おやすみ= Good night

といったテキストがあり、=の前後の単語で辞書型オブジェクトを生成しなさい、という問題です。意図されたものでは無いのですが、=の前後にスペースが有ったり無かったりと、統一されていないところがいやらしい感じです。

しかし、私は「貪欲マッチを使えば、楽勝楽勝っ♪」と、意気揚々と以下のコードを書きました。

matched  = re.find(r'^(.*) *= *(.*)$', text, flags=re.MULTILINE)
d = {key: value for key, value in matched}

そして、この出力を見て、目を疑いました。

{'おはよう': 'Good morning', 'おやすみ': 'Good night', 'こんにちは ': 'Hello'}

'こんにちは '

「なんでスペースまで拾ってるんじゃーっ！！Σ(ﾟдﾟ;)」

若干大袈裟ですが、 *= *の貪欲マッチで、=の前後のスペースが消えると思っていた私には、実際何が起こっているのかすぐにはわかりませんでした。

ここまで読んでくださっている方には簡単と思いますが、より前方にある(.*)が優先されてしまっているんですね。なので、その部分を最短マッチにすることで、想定通りの答えが得られます。

re.find(r'^(.*?) *= *(.*)$', text, flags=re.MULTILINE)
# [('こんにちは', 'Hello'), ('おはよう', 'Good morning'), ('おやすみ', 'Good night')]

ちなみに、=の後ろにある(.*)は、これよりも *= *の方が優先されるので、(.*?)と書く必要はありません。

まとめ

「より前方の貪欲/最短マッチが優先される」

結論としては簡単ですし、アルゴリズムを理解すれば当たり前ですが、ブラックボックス的に扱っていると結構ハマってしまう部分かなと思います。
似た話では、[正規表現] .*?は最短マッチではないとかも、ハマりポイントと思います。（というか、こちらの方が頻出）

少しでも参考になれば幸いです。
お読みいただきありがとうございました。

参考サイト

• 貪欲と怠惰な量指定子