最長一致数量子/最短一致数量子/強欲な数量子

広告

量指定子を使う場合の考え方を先に確認しておきます。

例として"+"を使って考えます。"+"は直前の文字が1回以上繰り返す場合にマッチするメタ文字です。例として次のようなパターンを考えてみます。

"ab+"

上記のパターンの場合、"a"で始まり"b"が1回以上続く場合にマッチします。例えば次のような文字にマッチします。

○ abc
○ abbc
○ abbbbc

ここでターゲットとなる文字列のどの部分にマッチしたかを考えます。単に"+"と記載した場合は最長一致数量子と呼ばれるもので、最も長い部分にマッチします。つまり先ほどの例でどの部分にマッチしたのかを記述すると次の部分にマッチしています。

[ab]c
[abb]c
[abbbb]c

それに対して"+?"は直前の文字が1回以上繰り返す場合にマッチするメタ文字とう点では同じですが最短一致数量子と呼ばれるものです。最短一致数量子は最も短い部分にマッチします。

"ab+?"

先ほどと同じターゲット文字列にマッチさせた場合、どの部分にマッチしたのかを記述すると次の部分にマッチします。

[ab]c
[ab]bc
[ab]bbbc

このように最長一致数量子である"+"でも最短一致数量子である"+?"でも直前の文字を1回以上繰り返すものにマッチするという意味では同じなのですが、マッチする部分が異なってきます。

強欲な数量子

多くのプログラミング言語では最長一致数量子と最短一致数量子しかありませんが、Javaにおいては強欲な数量子(又は絶対最大指定子)と呼ばれるものがあります。

例えば任意の一文字を表す"."を1回以上繰り返すようなパターンを記述してみます。

".+g"

上記の場合、任意の1文字が1回以上続き、最後に"g"が出現する場合にマッチします。

では次のようなターゲット文字列を対象にマッチさせてみます。

abcdefg

上記は任意の文字が1回以上続いた後に"g"が出ているのでマッチします。この時"+"は最長一致数量子でありできるだけ長い部分にマッチしようとします。そこでパターン野中で".+"は"abcdefg"全体にマッチしようとします。

abcdefg
-------
  .+    g

ただ".+"の部分で全体にマッチさせてしまうとパターンの最後の"g"がマッチせず、パターン全体としてはマッチしなくなってしまいます。そこで".+"の部分は"abcdefg"ではなく"abcdef"にマッチします。

abcdef g
------ -
 .+    g

この結果、パターン全体の".+g"はターゲット文字列にマッチします。"+"はできるだけ長い部分にマッチしようとしますが、パターン全体がマッチすることを優先し、マッチする部分を減らして調整するということです。

次に強欲な数量子(又は絶対最大指定子)を使う場合を考えてみます。"++"は"+"の強欲な数量子バージョンです。次のように記述することができます。

".++g"

強欲な数量子の特徴は、パターン全体がマッチするかどうかは考慮せず、とにかく一番長い部分にマッチしようとする点です。

では次のようなターゲット文字列を対象にマッチさせてみます。

abcdefg

パターの中で".++"の部分は任意の文字が1文字以上続く場合にマッチしますので、ターゲット文字列全体の"abcdefg"にマッチします。

abcdefg
-------
  .++   g

パターンの中で残っている"g"にマッチする部分がターゲット文字列には残っていない為、結果的にパターン全体の".++g"はマッチしなくなります。

このようにJavaでは1つの量指定子に対して3つの種類が用意されています。最長一致数量子と最短一致数量子ではマッチする部分が違うだけですが、強欲な数量子(又は絶対最大指定子)の場合はマッチそのものがしなくなる場合もありますので注意して下さい。

サンプルプログラム

では実際に試してみます。

JSample2_1.java

import java.util.regex.Pattern;
import java.util.regex.Matcher;

class JSample2_1{
  public static void main(String args[]){
    String str1 = "abc";
    String str2 = "abbc";
    String str3 = "abbbbc";

    String regex1 = "ab+";
    Pattern p1 = Pattern.compile(regex1);

    String regex2 = "ab+?";
    Pattern p2 = Pattern.compile(regex2);

    System.out.println("パターン : " + regex1);

    check(p1, str1);
    check(p1, str2);
    check(p1, str3);

    System.out.println("パターン : " + regex2);

    check(p2, str1);
    check(p2, str2);
    check(p2, str3);
  }

  private static void check(Pattern p, String target){
    Matcher m = p.matcher(target);

    if (m.find()){
      int start = m.start();
      int end = m.end();
      String str  = target.substring(0, start) + "[" + m.group() + "]"
                      + target.substring(end, target.length());
      System.out.println("○ " + str);
    }else{
      System.out.println("× " + target);
    }
  }
}

ではコンパイルを行った上で実行してみます。

p2-1

このサンプルでは最長一致数量子と最短一致数量子でマッチする部分がどのように違うのかを表示しています。

もう一つサンプルを試してみます。

JSample2_2.java

import java.util.regex.Pattern;
import java.util.regex.Matcher;

class JSample2_2{
  public static void main(String args[]){
    String str1 = "abbc";
    String str2 = "abbbbc";
    String str3 = "abbbbbbc";

    String regex1 = "ab+b";
    Pattern p1 = Pattern.compile(regex1);

    String regex2 = "ab++b";
    Pattern p2 = Pattern.compile(regex2);

    String regex3 = "ab++c";
    Pattern p3 = Pattern.compile(regex3);

    System.out.println("パターン : " + regex1);

    check(p1, str1);
    check(p1, str2);
    check(p1, str3);

    System.out.println("パターン : " + regex2);

    check(p2, str1);
    check(p2, str2);
    check(p2, str3);

    System.out.println("パターン : " + regex3);

    check(p3, str1);
    check(p3, str2);
    check(p3, str3);
  }

  private static void check(Pattern p, String target){
    Matcher m = p.matcher(target);

    if (m.find()){
      int start = m.start();
      int end = m.end();
      String str  = target.substring(0, start) + "[" + m.group() + "]"
                      + target.substring(end, target.length());
      System.out.println("○ " + str);
    }else{
      System.out.println("× " + target);
    }
  }
}

ではコンパイルを行った上で実行してみます。

p2-2

このサンプルでは最長一致数量子と強欲な数量子でマッチするかどうかに違いが出てくるのを分かるようにしています。

( Written by Tatsuo Ikura )

関連記事 (一部広告含む)