Wie funktioniert das Java-regex erkennen Palindrome?

Das Große Bild

Werden wir den ersten Blick auf diese regex vom großen ganzen-Algorithmus, und dann nehmen Sie einen genaueren Blick auf die konkrete Umsetzung im Detail später. Die regex ist eine fast direkte übersetzung des folgenden Java-code:

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"
}

Dies ist natürlich nicht die einfachste/effizienteste Java-code zu überprüfen, Palindrome, aber es funktioniert, und die meisten faszinierend, es ist fast direkt übersetzbar, regex mit einer nahezu eins-zu-eins-Zuordnung. Hier ist die regex wieder reproduziert hier für die Bequemlichkeit, kommentierte hervorzuheben ist die auffallende ähnlichkeit:

// isEmpty  _for-loop_
//      ↓  /         \
    "(?x) | (?:(.) add)+ chk"
//            \_/ ↑
//            g1   loop body                   ___g2___
//                                            /       \
           .replace("add", assertEntirety(".*? (\\1 \\2?)"))
           .replace("chk", assertEntirety("\\2"));
                           //s.equals(g2)

Anlage: kommentierte und erweiterte version der source code auf ideone.com

(Fühlen Sie sich frei, zu ignorieren, die details von assertEntirety für heute: denken Sie nur als black-box-regex-Mechanismus stellen Sie eine Behauptung auf die gesamte Zeichenfolge unabhängig davon, wo wir gerade sind.)

Also der grundlegende Algorithmus ist, dass wir versuchen, zu bauen ein suffix, subject, um ein Palindrom Einschränkung, als wir Scannen die Zeichenfolge von Links nach rechts. Wir dann prüfen, ob wir in der Lage sind, zu bauen, die den kompletten string in dieser Art und Weise. Wenn wir können, dann ist der string ist ein Palindrom. Auch, als Sonderfall, der leere string ist trivial ein Palindrom.

Einmal das große Bild-Algorithmus verstanden wird, können wir untersuchen, wie die regex-pattern implementiert.

---

Was ist mit all den String.replace?

Regex-patterns in Java sind letztlich nichts als strings, das heißt, Sie können abgeleitet werden durch string-Manipulationen die Möglichkeit eine beliebige Zeichenfolge kann. Ja, wir können sogar mit regex zu generieren, die ein regex-Muster-eine Art meta-regexing Ansatz, wenn man so will.

Betrachten Sie dieses Beispiel der Initialisierung einer int konstant (was letztlich nichts enthält aber eine Reihe):

final int X = 604800;
final int Y = 60 * 60 * 24 * 7;
//now X == Y

Nummer zu X ist ein integer-literal: wir können deutlich sehen was die Nummer ist. Dies ist nicht der Fall mit Y die einen Ausdruck verwendet, statt, und doch ist diese Formel scheint zu vermitteln, eine Idee, was diese Zahl darstellt. Auch ohne korrekte Benennung dieser Konstanten werden wir dennoch auf die Idee kommen, dass Y wahrscheinlich stellt die Anzahl der Sekunden in einer Woche, auch wenn wir vielleicht nicht sofort wissen, was der numerische Wert ist. Auf der anderen Seite, mit X wir wissen genau, dass die Nummer, aber wir bekommen weniger eine Idee von dem, was es darstellt.

Die Verwendung von string-Ersetzungen im snippet ist eine analoge situation, aber für strings regex-Muster. Anstatt explizit schreiben das Muster als eine literal-Zeichenfolge, manchmal systematische und logische Ableitung ("Formel") der Wert von einfacheren teilen kann, ist viel mehr sinnvoll. Dies gilt insbesondere mit regex, wo es oft wichtig ist, dass wir verstehen, was das Muster bedeutet, als dass Sie in der Lage, um zu sehen, was es sieht aus wie ein string-literal (das ist nicht viel von einem Hingucker wie auch immer, was mit all den zusätzlichen backslashes).

Einen Teil des snippets wird hier wiedergegeben erneut für die Bequemlichkeit:

//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         |
     //       |_______________________________|

Ohne Zweifel die "Formel" ist viel besser lesbar als die etwaigen string "Wert" in diesem Fall.

Gibt es sicherlich viel mehr raffinierte Möglichkeiten, um programmatisch erzeugt ein regex-Muster, und es ist sicherlich möglich zu schreiben in einer Weise, die verschleiert, statt akzentuiert Ihre Bedeutung, aber achtsam Nutzung auch einfache string-Ersetzungen können sich noch Wundern (hoffentlich in diesem Beispiel gezeigt).

Lektion: Betrachten Sie die programmatische Generierung von regex-mustern.

---

Wie funktioniert add Arbeit?

Den (?:(.) add)+ konstruieren, wo add ist eine Behauptung, die nicht irgendeine Art von "zählen", wurde bereits ausführlich diskutiert und in den beiden vorangegangenen teilen. Zwei Besonderheiten sind erwähnenswert, aber:

• Die (.) erfasst in der Gruppe 1, so dass Rückverweis später
• Die Behauptung ist assertEntirety anstatt nur zu schauen Voraus von unserer aktuellen position
  • Wir werden dies besprechen in mehr detail später; man denke nur an es als eine Möglichkeit, zu behaupten, die auf die gesamte Zeichenfolge

Muster angewendet assertEntirety im add ist folgende:

# prefix   _suffix_
#    ↓    /        \
    .*?   ( \1 \2? )
#         \________/   i.e. a reluctant "whatever" prefix (as short as possible)
#          group 2          followed by a suffix captured into group 2

