Как это регулярное выражение Java обнаруживает палиндромы?

Это третья часть в серии учебных статей регулярных выражений. Это следует за Как это регулярное выражение находит треугольные числа? (где сначала вставляются вложенные ссылки) и Как мы можем сопоставить ^ nb ^ n с регулярным выражением Java?(где детальный механизм подсчета голосов). Эта часть вводит конкретную форму вложенного утверждения, которое в сочетании с вложенными ссылками позволяет регулярному выражению Java соответствовать тому, что большинство людей считают "невозможным": палиндромы!!

Язык палиндромов не является regular; это фактически context-free (для данного алфавита). Тем не менее, современная реализация регулярных выражений распознает больше, чем просто обычные языки, а рекурсивные шаблоны Perl/PCRE и группы балансировки .NET могут легко распознать палиндромы (см.: Вопросы, относящиеся).

Однако механизм Java regex не поддерживает ни одну из этих "расширенных" функций. И все же "кому-то" (* wink *) удалось написать следующее регулярное выражение, которое, похоже, прекрасно выполняет работу (см. Также на ideone.com):

public class Palindrome {
    // asserts that the entirety of the string matches the given pattern
    static String assertEntirety(String pattern) {
        return "(?<=(?=^pattern$).*)".replace("pattern", pattern);
    }

    public static void main(String[] args) {
        final String PALINDROME =
            "(?x) | (?:(.) add)+ chk"
                .replace("add", assertEntirety(".*? (\\1 \\2?)"))
                .replace("chk", assertEntirety("\\2"));

        System.out.println(PALINDROME);
        // (?x) | (?:(.) (?<=(?=^.*? (\1 \2?)$).*))+ (?<=(?=^\2$).*)

        String[] tests = {
            "",     // true
            "x",    // true
            "xx",   // true
            "xy",   // false
            "xyx",  // true
            "xxx",  // true
            "xxyx", // false
            "racecar",                // true
            "step on no pets",        // true
            "aManaPlanaCanalPanaMa",  // true
            "this is impossible",     // FALSE!!!
        };
        for (String test : tests) {
            System.out.printf("[%s] %s%n", test, test.matches(PALINDROME));
        }
    }
}

Итак, это работает, но как?

Ссылки

ОБЩИЙ УДОВЛЕТВОРИТЕЛЬНЫЙ ОШИБКА!!!

Это не лучший способ обнаружить палиндромы; это O(N^3) в лучшем случае. Выполнение этого обнаружения на более общем языке программирования является более эффективным и более простым.

Вы не захотите использовать регулярное выражение для обнаружения палиндромов по тем же причинам, по которым вы не захотите использовать регулярное выражение для нахождения простых чисел. Тем не менее, вы бы изучили, как нерекурсивное неравновесное групповое регулярное выражение может обнаруживать палиндромы по тем же причинам, что и вы изучаете, как регулярное выражение может использоваться для тестирования примитивов: это забавно, это сложно, оно образовательное.

Связанные вопросы

Ответы

Ответ 1

Большое изображение

Сначала мы рассмотрим это регулярное выражение из общего алгоритма большой картины, а затем более подробно рассмотрим конкретные детали реализации. Регулярное выражение представляет собой почти прямой перевод следующего кода 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-код для проверки палиндромов, но он работает, и наиболее увлекательно, он почти непосредственно переводится в регулярное выражение с сопоставлением "один-к-одному". Здесь regex снова, воспроизведенный здесь для удобства, аннотированный, чтобы подчеркнуть поразительное сходство:

//  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 - это, в конечном счете, ничего, кроме строк, то есть они могут быть получены посредством строковых манипуляций, как может быть любая строка. Да, мы можем даже использовать регулярное выражение для генерации шаблона регулярных выражений - своего рода мета-regexing-подход, если вы это сделаете.

Рассмотрим этот пример инициализации константы int (которая в конечном итоге не содержит ничего, кроме числа):

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

