大きな絵
最初に全体像のアルゴリズムからこの正規表現を見てから、後で特定の実装の詳細を詳しく見ていきます。正規表現は、次の Java コードをほぼそのまま翻訳したものです。
static boolean isPalindrome(String s) {
if (s.isEmpty()) {
return true;
}
String g2 = null;
for (char ch : s.toCharArray()) {
String g1 = String.valueOf(ch);
// "add"
if (g2 != null && s.endsWith(g1 + g2)) {
g2 = g1 + g2;
} else if (s.endsWith(g1)) {
g2 = g1;
} else {
break;
}
}
return s.equals(g2); // "chk"
}
これは明らかに、回文をチェックするための最も単純で効率的な Java コードではありませんが、機能し、最も魅力的なことに、ほぼ 1 対 1 のマッピングで正規表現にほぼ直接変換できます。再び正規表現を示します。便宜上、ここで再掲し、顕著な類似性を強調するために注釈を付けています。
// isEmpty _for-loop_
// ↓ / \
"(?x) | (?:(.) add)+ chk"
// \_/ ↑
// g1 loop body ___g2___
// / \
.replace("add", assertEntirety(".*? (\\1 \\2?)"))
.replace("chk", assertEntirety("\\2"));
// s.equals(g2)
添付ファイル: ideone.com のソース コードの注釈付きおよび拡張版
(今のところ、 の詳細は無視してかまいません。現在の場所に関係なく、文字列全体assertEntiretyに対してアサーションを作成できるブラック ボックスの正規表現メカニズムと考えてください。)
したがって、基本的なアルゴリズムは、文字列を左から右にスキャンしながら、パリンドロームの制約に従ってサフィックスを構築しようとすることです。次に、この方法で完全な文字列を作成できるかどうかを確認します。可能であれば、文字列は回文です。また、特殊なケースとして、空の文字列は自明に回文です。
全体像のアルゴリズムを理解したら、正規表現パターンがそれをどのように実装するかを調べることができます。
すべてとは何String.replaceですか？
Java の正規表現パターンは、最終的には文字列にすぎません。つまり、文字列操作によって、通常の文字列と同じように派生させることができます。はい、正規表現を使用して正規表現パターンを生成することもできます。これは一種のメタ正規表現アプローチです。
定数を初期化する次の例を考えてみましょうint(最終的には数値のみが含まれます)。
final int X = 604800;
final int Y = 60 * 60 * 24 * 7;
// now X == Y
に割り当てられた数値Xは、文字通りの整数です:数値が何であるかを明確に見ることができます。代わりに式を使用する場合はそうではYありませんが、この数式は、この数値が何を表しているかのアイデアを伝えているようです。これらの定数に適切な名前を付けなくてもY、数値が何であるかがすぐにはわからなくても、おそらく 1 週間の秒数を表すという考えが得られます。一方、X私たちはその数を正確に知っていますが、それが何を表しているのかについてはあまり理解していません.
スニペットでの文字列置換の使用は類似の状況ですが、文字列正規表現パターンの場合です。パターンを 1 つのリテラル文字列として明示的に記述する代わりに、より単純な部分からその値を体系的かつ論理的に導き出す(「式」) 方がはるかに意味のある場合があります。これは特に正規表現に当てはまります。多くの場合、パターンが文字列リテラルとしてどのように見えるかを理解することよりも、パターンが何をするかを理解することが重要です (余分なバックスラッシュがあるので、見栄えはよくありません)。 .
便宜上、スニペットの一部をここに再掲します。
// the "formula"
final String PALINDROME =
"(?x) | (?:(.) add)+ chk"
.replace("add", assertEntirety(".*? (\\1 \\2?)"))
.replace("chk", assertEntirety("\\2"));
// the "value"
System.out.println(PALINDROME);
// ____add_____ chk_
// _______/ \____ _______/ \_____
// (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)
// | \_/ \______/ |
// | 1 2 |
// |_______________________________|
この場合、最終的な文字列「値」よりも「式」の方がはるかに読みやすいことは間違いありません。
プログラムで正規表現パターンを生成するもっと洗練された方法が確かにあり、その意味を強調するのではなく難読化するような方法で書くことは確かに可能ですが、単純な文字列の置換でさえ注意して使用することは依然として驚くべきことです (うまくいけば、これで示されているように)例）。
レッスン: プログラムによる正規表現パターンの生成を検討してください。
どのように機能しaddますか？
ある種の「カウント」を行うアサーションである(?:(.) add)+構文addは、前の 2 つの部分ですでに十分に説明されています。ただし、次の 2 つの機能は注目に値します。
- キャプチャはグループ 1 に分類され、
(.)後で逆参照できるようになります
- アサーションは
assertEntirety、現在の位置から先を見るのではなく、
- これについては後で詳しく説明します。文字列全体でアサートする方法と考えてください
assertEntiretyin に適用されるパターンaddは次のとおりです。
# prefix _suffix_
# ↓ / \
.*? ( \1 \2? )
# \________/ i.e. a reluctant "whatever" prefix (as short as possible)
# group 2 followed by a suffix captured into group 2
グループ 2 は、オプションの指定子を使用した自己参照であることに注意してください。これは、シリーズのパート 2 で既に説明した手法です。言うまでもなく、グループ 2 はこのパターンの「カウンター」です。これは、「ループ」の反復ごとに左方向に拡張しようとするサフィックスです。左から右にそれぞれ反復する(.)とき、同じ文字を ( への後方参照を使用して\1) サフィックスの先頭に追加しようとします。
上記のパターンの Java コード変換をもう一度思い出してください。便宜上、ここで再現します。
if (g2 != null && s.endsWith(g1 + g2)) { // \2? is greedy, we try this first
g2 = g1 + g2;
} else if (s.endsWith(g1)) { // since \2? is optional, we may also try this
g2 = g1;
} else { // if there's no matching suffix, we "break" out of the "loop"
break;
}
\2?オプションであるという事実は、いくつかのことを意味します。
- 自己参照の「基本ケース」を提供します (これを行う主な理由です!)
- は接尾辞パターンの一部であるため
\2?(したがって、パターン全体の後半に表示されます)、接頭辞部分は消極的でなければなりませ.*?ん.*。これにより\2?、貪欲さを行使することができます。
- 「カウンター」も「リセット」され、「間違った」結果になる可能性があります
?パート 2 では、バックトラックが同じ種類の問題のあるリセットを引き起こす可能性があること
を示しました
- 所有量指定子を使用して問題を解決しました
?+が、これはここでは当てはまりません
3 番目のポイントについては、次のセクションで詳しく説明します。
レッスン: パターンの部分で貪欲/消極的な繰り返しの間の相互作用を慎重に分析します。
関連する質問
なぜchkフェーズが必要なのですか？
前のセクションで触れたように、オプションでバックトラック\2?可能であることは、状況によってはサフィックスが縮小される可能性があることを意味します。この入力について、そのようなシナリオを段階的に検討します。
x y x y z y x
↑
# Initial state, \2 is "uninitialized"
_
(x)y x y z y x
↑
# \1 captured x, \2 couldn't match \1\2 (since \2 is "uninitialized")
# but it could match \1 so it captured x
___
x(y)x y z y x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yx
_
x y(x)y z y x
↑
# \1 captured x, \2 couldn't match \1\2,
# but it could match \1 so it shrunk to capture x (!!!)
___
x y x(y)z y x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yx
_____
x y x y(z)y x
↑
# \1 captured z, \2 matched \1\2 and grew to capture zyx
_______
x y x y z(y)x
↑
# \1 captured y, \2 matched \1\2 and grew to capture yzyx
_________
x y x y z y(x)
↑
# \1 captured x, \2 matched \1\2 and grew to capture xyzyx
パターン (および対応する Java コード) を変更してchkフェーズを省略すると、実際に次のようになることがわかります。
// modified pattern without a chk phase; yields false positives!
final String PALINDROME_BROKEN =
"(?x) | (?:(.) add)+"
.replace("add", assertEntirety(".*? (\\1 \\2?)"));
String s = "xyxyzyx"; // NOT a palindrome!!!
Matcher m = Pattern.compile(PALINDROME_BROKEN).matcher(s);
if (m.matches()) {
System.out.println(m.group(2)); // prints "xyzyx"
}
説明したように"xyxyzyx"、回文ではないは誤って回文として報告されます。これは、成長する接尾辞が最終的に完全な文字列になるかどうかを確認しなかったためです (この場合は明らかにそうではありませんでした)。したがって、chkフェーズ (assertEntiretyパターンの\2) は、セットアップで絶対に必要です。実際にサフィックスを最後まで伸ばすことができたことを確認する必要があります。この場合、私たちは回文を持っています。
教訓: オプションの自己参照マッチングの意図しない副作用を慎重に分析してください。
メインコース：assertEntirety
Java の正規表現パターンを記述して回文を検出できるのは素晴らしいことですが、ここにある以外のすべてのことassertEntiretyは、シリーズの前の部分で既に説明されています。ここで唯一新しいのは、この神秘的なブラック ボックスです。これは、魔法のように「不可能」なことを可能にする強力なメカニズムです。
このassertEntirety構造は、ネストされたルックアラウンドの次のメタパターンに基づいています。
(?<=(?=^pattern$).*)
「後ろのどこかに、前を向いて見える場所が見えます ^pattern$」
「見回す」という名前は、私たちの現在の位置に対する相対性を意味します。私たちは、立っている場所から、おそらく前または後ろで、私たちの周りを見ています. このように後読みで先読みをネストすることにより、比喩的に「空を飛んで」全体像を見ることができます。
このメタパターンを抽象化することassertEntiretyは、前処理置換マクロを書くことに少し似ています。どこにでも入れ子になったルックアラウンドがあると、可読性と保守性が損なわれる可能assertEntirety性があります。
教訓: メタパターンを抽象化して、複雑さを隠し、セマンティクスを伝えることを検討してください。
付録: Java での無限長後読みについて
assertEntirety注意深い読者は、後読みにa が含まれていることに気付くでしょう.*。これにより、理論上の最大長は無限になります。いいえ、Java は公式には無限長の後読みをサポートしていません。はい、ここで十分に実証されているので、とにかく動作します。公式には「バグ」に分類されています。しかし、「誰か」(*ウィンク*)はそれを「隠れた機能」と見なすこともできます。
この「バグ」が将来「修正」される可能性は確かにあります。この隠された機能を削除すると、Java 正規表現の回文問題に対するこの特定のソリューションが壊れます。
関連する質問