[解決済み] a^n b^n に一致させるには？

2022-11-19 14:15:26

質問

_{この記事は正規表現に関する教育的な記事の第二部です。この記事では、ルックアヘッドとネストされた参照を用いて、非正規表現の
ⁿ
b
ⁿ
. ネストされた参照は、最初に紹介した

この正規表現はどのようにして三角数を見つけるのでしょうか？}

原型となる非正規言語である。

L = { a ⁿ b ⁿ : n > 0 }

これは、ある数の a の後に、同じ数の b 's. この言語での文字列の例としては ab , aabb , aaabbb .

この言語が非正則であることはポンピングのレンマ . これは実際、典型的な文脈自由言語によって生成することができます。文脈自由文法 S → aSb | ab .

それでも、現代の正規表現実装は、明らかに単なる正規言語以上のものを認識しています。つまり、正式な言語理論の定義では、これらは正規表現ではありません。PCRE と Perl は再帰的な正規表現をサポートし、.NET はバランシンググループの定義をサポートしています。後方参照マッチングなどのあまり "fancy"でない機能でさえ、正規表現が正規表現でないことを意味します。

しかし、この "基本的な"機能はどの程度強力なのでしょうか。私たちは L を Java 正規表現で認識できるでしょうか？ルックアラウンドとネストされたリファレンスを組み合わせて、たとえば String.matches のような文字列にマッチするように ab , aabb , aaabbb などでしょうか？

参考文献

perlfaq6: Perl の正規表現を使ってバランスのとれたテキストにマッチさせることはできますか?
MSDN - 正規表現言語要素 - バランスグループの定義
pcre.org - PCRE マニュアルページ
正規表現.info - ルックアラウンドとグループ化および後方参照
java.util.regex.Pattern

リンクされた質問

lookaround は、正規表現でマッチする言語に影響を与えますか？
.NET Regex Balancing GroupsとPCRE Recursive Patternsの比較

どのように解決するのですか？

答えは言うまでもありません。 YES! にマッチするJava正規表現パターンを書くことができます。 a ⁿ b ⁿ . これは、アサーションに正のルックヘッドを使用し、"counting"に1つのネストされた参照を使用します。

すぐにパターンを提供するのではなく、この回答は読者を次のように導きます。 プロセス を導くものです。様々なヒントを与えながら、ゆっくりと解決策を構築していきます。このような観点から、この解答が単なるきれいな正規表現パターン以上のものを含んでいることを望みます。また、読者の皆さんには、どのように正規表現で考えるか、どのように様々な構成要素を調和させるかを学んでいただき、将来的に自分自身でより多くのパターンを導き出すことができるようになればと願っています。

ソリューションを開発するために使用される言語は、その簡潔さのためにPHPになります。パターンが確定した後の最終テストは、Javaで行う予定です。

ステップ1：アサーション用ルックヘッド

もっと単純な問題から始めましょう。 a+ をマッチさせたいが、その後にすぐに b+ . 私たちが使えるのは ^ からアンカーにマッチしており、マッチさせたいのは a+ にはマッチせず b+ を使用するとルックヘッドアサーション (?=…) .

ここでは、簡単なテストハーネスを使ったパターンを紹介します。

function testAll($r, $tests) {
   foreach ($tests as $test) {
      $isMatch = preg_match($r, $test, $groups);
      $groupsJoined = join('|', $groups);
      print("$test $isMatch $groupsJoined\n");
   }
}
 
$tests = array('aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb');
 
$r1 = '/^a+(?=b+)/';
#          └────┘
#         lookahead

testAll($r1, $tests);

出力は ( ideone.comで見たように ):

aaa 0
aaab 1 aaa
aaaxb 0
xaaab 0
b 0
abbb 1 a

これはまさに私たちが欲しい出力です。 a+ にマッチし、それが文字列の先頭にある場合のみ、そしてその直後に b+ .

レッスン : ルックアラウンドのパターンを使って、アサーションを行うことができます。

ステップ2：ルックアヘッドでの捕捉（およびf r e e - s p a c i n g モード）

ここで、たとえ私たちが b+ をマッチの一部としたくない場合でもをキャプチャします。また、より複雑なパターンが予想されるので x を修飾してフリースペーシングを追加することで、より読みやすい正規表現にすることができます。

前のPHPスニペットを基にすると、次のようなパターンになります。

