备选本地过滤引擎
AdBlock
AdBlock 目前主流支持easylist规则，基本格式是 filter$options 这种语法。
规则匹配引擎，要解决的问题主要是在海量规则中判断是否命中的问题。如果用正则或者遍历，消耗过大，一般采取的都是先把规则依据某种判据先分成小类别，匹配时先找到对应的小类别，然后在小类别中遍历规则完成匹配。
下面从分类方法、存储方法、匹配方法简述几种匹配引擎的实现。
Brave AdBlock c++ 实现
Brave AdBlock c++ 使用的分类方法是：
- 计算阶段，用规则的filter部分，去掉特殊字符之后, 用指定长度算出一个key，插入到布隆过滤器中,插入前会先过一个坏key的大表（坏key可以认为是人工过了线上的top站点得出的冲突率最高的key）
- 如果不是坏key则插入布隆过滤器，如果是坏key，则插入人工分类的几个集合中(例如根据规则是否限制域名，是否限制域名取反等特性分类），并通过hashset查询，hashset中使用规则的host或者filter部分计算key
- 匹配阶段，先计算目标url所在的domain是否存在于几个hashset中，如果存在则在对应的规则集合中遍历；如果都不存在，则通过url算出所有可能的key，例如固定长度是7，就用url中的连续字符每7个字符算一个key，在布隆过滤器中匹配，如果不命中，则说明命中不了规则，如果命中则在剩余规则中遍历。
- 规则的序列化和反序列化使用brave实现的格式，加载时需要简单解析一下内容，然后用指针指向对应内存，反序列化文件mmap之后不能释放。
Brave Adblock Rust实现
- 计算阶段，首先规则的filter 部分，用规则包含的特殊字符（除了子母和数字之外的字符)将规则切分成多个token，这里需要注意的是，如果一个规则中间有通配符，则包含通配符的部分不能作为token，如www.ba*du.com，计算出来的token是 {www,com}，ba和du因为包含通配符，如果作为token，在这个引擎的实现中，匹配时是无法处理的。
- 准备将token作为当前规则的索引插入hashmap中，首先计算现存所有规则的token对应的map中，当前规则的token中出现次数最少的那个token，即最能独立代表当前规则的token，然后用这个token作为当前规则的key，插入hashmap
- 匹配阶段，用上文计算过程中相同的分割规则，将目标url切分成对等的token，找到对应规则所在的所有小集合，遍历集合中的规则进行过滤。
- 存储，还没看
Chromium Subresource Filter实现
Subresource Filter是chromium 7x版本开始自己实现的规则引擎，目前还在测试阶段未正式上线，可以为浏览器插件提供支持easylist语法的引擎（官方逼死同人系列）。 - 计算阶段，处理规则的filter，chromium的实现是把规则中除了通配符()和分隔符（^)之外的字符，用固定长度计算key，如果不到固定长度则忽略。例如 www.badu.com 这个规则中，用chromium的方法计算key用的原始字符（假设长度是5)，就是{www.b , ww.ba, du.co, u.com},这种集合
- 计算key之后，插入hashmap时，寻找所有的key中，桶中元素最少的，类似brave的rust实现
- 匹配阶段，首先对url也用固定长度算key，能算出很多个，然后每个key在hashmap中寻找对应规则所在的集合，遍历集合中的规则进行过滤。
- 存储阶段，chromium使用了自家的FlatBuffer，可以不经过反序列化，mmap之后直接使用，效率极高。
看起来brave c++的实现在三者中最差，chromium的有可能略好于brave rust的实现，因为可以在算key时利用上规则里，通配符两边的字符，感觉上找到规则的准确率会提高。
性能对比
过滤引擎性能对比测试结论，brave rust略优于chromium实现，都远好于brave c++实现。