Algoritmo rápido de coincidencia de cadenas con soporte de comodines simples

Question

Necesito hacer coincidir cadenas de entrada (URL) con un conjunto grande (entre 1k y 250k) de reglas de cadenas con soporte de comodín simple.

Los requisitos para la compatibilidad con comodines son los siguientes:

El comodín (*) solo puede sustituir una "parte" de una URL.Es decir, fragmentos de un dominio, ruta y parámetros.Por ejemplo, "*.part.part/*/part?part=part&part=*".La única excepción a esta regla es en el área de ruta donde "/*" debe coincidir con cualquier valor después de la barra.

Ejemplos:

• *.site.com/* -- debe coincidir con sub.site.com/home.html, sub2.site.com/path/home.html
• sub.site.*/path/*: debe coincidir con sub.site.com/path/home.html, sub.site.net/path/home.html, pero no con sub.site.com/home.html

Requerimientos adicionales:

• Búsqueda rápida (me doy cuenta de que "rápido" es un término relativo.Dadas las reglas máximas de 250 000, aún queda dentro de < 1,5 s si es posible.)
• Trabaje dentro del alcance de un escritorio moderno (p. ej.no es una implementación de servidor)
• Capacidad de devolver coincidencias 0:n dada una cadena de entrada
• Las partidas tendrán datos de reglas adjuntos.

¿Cuál es el mejor sistema/algoritmo para tal tarea?Desarrollaré la solución en C++ con las reglas almacenadas en una base de datos SQLite.

Answer 1

Si no me equivoco, puede tomar la regla de cadena y dividirla en dominio, ruta y consulta, tal como si fuera una URL.Entonces puedes aplicar un estándar. algoritmo de coincidencia de comodines con cada una de esas piezas contra las piezas correspondientes de las URL con las que desea realizar la prueba.Si todas las piezas coinciden, la regla es coincidencia.

Ejemplo

Rule: *.site.com/*
    domain => *.site.com
    path   => /*
    query  => [empty]

URL: sub.site.com/path/home.html
    domain => sub.site.com
    path   => /path/home.html
    query  => [empty]

Matching process:
    domain => *.site.com matches sub.site.com?     YES
    path   => /*         matches /path/home.html?  YES
    query  => [empty]    matches [empty]           YES

Result: MATCH

Como almacena las reglas en una base de datos, yo las almacenaría ya divididas en esas tres partes.Y si quieres súper velocidad, puedes convertir el *es para %'s y luego usar el nativo de la base de datos LIKE Operación para hacer la coincidencia por usted.Entonces solo tendrías una consulta como

SELECT *
FROM   ruleTable
WHERE  @urlDomain LIKE ruleDomain
   AND @urlPath   LIKE rulePath
   AND @urlQuery  LIKE ruleQuery

dónde @urlDomain, @urlPath, y @urlQuery son variables en una declaración preparada.La consulta devolvería las reglas que coinciden con una URL o un conjunto de resultados vacío si no hay nada que coincida.

Answer 2

En primer lugar, una de las búsquedas con peor rendimiento que puede realizar es con un comodín en ambos extremos de la cadena ".dominio.com/ruta" -- y creo que vas a acertar mucho en este caso.Entonces, mi primera recomendación es invertir el orden de los dominios tal como están almacenados en su base de datos:com.dominio.ejemplo/ruta1/ruta2/página.html.Eso le permitirá mantener las cosas mucho más ordenadas y utilizar sólo comodines en "una dirección" en la cadena, lo que proporcionará búsquedas MUCHO más rápidas.

Creo que John menciona algunos buenos puntos sobre cómo hacer todo esto dentro de su base de datos.Si eso no funciona, usaría una biblioteca de expresiones regulares en C++ en la lista.Apuesto a que obtendrás el mejor rendimiento y la sintaxis de expresiones regulares más general de esa manera.