支持简单通配符的快速字符串匹配算法

如果我没弄错的话,您可以将字符串规则分解为域、路径和查询片段,就像它是一个URL一样。然后你可以应用一个标准 wildcard matching algorithm 其中的每一个片段都对应于您要测试的URL中的相应片段。如果所有的棋子都匹配,规则就是匹配。

例子

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

当您将规则存储在数据库中时,我会将它们存储到已经分成三部分的数据库中。如果你想要超高速,你可以转换 * 对… % ,然后使用数据库的本机 LIKE 为您进行匹配的操作。那么你只需要一个类似

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

哪里 @urlDomain , @urlPath 和 @urlQuery 是准备好的语句中的变量。查询将返回与URL匹配的规则,如果没有匹配的结果,则返回空结果集。

首先,最糟糕的搜索是在字符串的两端使用通配符。” .domain.com/路径 “——我认为你会经常碰到这个案子。所以我的第一个建议是颠倒域存储在db:com.domain.example/path1/path2/page.html中的顺序。这将使您能够使事情更加整洁,并且只在字符串的“单向”中使用通配符,这将提供更快的查找速度。

我认为约翰提到了一些关于如何在数据库中实现这一切的好点。如果这不起作用,我会使用C++中的正则表达式库来对付这个列表。我敢打赌你会得到最好的性能和最通用的regex语法。