pattern example java regex palindrome lookaround nested-reference

example - ¿Cómo este Java regex detecta los palíndromos?



java regex example (1)

Esta es la tercera parte de una serie de artículos de regex educativos. Sigue ¿Cómo encuentra esta expresión regular los números triangulares? (donde se introducen las referencias anidadas por primera vez) y ¿Cómo podemos relacionar una ^ nb ^ n con la expresión regular de Java? (donde se profundiza el mecanismo de "conteo" de lookahead). Esta parte introduce una forma específica de aseveración anidada, que cuando se combina con referencias anidadas permite que las expresiones regulares de Java coincidan con lo que la mayoría de la gente cree que es "imposible": ¡palíndromos!

El lenguaje de los palíndromos no es regular ; es en realidad context-free (para un alfabeto dado). Dicho esto, la implementación moderna de expresiones regulares reconoce más que solo lenguajes regulares, y los patrones recursivos de Perl / PCRE y los grupos de equilibrio de .NET pueden reconocer fácilmente los palíndromos (consulte: Preguntas relacionadas ).

Sin embargo, el motor de expresiones regulares de Java no es compatible con ninguna de estas características "avanzadas". Y sin embargo, "alguien" ( * wink * ) logró escribir la siguiente expresión regular que parece que funciona bien ( vea también en 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)); } } }

Así que esto parece funcionar, pero ¿cómo?

Referencias

ALERTA DE SENTIDO COMÚN !!!

Esta no es la mejor manera de detectar palíndromos; es O(N^3) en el mejor de los casos. Realizar esta detección en un lenguaje de programación de propósito más general es a la vez más eficiente y más directo.

No querría usar expresiones regulares para detectar palíndromos por las mismas razones por las que no querría usar expresiones regulares para encontrar números primos. Dicho esto, usted estudiaría cómo una expresión regular de grupo no equilibrada no recursiva puede detectar palíndromos por las mismas razones por las que estudiaría cómo se puede utilizar una expresión regular para las pruebas de primalidad: es divertido, es desafiante, es educativo.

Preguntas relacionadas

El panorama

Primero veremos esta expresión regular del algoritmo general de imagen general, y luego veremos más de cerca los detalles específicos de la implementación más adelante. La expresión regular es una traducción casi directa del siguiente código de 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" }

Obviamente, este no es el código Java más sencillo / eficiente para verificar los palíndromos, pero funciona, y lo más fascinante es que es casi directamente traducible a expresiones regulares con un mapeo casi uno a uno. Aquí está la expresión regular de nuevo, reproducida aquí por conveniencia, anotada para resaltar el sorprendente parecido:

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

Adjunto : versión anotada y expandida del código fuente en ideone.com

(Siéntase libre de ignorar los detalles de assertEntirety por ahora: solo piense en ello como un mecanismo de assertEntirety regulares de caja negra que puede hacer una afirmación en toda la cadena, independientemente de dónde se encuentre actualmente).

Entonces, el algoritmo básico es que intentamos construir un sufijo, sujeto a una restricción palindrómica, mientras escaneamos la cadena de izquierda a derecha. Luego, verificamos si podemos construir la cadena completa de esta manera. Si podemos, entonces la cadena es un palíndromo. Además, como un caso especial, la cadena vacía es trivialmente un palíndromo.

Una vez que se comprende el algoritmo de imagen general, podemos examinar cómo el patrón regex lo implementa.

¿Qué pasa con todo el String.replace ?

Los patrones de expresión regular en Java no son, en última instancia, nada más que cadenas, lo que significa que pueden derivarse a través de manipulaciones de cadenas de la misma forma que cualquier cadena. Sí, incluso podemos usar expresiones regulares para generar un patrón de expresiones regulares: un tipo de enfoque de meta-regexing, por así decirlo.

Considere este ejemplo de inicialización de una constante int (que en última instancia no contiene más que un número):

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

El número asignado a X es un entero literal: podemos ver claramente cuál es el número. Este no es el caso con Y que usa una expresión en su lugar, y sin embargo, esta fórmula parece transmitir una idea de lo que representa este número. Aun sin nombrar adecuadamente estas constantes, sin embargo, tenemos la idea de que Y probablemente representa el número de segundos en una semana, incluso si es posible que no sepamos de inmediato cuál es el valor numérico. Por otro lado, con X conocemos precisamente ese número, pero tenemos menos idea de lo que representa.

El uso de reemplazos de cadenas en el fragmento es una situación análoga, pero para los patrones de expresiones regulares de cadenas. En lugar de escribir explícitamente el patrón como una cadena literal, a veces la derivación lógica y sistemática (la "fórmula") de ese valor a partir de partes más simples puede ser mucho más significativa. Esto es especialmente cierto con las expresiones regulares, donde a menudo es más importante que entendamos lo que hace el patrón que ser capaces de ver cómo se ve como un literal de cadena (que de todos modos no tiene mucho aspecto, que con todas las barras inversas adicionales) .

Una parte del fragmento se reproduce aquí de nuevo para su comodidad:

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

Sin lugar a dudas, la "fórmula" es mucho más legible que la cadena "valor" en este caso.

Ciertamente, hay formas mucho más sofisticadas de generar mediante programación un patrón de expresiones regulares, y es ciertamente posible escribir de tal manera que ofusque en lugar de acentuar su significado, pero el uso consciente de incluso reemplazos de cadenas simples puede ser sorprendente (como se muestra en este ejemplo). ejemplo).

