如何实现高效的 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 的评论也没有评测数据验证,只是希望对读者能够有些用处。此外,也欢迎大家用更好的算法来打脸

那么,屏蔽词系统到底该怎么做?

目录 算法

caoz 在最近一篇公众号文章《企业面试需要几轮》中提到一个面试问题:

大家都知道做互联网有很多屏蔽词要处理,那么需要对用户发布的内容,做屏蔽词过滤,先不考虑一些正则组合的情况,假设我有一个屏蔽词库,里面有几万条屏蔽词信息,然后我有个非常火爆的社区,每天用户产生海量内容,比如上百万篇文章或评论,现在我要求每篇文章都能快速通过屏蔽词库去检索,而且要求服务器可以支撑尽可能多的处理请求,毕竟这是成本啊。那么请设计一个屏蔽词过滤的算法逻辑。

碰巧我在面试中也喜欢问这个问题,可惜的是能答上来的的确不多。

单单从算法层面论,大概有 50% 的人能回答出来逐个进行 KMP 匹配(另外 50% 不知道什么是 KMP)。让他更进一步优化的话,20% 的人能想到一些粗糙的优化技巧,10% 的人能说出前缀树匹配。大部分能答出前缀树匹配的人会提到 AC 自动机,但只有一半能大概答出 AC 自动机的大概算法。到目前为止,还没有人回答过其它算法,比如 Rabin-Karp 或者 Commentz-Walter。

即使在算法层面上能回答出来 AC 自动机,在实现上候选人也只能形象地描述一下 Trie 树和失败指针,Trie 树的每一层使用一个 Set 或者哈希表数据结构。到目前为止,还没有人回答过用 Double Array 来实现 Trie,甚至连用前缀做 key 的一个大哈希表来模拟 Trie 树的优化也没有。虽然构造 Double Array Trie 的代价非常高,但内存占用非常小,检索效率也很高,特别适用于屏蔽词的场合。离线建好 Double Array Trie,推送到线上仅仅需要读入两个内存块就能完成更新,加载过程到了极简。

哪怕是回答出了高效的算法和实现,离一个真正有效的屏蔽词系统还相差很远。首先要清楚一件事,道高一尺,魔高一丈。你平时想过什么办法绕过屏蔽词系统,现在就得想办法对抗你曾经开过的脑洞。下面举几个最常见的例子:

  1. 简繁体混用,大小写混用,全半角混用。首先得做归一化,繁体转简体,大写转小写,全角转半角。
  2. 在屏蔽词中间加特殊字符。原串先过一遍,去掉特殊字符再过一遍。
  3. 字形相近,读音相似。积累相近字典,替换为常用字再过一遍,将所有的字转为拼音再过一遍。
  4. 同义词替换。加屏蔽词时考虑替换场景,或者挖掘替换词库用来替代。

上面这几种方法,说起来简单,做起来都是坑。一不小心,就把正常的内容当成包含屏蔽词干掉了。这就是为啥大家老吐槽在某些网站发帖,动不动就被屏蔽,关键就在于坏招太多,规则多了就有误伤啊!所以一个优秀的屏蔽词系统,还得尽量避免误伤情况,也有一些办法。

  • 先切词,如果命中屏蔽词的范围不在切词的边缘,应该是误伤。最简单的例子是:24口交换机。
  • 添加屏蔽词的例外规则,比如“成人牙刷”需要是“成人”的例外规则。

最近几年机器学习特别火,其实机器学习也特别适合这种场景,就是一个二分类问题嘛。只是超出了简单算法的范畴,这里就不展开了。

所以你看,就一个“屏蔽词过滤的算法逻辑”,就有那么多要探讨的东西。而且以目前国内大部分互联网产品的实现上来看,可能考虑的还没我这篇文章全面。这可真不是一个能轻松就回答完美的问题。