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

Question

我需要将输入字符串 (URL) 与一大组（1k-250k 之间的任何位置）字符串规则进行匹配，并提供简单的通配符支持。

通配符支持的要求如下：

通配符 (*) 只能替换 URL 的“部分”。这是域、路径和参数的片段。例如，“*.part.part/*/part?part=part&part=*”。此规则的唯一例外是在路径区域中，其中“/*”应匹配斜杠之后的任何内容。

例子：

• *.site.com/* -- 应匹配 sub.site.com/home.html、sub2.site.com/path/home.html
• sub.site.*/path/* -- 应匹配 sub.site.com/path/home.html、sub.site.net/path/home.html，但不匹配 sub.site.com/home.html

其他要求：

• 快速查找（我意识到“快速”是一个相对术语。考虑到最大 250k 规则，仍然落在 < 1.5 秒内 如果可能的话.)
• 在现代桌面范围内工作（例如不是服务器实现）
• 能够在给定输入字符串的情况下返回 0:n 匹配项
• 比赛将附加规则数据

对于此类任务来说，最好的系统/算法是什么？我将使用 C++ 开发解决方案，并将规则本身存储在 SQLite 数据库中。

Answer 1

如果我没记错的话，您可以采用字符串规则并将其分解为域、路径和查询部分，就像它是 URL 一样。然后你可以应用一个标准 通配符匹配算法 将其中的每一个片段与您要测试的 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 匹配的规则，如果没有匹配，则返回空结果集。

Answer 2

首先，性能最差的搜索之一是在字符串两端使用通配符“.domain.com/路径“——我认为你会经常打这个案子。因此，我的第一个建议是颠倒域存储在数据库中的顺序：com.domain.example/path1/path2/page.html。这将使您保持事物更加整洁，并且仅在字符串的“一个方向”上使用通配符，这将提供更快的查找速度。

我认为约翰提到了一些关于如何在数据库中完成这一切的好点。如果这不起作用，我会针对该列表使用 C++ 中的正则表达式库。我敢打赌，这样您将获得最佳性能和最通用的正则表达式语法。