$r2 = '/ ^ a+ (?= (b+) ) /x';
#             │   └──┘ │
#             │     1  │
#             └────────┘
#              lookahead
 
testAll($r2, $tests);

これで出力は( は ideone.com で見たとおりです。 ):

aaa 0
aaab 1 aaa|b
aaaxb 0
xaaab 0
b 0
abbb 1 a|bbb

なお、例えば aaa|b は join -で各グループが捉えたものを '|' . この場合、グループ 0（つまりパターンにマッチしたもの）が捕捉したのは aaa をキャプチャし、グループ1が b .

レッスン : ルックアラウンドの内側をキャプチャすることができます。フリースペースで読みやすくすることができます。

ステップ3：lookaheadを"loop"にリファクタリングします。

カウントの仕組みを導入する前に、パターンをひとつ修正する必要があります。現在、ルックアヘッドは + の繰り返しの外側にあります。これは今のところ問題ありません。 b+ の後に a+ が、私たちが 本当に が、最終的にやりたいことは、それぞれの a に対して、対応する b があります。

カウントの仕組みはとりあえず気にせず、以下のようにリファクタリングしてみましょう。

最初のリファクタリング a+ を (?: a )+ (ただし (?:…) は非捕捉グループであることに注意)
次に、この非捕捉グループの内部でルックヘッドを移動します。
- ここで、"skip" をしなければならないことに注意してください。 a* を見ることができるようになります。 b+ を見ることができないので、それに応じてパターンを変更します。

ということで、現在は以下のようになっています。

$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
#          │     │      └──┘ │ │
#          │     │        1  │ │
#          │     └───────────┘ │
#          │       lookahead   │
#          └───────────────────┘
#           non-capturing group

出力は以前と同じ ( は ideone.com で見たとおり ) ですので、その点では変化はありません。重要なのは、今度は 各反復 の + ループ"ループ"。現在のパターンでは、これは必要ありませんが、次に、自己参照を使用してグループ 1 の "カウント" を作成することにします。

レッスン : キャプチャーしないグループの内部でもキャプチャーできる。ルックアラウンドは繰り返すことができる。

ステップ4: カウントを開始するステップです。

ここで、グループ1をこのように書き換えます。

の最初の繰り返しの最後に + が終了したとき、最初の a がマッチした場合、それは b
二回目の繰り返しの最後に、別の a がマッチした場合、それは bb
3回目の繰り返しの最後には bbb
...
の末尾にある n -の繰り返しで、グループ 1 は b ⁿ
十分な数がない場合 b がグループ 1 に捕捉される場合、アサーションは単に失敗します。

というわけで、グループ 1 は、現在 (b+) であるグループ 1 は、次のように書き直さなければならないでしょう。 (\1 b) . つまり、quot;add" に b を、グループ 1 が前の反復で捕捉したものに追加しようとします。

このパターンには、quot;base" つまり、自己参照なしで一致できるケースがないという点で、若干の問題があります。グループ 1 はまだ何も捕捉していない (空文字列でさえも) ので、自己参照の試みは常に失敗します。

これを回避する方法はたくさんありますが、とりあえず自己参照のマッチングをオプションでにしてみましょう。 \1? . これは完璧に動作するかもしれませんし、そうでないかもしれませんが、とりあえずこれがどうなるか見てみましょう。また、ついでにテストケースもいくつか追加しておきましょう。

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb'
);
 
$r4 = '/ ^ (?: a (?= a* (\1? b) ) )+ /x';
#          │     │      └─────┘ | │
#          │     │         1    | │
#          │     └──────────────┘ │
#          │         lookahead    │
#          └──────────────────────┘
#             non-capturing group

これで出力は( は ideone.com で見たとおりです。 ):

aaa 0
aaab 1 aaa|b        # (*gasp!*)
aaaxb 0
xaaab 0
b 0
abbb 1 a|b          # yes!
aabb 1 aa|bb        # YES!!
aaabbbbb 1 aaa|bbb  # YESS!!!
aaaaabbb 1 aaaaa|bb # NOOOOOoooooo....

あちゃー！どうやら解決に近づいたようですね。自己参照を使ってグループ 1 を "count"させることに成功しました! しかし、2つ目と最後のテストケースは何かがおかしい! を使うには、十分な b が足りず、なぜかカウントがおかしくなっています! この原因は次のステップで検証します。

