布爾表達式檢索是廣告受眾定向的檢索問題，本文從基礎(chǔ)概念和方法出發(fā)，結(jié)合實際案例，深入淺出地闡述了布爾表達式檢索的作用以及用法。

廣告主投放廣告的本質(zhì)是流量的采買，所以廣告主在投放時會選擇自身角度的潛在用戶群，也就是當代廣告的受眾定向售賣方式?，F(xiàn)在的廣告系統(tǒng)對于大數(shù)據(jù)量處理及實時性都有著極高的要求，當用戶發(fā)起廣告請求時，廣告引擎如何快速篩選出符合定向條件的廣告，讓索引設(shè)計變得極為關(guān)鍵。

基礎(chǔ)概念

一般的廣告主定向條件都類似于：20歲+女性，25歲+北京

這里的定向條件用布爾表達式進行表示：

a1=｛age∈（20）∩gender∈（female）｝∪｛age∈（25）∩geo∈（一線）｝

這里的形式即為析取范式（Disjunctive Normal Form，DNF）

每個DNF都可以分解成一個或者多個交集（conjunction），即age∈（25）∩geo∈（一線）

每個交集進一步分解成一個或者多個賦值集（assignment），即age∈（25），geo∈（一線）

雙層索引結(jié)構(gòu)設(shè)計

算法會維護一個兩層的倒排索引，即conjunction-ad，attribute-conjunction。

實際檢索過程中：

通過assignment篩選出滿足條件的 conjunction，再根據(jù)conjunction找出滿足條件的廣告集合。

下面就是一步一步的舉例過程！

假設(shè)線上有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）

對應(yīng)有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

根據(jù)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）表示請求中的定向標簽個數(shù)，如果size of（query）＜size of（conjunction），該conjunction一定不滿足要求。可以先利用這個判斷減少計算。

當線上有一個用戶發(fā)起了廣告請求，該用戶的標簽為：

age∈（20）∩geo∈（一線）

因為size of（query）=2，則從size為1和2的conjunction中進行查詢

Size=2的查詢

age∈（20）???（2，∈）（3，∈）

geo∈（一線） ?（3，∈）

只有Conjunction3滿足條件，對應(yīng)Ad3

Size=1的查詢

age∈（20）???（1，∈）

只有Conjunction1滿足條件，對應(yīng)Ad1

維度爆炸問題

這里的維度組合并不取決于標簽的乘積，即2個性別，100個年齡，34個地理……（2*100*34……），而是取決于廣告的規(guī)模，假設(shè)有100w的廣告，每個廣告的定向標簽都不一樣，也只是百萬級的檢索，并且大量的廣告受眾定向是重復(fù)的，遠遠小于廣告數(shù)量。

本文由 @崔巍Bella 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議