关键词匹配与NPC问题

规则匹配

常见业务逻辑

if r := rule1(arg):
    return r
if r := rule2(arg):
    return r
...

代码逻辑调整为配置加载形式

for rule in rules:
    if r := rule(arg):
        return r

规则匹配性能优化:

前提: 规则是互斥的, 即打乱规则顺序不影响输出结果. 实际上业务代码不能保障这一点, 都有潜在的依赖假设关系, 这也是潜在的BUG源. 如何找出? 配置形式, 随机化规则, 并测试保障.

进一步, 规则层级分组, 逻辑写成规则树模式, 减少不必要重复计算及遍历 (从不命中中找到有用的信息)

def match(arg, rules: dict):
    for f, sub_rules in rules.items():
        if r := f(arg):
            return match(r, sub_rules)
    return arg

例子

rules0 = {
  "^https://.*byteoversea\.com/.*/([0-9a-z]{32})/toutiao.mp4$": {}
  "^https://.*byteoversea\.com/.*/([0-9a-zA-Z]{38})/toutiao.mp4$": {},
  ...
}
# VS
rules1 = {
  "^https://.*byteoversea\.com/(.*)": {
      "([0-9a-z]{32})/toutiao.mp4$": {},
      "([0-9a-zA-Z]{38})/toutiao.mp4$": {},
      ...
  },
  ...
}

实际上, 任意业务逻辑, 都是这样一个匹配返回过程

文本规则匹配

文本分类问题, 加规则 (一般都可以表达成正则形式) 快速召回

优点: 简单有效, 快速定向提点 缺点: 规则加太多时的匹配性能问题; 规则冲突问题; 没考虑潜在分词问题

弱化形式: 词包模型, 关键词匹配

关键词匹配简化

黑名单去除

括号去除

因此关键是词包匹配

词包匹配

做关键词索引快速过滤需检查规则

  1. 规则集整理提取: l1=a&b, l2=a
  2. 词出发的规则关联及关联词转换: a={l1:[b], l2:[]}, b={l1:[a]}
  3. AC文本匹配找到所有潜在命中规则后进一步过滤

See Code

说明

这里的假设: 单个词包不能太长, 一个词不能出现于过多的词包中, 否则二次过滤是个耗时

本质问题: 给定一个集合, 从一批备选集合中快速找出被包含的

词包约化

由于规则都是人工加的, 会存在冲突或者歧义的场景

单分类下规则约化:

规则约化: 删除被包含规则, 删除不可能有匹配的规则

多分类下消岐:

正交规则定义: 两规则不会同时命中同一序列 歧义规则定义: 两规则会命中相同文本, 且包含相同片段

消岐办法: 差集纳入黑名单, 一个避嫌即可

消岐问题翻译: 一组序列/集合的包含/相交判定

词包 = 序列的集合, 导致问题的额外复杂性, 这里集合元素(即词)本身也具有序列包含/相交关系

CSF & LCS

序列包含/相交问题: 判断是否单字共现即可, 是简单的, 更有价值的问题是找到最长公共子串 (longest common substring)

更有价值的问题: common substring (子串) finding (这里记为CSF问题先)

CSF解法: 用suffix tree, 记录公共枝以及对应共现频次即可

longest common substring for k strings: 找频次=序列大小的公共子串, 视作CSF的简单版

See Code

类似的问题 = common subsequence (子序列) finding

LCS (longest common subsequence) 问题 / 后提

关键词规则提取问题表述

samples = {
  seq1: cls1,
  seq2: cls1,
  seq3: cls2,
  ...
}

# 目标规则
rules = {s1: cls1, s2: cls2, ...}

def classifier(txt, rules):
  for seq, cls in rules.items():
    if is_sub_sequence(seq, txt):
      return cls

assert all(classifier(txt, rules) == cls for txt, cls in samples.items())

显然一个最无泛化性的规则

rules = {seq1: cls1, seq2: cls2, ...}

泛化性 ~ 整体检索关键词序列长度

问题定义: 寻找最短通过子序列匹配做判定的分类器

minimize sum(map(len, rules))

说明:

问题简化先认为只有两分类

对于两样本序列区分, 只需找出最短的唯一片段即可

若每个分类只有单词包规则, 则可以当作类LCS问题处理:

实际上每个类样本肯定不存在LCS, 假设每个规则有最小样本支持度k, 则问题: 抽取每个类中所有最小频次k的子序列, 并分别做上述唯一性提取

核心问题翻译:

另外一种问题”曲解”: 忽略分类标号信息, 当作最小序列辨别器问题, 再映射到分类标号. 缺点: 泛化误差高, 因为倾向提取到每个样本数据的个性特征, 没有对于同标号数据充分压缩.

集合VS序列

序列最小辨别器和tokenization的联系及区别

序列最小辨别器问题: CSF+辨别顺序决策

tokenization: 给定一堆文本, 最少token数编码

简单的tokenization: CSF的片段先纳入词表, 然后剩余片段再纳入

和FPM问题的联系与区别

FPM: Frequent Pattern Mining / Frequent Itemset Mining / 关联规则提取, 规则学习, …

FPM对于无标号集合数据, 找共现概率最大共现元素. 需要文本先分词, 基于置信度的提取方案. 先单分类下FPM找出支持度较高的词包, 再跨分类判定该词包的唯一性, 或者识别质量提升.

计算理论

知道点计算理论对于我们”凡人”的好处: 及时放弃幻想, 意识到问题的难度, 不要死磕问题, 认为会有精巧的最优解法.

NP问题: 可快速验证的问题, 是否一定存在快速的解法?

NPC一般是决策问题表述:

以下一些NPC问题列举

SAT

satisfiability problem

第一个被证明是NPC的问题

判定任意一个逻辑运算表达式是否有可行解, 例子:

给了一个解, 验证是否正确, 自然是平凡的; 暴力判定: 穷举2**n中可能性看是否有通过结果

回到我们业务:

LCS

决策问题表述: 是否有超过指定长度的子序列?

2输入时: DP, O(mn)时间空间复杂度, 注意对于长文本这也不是可接受的

暴力计算: 对于给定的一组序列, 枚举最短序列的所有子序列去判定即可, O(2**k)

对于确定的字典, 以及假定最大序列长度时, 则问题可以枚举解决 C**K, 理论上是P的, 但实际上是不可行的

对于不确定的输入文本时, 指数复杂度 (注意这里问题参数是输入序列个数, 且每个序列长度无上限)

Q: LCS和编辑距离关系? 最短公共序列(shortest common supersequence)问题的关系?

See Code

衍生问题:

最大团问题

找出图里面最大的全联通子图

背包问题

贪心算法不保证最优解

DP算法, 由于不能memorize子问题, 实际上是不可行的

Recall:

三色问题

一笔画问题

如何证明一个问题很难?

从一个已知NPC问题触发, 证明其可以约化成目标问题

注意不是反向, 随便一个问题当然可以泛化成一个NPC问题

如何”击败”NPC

NPC之于数据挖掘问题

数据挖掘表述: 寻找算法, 使得, 对于样本数据的任意k参数训练/验证集划分, 基于训练集生成的规则, 在验证集上的评价指标期望最小

显然, 样本划分问题空间本身就是幂次的

Beat the impossible

对于数据特征的观察/假设, 经验性的算法, 达到一个还不错的结果

步步为营, 百尺竿头, 更近一步

Reference

HOME