Lección : Considerar la generación programática de patrones de expresiones regulares.

¿Cómo funciona add ?

La construcción (?:(.) add)+ , donde add es una afirmación que hace algún tipo de "conteo", ya se ha analizado a fondo en las dos partes anteriores. Dos características son dignas de mención, sin embargo:

  • El (.) Captura en el grupo 1, lo que permite una referencia posterior más adelante
  • La afirmación es assertEntirety lugar de mirar hacia adelante desde nuestra posición actual
    • Discutiremos esto con más detalle más adelante; solo piénsalo como una manera de afirmar en toda la cadena

El patrón aplicado a assertEntirety en add es el siguiente:

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

Tenga en cuenta que el grupo 2 hace referencia a sí mismo con un especificador opcional, una técnica que ya se analizó en la parte 2 de la serie. No hace falta decir que el grupo 2 es nuestro "contador" en este patrón: es un sufijo que intentaremos crecer hacia la izquierda en cada iteración del "bucle". A medida que iteramos en cada (.) izquierda a derecha, intentamos anteponer ese mismo carácter (usando la referencia inversa a /1 ) a nuestro sufijo.

Recordemos nuevamente la traducción del código Java del patrón anterior, reproducido aquí por conveniencia:

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

El hecho de que /2? Es opcional significa algunas cosas:

  • Proporciona un "caso base" para la auto-referencia (¡la razón principal por la que hacemos esto!)
  • Desde /2? es parte del patrón de sufijo (y, por lo tanto, aparece más adelante en el patrón general), la parte del prefijo debe ser renuente, por lo tanto, .*? en lugar de .* . Esto permite /2? Para ejercer su avidez.
  • El "contador" también puede "reiniciar" y dar el resultado "incorrecto"
    • En la parte 2 mostramos cómo retroceder ? puede resultar en el mismo tipo de reinicio problemático
      • Resolvimos el problema usando un cuantificador posesivo ?+ , Pero esto no es aplicable aquí

El tercer punto se detalla en la siguiente sección.

Lección : Analice cuidadosamente las interacciones entre repeticiones codiciosas / renuentes en partes de un patrón.

Preguntas relacionadas

¿Por qué necesitamos una fase chk ?

Como se mencionó en la sección anterior, ¿el opcional y el backtrackable /2? significa que nuestro sufijo puede encogerse en algunas circunstancias. Examinaremos tal escenario paso a paso para esta entrada:

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

Podemos modificar nuestro patrón (y el código Java correspondiente) para omitir la fase chk , y ver que de hecho esto es lo que sucede:

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

Como se explicó, "xyxyzyx" , que NO es un palíndromo, se informa falsamente como tal, porque no verificamos si el sufijo en crecimiento se convirtió finalmente en la cadena completa (lo que claramente no ocurrió en este caso). Por lo tanto, la fase chk (que es una assertEntirety del patrón /2 ) es una necesidad absoluta en nuestra configuración. Necesitamos confirmar que efectivamente logramos crecer nuestro sufijo todo el tiempo. Si este es el caso, entonces tenemos un palíndromo.

Lección : Analice cuidadosamente cualquier efecto secundario no deseado de la coincidencia de auto-referencia opcional.

El plato principal: assertEntirety

Si bien es bueno que podamos escribir un patrón de assertEntirety regulares de Java para detectar palíndromos, todo aquí, excepto assertEntirety ya se ha cubierto en las partes anteriores de la serie. Lo único nuevo aquí es esta misteriosa caja negra, este poderoso mecanismo que mágicamente nos permitió hacer lo que de otra manera es "imposible".

El constructo assertEntirety se basa en el siguiente patrón meta de los sistemas de búsqueda anidados:

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

" Puedo ver un lugar en algún lugar detrás de mí donde puedo mirar hacia adelante y ver ^pattern$ "

El nombre "lookaround" implica la relatividad a nuestra posición actual: estamos mirando a nuestro alrededor , tal vez delante o detrás, desde donde estamos parados. Al anidar un lookahead de esta manera, podemos metafóricamente "volar a los cielos" y mirar la imagen completa.

assertEntirety este meta-patrón en assertEntirety es un poco como escribir macros de sustitución de preprocesamiento. Tener miradas anidadas en todas partes probablemente daña la legibilidad y la capacidad de mantenimiento, por lo que lo encapsulamos en assertEntirety , que no solo oculta la complejidad de su funcionamiento interno, sino que también enfatiza su semántica al darle un nombre apropiado.

Lección : Considere la posibilidad de abstraer los meta-patrones para ocultar la complejidad y transmitir semántica

Apéndice: Sobre la mirada de longitud infinita detrás de Java

Los lectores observadores notarán que assertEntirety contiene un .* En una mirada, lo que hace que su longitud máxima teórica sea infinita. No, Java no admite oficialmente la apariencia de longitud infinita. Sí, como se ha demostrado adecuadamente aquí, funciona de todos modos. Oficialmente se clasifica como un "error"; pero "alguien" (* wink *) también podría considerarlo una "característica oculta".

Es ciertamente posible que este "error" se "arregle" en el futuro. La eliminación de esta característica oculta romperá esta solución particular al problema del palíndromo de expresiones regulares de Java.

Preguntas relacionadas