计算广告实现入门-索引布尔表达式

概念
目标
DNF 算法
CNF
范围断言
实践
参考

本文重点为介绍一个计算广告的匹配算法，来自 Indexing Boolean Expression 。这种匹配算法可以匹配较为复杂的布尔表达式。

尽量以说人话的方式解释这种算法。

不涉及权重排序等规则。

概念

倒排索引：Inverted Index，反向索引，根据内容查找文档记录
- 如 document1: { a: [1,2] }，document2: { a:[1], b: [9] }
- 建立倒排索引为 a.1: [document1, document2], a.2: [document1]，b.1: [document2]
- 能快速找到到内容所在的文档记录
析取：Disjunctive，逻辑或
合取：Conjunctive，逻辑与，后文称为且
析取范式：
- （一个或多个且）的或被认为是一个 DNF
- 如：(A)、(B) ∪ (C)、(D ∩ E) ∪ (F)
合取范式：
- （一个或多个析取）的且被认为是一个 CNF
- 如：(A)、(B) ∩ (C)、(D ∪ E) ∩ (F)
- 所有逻辑公式都可以转换成合取范式 CNF
断言：在后续的描述中，我们将最小的逻辑单元称为一个断言，如 (a=1 ∩ b=2) ∪ c!=3 中的，a=1、b=2、c!=3

目标

既然所有的逻辑公式都可以转为 CNF，那么我们的目标就是实现一个可快速查找目标所匹配的 CNF 布尔表达式（boolean expressions）的算法。

DNF 算法

先来匹配 DNF 表达式

