量指定子を使ったPerlの正規表現でバックトラックを低減する方法

2006年12月21日 オフ 投稿者: KYO
Table of Contents

Perlの正規表現(おそらくPHPでも?)言えることですが、量指定子[ .+ ]を使用する場合の注意点。
Perl内部での量指定子の動作のメモ。


Perlといえば、テキスト処理。
くらいに色々出来る正規表現ですが、若干・・・落とし穴?があるようなのでメモ。
実際のレスポンスタイムのベンチマークテストはやってないので、概論として。

量指定子[ .+ ]の内部処理

$string = 'Tom_And_Jerry_on_TV';
$pattern = 'Tom.+Jerry';
m/$string/$pattern/;

この場合、$pattern は $string にマッチするが、内部的には以下のように動作しているらしい。

Perl内部でのマッチ処理

  • サブパターン[ Tom ]のマッチ処理 => マッチ[ Tom ]
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_on_TV ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_on_T ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_on_ ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_on ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_o ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry_ ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerry ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jerr ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Jer ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_Je ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_J ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチしない
  • [ .+ ]のマッチ処理 => マッチ[ _And_ ]
  • サブパターン[ Jerry ]のマッチ処理 => マッチ[ Jerry ]
  • バックトラックを抑える量指定子の使用方法

    [ .+ ]はなるべく多くの(長い文字長の)文字にマッチしようとする。
    そこで、[ .+? ]を使用することで、なるべく少ない(短い文字長の)文字にマッチさせるようにする。
    なるほどねー。
    ってことで、メモ。