如何实现高效的 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口交换机。
  • 添加屏蔽词的例外规则,比如“成人牙刷”需要是“成人”的例外规则。

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

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

Caffe 神经网络配置 - All in one network

目录 算法

很多人使用 Caffe 配置神经网络的时候,习惯于撰写两个配置文件,一个叫 train_val.prototxt,在训练的时候使用;一个叫 deploy.prototxt,在预测的时候使用。这两个文件的本质区别,往往在输入、输出层不同。train_val.prototxt 里包含 train/test 的输入数据和标签,但出于效率考虑,train/test 都是分 batch 进行的,而输出的往往是 acc/loss;deploy.prototxt 里只包含 test 的输入,而且一般是每次输入一个数据(没有标签),输出的也不是 acc/loss,而是预测值(Top N 类别或者预测概率)。可以把 deploy.prototxt 看成可以往线上部署的网络配置文件,来一个用户请求,执行 network 的 forward,预测返回给用户结果。

这样做没什么不可以,而且很多开源的例子都是这么做的。但实际操作中,有一个很麻烦的地方是,当你在频繁调整模型的时候,每次修改隐层都要同时修改两个 .prototxt 让人很烦恼。Caffe 的配置文件不像 Keras 那样,每层就是简单的一行代码,而是一个 Protobuf 的 txt message,有很多行,这样电脑的一屏显示不全,就需要花精力去仔细 diff 两个文件。

其实我们有更好的办法,使用 Caffe 的 proto 协议实现 All in one network。那就是充分利用 NetStateRule 这个结构,结合 phase 和 stage/not_stage,实现不同场合下 layer 的过滤。

message NetStateRule {
  // Set phase to require the NetState have a particular phase (TRAIN or TEST)
  // to meet this rule.
  optional Phase phase = 1;

  // Set the minimum and/or maximum levels in which the layer should be used.
  // Leave undefined to meet the rule regardless of level.
  optional int32 min_level = 2;
  optional int32 max_level = 3;

  // Customizable sets of stages to include or exclude.
  // The net must have ALL of the specified stages and NONE of the specified
  // "not_stage"s to meet the rule.
  // (Use multiple NetStateRules to specify conjunctions of stages.)
  repeated string stage = 4;
  repeated string not_stage = 5;
}

以 Caffe 里的 example/minist/lenet_train_test.prototxt 为例 ,那怎么把它改成 all in one 的 prototxt 呢?

name: "LeNet"
layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TRAIN
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_train_lmdb"
    batch_size: 64
    backend: LMDB
  }
}
layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TEST
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_test_lmdb"
    batch_size: 100
    backend: LMDB
  }
}

首先,我们要明确解决的是 TEST phase 的冲突(验证集和测试集的 input/output 不同),不用去管 TRAIN phase。而为了解决 TEST phase 的冲突,就需要通过为 NetStateRule 增加参数来实现。min_level/max_level 和 stage/not_stage 都可以做这个事情,但我习惯用 stage,因为文字看起来比数字更直观一些。所以我会在原来的 train_val.prototxt 里再增加一个 TEST 输入层,通过 stage 区分不同的应用场景,如下所示:

layer {
  name: "mnist"
  type: "Data"
  top: "data"
  top: "label"
  include {
    phase: TEST
    not_stage: "predict"    # 在 predict 时过滤掉这一层
  }
  transform_param {
    scale: 0.00390625
  }
  data_param {
    source: "examples/mnist/mnist_test_lmdb"
    batch_size: 100
    backend: LMDB
  }
}
# 增加 deploy 的输入层
layer {
  name: "data"
  type: "Input"
  top: "data"
  input_param { shape: { dim: 1 dim: 1 dim: 28 dim: 28 } }
  include {
    phase: TEST
    stage: "predict"    # 在 predict 时加上这一层
  }
}

在 caffe.bin train 时,由于 solver.prototxt 没有提供特殊的参数,所以只包含 batch_size 100 的 TEST 输入层;在预测的时候,设置 stage='predict' 参数(设置方式下文有介绍),网络的输入层就变成了 dim: 1 的 TEST 输入层了。

同理,对输出层也是一样,在 loss layer 加上 exclude stage: "predict" 的参数,预测时就无需提供 label 和计算 loss 了,如下所示:

layer {
  name: "accuracy"
  type: "Accuracy"
  bottom: "ip2"
  bottom: "label"
  top: "accuracy"
  include {               #
    phase: TEST           #
    not_stage: "predict"  # 在 predict 时过滤掉 accuracy 层
  }                       #
}
layer {
  name: "loss"
  type: "SoftmaxWithLoss"
  bottom: "ip2"
  bottom: "label"
  top: "loss"
  exclude {           # 注意是 exclude
    phase: TEST       #
    stage: "predict"  # 在 predict 时过滤掉 loss 层
  }                   #
}

这样,你就能得到一个 all in one 的网络配置 lenet_train_val_deploy.prototxt,可以统一用它进行训练和预测,修改隐层再也不用拷贝来拷贝去了。其实使用 NetStateRule 可以进行各种组合,其它的参数组合也能实现 all in one 的网络设置,但我上面介绍的这种配置方法有个好处是完全不用修改原来的 solver.prototxt。也就是 default 走 non-predict,显式走 predict。

那怎样显式提供 stage='predict' 参数呢?在 caffe.bin 命令行可以使用:

$ caffe.bin test --stage="predict" --model="train_val_deploy.prototxt" \
--weights="iter_N.caffemodel"

当然,这时候输入层可能要换成其它的类型,不能是 Input 类型,不然 caffe 没法读取数据。使用 Input 类型时,就得用 Python/C++ 来加载数据。使用 stage="predict" 初始化 Python 和 C++ 的方法如下:

Python:
net = caffe.Net("train_val_deploy.prototxt", caffe.TEST, stages=['predict'],
                weights="iter_N.caffemodel")
C++:
caffe::vector<caffe::string> stages;
stages.push_back("predict");
caffe::Net *net = new caffe::Net("train_val_deploy.prototxt", caffe::TEST, 0, &stages);