Beachten Sie, dass die Gruppe 2 ist selbst-referenzierend, optional mit einem Bezeichner, einer Technik, die bereits im Teil 2 der Serie. Unnötig zu sagen, die Gruppe 2 ist unsere "Zähler" in dieses Muster: es ist ein suffix, das werden wir versuchen zu wachsen, nach Links, auf jeder iteration der "loop". Als wir die Iteration auf jeden (.) Links nach rechts, versuchen wir voranstellen, dass die gleichen Zeichen (mit Rückverweis auf \1) zu unserem suffix.

Erneut aufrufen die Java-code übersetzung der oben genannten Muster, reproduziert hier für die Bequemlichkeit:

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;
}

Die Tatsache, dass \2? ist optional bedeutet, ein paar Dinge:

• Es bietet ein "base case" für die selbst-Referenz (der Hauptgrund, warum wir dies tun!)
• Seit \2? ist Teil des suffix-Muster (und damit erscheint später in der gesamten Muster), das Präfix müssen Sie nur ungern, daher .*? statt .*. Dies ermöglicht \2? um die Ausübung Ihrer Habgier.
• Der "Zähler" kann auch "reset" und geben die "falschen" Ergebnis
  • In Teil 2 haben wir gezeigt, wie backtracking ? kann in der gleichen Art problematisch zurücksetzen
    • Wir lösten das problem, indem Sie possessive Quantifizierer ?+, aber das ist hier nicht zutreffend,

Der Dritte Punkt, der erarbeitet wird, weiter in den nächsten Abschnitt.

Lektion: Sorgfältig analysieren die Wechselwirkungen zwischen gierig/nur ungern Wiederholungen in den teilen der Muster.

Fragen

• Unterschied zwischen .*? und .* für regex
• Regulärer Ausdruck: wer greedier?

---

Warum brauchen wir eine chk phase?

Wie angedeutet, die im vorherigen Abschnitt, die optional und backtrackable \2? bedeutet, dass unser suffix schrumpfen können, unter gewissen Umständen. Untersuchen wir ein solches Szenario Schritt für Schritt für diesen Eingang:

 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

Können wir ändern unsere Muster (und den entsprechenden Java-code) weglassen chk phase, und sehen, dass in der Tat dies ist, was passiert:

    //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"
    }

Wie gesagt "xyxyzyx", die NICHT ein Palindrom, wird fälschlicherweise gemeldet, weil wir nicht überprüfen, ob die wachsende suffix wurde schließlich die vollständige Zeichenfolge (die es offensichtlich nicht in diesem Fall). Die chk phase (das ist ein assertEntirety des Musters \2) ist daher eine absolute Notwendigkeit in unserem setup. Wir müssen bestätigen, dass in der Tat haben wir es geschafft, zu wachsen, unsere suffix Weg. Wenn dies der Fall ist, dann haben wir uns selbst ein Palindrom.

Lektion: Sorgfältig analysieren, eventuell unbeabsichtigte Nebenwirkungen der optionale selbst-Referenz-matching.

---

Der Hauptgang: assertEntirety

Während es ist nett, dass wir können, schreiben Sie ein Java-regex-Muster zu erkennen Palindrome, alles hier, außer assertEntirety bereits abgedeckt in den vorherigen teilen der Serie. Die einzige neue Sache hier ist dieses mysteriöse schwarze box, diese leistungsfähigen Mechanismus, der magisch uns erlaubt, zu tun, was sonst "unmöglich".

Den assertEntirety Konstrukt basiert auf den folgenden meta-Muster von verschachtelten lookarounds:

(?<=(?=^pattern$).*)

" Ich kann sehen, ein Ort, der irgendwo hinter mir, wo kann ich nach vorne schauen und sehen ^pattern$ "

Dem Namen "lookaround" impliziert die Relativität unserer aktuellen Lage: wir sind auf der Suche um uns, vielleicht vor oder hinter, von wo wir stehen. Durch die Verschachtelung ein lookahead in einem lookbehind auf diese Weise sind wir in der Lage, die sprichwörtliche "fliege in den Himmel" und betrachten das ganze Bild.

Abstrahiert diesem meta-Muster in assertEntirety ist ein bisschen wie das schreiben Vorverarbeitung substitution von Makros. Mit verschachtelten lookarounds überall wohl weh tut, Lesbarkeit und Wartbarkeit, also wir fassen es in assertEntirety, die nicht nur versteckt die Komplexität der inneren Funktionsweise, aber auch betont weiter Ihre Semantik, indem Sie ihm einen passenden Namen.

Lektion: Betrachten Sie abstrahiert meta-Muster zu verstecken die Komplexität und vermitteln Semantik.

---

Anhang: die Auf unendliche Länge lookbehind in Java

Aufmerksame Leser hätte bemerkt, dass assertEntirety enthält eine .* in einer lookbehind, wodurch die theoretische maximale Länge unendlich. Nein, in Java nicht offiziell unterstützen, unendliche Länge lookbehind. Ja, es wurde adequatedly hier zeigt sich, es funktioniert trotzdem. Offiziell ist es kategorisiert als ein "bug", sondern "jemand"^(*Zwinker*) könnte auch überlegen, es zu einem "hidden feature".

Es ist sicherlich möglich, dass dieser "bug" wird "fixiert" in der Zukunft. Die Entfernung von dieser versteckten Funktion wird brechen diese spezielle Lösung um die Java-regex-Palindrom-problem.

Fragen

• Regex-suchen-hinter ohne offensichtliche maximale Länge in Java