2

我需要使用简单的通配符支持将输入字符串 (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.5s 内。）
  • 在现代桌面范围内工作（例如，不是服务器实现）
  • 给定输入字符串返回 0:n 匹配的能力
  • 比赛将附加规则数据

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

4

2 回答 2

2

首先，您可以执行的最差搜索之一是在字符串“ .domain.com/path ”的两端使用通配符——我认为您会经常遇到这种情况。所以我的第一个建议是颠倒存储在数据库中的域的顺序：com.domain.example/path1/path2/page.html。这将使您保持更整洁，并且仅在字符串的“一个方向”上使用通配符，这将提供更快的查找速度。

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

于 2009-07-02T05:52:18.280 回答
1

如果我没记错的话，您可以使用字符串规则并将其分解为域、路径和查询部分，就像它是一个 URL 一样。然后，您可以针对要测试的 URL 中的相应部分应用标准通配符匹配算法。如果所有的部分都匹配，则规则是匹配的。

例子

规则：*.site.com/*
    域 => *.site.com
    路径 => /*
    查询 => [空]

网址：sub.site.com/path/home.html
    域 => sub.site.com
    路径 => /path/home.html
    查询 => [空]

匹配过程：
    域 => *.site.com 匹配 sub.site.com？是的
    path => /* 匹配 /path/home.html? 是的
    查询 => [空] 匹配 [空] 是

结果：匹配

当您将规则存储在数据库中时，我会将它们存储为这三个部分。如果您想要超高速，您可以将*'s 转换为%'s，然后使用数据库的本机LIKE操作为您进行匹配。然后你就会有一个像这样的查询

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

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

于 2009-07-02T04:39:25.487 回答