algorithme de correspondance de chaîne rapide avec support simple, wildcards

Question

Je dois correspondre à des chaînes d'entrée (URL) contre un grand nombre (allant de 1k-250k) des règles de chaîne avec le soutien générique simple.

Exigences pour le support générique sont les suivantes:

Wildcard (*) ne peut remplacer une "partie" d'une URL. C'est des fragments d'un domaine, le chemin et les paramètres. Par exemple, "* .part.part / * / partie? Partie = partie et partie = *". La seule exception à cette règle est dans la zone de chemin où « / * » devrait correspondre à quelque chose après la barre oblique.

Exemples:

.
• * site.com/* - doit correspondre sub.site.com/home.html, sub2.site.com/path/home.html
• sub.site * / chemin / * -. Sub.site.com/path/home.html doit correspondre, sub.site.net/path/home.html, mais pas sub.site.com/home. html

Exigences supplémentaires:

• recherche rapide (je me rends compte "rapide" est un terme relatif. Compte tenu des règles de 250k max, relèvent toujours <1.5s si possible .)
• Les travaux dans le cadre d'un bureau moderne (par exemple pas une implémentation du serveur)
• Possibilité de revenir 0: n matchs d'une chaîne d'entrée
• Matches auront des données de règles qui leur sont rattachés

Quel est le meilleur système / algorithme pour, comme tâche? Je développerons la solution en C ++ avec les règles elles-mêmes stockées dans une base de données SQLite.

Answer 1

Si je ne me trompe pas, vous pouvez prendre la règle de chaîne et le diviser en domaine, chemin, et des morceaux de requête, tout comme il est une URL. Ensuite, vous pouvez appliquer une norme algorithme de correspondance générique avec chacune de ces pièces contre les pièces correspondantes des URL que vous souhaitez tester contre. Si toutes les pièces correspondent, la règle est un match.

Exemple

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

Comme vous stockez les règles dans une base de données, je les stocker déjà brisés dans ces trois pièces. Et si vous voulez uber-vitesse vous pouvez convertir de s à * la % puis utilisez le fonctionnement natif de la LIKE base de données pour faire la mise en correspondance pour vous. Ensuite, vous auriez tout simplement avoir une requête comme

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

où @urlDomain, @urlPath et sont variables dans @urlQuery une déclaration préparée. La requête retournerait les règles qui correspondent à une URL, ou un jeu de résultats vide si rien ne correspond.

Answer 2

Tout d'abord, l'un des moins performants des recherches que vous pouvez faire est avec un joker aux deux extrémités de la chaîne « .domaine.com / path » - et je pense que vous allez de frapper ce cas beaucoup. Ma première recommandation est d'inverser l'ordre des domaines comme ils sont stockés dans votre DB: com.domain.example / chemin1 / chemin2 / page.html. Cela vous permettra de garder les choses beaucoup plus propre et d'utiliser uniquement jokers dans « une direction » sur la chaîne, qui fournira beaucoup plus rapide lookups.

Je pense que John mentionne quelques bons points sur la façon de le faire tout dans votre base de données. Si cela ne fonctionne pas, j'utiliser une bibliothèque regex en C ++ contre la liste. Je parie que vous obtiendrez les meilleures performances et la syntaxe des expressions régulières le plus général de cette façon.