Base de datos o estructura adecuada para hacer coincidir cadenas con patrones de expresiones regulares

Question

Tengo una serie de patrones de expresiones regulares. Cuando se ingresa una cadena, tengo que encontrar que todos los patrones coinciden con esta cadena. Esto es normalmente una operación O (n):

SELECT regex FROM regexes WHERE 'string' RLIKE regex 

¿Cuál es la manera más rápida de hacer esto? ¿Hay estructuras de bases de datos o sistemas de almacenamiento que estén optimizados para realizar tal operación?

Answer 1

La respuesta corta es 'No.' No existe actualmente ninguna estructura de índice disponible en ninguna plataforma DBMS que indexe las coincidencias parciales de una expresión regular como esta.

La respuesta larga es que una constante inicial en una coincidencia de comodín (por ejemplo, 'foo_') se puede usar como un prefijo para las coincidencias de índice. Muchas plataformas DBMS optimizarán esto y usarán un índice (si está disponible) para resolver el prefijo. Sin embargo, esto no es nada tan inteligente como una expresión regular completa, y la indexación solo se puede usar si tienes un prefijo constante.

La respuesta incluso más larga es que hay algoritmos como RETE que optimizarán las coincidencias parciales como esta. Esto podría aplicarse si puede expresar sus coincidencias como reglas de producción de encadenamiento directo en lugar de expresiones regulares.

Rete funciona al calcular las coincidencias parciales y solo presenta las reglas que se pueden alcanzar con esta coincidencia parcial, por lo que es más eficiente que O (n) (más como O (log n) pero no estoy seguro de la complejidad de tiempo) para emparejar n reglas contra un hecho.

Answer 2

Una optimización que podría poner en práctica, si es aplicable a su caso, sería la de clasificar sus expresiones regulares y organizarlas en jerarquías de modo que:

• es suficiente para probar un puñado de expresiones regulares más general.

• para cualquier expresión regular que coincida, luego proceda a probar la cadena contra todas las expresiones regulares de la misma categoría solamente.

Por ejemplo, si sus cadenas de entrada pueden ser cualquier cosa arbitrariamente compleja y tiene miles de expresiones regulares, puede organizarlos en categorías como:

• la categoría \d+, que pondría a prueba los patrones numéricos (SSN, números de teléfono, etc)

• la categoría <.*?>, lo que prueba la presencia de etiquetas HTML

• la categoría \w+@\w+, lo que podría probar la presencia de mensajes de correo electrónico direcciones

etc.

Si cualquier patrón de raíz no coincide, entonces se evita tener que probar todo rangos de patrones que fallen todos modos .

No sé si eso coincidiría con su dominio exacto, pero es una posible optimización.