レッスン : 自己参照グループを初期化する1つの方法は、自己参照のマッチングをオプションにすることです。

ステップ4½: 何が問題だったのかを理解する

問題は、自己参照のマッチングをオプションにしたため、十分な数の自己参照がないときに "カウンタ" が 0 に戻ってしまうことです。 b 's. でパターンを反復するたびに何が起こるかを詳しく調べてみましょう。 aaaaabbb を入力として、パターンの各反復で何が起こるかを詳しく調べてみましょう。

 a a a a a b b b
↑
# Initial state: Group 1 is "uninitialized".
           _
 a a a a a b b b
  ↑
  # 1st iteration: Group 1 couldn't match \1 since it was "uninitialized",
  #                  so it matched and captured just b
           ___
 a a a a a b b b
    ↑
    # 2nd iteration: Group 1 matched \1b and captured bb
           _____
 a a a a a b b b
      ↑
      # 3rd iteration: Group 1 matched \1b and captured bbb
           _
 a a a a a b b b
        ↑
        # 4th iteration: Group 1 could still match \1, but not \1b,
        #  (!!!)           so it matched and captured just b
           ___
 a a a a a b b b
          ↑
          # 5th iteration: Group 1 matched \1b and captured bb
          #
          # No more a, + "loop" terminates

あちゃー。4回目の繰り返しで、まだ \1 にはマッチしますが \1b ! で自己参照マッチングを任意に許可しているので \1? で自己参照マッチングを許可しているので、エンジンはバックトラックして "no thanks" オプションを取り、マッチングとキャプチャを b !

