一个产品小白如何理解布尔表达式检索

　　布尔表达式检索是广告受众定向的检索问题，本文从基础概念和方法出发，结合实际案例，深入浅出地阐述了布尔表达式检索的作用以及用法。
　　广告主投放广告的本质是流量的采买，所以广告主在投放时会选择自身角度的潜在用户群，也就是当代广告的受众定向售卖方式。现在的广告系统对于大数据量处理及实时性都有着极高的要求，当用户发起广告请求时，广告引擎如何快速筛选出符合定向条件的广告，让索引设计变得极为关键。
　　基础概念
　　一般的广告主定向条件都类似于：20岁+女性，25岁+北京
　　这里的定向条件用布尔表达式进行表示：
　　a1=｛age∈（20）∩gender∈（female）｝∪｛age∈（25）∩geo∈（一线）｝
　　这里的形式即为析取范式（Disjunctive Normal Form，DNF）
　　每个DNF都可以分解成一个或者多个交集（conjunction），即age∈（25）∩geo∈（一线）
　　每个交集进一步分解成一个或者多个赋值集（assignment），即age∈（25），geo∈（一线）
　　双层索引结构设计
　　算法会维护一个两层的倒排索引，即conjunction-ad，attribute-conjunction。
　　实际检索过程中：
　　通过assignment筛选出满足条件的 conjunction，再根据conjunction找出满足条件的广告集合。
　　下面就是一步一步的举例过程！
　　假设线上有7个广告，定向条件如下：
　　Ad1：age∈（20）
　　Ad2：age∈（20）∩ gender∈（female）
　　Ad3：age∈（20）∩ geo∈（一线）
　　Ad4：age∈（20）∩ gender∈（female）∩geo∈（一线）
　　Ad5：age∈（20）∩ gender∈（female）∩geo∈（一线）
　　Ad6：age∈（20）∩ geo∈（一线）∩ mobile∉（apple）
　　Ad7：age∈（20）∩ gender∈（female）∩mobile∈（apple）
　　对应有6种定向条件，将定向条件编辑如下（其中size表示其中含有几个assignment）：
　　Conjunction1：age∈（20），size1
　　Conjunction2：age∈（20）∩ gender∈（female），size2
　　Conjunction3：age∈（20）∩geo∈（一线），size2
　　Conjunction4：age∈（20）∩gender∈（female）∩ geo∈（一线），size3
　　Conjunction5：age∈（20）∩geo∈（一线）∩ mobile∉（apple），size3
　　Conjunction6：age∈（20）∩gender∈（female）∩mobile∈（apple），size3
　　则可以建立从conjunction到ad的第一层倒排索引：
　　Conjunction1：Ad1
　　Conjunction2：Ad2
　　Conjunction3：Ad3
　　Conjunction4：Ad4，Ad5
　　Conjunction5：Ad6
　　Conjunction6：Ad7
　　根据conjunction 的size大小及包含情况建立从attribute到conjunction的第二层倒排索引（标注conjunction是否含有/不含有该assignment）：
　　Size1：age∈（20），（1，∈）
　　Size2：
　　age∈（20），（2，∈）（3，∈）
　　gender∈（female），（2，∈）
　　geo∈（一线），（3，∈）
　　Size3：
　　age∈（20），（4，∈）（5，∈）（6，∈）
　　gender∈（female），（4，∈）（6，∈）
　　geo∈（一线），（4，∈）（5，∈）
　　mobile∈（apple），（5，∉）（6，∈）
　　线上请求检索过程
　　当某次广告请求的定向条件满足某个conjunction，一定满足包含该conjunction的所有广告。如果用size of（query）表示请求中的定向标签个数，如果size of（query）＜size of（conjunction），该conjunction一定不满足要求。可以先利用这个判断减少计算。
　　当线上有一个用户发起了广告请求，该用户的标签为：
　　age∈（20）∩geo∈（一线）
　　因为size of（query）=2，则从size为1和2的conjunction中进行查询
　　Size=2的查询
　　age∈（20）（2，∈）（3，∈）
　　geo∈（一线） （3，∈）
　　只有Conjunction3满足条件，对应Ad3
　　Size=1的查询
　　age∈（20）（1，∈）
　　只有Conjunction1满足条件，对应Ad1
　　维度爆炸问题
　　这里的维度组合并不取决于标签的乘积，即2个性别，100个年龄，34个地理……（2*100*34……），而是取决于广告的规模，假设有100w的广告，每个广告的定向标签都不一样，也只是百万级的检索，并且大量的广告受众定向是重复的，远远小于广告数量。