这是一个创建于 1998 天前的主题，其中的信息可能已经有所发展或是发生改变。
白名单是个正则表达式列表(大概有 2000 个)：
例如：
(^|\.)abc\.baidu\.com$
(^|\.)123\.baidu\.com$
...
然后浏览器发起了个请求：666.baidu.com ，怎么能快速计算出白名单是否包含这个域名？
有什么比较好的算法吗?
例如：
(^|\.)abc\.baidu\.com$
(^|\.)123\.baidu\.com$
...
然后浏览器发起了个请求：666.baidu.com ，怎么能快速计算出白名单是否包含这个域名？
有什么比较好的算法吗?
第 1 条附言 · 2019-06-06 16:37:48 +08:00
可能有些误解
1.对多个域名匹配
2.可能有二级域名，也可能没有
1.对多个域名匹配
2.可能有二级域名，也可能没有
 |
1
azh7138m 2019-06-06 16:26:15 +08:00  1
域名一级的匹配的话，就是不存在 prefix([^.]+).domain 的格式的话，用前缀树会不会快点，一次匹配一级域名。
我的 uBlock Origin 有 16+w 过滤规则，感觉也不慢，真的量大可以参考下他的算法？ Trie 比正则性能是翻倍了 https://raw.githack.com/gorhill/uBlock/master/docs/tests/hnset-benchmark.html |
 |
2
senghoo 2019-06-06 16:33:59 +08:00
构建个 dfa
|
|
3
azh7138m 2019-06-06 16:55:28 +08:00 1
我的意思是每个节点放一级域名
com - baidu - wiki - true |- tieba - false 任意级啊，前缀树也没要求你固定级别 |
 |
5
john990 OP |
Select Language