Relacionando 2 expresiones regulares en Python

¿Es posible hacer coincidir 2 expresiones regulares en Python?

Por ejemplo, tengo un caso de uso en el que necesito comparar 2 expresiones como esta:

re.match('google\.com\/maps', 'google\.com\/maps2', re.IGNORECASE) 

Espero que me devuelvan un objeto RE.

Pero obviamente, Python espera una cadena como segundo parámetro. ¿Hay alguna forma de lograr esto, o es una limitación de la forma en que funciona la comparación de expresiones regulares?


Antecedentes: tengo una lista de expresiones regulares [r1, r2, r3, …] que coinciden con una cadena y necesito averiguar qué expresión es la coincidencia más específica de la cadena dada. La forma en que asumí que podía hacerlo funcionar era por:
(1) haciendo coincidir r1 con r2.
(2) luego empareja r2 con r1.
Si ambos coinciden, tenemos un ’empate’. Si solo (1) funcionó, r1 es una “mejor” coincidencia que r2 y viceversa.
Haría un bucle (1) y (2) sobre toda la lista.

Admito que es un poco para envolver la cabeza (principalmente porque mi descripción es probablemente incoherente), pero realmente agradecería que alguien me diera una idea de cómo puedo lograr esto. ¡Gracias!

Fuera de la aclaración de la syntax en re.match , creo que estoy entendiendo que está teniendo problemas para tomar dos o más expresiones de expresiones regulares (entrada de usuario) desconocidas y clasificar que es una coincidencia más ‘específica’ contra una cadena.

Recordemos por un momento que una expresión regular de Python es realmente un tipo de progtwig de computadora. La mayoría de las formas modernas, incluyendo la expresión regular de Python, se basan en Perl. Las expresiones regulares de Perl tienen recursión, retroceso y otras formas que desafían la inspección trivial. De hecho, una expresión regular deshonesta se puede utilizar como una forma de ataque de denegación de servicio .

Para ver esto en tu propia computadora, prueba:

 >>> re.match(r'^(a+)+$','a'*24+'!') 

Eso toma aproximadamente 1 segundo en mi computadora. Ahora aumente el 24 en 'a'*24 a un número un poco más grande, digamos 28 . Eso lleva mucho más tiempo. Intente 48 … Probablemente necesite CTRL + C ahora. El aumento de tiempo a medida que aumenta el número de a es, de hecho, exponencial.

Puede leer más sobre este problema en el maravilloso artículo de Russ Cox sobre ‘La comparación de expresiones regulares puede ser simple y rápida’ . Russ Cox es el ingeniero de Goggle que construyó Google Code Search en 2006. Como observa Cox, considere comparar la expresión regular 'a?'*33 + 'a'*33 con la cadena 'a'*99 con awk y Perl (o Python o PCRE o Java o PHP o …) Awk coincide en 200 microsegundos, pero Perl requeriría 10 15 años debido al retroceso exponencial.

Así que la conclusión es: ¡depende! ¿Qué quieres decir con un partido más específico ? Vea algunas de las técnicas de simplificación de expresiones regulares de Cox en RE2 . Si su proyecto es lo suficientemente grande como para escribir sus propias bibliotecas (o usar RE2) y está dispuesto a restringir la gramática de expresiones regulares (es decir, sin retroceso o formas recursivas), creo que la respuesta es que clasificaría “una mejor coincidencia” en una variedad de formas.