Число, присвоенное X, является буквальным целым числом: мы можем четко видеть, что это за число. Это не относится к Y, который использует выражение вместо этого, и все же эта формула, похоже, передает представление о том, что представляет это число. Даже без правильного обозначения этих констант мы тем не менее получаем мысль о том, что Y, вероятно, представляет количество секунд в неделю, даже если мы не можем сразу знать, что такое числовое значение. С другой стороны, с X мы точно знаем это число, но мы меньше понимаем, что он представляет.

Использование заменой строк в фрагменте является аналогичной ситуацией, но для шаблонов регулярных выражений строк. Вместо того, чтобы явно писать шаблон как одну литеральную строку, иногда систематический и логический вывод ( "формула" ) этого значения из более простых частей может быть гораздо более значимым. Это особенно актуально для регулярного выражения, где часто важно, что мы понимаем, что делает шаблон, чем возможность увидеть, как он выглядит как строковый литерал (который в любом случае не похож на looker, что со всеми лишними обратными косыми чертами).

Часть фрагмента воспроизводится здесь для удобства:

// 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 является утверждением, которое делает какой-то "подсчет", уже было подробно обсуждено в предыдущих двух частях. Следует отметить две особенности:

  • (.) захватывается в группу 1, позволяя более позднюю ссылку
  • Утверждение assertEntirety вместо того, чтобы просто смотреть вперед с нашей текущей позиции
    • Мы обсудим это более подробно позже; просто подумайте об этом как о способе утверждения во всей строке

Образец, применяемый к assertEntirety в 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 no matching suffix, we "break" out of the "loop"
   break;
}

Тот факт, что \2? является необязательным, означает несколько вещей:

  • Он предоставляет "базовый регистр" для самореференции (основная причина, по которой мы это делаем!)
  • Так как \2? является частью шаблона суффикса (и таким образом появляется позже в общем шаблоне), часть префикса должна быть неохотной, следовательно .*? вместо .*. Это позволяет \2? проявлять свою жадность.
  • "Счетчик" может также "reset" и дать "неправильный" результат
    • В части 2 мы показали, как откат ? может привести к такому же проблемному сбросу
      • Мы решили проблему, используя притяжательный квантор ?+, но здесь это не применимо.

Третий пункт более подробно рассматривается в следующем разделе.

Урок: тщательно проанализируйте взаимодействия между жадными/неохотными повторениями в частях шаблона.

Связанные вопросы

Зачем нужна фаза 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$"

Название "lookaround" означает относительность к нашей нынешней позиции: мы оглядываемся вокруг нас, возможно, впереди или позади, откуда мы стоим. Размещая взгляд в lookbehind таким образом, мы можем метафорически "летать в небо" и смотреть на всю картину.

Абстрагирование этого мета-шаблона на assertEntirety немного напоминает запись макросов подстановки предварительной обработки. Наличие вложенных обращений повсюду, вероятно, ущемляет читаемость и ремонтопригодность, поэтому мы инкапсулируем его в assertEntirety, который не только скрывает сложность его внутренних выработок, но и еще больше подчеркивает его семантику, присваивая ему соответствующее имя.

Урок. Рассмотрим абстрагирование мета-шаблонов, чтобы скрыть сложность и передать семантику.

Приложение: на бесконечно длинном lookbehind в Java

Наблюдатели читатели заметят, что assertEntirety содержит a .* в lookbehind, что делает его теоретическую максимальную длину бесконечной. Нет, Java официально не поддерживает бесконечно длинный lookbehind. Да, так как это было продемонстрировано здесь, оно все равно работает. Официально он классифицируется как "ошибка"; но "кто-то" (* wink *) также может считать это "скрытой функцией".

Конечно, возможно, что эта "ошибка" будет "исправлена" в будущем. Удаление этой скрытой функции нарушит это конкретное решение проблемы палиндрома Java regex.

Связанные вопросы