在上一篇文章《那么，屏蔽词系统到底该怎么做？》中，我简单讲了一下屏蔽词系统的实现思路。这篇就讲一讲另一个类似的话题，那就是如何实现高效的 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 的评论也没有评测数据验证，只是希望对读者能够有些用处。此外，也欢迎大家用更好的算法来打脸。