Si está buscando una forma sencilla de indicar que (regex_3

Editar

¡Todo lo que dije arriba es verdad! Sin embargo, aquí hay un bash de ordenar las expresiones regulares coincidentes basadas en una forma de ‘específica’: cuántas ediciones se deben obtener de la expresión regular a la cadena. Cuanto mayor sea el número de ediciones (o cuanto mayor sea la distancia de Levenshtein), menos “específica” será la expresión regular.

Serás el juez si esto funciona (no sé qué significa ‘específico’ para ti en tu solicitud):

 import re def ld(a,b): "Calculates the Levenshtein distance between a and b." n, m = len(a), len(b) if n > m: # Make sure n <= m, to use O(min(n,m)) space a,b = b,a n,m = m,n current = range(n+1) for i in range(1,m+1): previous, current = current, [i]+[0]*n for j in range(1,n+1): add, delete = previous[j]+1, current[j-1]+1 change = previous[j-1] if a[j-1] != b[i-1]: change = change + 1 current[j] = min(add, delete, change) return current[n] s='Mary had a little lamb' d={} regs=[r'.*', r'Mary', r'lamb', r'little lamb', r'.*little lamb',r'\b\w+mb', r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'\blittle\b',s,r'little'] for reg in regs: m=re.search(reg,s) if m: print "'%s' matches '%s' with sub group '%s'" % (reg, s, m.group(0)) ld1=ld(reg,m.group(0)) ld2=ld(m.group(0),s) score=max(ld1,ld2) print " %i edits regex->match(0), %i edits match(0)->s" % (ld1,ld2) print " score: ", score d[reg]=score print else: print "'%s' does not match '%s'" % (reg, s) print " ===== %s ===== === %s ===" % ('RegEx'.center(10),'Score'.center(10)) for key, value in sorted(d.iteritems(), key=lambda (k,v): (v,k)): print " %22s %5s" % (key, value) 

El progtwig está tomando una lista de expresiones regulares y haciendo coincidir la cadena que Mary had a little lamb .

Aquí está la clasificación ordenada de “más específico” a “menos específico”:

  ===== RegEx ===== === Score === Mary had a little lamb 0 Mary.*little lamb 7 .*little lamb 11 little lamb 11 .*[lL]ittle [Ll]amb 15 \blittle\b 16 little 16 Mary 18 \b\w+mb 18 lamb 18 .* 22 

Esto se basa en la suposición (quizás simplista) de que: a) el número de ediciones (la distancia de Levenshtein) que debe obtenerse desde la expresión regular a la subcadena correspondiente es el resultado de expansiones o reemplazos de comodines; b) las ediciones para obtener de la subcadena correspondiente a la cadena inicial. (solo toma uno)

Como dos ejemplos simples:

  1. .* (o .*.* o .*?.* etc) contra cualquier picadura es un gran número de ediciones para llegar a la cadena, de hecho igual a la longitud de la cadena. Este es el máximo posible de ediciones, la puntuación más alta y la expresión regular menos “específica”.
  2. La expresión regular de la cadena en sí contra la cadena es lo más específica posible. No hay ediciones para cambiar de una a la otra, lo que da como resultado un 0 o la puntuación más baja

Como se dijo, esto es simplista. Los anclajes deberían boost la especificidad pero no lo hacen en este caso. Las picaduras muy cortas no funcionan porque el comodín puede ser más largo que la cadena.

Editar 2

Conseguí que el análisis de anclas funcionara bastante bien utilizando el módulo sre_parse no sre_parse en Python. Escriba >>> help(sre_parse) si desea leer más …

Este es el módulo goto worker que se encuentra debajo del módulo re . Ha estado en todas las distribuciones de Python desde 2001, incluidas todas las versiones P3k. Puede desaparecer, pero no creo que sea probable …

Aquí está el listado revisado:

 import re import sre_parse def ld(a,b): "Calculates the Levenshtein distance between a and b." n, m = len(a), len(b) if n > m: # Make sure n <= m, to use O(min(n,m)) space a,b = b,a n,m = m,n current = range(n+1) for i in range(1,m+1): previous, current = current, [i]+[0]*n for j in range(1,n+1): add, delete = previous[j]+1, current[j-1]+1 change = previous[j-1] if a[j-1] != b[i-1]: change = change + 1 current[j] = min(add, delete, change) return current[n] s='Mary had a little lamb' d={} regs=[r'.*', r'Mary', r'lamb', r'little lamb', r'.*little lamb',r'\b\w+mb', r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'\blittle\b',s,r'little', r'^.*lamb',r'.*.*.*b',r'.*?.*',r'.*\b[lL]ittle\b \b[Ll]amb', r'.*\blittle\b \blamb$','^'+s+'$'] for reg in regs: m=re.search(reg,s) if m: ld1=ld(reg,m.group(0)) ld2=ld(m.group(0),s) score=max(ld1,ld2) for t, v in sre_parse.parse(reg): if t=='at': # anchor... if v=='at_beginning' or 'at_end': score-=1 # ^ or $, adj 1 edit if v=='at_boundary': # all other anchors are 2 char score-=2 d[reg]=score else: print "'%s' does not match '%s'" % (reg, s) print print " ===== %s ===== === %s ===" % ('RegEx'.center(15),'Score'.center(10)) for key, value in sorted(d.iteritems(), key=lambda (k,v): (v,k)): print " %27s %5s" % (key, value) 

Y citó RegEx's:

  ===== RegEx ===== === Score === Mary had a little lamb 0 ^Mary had a little lamb$ 0 .*\blittle\b \blamb$ 6 Mary.*little lamb 7 .*\b[lL]ittle\b \b[Ll]amb 10 \blittle\b 10 .*little lamb 11 little lamb 11 .*[lL]ittle [Ll]amb 15 \b\w+mb 15 little 16 ^.*lamb 17 Mary 18 lamb 18 .*.*.*b 21 .* 22 .*?.* 22 

Depende de qué tipo de expresiones regulares tengas; como sugiere @ carrot-top, si realmente no estás tratando con “expresiones regulares” en el sentido de CS, y en lugar de eso tienes extensiones locas, entonces definitivamente no tienes suerte.

Sin embargo, si tiene expresiones regulares tradicionales, podría progresar un poco más. Primero, podríamos definir qué significa “más específico”. Supongamos que R es una expresión regular y L (R) es el lenguaje generado por R. Entonces podríamos decir que R1 es más específico que R2 si L (R1) es un subconjunto (estricto) de L (R2) (L (R1) .*mary y lamb.* .

Una solución no ambigua es definir la especificidad a través de la implementación . Por ejemplo, convierta su expresión regular de forma determinista (definida por la implementación) a un DFA y simplemente cuente los estados. Desafortunadamente, esto podría ser relativamente opaco para un usuario.

De hecho, parece que tienes una noción intuitiva de cómo quieres que se comparen dos expresiones regulares, en términos de especificidad. ¿Por qué no escribir simplemente una definición de especificidad, basada en la syntax de las expresiones regulares, que coincida con su intuición razonablemente bien?

Siguen reglas totalmente arbitrarias:

  1. Caracteres = 1 .
  2. Rangos de caracteres de n caracteres = n (y digamos \b = 5 , porque no estoy seguro de cómo podría elegir escribirlo a mano larga).
  3. Los anclajes son de 5 cada uno.
  4. * divide su argumento por 2 .
  5. + divide su argumento por 2 , luego agrega 1 .
  6. . = -10 .

De todos modos, solo hay que pensar, ya que las otras respuestas hacen un buen trabajo al esbozar algunos de los problemas que enfrentas; Espero eso ayude.

No creo que sea posible.

Una alternativa sería tratar de calcular el número de cadenas de longitud n que también coinciden con la expresión regular. Una expresión regular que coincida con 1,000,000,000 cadenas de longitud de 15 caracteres es menos específica que una que coincide solo con 10 cadenas de longitud de 15 caracteres.

Por supuesto, calcular el número de coincidencias posibles no es trivial a menos que las expresiones regulares sean simples.

Opción 1:

Dado que los usuarios están suministrando las expresiones regulares, quizás les pida que también presenten algunas cadenas de prueba que consideren ilustrativas de la especificidad de su expresión regular. (es decir, que muestran que su expresión regular es más específica que la expresión regular de un competidor). Recopile todas las cadenas de prueba enviadas por el usuario y luego pruebe todas las expresiones regulares contra el conjunto completo de cadenas de prueba.

Para diseñar una buena expresión regular, el autor debe haber pensado en qué cadenas coinciden y no coinciden con sus expresiones regulares, por lo que debería ser fácil para ellos proporcionar buenas cadenas de prueba.


Opcion 2:

Puede intentar un enfoque de Monte Carlo: Comenzando con la cadena que coinciden ambas expresiones regulares, escriba un generador que genere mutaciones de esa cadena (permutar caracteres, agregar / eliminar caracteres, etc.) Si ambas expresiones regulares coinciden o no coinciden de la misma manera para cada mutación, entonces las expresiones regulares ” probablemente empaten “. Si uno coincide con una mutación que el otro no, y viceversa, entonces “se unen absolutamente “.

Pero si uno coincide con un superconjunto estricto de mutaciones, entonces es ” probablemente menos específico ” que el otro.

El veredicto después de un gran número de mutaciones puede no ser siempre correcto, pero puede ser razonable.


Opción 3:

Utilice ipermute o pyParsing’s invert para generar cadenas que coincidan con cada expresión regular. Esto solo funcionará en una expresión regular que use un subconjunto limitado de syntax de expresión regular.

Creo que podrías hacerlo mirando el resultado de unir el resultado más largo

 >>> m = re.match(r'google\.com\/maps','google.com/maps/hello') >>> len(m.group(0)) 15 >>> m = re.match(r'google\.com\/maps2','google.com/maps/hello') >>> print (m) None >>> m = re.match(r'google\.com\/maps','google.com/maps2/hello') >>> len(m.group(0)) 15 >>> m = re.match(r'google\.com\/maps2','google.com/maps2/hello') >>> len(m.group(0)) 16 
 re.match('google\.com\/maps', 'google\.com\/maps2', re.IGNORECASE) 

El segundo elemento de re.match() anterior es una cadena, por eso no funciona: la expresión regular dice que coincide con un período posterior a Google, pero en su lugar encuentra una barra invertida. Lo que debe hacer es duplicar las barras invertidas en la expresión regular que se está utilizando como una expresión regular:

 def compare_regexes(regex1, regex2): """returns regex2 if regex1 is 'smaller' than regex2 returns regex1 if they are the same returns regex1 if regex1 is 'bigger' than regex2 otherwise returns None""" regex1_mod = regex1.replace('\\', '\\\\') regex2_mod = regex2.replace('\\', '\\\\') if regex1 == regex2: return regex1 if re.match(regex1_mod, regex2): return regex2 if re.match(regex2_mod, regex1): return regex1 

Puede cambiar los rendimientos a lo que mejor se adapte a sus necesidades. Ah, y asegúrate de que estás utilizando cadenas en bruto con re. r'like this, for example'

¿Es posible hacer coincidir 2 expresiones regulares en Python?

Eso ciertamente es posible. Usa grupos de parejas entre paréntesis unidos por | por alteración. Si organiza los grupos de coincidencias entre paréntesis por la mayoría de las expresiones regulares específicas a las menos específicas, el rango en la tupla devuelta de m.groups() mostrará qué tan específica es su coincidencia. También puede usar grupos con nombre para s10 qué tan específica es su coincidencia, como s10 para muy específica y s0 para una coincidencia no tan específica.

 >>> s1='google.com/maps2text' >>> s2='I forgot my goggles at the house' >>> s3='blah blah blah' >>> m1=re.match(r'(^google\.com\/maps\dtext$)|(.*go[az]+)',s1) >>> m2=re.match(r'(^google\.com\/maps\dtext$)|(.*go[az]+)',s2) >>> m1.groups() ('google.com/maps2text', None) >>> m2.groups() (None, 'I forgot my goggles') >>> patt=re.compile(r'(?P^google\.com\/maps\dtext$)| ... (?P.*go[az]+)|(?P[az]+)') >>> m3=patt.match(s3) >>> m3.groups() (None, None, 'blah') >>> m3.groupdict() {'s10': None, 's0': 'blah', 's5': None} 

Si no sabe de antemano qué expresión regular es más específica, este es un problema mucho más difícil de resolver. Desea echar un vistazo a este documento que cubre la seguridad de las coincidencias de expresiones regulares con nombres de sistemas de archivos.

Me doy cuenta de que esto no es una solución, pero como no hay una manera inequívoca de saber cuál es la “coincidencia más específica”, ciertamente cuando depende de lo que “significaron” los usuarios, lo más fácil sería preguntarles. Para proporcionar su propia prioridad. Por ejemplo, simplemente poniendo las expresiones regulares en el orden correcto. Entonces simplemente puedes tomar el primero que coincida. Si esperas que los usuarios se sientan cómodos con las expresiones regulares de todos modos, ¿quizás no sea mucho pedir?