regex - solo - Consultando eficientemente una cadena contra múltiples expresiones regulares
javascript regex test (16)
Digamos que tengo 10.000 expresiones regulares y una cadena y quiero averiguar si la cadena coincide con cualquiera de ellos y obtener todas las coincidencias. La forma trivial de hacerlo sería simplemente consultar la cadena uno por uno contra todas las expresiones regulares. ¿Hay una manera más rápida y más eficiente de hacerlo?
EDITAR: He intentado sustituirlo por DFA (lex). El problema aquí es que solo le daría un patrón único. Si tengo una cadena "hola" y los patrones "[H | h] ello" y ". {0,20} ello", DFA solo coincidirá con uno de ellos, pero quiero que ambos peguen.
Creo que la respuesta corta es que sí, que hay una forma de hacerlo, y que es bien conocida por la informática, y que no puedo recordar de qué se trata.
La respuesta corta es que puede encontrar que su intérprete de expresiones regulares ya se ocupa de todos estos de manera eficiente cuando están juntos, o puede encontrar uno que sí lo haga. De lo contrario, es hora de que google los algoritmos de búsqueda y coincidencia de cadenas.
Diría que es un trabajo para un analizador real. Un punto medio podría ser una gramática de expresión de análisis (PEG) . Es una abstracción de nivel superior de coincidencia de patrones, una característica es que puede definir una gramática completa en lugar de un patrón único. Existen algunas implementaciones de alto rendimiento que funcionan al compilar su gramática en un bytecode y ejecutarlo en una máquina virtual especializada.
descargo de responsabilidad: el único que conozco es LPEG , una biblioteca para Lua , y no fue fácil (para mí) comprender los conceptos básicos.
Esta es la manera en que trabajan los lexers.
Las expresiones regulares se convierten en un único autómata no determinista (NFA) y posiblemente se transforman en un autómata determinista (DFA).
El autómata resultante intentará hacer coincidir todas las expresiones regulares a la vez y tendrá éxito en una de ellas.
Hay muchas herramientas que pueden ayudarlo aquí, se les llama "generador de lexer" y hay soluciones que funcionan con la mayoría de los idiomas.
Usted no dice qué idioma está usando. Para los programadores de C, les sugiero echar un vistazo a la herramienta re2c . Por supuesto, la lex tradicional (f) siempre es una opción.
Si está utilizando expresiones regulares reales (las que corresponden a los lenguajes regulares de la teoría del lenguaje formal, y no a algo similar a Perl), entonces tiene suerte, porque los idiomas regulares se cierran bajo unión. En la mayoría de los idiomas regex, pipe (|) es union. Por lo tanto, debería poder construir una cadena (que represente la expresión regular que desee) de la siguiente manera:
(r1)|(r2)|(r3)|...|(r10000)
donde los paréntesis son para agrupar, no coincidentes. Cualquier cosa que coincida con esta expresión regular coincide con al menos una de sus expresiones regulares originales.
Casi me gustaría sugerir escribir un motor de expresiones regulares "de adentro hacia afuera", uno donde el "objetivo" era la expresión regular, y el "término" era la cadena.
Sin embargo, parece que su solución de probar cada uno de forma iterativa va a ser mucho más fácil.
Intenta combinarlos en una gran expresión regular.
Puedes combinarlos en grupos de tal vez 20.
(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?)
Siempre que cada expresión regular tenga cero (o al menos el mismo número de) grupos de captura, puede ver qué capturó para ver qué patrón (s) coinciden.
Si regex1 coincide, el grupo de captura 1 tendría su texto coincidente. Si no, sería undefined / None / null / ...
Tendría que tener alguna manera de determinar si una expresión regular dada era "aditiva" en comparación con otra. Crear una "jerarquía" de expresiones regulares que le permita determinar que todas las expresiones regulares de una determinada rama no coinciden
Tuvimos que hacer esto en un producto en el que trabajé una vez. La respuesta fue compilar todas sus expresiones regulares juntas en una máquina determinista de estados finitos (también conocida como autómata finito determinista o DFA ). El DFA podría ser caminado carácter por carácter sobre su cadena y dispararía un evento de "coincidencia" cada vez que una de las expresiones coincida.
Las ventajas son que se ejecuta rápidamente (cada personaje se compara solo una vez) y no se vuelve más lento si agrega más expresiones.
Las desventajas son que requiere una gran tabla de datos para el autómata, y hay muchos tipos de expresiones regulares que no son compatibles (por ejemplo, referencias retrospectivas).
El que usamos fue codificado a mano por una plantilla de plantilla de C ++ en nuestra compañía en ese momento, así que desafortunadamente no tengo ninguna solución de FOSS que lo dirija. Pero si busca expresiones regulares en Google o expresiones regulares con " DFA ", encontrará elementos que lo orientarán en la dirección correcta.
Si está pensando en términos de "10.000 expresiones regulares", necesita cambiar sus procesos. Si nada más, piense en términos de "10,000 cadenas de destino para que coincidan". Luego, busque métodos no regex diseñados para lidiar con situaciones de "carga de barco de cuerdas objetivo", como las máquinas Aho-Corasick. Francamente, sin embargo, parece que algunas cosas se salieron de los rieles mucho antes en el proceso que la máquina a usar, ya que 10,000 cadenas de destino suena mucho más como una búsqueda de base de datos que una coincidencia de cadena.
Martin Sulzmann ha hecho bastante trabajo en este campo. Tiene un proyecto de HackageDB explicado brevemente aquí, que utiliza derivados parciales parece estar hecho a medida para esto.
El lenguaje utilizado es Haskell y, por lo tanto, será muy difícil traducirlo a un lenguaje no funcional, si ese es el deseo (creo que la traducción a muchos otros lenguajes de PF todavía sería bastante difícil).
El código no se basa en convertir a una serie de autómatas y luego combinarlos, sino que se basa en la manipulación simbólica de las expresiones regulares.
Además, el código es muy experimental y Martin ya no es un profesor, sino que está en ''empleo remunerado'' (1), por lo que puede no estar interesado / no puede proporcionar ninguna ayuda o aporte.
- esto es una broma: me gustan los profesores, ¡mientras menos intenten trabajar los inteligentes, más posibilidades tengo de que me paguen!
La forma más rápida de hacerlo parece ser algo como esto (el código es C #):
public static List<Regex> FindAllMatches(string s, List<Regex> regexes)
{
List<Regex> matches = new List<Regex>();
foreach (Regex r in regexes)
{
if (r.IsMatch(string))
{
matches.Add(r);
}
}
return matches;
}
Ah, ¿te referías al código más rápido? No lo sé entonces ...
10.000 expresiones regex eh? La sugerencia de Eric Wendelin de una jerarquía parece ser una buena idea. ¿Has pensado en reducir la enormidad de estos regexen a algo así como una estructura de árbol?
Como un simple ejemplo: todos los regexen que requieran un número podrían derivarse de una verificación regex para tal, todos los regexen no requieren uno en otra rama. De esta forma, podría reducir el número de comparaciones reales a una ruta a lo largo del árbol en lugar de hacer cada comparación en 10,000.
Esto requeriría descomponer las expresiones regulares proporcionadas en géneros, teniendo cada género una prueba compartida que los descartaría si fallara. De esta forma, teóricamente podrías reducir drásticamente el número de comparaciones reales.
Si tuviera que hacer esto en tiempo de ejecución, podría analizar sus expresiones regulares y "archivarlas" en géneros predefinidos (los más fáciles de hacer) o géneros comparativos generados en ese momento (no tan fácil de hacer).
Su ejemplo de comparar "hello" con "[H | h] ello" y ". {0,20} ello" no será realmente ayudado por esta solución. Un caso simple en el que esto podría ser útil sería: si tuviera 1000 pruebas que solo devolverían verdadero si "ello" existe en alguna parte de la cadena y su cadena de prueba es "adiós"; solo tendrías que hacer una prueba en "ello" y saber que las 1000 pruebas que lo requieren no funcionarán, y debido a esto, no tendrás que hacerlas.
Me he encontrado con un problema similar en el pasado. Usé una solución similar a la sugerida por akdom .
Tuve la suerte de que mis expresiones regulares generalmente tenían una subcadena que debe aparecer en cada cadena que coincide. Pude extraer estas subcadenas usando un analizador simple e indexarlas en una FSA utilizando los algoritmos de Aho-Corasick. El índice se usó para eliminar rápidamente todas las expresiones regulares que trivialmente no coinciden con una cadena dada, dejando solo algunas expresiones regulares para verificar.
Lancé el código bajo LGPL como un módulo de Python / C. Ver esmre en el alojamiento de código de Google .
Aho-Corasick fue la respuesta para mí.
Tenía 2000 categorías de cosas en las que cada una tenía listas de patrones para hacer coincidir. La longitud de cadena promedió unos 100,000 caracteres.
Advertencia principal: los patrones que coinciden son todos los patrones de lenguaje, no los patrones de expresiones regulares, por ejemplo, ''cat'' vs r''/w+'' .
Estaba usando python y lo usé https://pypi.python.org/pypi/pyahocorasick/ .
import ahocorasick
A = ahocorasick.Automaton()
patterns = [
[[''cat'',''dog''],''mammals''],
[[''bass'',''tuna'',''trout''],''fish''],
[[''toad'',''crocodile''],''amphibians''],
]
for row in patterns:
vals = row[0]
for val in vals:
A.add_word(val, (row[1], val))
A.make_automaton()
_string = ''tom loves lions tigers cats and bass''
def test():
vals = []
for item in A.iter(_string):
vals.append(item)
return vals
Ejecutar %timeit test() en mis categorías de 2000 con aproximadamente 2-3 trazas por categoría y una longitud _string de aproximadamente 100,000 me consiguió 2.09 ms frente a 631 ms haciendo re.search() secuencial re.search() 315 veces más rápido! .