乐趣区

关于elasticsearch:计算广告实现入门索引布尔表达式

jiezi

本文重点为介绍一个计算广告的匹配算法，来自 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 表达式

  1. 首先有几个匹配规定：

    • 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
  2. 有一个指标 s1，其属性为 a=1、b=3

  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 呢？因为无奈将指标的属性转化为非确切值进行索引命中

  4. 索引解决：

    • 应用 s1 在第 3 步的倒排索引中匹配的话咱们能找到所有蕴含 a=1 和 b=2 的匹配规定，后果必定是不对的，须要进一步解决
    • 或拆分：在或关系中，只须要满足其中一部分就可能满足整个布尔表达式，所以咱们将 DNF 拆分成独立的子句 C，判读 C 是否匹配即可
    • 且拆分：在且关系的子句中，咱们将需满足的 = 的数量记为 k
    • 将所有上述信息计入倒排索引中
    • 将 k 为 0 的子句写入一个非凡的 z 索引中，以防止漏掉指标无对应属性，而无奈间接命中的只有一个不等于的子句规定

  5. 倒排索引

    • 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}}

  6. 剪枝：

    • 对于只有两个属性的指标，最多只能满足两个等于条件
    • 所以以 s1: a=1、b=3 为例所以能够将 k > 2 的间接排除掉
    • 再进行 a,1、b,3 的查找得出新的倒排索引

  7. 索引命中：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}}

  8. 子句判断：以子句分组判断子句是否匹配

    • 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 的作用）等于，分组内为一项，合乎

  9. 后果：

    1. BE5 的 第一个子句 C1 匹配
    2. true 或 ? 恒为 true
    3. 最终匹配了布尔表达式 BE5

  10. 总结：

    • DNF 的 CNF 子句之间是或的关系，只须要满足一个 CNF 子句即可
    • 子句的断言间是且的关系，须要看是否满足所有断言。同时，指标属性少于断言数量 k 可间接排除（算法优化）
    • 断言为不等于时，须要一个非凡的 k=0 的倒排索引来命中不等于断言

CNF

  1. 首先有几个匹配规定：

    • 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)
  2. 有一个指标 s2，其属性是：a=2、d=2

  3. 对所有的匹配规定中的断言建设倒排索引

    • 索引：

      • 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]

  4. 索引解决

    • 以上索引仍然不能间接匹配指标
    • 在 CNF 中，其 DNF 子句之间是且的关系，须要命中所有的 DNF 子句 C
    • DNF 的算法咱们曾经晓得了，能够基于 DNF 进行匹配，再进行一次合并判断（相似于 DNF 算法中命中的数量是否等于 k）
    • 于是须要记录以下信息，即 DNF 子句 C 是 CNF 的第几局部，同时对每个子句的命中进行判断
    • 结构一个 CNF 的真值计数器，为数组，其长度为 DNF 子句的数量，其每项的值为示意否定的断言的数量
    • 对于 BE3，其计数器为[-1,-1]，对于 BE4，其计数器为[0,-2]
    • 同样咱们将所有子句都蕴含不等于的 CNF 的也计入非凡的 z 索引，以防止指标短少属性而无奈匹配的状况

  5. 基于以上信息咱们创立：

    • 倒排索引：

      • 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]

  6. 索引命中：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: ‘!=’}}

  7. 计数器计算：

    • 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 命中

  8. 后果：

    • 计数器：

      • BE1：[0,-1]
      • BE2：[1,1]
      • BE3：[1,0]
      • BE4：[1,-1]
      • z: BE5
    • 含有 0 计数的，不匹配，所以后果为 BE2、BE4、BE5

  9. 总结：

    • 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

参考

  • Indexing Boolean Expression
  • Indexing Boolean Expression 的工程实现
  • 基于布尔表达式的广告索引设计
退出移动版