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

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

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

Однако механизм регулярных выражений Java не поддерживает ни одну из этих "расширенных" функций. И все же "кто-то" (* 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 для проверки на палиндромы, но он работает, и, что самое интересное, он почти напрямую переводится в регулярные выражения с сопоставлением "один к одному". Вот снова регулярное выражение, воспроизведенное здесь для удобства, аннотированное, чтобы подчеркнуть поразительное сходство:

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

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

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

// 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 является нашим "счетчиком" в этом шаблоне: это суффикс, который мы будем пытаться увеличивать влево на каждой итерации "цикла". Как мы повторяем на каждом (.) слева направо, мы пытаемся добавить этот же символ (используя обратную ссылку на \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? проявлять свою жадность.
  • "Счетчик" также может "сбрасывать" и давать "неправильный" результат
    • Во второй части мы показали, как откат ? может привести к тому же виду проблемного сброса
      • Мы решили проблему с помощью собственнического квантификатора ?+, но это не применимо здесь

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

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

Смежные вопросы

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

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

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

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

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

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

Смежные вопросы

Источник
Другие вопросы по тегам