如何实现高效的 URL 过滤算法

目录 算法

在上一篇文章《那么,屏蔽词系统到底该怎么做?》中,我简单讲了一下屏蔽词系统的实现思路。这篇就讲一讲另一个类似的话题,那就是如何实现高效的 URL 过滤算法。

通过某些字面特征,筛选出符合条件的 URL,对其执行特定的操作。虽然看起来像是很遥远专业的技术,但其实早就根植在你手机里的各类浏览器相关 app,以及你使用的各类互联网服务中了。举一个最简单的例子:你在微信里打开淘宝链接,背后就是一个 URL 过滤算法的实现。

还有,很多浏览器 APP 设置项里有一个开关,叫做“广告过滤”,其中很大一部分也是通过 URL 过滤实现的。那如何做到高效的 URL 过滤呢

如果拿这个问题来面试,大概率候选人会回答用正则表达式实现。其实这一点不令人惊讶,因为我曾经亲眼见过一个日活惊人的 APP 也是用正则表达式做的(真不敢相信自己的眼睛)。用正则表达式本身来实现 URL 匹配不是很大的问题,但在“广告过滤”这样的场合,意味着有成千上万的 URL 规则,很难有人能用这些规则写出来高效的正则表达式

关于这点,展开说一下。理论上来讲,把所有 URL 规则融合到一条正则表达式里,也不是不可能。比如:"http[s]{0,1}://..{0,1}(taobao|tmall).com/.",可以融合两条淘宝和天猫的 url 规则。但如果让你融合一千个不同的 url 规则到一条正则表达式里,我想很难有人有信心把它完全做对,更不敢保证后续维护这个规则库的人能做对。所以很多情况下,他们只是用几千个正则表达式实现了几千条 url 规则,想想这个匹配效率有多低!!

所以,真正在乎 URL 匹配效率的人,不会使用正则表达式。举个最典型的例子,Adblock Plus 的过滤规则(https://adblockplus.org/filters),是完全自定义了一套匹配规则。不过,Adblock Plus 在早期也是用正则表达式,而且完全就是我上面讲的那种用法,不过后来他们改进了,还专门发了篇博客(https://adblockplus.org/blog/investigating-filter-matching-algorithms , 注意里面也用到了我上篇文章提到到 Rabin-Karp )。

可是在我看来,Adblock Plus 的实现只是够用,却还不够高效。我上一篇文章提到的 Trie 树,更合适做这种事情,可能也更高效(未比较),至少更简洁。Adblock 最核心的地方,是 URL 匹配。从 Adblock Plus 定义的规则也能看出,URL 匹配其实比正则表达式匹配简单很多,无非是在普通字符串匹配之上加了一些通配符而已。

那以 Adblock Plus 的通配符为例,我来讲一下如何用 Trie 树来实现含通配符的字符串匹配

  • "*" 通配符匹配任意长的字符串
    • 包含匹配时模式串前后的 "*" 没有意义,可以直接丢掉;
    • 以中间的 "*" 做划分,原串 * 位置后面的部分进行递归子树匹配;
  • "|" 匹配网址开头结尾:对 url 预处理,扔掉 scheme 部分 "http://",头尾都加上 "|",这样自然就能匹配上模式串中的 "|" 了。
  • "^" 标记分隔符:这就更简单了,遇到 ^ 规则时,不是比较原串中字符是否与其相等,而是是否包含在某个符号表中即可。

在这些匹配规则的基础上,结合 Double Array Trie 数据结构,可以实现一个内存占用超级小但效率又非常高的 URL 过滤器了。而且 Trie 树的结构对规则的条数非常不敏感,耗时并不会随着过滤规则的增多而显著增加。

不过还得多说一句,算法是效率核心,但真正解决问题还得花很多心思在算法外。比如例外规则,规则库的动态更新等等,这里就不继续展开了。

以上只是本人的一点拙见,对 Adblock Plus 的评论也没有评测数据验证,只是希望对读者能够有些用处。此外,也欢迎大家用更好的算法来打脸

长按识别二维码关注《边际效应》
长按识别二维码关注《边际效应》

暂无评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注