最長一致数量子、最短一致数量子、強欲な数量子の違い

正規表現で繰り返しを表す数量子のメタ文字を使用する場合、対象文字列のどの部分とマッチするのかを考える必要があります。例えば A が 1 文字以上続く文字列とマッチするパターンを考えたとき、対象の文字列が AAA の場合にマッチするのは A なのかそれとも AAA なのかは使用する数量子の種類によって異なります。ここでは Java で数量子のメタ文字を使用する場合に最長一致数量子、最短一致数量子、強欲な数量子の違いについて解説します。

(Last modified: )

数量子の種類

最初に Java の正規表現で用意されている数量子のメタ文字の一覧をご紹介します。 

・最長一致数量子
?       1または0回
*       0回以上
+       1回以上
{n}     n回
{n,}    n回以上
{n,m}   n回以上、m回以下

・最短一致数量子
??      1または0回
*?      0回以上
+?      1回以上
{n}?    n回
{n,}?   n回以上
{n,m}?  n回以上、m回以下

・強欲な数量子(絶対最大指定子)
?+      1または0回
*+      0回以上
++      1回以上
{n}+    n回
{n,}+   n回以上
{n,m}+  n回以上、m回以下

数量子の種類は 6 種類用意されていますが、それぞれに対して最長一致数量子、最短一致数量子、強欲な数量子の 3 つのタイプが用意されています。(強欲な数量子は絶対最大指定子と呼ばれることもあります)。

例えば直前の文字の 1 回または 0 回繰り返すことを表す数量子は ? ですが、単に ? と記述した場合は最長一致数量子となります。 ? のあとに ? を記述した ?? が最短一致数量子、 ? のあとに + を記述した ?+ が強欲な数量子です。他に数量子についても同じルールとなっています。 

・1または0回を表す数量子
?   最長一致数量子
??  最短一致数量子
?+  強欲な数量子

どのタイプを選ぶのかによって、実際に対象の文字列のどの部分とマッチするのかが変わってきます。このあと、それぞれのタイプを選択した場合に、対象文字列のどの部分にマッチするのかを解説していきます。

最長一致数量子とは

最長一致数量子の数量子を使用した場合は、できる限り長い文字列とマッチしようとします。例えば直前の文字が 1 文字以上繰り返されることを意味する + を使用してみます。最初に A 、次に B が 1 回以上続く文字列とマッチします。 

String regex = "AB+";

対象の文字列が ABBBC だった場合、 A のあとに B が 1 回以上続くパターンにマッチする部分は次のいずれかです。 

ABBBC
ABBBC
ABBBC

最長一致数量子はできる限り長い文字列とマッチしようとするので、 "AB+" とマッチする部分は "ABBB" となります。 

ABBBC

実際にサンプルで試してみます。 

import java.util.regex.*;

class JSample11_1{
  public static void main(String[] args){
    String regex = "AB+";
    Pattern p = Pattern.compile(regex);

    Matcher m = p.matcher("ABBBC");
    if (m.find()){
      System.out.println(m.group());  // ABBB
    }
  }
}

パターンとマッチした部分を画面に出力してみると "ABBB" となりました。

パターン全体がマッチするように調整する

最長一致数量子はできる限り長い文字列とマッチしようとしますが、一番長い部分とマッチさせるとパターン全体がマッチしない場合があります。次のパターンを見てください。 

String regex = "A.+B";

最初に A 、次に任意の文字が 1 回以上続き、最後に B と続く文字列とマッチします。

対象の文字列が ACCBEE だった場合で考えてみます。まず A.+ の部分がマッチする部分です。 A のあとに任意の文字が(最長一致で) 1 回以上続くパターンにマッチする部分は次の箇所です。文字列の末尾までとなります。 

ACCBEE

ただ今回のパターンの場合、最後に B が続く必要があります。 A.+ の部分だけで文字列の最後までマッチさせてしまうと、パターンの最後の B がマッチせずにパターン全体がマッチしませんので、 A.+ の部分がマッチする分を 3 つ減らして次のところまでにします。 

ACCBEE

これならば最後に B が続くためパターン全体もマッチします。結果としてパターン全体がマッチしたのは ACCB の部分となります。 

ACCBEE

