Consulta eficiente de una cadena contra expresiones múltiples

Question

Digamos que tengo 10.000 expresiones regulares y una cadena y quiero averiguar si la cadena coincide con cualquiera de ellas y obtener todas las coincidencias. La manera trivial de hacerlo sería simplemente consultar la cadena una por una contra todas las expresiones regulares. ¿Hay una manera más rápida y más eficiente de hacerlo?

EDIT: He intentado sustituirlo con 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.

Answer 1

Martin Sulzmann Ha hecho bastante trabajo en este campo. Tiene a HackageDB project explicó breifly here que utiliza partial derivatives 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 FP 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.

También 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.

---

1. esto es una broma - me gustan los profesores, menos los más inteligentes tratan de trabajar, más posibilidades tengo de que me paguen!

Answer 2

¿Intenta combinarlos en una gran expresión regular?

Answer 3

Tendría que tener alguna forma 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

Answer 4

Casi me gustaría escribir un motor de expresiones regulares "de adentro hacia afuera", uno donde el "objetivo" fuera la expresión regular , y el 'término' fue la cadena.

Sin embargo, parece que su solución de probar cada uno de forma iterativa va a ser mucho más fácil.

Answer 5

Se puede combinar en grupos de tal 20.

(?=(regex1)?)(?=(regex2)?)(?=(regex3)?)...(?=(regex20)?) 

Mientras cada expresión regular tiene cero (o al menos el mismo número de) los grupos de captura, se puede ver lo que lo capturado para ver qué patrón (s) emparejado.

Si regex1 coincide, el grupo de captura 1 tendrá su texto coincidente. Si no, sería undefined/None/null/...

Answer 6

10,000 regexen eh? Eric Wendelin's sugerencia 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 ejemplo simple: todos los regexen que requieren un número podrían derivarse de una comprobación de expresiones regulares para tal, todos 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 la descomposición de 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 (más fáciles de hacer) o géneros comparativos generados en ese momento (no tan fácil de hacer).

Su solución de comparación de "hello" a "[H | h] ello" y ". {0,20} ello" realmente no será 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.

Answer 7

Creo que la respuesta corta es que sí, hay una manera de hacer esto, 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 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.

Answer 8

Tuvimos que hacer esto en un producto en el que trabajé una vez. La respuesta fue compilar todas sus expresiones regulares juntas en un Deterministic Finite State Machine (también conocido como autómata finito determinista o DFA). El DFA luego se puede recorrer carácter por carácter sobre su cadena y se activará un evento de "coincidencia" cuando una de las expresiones coincida.

Ventajas se ejecuta rápido (cada carácter se compara solo una vez) y no se vuelve más lento si se agregan más expresiones.

Desventajas son que requiere una enorme mesa de datos para el autómata, y hay muchos tipos de expresiones regulares que no son compatibles (por ejemplo, copias de referencias).

La que usamos fue codificada a mano por una tuerca 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á cosas que lo orientarán en la dirección correcta.

Answer 9

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.

Existen muchas herramientas que pueden ayudarlo aquí, se llaman "generador de lexer" y existen soluciones que funcionan con la mayoría de los idiomas.

No dice qué idioma está utilizando. Para los programadores de C sugeriría echar un vistazo a la herramienta re2c. Por supuesto, el tradicional (f)lex es siempre una opción.

Answer 10

Si está utilizando expresiones regulares reales (las que corresponden a los lenguajes normales 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 que debe ser capaz de construir una cadena (que representa la expresión regular que desee) de la siguiente manera:

(r1)|(r2)|(r3)|...|(r10000) 

en paréntesis son para la agrupación, que no coincida. Cualquier cosa que coincida con esta expresión regular coincide con al menos una de sus expresiones regulares originales.

Answer 11

Yo diría que es un trabajo para un analizador real. Un punto medio podría ser un Parsing Expression Grammar (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: la única que conozco es LPEG, una biblioteca para Lua, y no fue fácil (para mí) comprender los conceptos básicos.

Answer 12

Puede compilar la expresión regular en un DFA/Bucchi automata híbrido, donde cada vez que BA entra en un estado de aceptación marca qué regla de expresiones regulares "acertar".

Bucchi es un poco excesivo para esto, pero modificar la forma en que funciona su DFA podría hacer el truco.

Answer 13

Me he encontrado con un problema similar en el pasado. Usé una solución similar a the one suggested by akdom.

Tuve la suerte de que mis expresiones regulares generalmente tenían alguna 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 on Google code hosting.

Answer 14

Si está pensando en términos de "10.000 expresiones regulares", debe 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.

Answer 15

La forma más rápida de hacerlo parece ser algo como esto (código 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; 
} 

Oh, que significó el código más rápido ? no sé entonces ....

Answer 16

Aho-Corasick fue la respuesta para mí.

Tenía 2000 categorías de cosas 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 idiomas, no los patrones regex, p. 'cat' contra r'\w+'.

Yo estaba usando python y así 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 

Correr %timeit test() en mis categorías 2000 con 2-3 rastros por categoría y una longitud de alrededor de _string100,000 me tiene 2.09 ms vs 631 ms haciendo secuencial re.search()315x más rápido!.