¿Cómo hacer coincidir eficientemente una cadena de entrada con varias expresiones regulares a la vez?

Question

¿Cómo podría uno eficientemente hacer coincidir una cadena de entrada con cualquier cantidad de expresiones regulares?

Un escenario donde esto podría ser útil es con los servicios web REST. Vamos a suponer que he llegado con una serie de patrones de URL para la interfaz pública de un servicio web REST:

• /user/with-id/{userId}
• /user/with-id/{userId}/profile
• /user/with-id/{userId}/preferences
• /users
• /users/who-signed-up-on/{date}
• /users/who-signed-up-between/{fromDate}/and/{toDate}
• ...

donde {…} se denominan marcadores de posición (como grupos de captura de la expresión regulares).

_{Nota: Esta pregunta no es si la interfaz REST anterior está bien diseñado o no. (Probablemente no es, pero eso no debería importar en el contexto de esta pregunta.)}

Se puede suponer que los marcadores de posición por lo general no aparecen en el comienzo de un patrón (pero podrían) También se puede suponer con seguridad que es imposible que una cadena concuerde con más de un patrón.

Ahora el servicio web recibe una solicitud. Por supuesto, uno podría hacer coincidir secuencialmente el URI solicitado con un patrón de URL, luego con el siguiente, y así sucesivamente; pero eso probablemente no se escalará bien para un mayor número de patrones que deben verificarse.

¿Existen algoritmos eficientes para esto?

Entradas:

• una cadena de entrada
• un conjunto de expresiones regulares "mutuamente excluyentes" (es decir, sin cadena de entrada puede coincidir con más de una expresión.)

de salida :

• La expresión regular (si existe) con la que coincide la cadena de entrada.

Answer 1

El Aho-Corasick algorithm es un algoritmo muy rápido para hacer coincidir una cadena de entrada con un conjunto de patrones (en realidad, palabras clave), que están preprocesados ​​y organizados en un trie, para acelerar la coincidencia.

Existen variaciones del algoritmo para admitir patrones de expresiones regulares (es decir, http://code.google.com/p/esmre/ solo para nombrar uno) que probablemente valen la pena ver.

O bien, podría dividir las urls en trozos, organizarlas en un árbol, luego dividir la url para que coincida y caminar el árbol un pedazo a la vez. El {userId} puede considerarse un comodín o coincidir con un formato específico (es decir, ser un int).

Al llegar a una hoja, usted sabe qué URL emparejado

Answer 2

Use expresiones con nombre y el operador OR, es decir "(?P<re1>...)|(?P<re2>...)|...".

Answer 3

Si hay una jerarquía en la estructura de la url, debería utilizarse para maximizar el rendimiento. Solo una URL que comienza con/usuario/puede coincidir con cualquiera de los tres primeros, y así sucesivamente.

Sugiero almacenar la jerarquía para que coincida en un árbol correspondiente a la jerarquía de la url, donde cada nodo coincide con un nivel en la jerarquía. Para hacer coincidir una url, pruebe la url contra todas las raíces del árbol donde solo hay nodos con expresiones regulares para "usuario" y "usuarios". Las URL coincidentes se prueban contra los hijos de esos nodos hasta que se encuentra una coincidencia en un nodo de hoja. Se puede devolver una coincidencia exitosa como la lista de nodos desde la raíz hasta la hoja. Los grupos con nombre con valores de propiedad, como {user-id}, se pueden obtener de los nodos de la coincidencia exitosa.

Answer 4

Primero pensé que no pude ver ninguna buena optimización para este proceso.

Sin embargo, si tiene una gran cantidad de expresiones regulares, es posible que desee dividirlas (no estoy seguro de si esto es una partición técnica).

Lo que os digo que hacer es:

suponga que tiene 20 posibles direcciones URL que comienzan con user:

/user/with-id/X 
/user/with-id/X/preferences # instead of preferences, you could have another 10 possibilities like /friends, /history, etc 

Entonces, también hay 20 posibles direcciones URL a partir de users:

/users/who-signed-up-on 
/users/who-signed-up-on-between  #others: /registered-for, /i-might-like, etc 

Y la lista continúa para /products, /companies, etc. en lugar de usuarios.

Lo que podría hacer en este caso es usar "multi-level" matching.

Primero, haga coincidir el comienzo de la cadena. Debería coincidir con /products, /companies, /users, uno a la vez e ignorar el resto de la cadena. De esta manera, no tienes que probar todas las 100 posibilidades.

Después de saber que la url comienza con /users, puede hacer coincidir solo las URL posibles que comienzan con los usuarios.

De esta manera, reduciría una gran cantidad de coincidencias innecesarias. No coincidirá con la cadena para todas las posibilidades de /procucts.

Answer 5

La solución estándar para hacer coincidir múltiples expresiones regulares contra un flujo de entrada es un lexer-generator como Flex (hay un montón de estos avalable, por lo general varios para cada uno lengua de programación).

Estas herramientas toman un conjunto de expresiones regulares asociadas con "tokens" (piense en tokens como nombres para cualquier expresión regular que coincida) y genera eficiente autómata de estado finito para hacer coincidir todas las expresiones regulares al mismo tiempo. Este es un tiempo lineal con una constante muy pequeña en el tamaño de la corriente de entrada; difícil de pedir "más rápido" que esto. Le das un flujo de caracteres y emite el nombre del token de la expresión regular que coincide con "mejor" (esto maneja el caso donde dos expresiones regulares pueden coincidir con la misma cadena, vea el generador lexer para la definición de esto) y avanza la secuencia por lo que fue reconocido. Entonces puede aplicarlo una y otra vez para que coincida con el flujo de entrada de una serie de tokens.

Diferentes generadores lexer le permitirán capturar diferentes bits de la secuencia reconocida de diferentes maneras, para que pueda, después de reconocer un token, seleccionar la parte que le interesa (por ejemplo, para una cadena literal entre comillas, solo se preocupan por el contenido de la cadena, no por las comillas).