しかし、最初の反復を除いて、常に自己参照である \1 . これはもちろん、前の反復で捕捉したものであり、今回の設定ではいつでも再びマッチさせることができるからです (たとえば bbb をキャプチャした場合、まだ bbb があることは保証されていますが、あるともないとも言えない bbbb はないかもしれません）。

レッスン : バックトラックに気をつけよう。正規表現エンジンは、与えられたパターンがマッチするまで、あなたが許す限りバックトラックを実行します。これはパフォーマンスに影響を与えるかもしれません (例破滅的バックトラックや正しさに影響を与えるかもしれません。

ステップ5：自己主張ができるようになる

修正方法は明らかでしょう。所有格量詞と組み合わせることです。つまり、単に ? を使用します。 ?+ を代わりに使用します（そのような "協力" が全体のパターンの一致をもたらすことがあっても、所有格として定量化される繰り返しは後戻りしないことを覚えておいてください）。

非常に非公式な用語で言うと、これは ?+ , ? と ?? は言う。

?+

(オプション) "なくてもよいです。

(所有格) "しかし、もしそれがそこにあるならば、あなたはそれを手にして離さなければなりません！"

?

(オプション) "なくてもよいです。

(欲張り) "でも、あればとりあえず取っておく、"

(逆ギレ) "でも、後で手放せと言われるかもしれません！"

??

(オプション) "なくてもよいです。

(渋い) "あったとしても、まだ取る必要はありません"

(後ろ向き) "でも、後で受けるように言われるかもしれませんよ！"

私たちのセットアップでは \1 は最初には存在しませんが、その後に は常に であり、私たちは常にはその時に合わせたいのです。このように \1?+ はまさに私たちが望むものを達成するでしょう。

$r5 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

これで、出力は ( は、ideone.comで見たように ):

aaa 0
aaab 1 a|b          # Yay! Fixed!
aaaxb 0
xaaab 0
b 0
abbb 1 a|b
aabb 1 aa|bb
aaabbbbb 1 aaa|bbb
aaaaabbb 1 aaa|bbb  # Hurrahh!!!

Voilà!!! 問題は解決しました!!! これでちゃんと、思い通りのカウントができるようになりました!

レッスン : 欲張り反復、消極的反復、所有的反復の違いを学びましょう。Optional-Possessiveは強力な組み合わせになります。

ステップ6: 仕上げ

というわけで、今あるのは a に繰り返しマッチし、それぞれの a にマッチした場合、それに対応する b はグループ 1 に取り込まれます。 + がなくなると終了する。 a がない場合、あるいは対応する b に対応する a .

最後に、このパターンに追加する必要があります。 \1 $ . これは、グループ 1 がマッチしたものへの後方参照であり、行末のアンカーがそれに続いています。このアンカーによって、余計な b がないこと、言い換えれば、実際には a ⁿ b ⁿ .

これが最終的なパターンで、1万字の長さのものを含む追加のテストケースがあります。

$tests = array(
  'aaa', 'aaab', 'aaaxb', 'xaaab', 'b', 'abbb', 'aabb', 'aaabbbbb', 'aaaaabbb',
  '', 'ab', 'abb', 'aab', 'aaaabb', 'aaabbb', 'bbbaaa', 'ababab', 'abc',
  str_repeat('a', 5000).str_repeat('b', 5000)
);
 
$r6 = '/ ^ (?: a (?= a* (\1?+ b) ) )+ \1 $ /x';
#          │     │      └──────┘ │ │
#          │     │          1    │ │
#          │     └───────────────┘ │
#          │         lookahead     │
#          └───────────────────────┘
#             non-capturing group

4つのマッチを見つけます。 ab , aabb , aaabbb を、そして a ⁵⁰⁰⁰ b ⁵⁰⁰⁰ . これはを実行するのにわずか0.06秒です。 .

ステップ7：Javaのテスト

このパターンはPHPで動作しますが、最終的な目標はJavaで動作するパターンを書くことです。

public static void main(String[] args) {
 
        String aNbN = "(?x) (?:  a  (?= a* (\\1?+ b))  )+ \\1";
        String[] tests = {
                "",      // false
                "ab",    // true
                "abb",   // false
                "aab",   // false
                "aabb",  // true
                "abab",  // false
                "abc",   // false
                repeat('a', 5000) + repeat('b', 4999), // false
                repeat('a', 5000) + repeat('b', 5000), // true
                repeat('a', 5000) + repeat('b', 5001), // false
        };
        for (String test : tests) {
                System.out.printf("[%s]%n  %s%n%n", test, test.matches(aNbN));
        }
 
}
 
static String repeat(char ch, int n) {
        return new String(new char[n]).replace('\0', ch);
}

このパターンは期待通りに動作します ( は ideone.com で見たように ).

そして今、私たちは結論に達しました...

ということが必要です。 a* は、ルックアヘッドで、そして実際に "メイン + ループの両方がバックトラックを許可しています。読者は、なぜこれが正しさの点で問題ないのか、そしてなぜ同時に両方を所有格にすることもうまくいくのかを確認してください (おそらく同じパターンで必須と非必須の所有格の量詞を混ぜることは、誤解を招くかもしれませんが)。

にマッチする正規表現パターンがあることは素晴らしいことですが、このパターンは a ⁿ b ⁿ しかし、これは実際には必ずしも最良の解決策ではありません。もっと良い解決策は、単純に ^(a+)(b+)$ とマッチさせ、ホスト側のプログラミング言語のグループ1と2によって捕捉された文字列の長さを比較することです。

PHPでは、次のようになります ( は ideone.com で見たように ):

function is_anbn($s) {
   return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
      (strlen($groups[1]) == strlen($groups[2]));
}

この記事の目的は NOT それは明らかにできません。そして、それができることであっても、より単純な解決策につながるのであれば、少なくともホスト言語への部分的な委譲は考慮されるべきです。

冒頭で述べたように、この記事は必然的にタグ付けされた [regex] というタグが付けられていますが、おそらくそれ以上のものです。アサーション、ネストされた参照、所有量詞などについて学ぶ価値は確かにありますが、おそらくここでのより大きな教訓は、問題を解決しようとする創造的なプロセス、さまざまな制約にさらされたときにしばしば必要となる決意と努力、作業ソリューションを構築するためのさまざまな部分からの体系的な構成、などに関するものです。

ボーナス材料! PCREの再帰的パターン!

PHPを持ち出したので、PCREが再帰的なパターンとサブルーチンをサポートしていることを言う必要があります。したがって、次のパターンは preg_match ( IDEONE.COMで見たように ):

$rRecursive = '/ ^ (a (?1)? b) $ /x';

現在、Javaの正規表現は再帰的なパターンをサポートしていません。

さらにボーナス材料! マッチング a ⁿ b ⁿ c ⁿ !!

というわけで、これまで a ⁿ b ⁿ は非正則ですが、文脈自由です。 a ⁿ b ⁿ c ⁿ というのは文脈自由でさえないのですか？

答えはもちろん イエスです! 読者は自分で解いてみることをお勧めしますが、解答は以下の通りです( の Java による実装は ideone.com にあります。 ).

^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $