Expresiones en vs regulares para verificar una lista negra de palabras: estimación del rendimiento de producción esperado

Tengo muchas páginas HTML en las que necesito verificar la existencia de palabras en la lista negra. Sé que la incorporada es mucho más rápida que las expresiones regulares, pero aquí estoy tratando de comparar muchas in una sola expresión regular.

Ya que

re.match () comprueba una coincidencia solo al principio de la cadena

Utilicé una expresión regular similar a .*(word|word...) y reemplazé los caracteres de nueva línea con un espacio.


Código

 from timeit import timeit import re from urllib2 import urlopen html = urlopen('http://en.wikipedia.org/wiki/Main_Page').read() # Random reversed strings to avoid unwanted match + one secure match words = [ "zihw","elbadartnu", "retlob", "ssenenif", "nnub", "detartsehcro", "elbappirnu", "banehc", "rebmunbus", "gnizilodi", "noituac", "deludehcsnu", "/body", "latnanosnocerp", "cihportomeh" ] def in_test(html, blacklist): html_lower = html.lower() return any(k in html_lower for k in blacklist): def search_test(html, pattern): if re.search(pattern, html): return True return False def match_test(html, pattern): html_line = html.replace("\r\n", " ").replace("\r", " ").replace("\n", " ") if re.match(pattern, html_line): return True return False # patternX is word|word|word... patternX_exc is .*(word|word|...) pattern5 = re.compile("|".join(words[:5]), re.I) pattern5_exc = re.compile(".*(" + "|".join(words[:5]) + ")", re.I) pattern10 = re.compile("|".join(words[:10]), re.I) pattern10_exc = re.compile(".*(" + "|".join(words[:10]) + ")", re.I) pattern15a = re.compile("|".join(words[:15]), re.I) pattern15a_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I) words[12] = "doctype" # A secure match at the beginning of the page pattern15b = re.compile("|".join(words[:15]), re.I) pattern15b_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I) words[12] = "featured list" # A secure match at ~half page pattern15c = re.compile("|".join(words[:15]), re.I) pattern15c_exc = re.compile(".*(" + "|".join(words[:15]) + ")", re.I) 

in vs re.match vs re.search sin coincidencia

 print timeit("in_test(html, words[:5])", "from __main__ import *") print timeit("search_test(html, pattern5)", "from __main__ import *") print timeit("match_test(html, pattern5_exc)", "from __main__ import *") 0.127397060394 2.05020999908 2.17416286469 print timeit("in_test(html, words[:10])", "from __main__ import *") print timeit("search_test(html, pattern10)", "from __main__ import *") print timeit("match_test(html, pattern10_exc)", "from __main__ import *") 0.210324048996 3.73544692993 3.8765540123 

Estas pruebas no coinciden con ninguna palabra. claramente es el ganador y la velocidad parece boost linealmente con el número de palabras.


in vs re.match vs re.search con coincidencia en una posición diferente

 print timeit("in_test(html, words[:15])", "from __main__ import *") # Match at the end print timeit("search_test(html, pattern15a)", "from __main__ import *") print timeit("match_test(html, pattern15a_exc)", "from __main__ import *") # Match at the beginning print timeit("search_test(html, pattern15b)", "from __main__ import *") print timeit("match_test(html, pattern15b_exc)", "from __main__ import *") # Match at ~half page print timeit("search_test(html, pattern15c)", "from __main__ import *") print timeit("match_test(html, pattern15c_exc)", "from __main__ import *") 

La salida es

 0.258332967758 5.9074420929 0.0433299541473 0.000770807266235 6.0548210144 2.47815990448 3.25421690941 

Cuando se produce una coincidencia, la expresión regular puede ser mucho más rápida que in pero depende de la posición de la coincidencia. Al principio, re.search será mejor, al final re.match es la mejor opción, en ~ media página ambas serán significativamente más lentas que in .


Las expresiones regulares me ayudarán a no duplicar palabras (por ejemplo, è , è …), y me permiten olvidarme de mayúsculas / minúsculas (especialmente con caracteres que no son ascii). Pero la velocidad parece ser demasiado variable y, en promedio, más lenta que in .

¿Son correctas estas pruebas? Si es así, ¿hay algún otro método incorporado que pueda probar u otros procedimientos que me ayuden en este escenario? La lista negra va a crecer, por lo que debo tener esto en cuenta.

El problema en general

Tiene una compensación de tiempo-espacio :

  • La solución más rápida posible (y la que requiere más memoria) es un árbol N-nario (donde N es el número de letras en el alfabeto). Cada nodo tiene N punteros, cada uno de ellos no es nulo si hay palabras en la lista con esa letra como la siguiente, y una marca que se establece es que hay una palabra que termina aquí.
  • Otra implementación rápida con una huella mucho más pequeña es la que está detrás de la búsqueda en T9 .
  • una tabla hash ( set en este caso, ya que solo le interesa si hay una clave presente) tiene una sobrecarga mayor (cálculos de hash, operaciones relacionadas con conflictos) pero se escala extremadamente bien ya que tiene un tiempo de búsqueda casi constante en un caso típico. La implementación de los tipos de mapeo de Python ajusta automáticamente el tamaño de la tabla hash para mantener bajo control la sobrecarga potencialmente ilimitada relacionada con conflictos.
  • Una expresión regular (preferiblemente optimizada al minimizar la cantidad de retroceso a realizar ) tiene una huella insignificante pero es lenta, ya que Python utiliza un motor dirigido a expresiones regulares que recorre el texto muchas veces : está dirigido por texto como el de egrep que es más adecuado para el tarea. Otro factor es que su tiempo de trabajo depende en gran medida de la entrada (a veces, catastróficamente ) y no se escala bien a medida que crece la lista de palabras.
  • la comparación con una lista de palabras es esencialmente un tipo primitivo de motor de expresiones regulares dirigido a texto. No hace retroceso, pero tiene una comparación mayor y una sobrecarga de lista. Puede ser más rápido o más lento que una expresión regular dependiendo de cómo se comparan estos gastos generales.

La pregunta específica sobre la comparación de los dos métodos:

Las pruebas se interpretan correctamente, para el material en el que se realizan. Pero, como dije, el rendimiento de estos dos métodos (por lo tanto, el rendimiento relativo) depende en gran medida del tamaño de la lista de palabras, el tamaño de la entrada y la entrada en sí y la optimización de expresiones regulares.

Curso de acción sugerido.

Por lo tanto, debe realizar pruebas en algunos ejemplos realistas que modelan el caso de uso típico. Es decir

  • Optimice la expresión regular si y de la misma manera que piensa en la producción.
  • tomar el promedio en varios documentos, donde
    • el porcentaje de aquellos con partidos
    • la distribución de ubicaciones de los partidos
    • la tasa relativa de ocurrencia de palabras de la lista de palabras

Es lo mismo que se espera que esté en producción.

También sugeriría probar la tabla hash: tiene una sobrecarga inicial mayor, pero en una entrada grande y / o lista de palabras debería comenzar a superar a las otras dos.

Para evitar la duplicación de palabras, es posible que desee probar los métodos con entrada de desinfección (minúsculas, & sustituciones de -seq) antes de la búsqueda. Nuevamente, esto es una sobrecarga adicional que comienza a pagar después de una cierta escala.

Minimizando los datos de prueba usando matemáticas

Si se presume que las ubicaciones de coincidencia están distribuidas uniformemente y las palabras de la lista de palabras tienen la misma tasa de aparición, los datos de prueba se pueden simplificar para:

  1. un texto sin coincidencia y sin muchas palabras que comienzan como palabras de la lista de palabras (la entrada “mejor típica”)
  2. un texto sin coincidencia, pero completamente de palabras que comienzan de la misma manera que las palabras de la lista de palabras, las “cabezas” se distribuyen de manera más o menos uniforme a través de la lista de palabras (la entrada “peor” para ambos métodos: ver 1) si puede haber fallas catastróficas en la producción; 2) ¿En qué medida estos casos sesgarán el resultado final?
  3. un texto con una coincidencia a mitad de camino, donde ubicar la palabra en la lista de palabras requiere aproximadamente la mitad del trabajo, tanto del texto como de la expresión regular, y sin muchas otras palabras que comienzan como palabras de la lista de palabras

Luego, el tiempo “promedio esperado” final:

 Txa = (Tn+(Ts-Tn)*Ps)*Pn + (Tm+((Ts-Tm)*Ps)/2)*Pm 

donde T – tiempos, P – probabilidades esperadas; n – de entrada sin coincidencia, s – (lento) de palabras que comienzan como las de la lista de palabras, m – de entrada con coincidencia.