このように最長一致数量子の場合はできるだけ長い部分とマッチしようとしますが、パターン全体がマッチしない場合には最長一致数量子がマッチする部分を減らしてパターン全体がマッチするように調整します。

最短一致数量子とは

最短一致数量子の数量子を使用した場合は、できる限り短い文字列とマッチしようとします。例えば直前の文字が 1 文字以上繰り返されることを意味する + を使用してみます。最短一致数量子を使用する場合は数量子は +? となります。最初に A 、次に B が 1 回以上続く文字列とマッチします。 

String regex = "AB+?";

対象の文字列が ABBBC だった場合、 A のあとに B が 1 回以上続くパターンにマッチする部分は次のいずれかです。 

ABBBC
ABBBC
ABBBC

最短一致数量子はできる限り長い文字列とマッチしようとするので、 "AB+?" とマッチする部分は "AB" となります。 

ABBBC

実際にサンプルで試してみます。 

import java.util.regex.*;

class JSample11_2{
  public static void main(String[] args){
    String regex = "AB+?";
    Pattern p = Pattern.compile(regex);

    Matcher m = p.matcher("ABBBC");
    if (m.find()){
      System.out.println(m.group());  // AB
    }
  }
}

パターンとマッチした部分を画面に出力してみると "AB" となりました。

強欲な数量子(絶対最大指定子)とは

強欲な数量子(絶対最大指定子)の数量子を使用した場合は、最長一致数量子と同じでできる限り長い文字列とマッチしようとします。例えば直前の文字が 1 文字以上繰り返されることを意味する + を使用してみます。最短一致数量子を使用する場合は数量子は ++ となります。最初に A 、次に B が 1 回以上続く文字列とマッチします。 

String regex = "AB++";

対象の文字列が ABBBC だった場合、 A のあとに B が 1 回以上続くパターンにマッチする部分は次のいずれかです。 

ABBBC
ABBBC
ABBBC

強欲な数量子はできる限り長い文字列とマッチしようとするので、 "AB++" とマッチする部分は "ABBB" となります。 

ABBBC

実際にサンプルで試してみます。 

import java.util.regex.*;

class JSample11_3{
  public static void main(String[] args){
    String regex = "AB++";
    Pattern p = Pattern.compile(regex);

    Matcher m = p.matcher("ABBBC");
    if (m.find()){
      System.out.println(m.group());  // ABBB
    }
  }
}

パターンとマッチした部分を画面に出力してみると "ABBB" となりました。

最長一致数量子と強欲な数量子(絶対最大指定子)との違い

最長一致数量子と強欲な数量子はどちらもできるだけ長い文字列とマッチしようとする点では同じです。ただ、最長一致数量子の方はパターン全体がマッチすることを優先し、場合によってはマッチする部分を一番長い部分から減らしてパターン全体をマッチしようとしますが、強欲な数量子の方はパターン全体がマッチしなくても必ず一番長い部分とマッチします。

次のパターンを見てください。 

String regex = "A.++B";

最初に A 、次に任意の文字が 1 回以上続き、最後に B と続く文字列とマッチします。

対象の文字列が ACCBEE だった場合で考えてみます。まず A.++ の部分がマッチする部分です。 A のあとに任意の文字が(強欲な数量子で) 1 回以上続くパターンにマッチする部分は次の箇所です。文字列の末尾までとなります。 

ACCBEE

ただ今回のパターンの場合、最後に B が続く必要があります。 A.++ の部分だけで文字列の最後までマッチさせてしまうと、パターンの最後の B がマッチせずにパターン全体がマッチしませんが、強欲な数量子は必ず一番長い文字列とマッチするため A.++ の部分がマッチする部分は変わりありません。

結果的にそのあとに B が続きませんので今回のパターンは対象の文字列にマッチしないことになります。

このように最長一致数量子と強欲な数量子は似ていますが同じではありません。目的に応じて使い分けるようにしてください。

-- --

Java で数量子のメタ文字を使用する場合に最長一致数量子、最短一致数量子、強欲な数量子の違いについて解説しました。

( Written by Tatsuo Ikura )

プロフィール画像

著者 / TATSUO IKURA

これから IT 関連の知識を学ばれる方を対象に、色々な言語でのプログラミング方法や関連する技術、開発環境構築などに関する解説サイトを運営しています。