首先有几个匹配规则：
- BE1：(a=1 且 b=2 且 c=1)
- BE2：(a=2 且 b=3) 或 c=1
- BE3: (a=1 且 b!=2) 或 c=1
- BE4：(a=1 且 b!=3)
- BE5：b!=2
有一个目标 s1，其属性为 a=1、b=3
对所有的匹配规则中的断言建立倒排索引
- 索引：
- a=1：[BE1、BE3]
- a=2：[BE2]
- b=2：[BE1、BE3、BE4]
- b=3：[BE2]
- c=1：[BE2、BE3]
- c=2：[BE1] * 为什么不建立索引 b!=2 呢？因为无法将目标的属性转化为非确切值进行索引命中
索引处理：
- 使用 s1 在第 3 步的倒排索引中匹配的话我们能找到所有包含 a=1 和 b=2 的匹配规则，结果肯定是不对的，需要进一步处理
- 或拆分：在或关系中，只需要满足其中一部分就可能满足整个布尔表达式，所以我们将 DNF 拆分成独立的子句 C，判读 C 是否匹配即可
- 且拆分：在且关系的子句中，我们将需满足的 = 的数量记为 k
- 将所有上述信息计入倒排索引中
- 将 k 为 0 的子句写入一个特殊的 z 索引中，以避免漏掉目标无对应属性，而无法直接命中的只有一个不等于的子句规则
倒排索引
- a,1：
- { C: ‘BE1-C1’, info: { p: ‘=’, k: 3 }}
- { C: ‘BE3-C1’, info: { p: ‘=’, k: 1 }}
- { C: ‘BE4-C1’, info: { p: ‘=’, k: 1 }} * a,2：
- { C：’BE2-C1’, info: { p: ‘=’, k: 2 }} * b,2：
- { C: ‘BE1-C1’, info: { p: ‘=’, k: 3 }}
- { C: ‘BE3-C1’, info: { p: ‘!=’, k: 1 }}
- { C: ‘BE4-C1’, info: { p: ‘!=’, k: 0 }} * b,3：
- { C: ‘BE2-C1’, info: { p: ‘=’, k: 2 }}
- { C: ‘BE4-C1’, info: { p: ‘!=’, k: 1 }} * c,1：
- { C: ‘BE1-C1’, info: { p: ‘=’, k: 3 }}
- { C: ‘BE2-C2’, info: { p: ‘=’, k: 1 }}
- { C：’BE3-C2’, info: { p: ‘=’, k: 1 } * c,2:
- { C: ‘BE1-C2’, info: { p: ‘=’, k: 1 }} * z: z 非真实存在，所以我们不记录子句信息
- { C：’BE5’, info: { p: ‘=’, k: 0 }}
剪枝：
- 对于只有两个属性的目标，最多只能满足两个等于条件
- 所以以 s1: a=1、b=3 为例所以可以将 k > 2 的直接排除掉
- 再进行 a,1、b,3 的查找得出新的倒排索引
索引命中：z 默认为命中的
- a,1：
- { C: ‘BE3-C1’, info: { p: ‘=’, k: 1 }}
- { C: ‘BE4-C1’, info: { p: ‘=’, k: 1 }} * b,3：
- { C: ‘BE2-C1’, info: { p: ‘=’, k: 2 }}
- { C: ‘BE4-C1’, info: { p: ‘!=’, k: 1 }} * z:
- { C: ‘BE5’, info: { p: ‘=’, k: 0 }}
子句判断：以子句分组判断子句是否匹配
- BE2-C1：
- 命中：{ p: ‘=’, k: 2 }
- 判断：需满足 2 个等于，子句内仅有一项，不符合 * BE3-C1：
- 命中：{ p: ‘=’, k: 1 }
- 判断：需满足 1 个等于，子句内有一项，符合 * BE4-C1：
- 命中：{ p: ‘=’, k: 1 }、{ p: ‘!=’, k: 1 }
- 判断：需满足 1 个等于，分组内有多于一项，但是命中了一项不等于，导致子句整体判断为假，不符合 * BE5：
- 命中：{ p: ‘=’, k: 0 }
- 判断：需满足 0 个（未出现不等于，这也是 z 的作用）等于，分组内为一项，符合
结果：
BE5 的第一个子句 C1 匹配
true 或 ? 恒为 true
最终匹配了布尔表达式 BE5
总结：
- DNF 的 CNF 子句之间是或的关系，只需要满足一个 CNF 子句即可
- 子句的断言间是且的关系，需要看是否满足所有断言。同时，目标属性少于断言数量 k 可直接排除（算法优化）
- 断言为不等于时，需要一个特殊的 k=0 的倒排索引来命中不等于断言

CNF

首先有几个匹配规则：
- BE1：(a=1 或 b=2) 且 (c=1 或 e!=2)
- BE2：(a=2 或 b=3) 且 (c=1 或 d=2)
- BE3: (a=2 或 b!=2) 且 (c=1 或 d!=2)
- BE4：(a=2 或 b=3) 且 (c!=1 或 d!=2)
- BE5：(a=1 或 e!=2)
有一个目标 s2，其属性是：a=2、d=2
对所有的匹配规则中的断言建立倒排索引
- 索引：
- a=1：[BE1、BE5]
- a=2：[BE2、BE3、BE4]
- b=2：[BE1、BE3]
- b=3: [BE2、BE4]
- c=1：[BE1、BE2、BE3、BE4]
- d=2：[BE2、BE3、BE4]
- e=2：[BE1、BE5]
索引
- 以上索引依然不能直接匹配目标
- 在 CNF 中，其 DNF 子句之间是且的关系，需要命中所有的 DNF 子句 C
- DNF 的算法我们已经知道了，可以基于 DNF 进行匹配，再进行一次合并判断（类似于 DNF 算法中命中的数量是否等于 k）
- 于是需要记录以下信息，即 DNF 子句 C 是 CNF 的第几部分，同时对每个子句的命中进行判断
- 构造一个 CNF 的真值计数器，为数组，其长度为 DNF 子句的数量，其每项的值为表示否定的断言的数量
- 对于 BE3，其计数器为[-1,-1]，对于 BE4，其计数器为[0,-2]
- 同样我们将所有子句都包含不等于的 CNF 的也计入特殊的 z 索引，以避免目标缺少属性而无法匹配的情况
基于以上信息我们创建：
- 倒排索引：
- a,1：
  - { C: ‘BE1-C1’, info: { p: ‘=’ }}
  - { C: ‘BE5-C1’, info: { p: ‘=’ }}
- a,2：
  - { C: ‘BE2-C1’, info: { p: ‘=’ }}
  - { C: ‘BE3-C1’, info: { p: ‘=’ }}
  - { C: ‘BE4-C1’, info: { p: ‘=’ }}
- b,2：
  - { C: ‘BE1-C1’, info: { p: ‘=’ }}
  - { C: ‘BE3-C1’, info: { p: ‘!=’ }}
- a,3：
  - { C: ‘BE2-C1’, info: { p: ‘=’ }}
  - { C: ‘BE4-C1’, info: { p: ‘=’ }}
- c,1：
  - { C: ‘BE1-C2’, info: { p: ‘=’ }}
  - { C: ‘BE2-C2’, info: { p: ‘=’ }}
  - { C: ‘BE3-C2’, info: { p: ‘=’ }}
  - { C: ‘BE4-C2’, info: { p: ‘!=’ }}
- d,2：
  - { C: ‘BE2-C2’, info: { p: ‘=’ }}
  - { C: ‘BE3-C2’, info: { p: ‘!=’ }}
  - { C: ‘BE4-C2’, info: { p: ‘!=’ }}
- e,2：
  - { C: ‘BE1-C2’, info: { p: ‘!=’ }}
  - { C: ‘BE5-C1’, info: { p: ‘!=’ }}
- z：
  - { C: ‘BE5’, info: { p: ‘!=’ }}
    - 真值计数器：
  - BE1：[0,-1]
  - BE2：[0,0]
  - BE3：[-1,-1]
  - BE4：[0,-2]
索引命中：s2，其属性是：a=2、d=2
- a,2：
  - { C: ‘BE2-C1’, info: { p: ‘=’ }}
  - { C: ‘BE3-C1’, info: { p: ‘=’ }}
  - { C: ‘BE4-C1’, info: { p: ‘=’ }}
- d,2：
  - { C: ‘BE2-C2’, info: { p: ‘=’ }}
  - { C: ‘BE3-C2’, info: { p: ‘!=’ }}
  - { C: ‘BE4-C2’, info: { p: ‘!=’ }}
- z：
  - { C: ‘BE5’, info: { p: ‘!=’ }}
计数器计算：
- BE2-C1 中命中 BE2 第 1 部分，判断为 =，BE2 计数器，第 1 位改为 1：[1,1]
- BE2-C2 中命中 BE2 第 2 部分，判断为 =，BE2 计数器，第 2 位改为 1：[1,1]
- BE3-C1 中命中 BE3 第 1 部分，判断为 =，BE1 计数器，第 1 位改为 1：[1,-1]
- BE3-C2 中命中 BE2 第 2 部分，判断为 !=，BE2 计数器，第 1 位加 1：[1,0]
- BE4-C1 中命中 BE4 第 1 部分，判断为 =，BE2 计数器，第 2 位改为 1：[1,-2]
- BE4-C2 中命中 BE2 第 2 部分，判断为 !=，BE2 计数器，第 2 位加 1：[1,-1]
- z命中，即缺属性命中不等于判断，即 BE5 命中
结果：
- 计数器：
- BE1：[0,-1]
- BE2：[1,1]
- BE3：[1,0]
- BE4：[1,-1]
- z: BE5 * 含有 0 计数的，不匹配，所以结果为 BE2、BE4、BE5
总结：
- CNF 为且关系的子句，需要满足所有 DNF 子句，所以我们
- 根据子句建立 CNF 否命中的计数器，如 BE3: (a=2 或 b!=2) 且 (c=1 或 d!=2) 真值计数器为 [-1,-1]，长度为子句长度，每项为子句中 != 的数量，每有 n 个记为 -n
- 将断言在第几个子句和断言符号计入倒排索引信息 * 使用目标匹配所有倒排索引 * 根据信息判断修改真值计数器
- 命中第 n 个子句，且断言符号为 =，则将真值第 n 个位置置为 1，（表示这个 DNF 子句满足要求，或关系满足一个即可）
- 命中第 n 个子句，且断言符号为 !=，则将真值第 n 个位置加 1，（表示这个 DNF 子句默认满足要求的 != 已经失效）

范围断言

范围断言：
- 我们已经知道如何命中 = 和 !=，对于 >、< 这种范围该怎么办？将值转为确切的值即可
- 如匹配规则：time > 2028-10
  - 转化为 time = 2028-10、2028-11、2028-12、2029、2030、2040、2050…2100、2200…
  - 当然，不减少精度也可以，但是过多的值可能会是倒排索引数量爆炸
  - 当目标属性 time: 2029-01 来命中时，转化为 2029-01、2029、2020、2010、2000、1000 即可依靠 2029 命中
  - 即原始格式的值用来命中 = 断言，小精度的值用来快速命中范围断言
- 极限：我们肯定不能无限的转化，根据实际情况对属性转化设置一个上下限即可
  - 年龄：上限 120、下限 0
  - 较为实时的时间属性：在转化和命中时取当前时间加减几年或即可满足需要
- 当然也可以基于以上 CNF 的算法自己实现范围查找的逻辑
存在：
- 如果对属性是否存在也有匹配要求，即可在转化时转化为特殊值即可
- 如匹配规则：a 存在且 b 不存在
  - 转化为：a=XXXNOTNULL、b=XXXNULL
  - 命中时，目标属性为 a=3，则转化为 a=3、XXXNOTNULL，b=XXXNULL 即可

实践

以 ElasticSearch 为例，说明如何将匹配规则存入和如何匹配目标

匹配规则 BE1： (a == 1 a == 2 b = 3) && c!=1
目标：{ a: 1, b:2 }

倒排索引

构造 ElasticSearch 的匹配规则文档为：

// 文档1，在查询时 [1,2] 满足一个即可，所以可以将同一子句中 a 的两个值合并在一起
{
  BE: 'BE1',
  a: [1,2],
  info: {
    C: 1,
    d: '=',
    trueList: [0, -1]
  },
}
// 文档2
{
  BE: 'BE1',
  b: 3,
  info: {
    C: 1,
    d: '=',
    trueList: [0, -1]
  }
}
// 文档3
{
  BE: 'BE1',
  c: 1,
  info: {
    C: 2,
    d: '!=',
    trueList: [0, -1]
  }
}
// 也可以将匹配规则的真值计数器 trueList 存在别的地方

可以设置使得 ElasticSearch 不索引 info 和 BE 字段

构造目标查询语句：

{
  "query": {
    "bool": {
      "should": [
        {
          term: {
            a: 1
          }
        },
        {
          term: {
            b: 2
          }
        }
      ]
    }
  }
}

查询结果：

// 只命中了 a
{
  BE: 'BE1',
  a: [1,2],
  info: {
    C: 1,
    d: '=',
    trueList: [0, -1]
  },
}

真值计算：断言符号为 =，第一位改为[1,-1]
结果：命中 BE1

计算广告实现入门-索引布尔表达式

概念

目标

DNF 算法

CNF

范围断言

实践

参考