答えは言うまでもなくYESです！a n b nに一致するように Java 正規表現パターンを作成できることは間違いありません。アサーションには肯定先読みを使用し、「カウント」にはネストされた参照を 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: 先読み (およびフリー - スペーシング モード) でのキャプチャ
b+をマッチの一部にしたくないとしても、とにかくグループ 1に取り込みたいとしましょう。正規表現をより読みやすくすることができます。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
eg は、各グループが でキャプチャしたものを ing しaaa|bた結果であることに注意してください。この場合、グループ 0 (つまり、パターンが一致したもの) が Capture 、グループ 1 が Captureです。join'|'aaab
レッスン: ルックアラウンド内をキャプチャできます。フリースペースを使用して読みやすくすることができます。
ステップ 3: 先読みを「ループ」にリファクタリングする
カウント メカニズムを導入する前に、パターンに 1 つの変更を加える必要があります。現在、先読みは+繰り返しの「ループ」の外にあります。b+に続くがあることをアサートしたかっただけなので、これまでのところこれで問題ありませんが、最終的a+に本当にやりたいことはa、「ループ」内で一致するそれぞれに対して、それに対応する があることをアサートするbことです。
ここでは、カウント メカニズムについては気にせず、次のようにリファクタリングを行います。
- 最初のリファクタリング(非キャプチャ グループであること
a+に(?: a )+注意してください)(?:…)
- 次に、先読みをこの非キャプチャ グループ内に移動します。
a*を「見る」前に「スキップ」する必要があることに注意してください。そのb+ため、それに応じてパターンを変更します。
したがって、次のようになります。
$r3 = '/ ^ (?: a (?= a* (b+) ) )+ /x';
# │ │ └──┘ │ │
# │ │ 1 │ │
# │ └───────────┘ │
# │ lookahead │
# └───────────────────┘
# non-capturing group
出力は以前と同じ ( ideone.com で見られるように) であるため、その点で変更はありません。重要なことは、「ループ」の反復ごとにアサーションを行っていることです。+現在のパターンでは、これは必要ありませんが、次に、自己参照を使用してグループ 1 を「カウント」します。
レッスン: 非キャプチャ グループ内でキャプチャできます。ルックアラウンドは繰り返すことができます。
ステップ 4: これは、カウントを開始するステップです。
グループ 1 を次のように書き換えます。
- の最初の反復の終わりに、最初の反復が一致し
+たときにaキャプチャする必要がありますb
- 2 回目の反復の最後に、別の反復
aが一致すると、キャプチャする必要があります。bb
- 3回目の繰り返しの終わりに、キャプチャする必要があります
bbb
- ...
- n回目の繰り返しの最後に、グループ 1 はb nをキャプチャする必要があります。
- グループ 1 にキャプチャするのに十分でない場合
b、アサーションは単に失敗します。
そのため、現在 であるグループ 1 は、(b+)のようなものに書き換える必要があります(\1 b)。つまりb、前の反復でグループ 1 がキャプチャしたものに a を「追加」しようとします。
ここで、このパターンには「基本ケース」、つまり自己参照なしで一致できるケースが欠けているという点で、わずかな問題があります。グループ 1 は「初期化されていない」状態で開始されるため、基本ケースが必要です。まだ何もキャプチャしていないため (空の文字列でさえも)、自己参照の試みは常に失敗します。
これには多くの方法がありますが、ここでは、自己参照の一致をoptional、つまり\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 を「カウント」することができました。しかし、待ってください... 2 番目と最後のテスト ケースに何か問題があります!! 十分な s がなくb、どういうわけかカウントが間違っています。これがなぜ起こったのかは、次のステップで調べます。
教訓: 自己参照グループを「初期化」する 1 つの方法は、自己参照マッチングをオプションにすることです。
ステップ 4½: 何が悪かったのかを理解する
問題は、自己参照の一致をオプションにしたため、「カウンター」が十分なb's がない場合に 0 に「リセット」できることです。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?、エンジンはバックトラックして「ノーサンクス」オプションを選択し、これによりb!
ただし、最初の反復を除いて、いつでも self-reference だけを照合できることに注意してください\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!!!
ほら!!! 問題が解決しました！！！私たちは今、まさに私たちが望んでいた方法で、適切に数えています!
レッスン: 貪欲、消極的、所有格の繰り返しの違いを学びます。オプション-所有は強力な組み合わせになる可能性があります。
ステップ 6: 仕上げ
したがって、現在私たちが持っているのは、a繰り返し一致するパターンであり、一致したすべてのパターンに対して、グループ 1aに対応するbキャプチャーがあります。+がなくなるaか、対応するbforがないためにアサーションが失敗した場合、 a。_
ジョブを完了するには、 pattern に追加するだけです\1 $。これは、グループ 1 が一致したものへの後方参照になり、その後に行末アンカーが続きます。bアンカーは、文字列に余分な 'sがないことを保証します。言い換えれば、実際にはn b nがあるということです。
10,000 文字の長さのテスト ケースを含む追加のテスト ケースを含む最終的なパターンを次に示します。
$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
ab、aabb、aaabbb、およびa 5000 b 5000の4 つの一致が見つかります。ideone.com での実行にはわずか 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 n b nに一致する正規表現パターンがあるのは素晴らしいことですが、実際にはこれが常に「最良の」解決策であるとは限りません。はるかに優れた解決策は、単純に を照合^(a+)(b+)$し、ホスティング プログラミング言語でグループ 1 と 2 によってキャプチャされた文字列の長さを比較することです。
PHP では、次のようになります ( ideone.com で見られるように)。
function is_anbn($s) {
return (preg_match('/^(a+)(b+)$/', $s, $groups)) &&
(strlen($groups[1]) == strlen($groups[2]));
}
この記事の目的は、正規表現でほとんど何でもできると読者に納得させることではありません。明らかに不可能であり、できることであっても、より簡単な解決策につながる場合は、ホスト言語への少なくとも部分的な委譲を検討する必要があります。
冒頭で述べたように、この記事は必ず[regex]スタックオーバーフローのタグが付けられていますが、おそらくそれ以上のものです。アサーション、ネストされた参照、所有量指定子などについて学ぶことには確かに価値がありますが、おそらくここでのより大きな教訓は、問題を解決しようとする創造的なプロセス、つまり、問題に直面したときにしばしば必要とされる決意とハードワークです。さまざまな制約、実用的なソリューションを構築するためのさまざまな部分からの体系的な構成など。
ボーナス素材！PCRE 再帰パターン!
PHP を取り上げたので、PCRE は再帰パターンとサブルーチンをサポートしていると言う必要があります。したがって、次のパターンはpreg_match( ideone.com で見られるように) に対して機能します。
$rRecursive = '/ ^ (a (?1)? b) $ /x';
現在、Java の正規表現は再帰パターンをサポートしていません。
さらにおまけ素材！マッチングa n b n c n !!
では、規則的ではないが文脈自由であるa n b nに一致させる方法を見てきましたが、文脈自由でさえないa n b n c nにも一致させることができるでしょうか?
もちろん、答えはイエスです！読者はこれを自分で解決することをお勧めしますが、解決策を以下に示します ( ideone.com の Java での実装)。
^ (?: a (?= a* (\1?+ b) b* (\2?+ c) ) )+ \1 \2 $