復雜布爾查詢下的文檔收集打分策略的優化*

黃 達，閆宏飛

北京大學 信息科學技術學院，北京 100871

復雜布爾查詢下的文檔收集打分策略的優化*

黃 達+，閆宏飛

北京大學 信息科學技術學院，北京 100871

HUANG Da,YAN Hongfei.Optimization for collecting and scoring documents for complex Boolean query. Journal of Frontiers of Computer Science and Technology,2017,11(1)：106-113.

雖然布爾查詢是信息檢索領域中較早提出的一個概念，但是對布爾查詢的大量研究主要還是針對布爾操作一致的布爾查詢。對于復雜布爾查詢，目前并沒有太多的相關研究，復雜布爾查詢卻越來越被頻繁地使用（如文本推薦領域）。為了促使這類查詢能夠被更加高效地執行，提出了一種基于DAAT（document-at-a-time）框架的文檔收集打分策略——DCQ（DAAT for complex query）算法，并與著名開源搜索引擎Lucene進行比較實驗，查詢性能有了顯著提升。此外，提出了一套對查詢性能的回歸預測機制，該機制能比較準確地決策DCQ算法的使用時機。實驗表明，結合了性能預測器的復合算法要遠優于Lucene當前的文檔收集打分算法。

復雜布爾查詢；查詢優化；性能回歸

1 引言

在信息檢索領域，所謂布爾查詢，是指在詞項上通過布爾邏輯操作符（與或非）構建出布爾表達式，從而表達用戶希望文檔所具有的特征[1]。這種查詢語義精確，易于實現，因此早期搜索引擎的查詢模式都是以布爾查詢為主。盡管在加入了打分排序機制后，布爾查詢的檢索功能有了顯著提高[2]，但由于其查詢表達式較為繁瑣，而且對大多數用戶來說，要用布爾表達式來精確定義檢索需求是非常困難的，從而在通用搜索領域，布爾查詢已經被更加簡單的關鍵詞查詢所替代[3]。

然而即便如此，憑借其精確和高效的特性，一方面，布爾查詢仍然為各大搜索引擎所保留，人們仍然可以通過搜索引擎的高級搜索功能來定義布爾查詢（如百度[4]、谷歌[5]）。另一方面，關鍵詞查詢在后臺進行預處理時往往會根據查詢日志、同義詞表等數據結構，轉換成極為復雜的布爾查詢表達式，在后臺發揮核心作用[6-7]。

此外，布爾查詢在一些面向特定領域的搜索引擎中仍然處于主導地位[8]。比如，法律搜索[9]和專利搜索[10]，因為法律和專利文書的用詞有著高度的嚴謹性和專業性，使得精確的布爾查詢反而更容易滿足用戶的檢索需求。

在一些新興的研究領域，特別是社交推薦領域[11]，隨著數據規模的增大，對每個候選信息單元進行打分顯然越來越不現實。因此，研究者們已經開始結合搜索引擎來制作推薦系統[12-13]。他們的框架往往是先利用用戶的個人信息提取出詞項，然后生成復雜的布爾查詢，進而通過搜索引擎檢索出前K個相關文檔，再在這K個文檔上進行細化打分。

由此可見布爾查詢在上述各應用場景下，查詢語句往往同時混合了多種布爾邏輯操作。然而，目前絕大多數搜索引擎的布爾查詢語法都是AND、OR、NOT和括號的組合，比如：((aANDb)ORcORd)AND NOTeAND NOTf，這種語法忽視了多種布爾操作混合在一起的優化可能性。著名開源搜索引擎Lucene（http://lucene.apache.org/）雖然可以用“+a+b c d-e-f”來表示上述查詢，但其內部處理的方法仍然沒有考慮混合型的優化。

針對這種情況，本文提出了一種針對復雜布爾查詢的基于DAAT（document-at-a-time）框架的文檔收集打分新策略——DCQ（DAAT for complex query）算法，該策略把復雜布爾查詢當成一個整體來進行優化。本文以Lucene作為基準程序（Baseline），以維基百科（http://en.wikipedia.org/）詞條作為數據集。通過實驗發現，DCQ算法能在復雜布爾查詢下優于基準程序。另外，提出了一種高效的性能回歸預測機制，使得人們可以根據具體的查詢，決策DCQ算法的使用時機，進而保證任何情況下查詢性能都不會下降。

本文探討了復雜布爾查詢下，文檔搜集和打分策略的優化方法，并對該方法的性能進行了深入分析，提出了一種性能回歸預測機制。本文組織結構如下：第2章對復雜布爾查詢下的文檔收集打分問題進行分析，并提出DCQ算法；第3章研究DCQ算法的性能，并給出一種性能回歸預測機制；第4章介紹實驗設置和實驗結果；最后對全文進行了總結。

2 問題分析與方法描述

2.1 問題描述

現有若干個待查詢的詞項：t11,t12,…,t1m,t21,t22,…,t2n,t31,t32,…,t3p，需要找到所有滿足下述條件的文檔d：

并對文檔d進行打分，其分值為：

顯然，上述定義所描述的是一個典型的復雜布爾查詢。在該定義下：

（1）每一個被命中的文檔，必須包含所有的t1i，故稱每個t1i項為該查詢的MUST子句；

（2）每一個被命中的文檔，不得包含任意一個t2j，故稱每個t2j項為該查詢的MUST_NOT子句；

（3）是否包含t3k并不會對文檔的命中產生影響，但總體上看，包含的t3k項越多，文檔分值越高，故稱每個t3k項為該查詢的SHOULD子句。

為簡潔起見，上述定義所描述的查詢符號化為q：

2.2 文檔收集打分策略分析

對所有命中文檔進行收集打分的方法主要有兩種：每一步收集一個命中文檔的DAAT，以及每一步疊加一個倒排表（posting list）的TAAT（term-at-a-time）。

TAAT的優點在于程序局部性較好，磁盤尋道時間較短，但其所占用的內存空間較大；DAAT的優點在于內存占用較少，但其需要在倒排表之間進行切換，以致程序局部性較差[14]。然而，跳表[15]和緩存技術的引入，使得DAAT在絕大多數情況下都要優于TAAT。因此，Lucene使用DAAT作為其主要的文檔收集打分方法。

然而在過去的研究中，對文檔收集打分方法的研究僅僅局限于“子句全與”(q=+t11+t12…+t1m)和“子句全或”(q=t31t32…t3p)，對于復雜布爾查詢下該如何對文檔進行收集打分，并沒有很深入的研究。

Lucene處理查詢表達式（2）的現行做法是把它按照以下的查詢結構來處理：

其含義是：用t11t12…t1m的合取式減去t21t22…t2n的析取式來得到結果集合，并對集合中的元素用t31t32…t3p的析取式的命中情況來加分。

顯然，在計算t21t22…t2n和t31t32…t3p的析取式的時候需要通過維護一個堆（heap）的結構來求得每個命中文檔，這就需要分別花費Θ(nlbn)和Θ(plbp)的時間開銷。然而，這個開銷實際上并不是完全必要的，因為人們只關心t1i與t2j、t3k之間的關系，而不關心各t2j之間、各t3k之間的關系。上述提到的維護堆的操作實際上就是計算這些多余的人們不關心的信息。

2.3 DCQ算法

為了減少多余的堆調整開銷，本文提出了DCQ算法。此算法是在DAAT的框架下同時處理查詢的所有子句，從而避免了用堆來維護t2j和t3k所產生的開銷。其迭代器的next方法的具體實現如下所示。

3 性能分析和性能回歸預測

3.1 性能分析

假設 +t11+t12…+t1m命中N個文檔，在最壞情況下Lucene每取一個文檔都要分別對MUST_NOT子句集和SHOULD子句集進行堆調整，其時間復雜度為Θ(N(nlbn+plbp))；而對于DCQ算法，由于不需要進行堆調整，其文檔收集打分的過程相當于把命中文檔集掃描n+p遍，因此其時間復雜度為Θ(N(n+p))。

DCQ算法雖然在時間復雜度上要優于Lucene，然而在實際使用的時候有兩個因素會導致DCQ算法慢于Lucene：

（1）DCQ算法需要同時處理多種不同邏輯連接的子句，其控制邏輯要更為復雜，使得時間復雜度的常系數會大一些，因此只有當n和p具有一定規模的時候，DCQ算法才會快于Lucene。

（2）因為現代搜索引擎都帶有完善的跳表機制，所以只有當文檔被t2j或者t3k命中時，在試圖收集該文檔的過程中才會觸發堆調整。也就是說：只有在t2j或者t3k所命中的文檔號分布比較稠密的情況下，Lucene對所有命中文檔進行收集打分的時間復雜度才會達到Θ(N(nlbn+plbp))。

因此，需要有一種高效的預測機制來決策DCQ算法的使用時機。

3.2 性能函數

為簡化問題，不妨令s1=+t11+t12…+t1m，并假設p=0，即沒有SHOULD子句（有SHOULD子句的情況可以在本節所提方法基礎上很容易地進行擴展）：

本文把某個特定算法針對查詢q的性能定義為：

QPSmethod表示在method算法下每秒處理完成q的次數（queries per second）。

定義算法m1對m0的相對性能為：

從3.1節的分析可以看出，DCQ算法的性能取決于兩個因素：

（1）MUST_NOT子句的總數n；

（2）s1和t2j所命中的文檔號分布情況。

因此可以把DCQ對Lucene的相對性能表達式寫成：

其中，dist(t)表示t所命中的文檔號在自然數域上的分布情況。

為簡化問題，近似地以cost(t)來替代dist(t)，cost(t)是t所命中的文檔頻數估計值。于是有：

又因為人們希望從總體上來考慮所有SHOULD子句，所以近似地以式（9）來替代cost(s1),cost(t21),cost(t22),…,cost(t2n)。

從而，perfDCQ|Lucene(q)又可以進一步簡化為：

令a=cost(s1),b=avgcost(t21,t22,…,t2n)，則有：

顯然，當f(n,a,b)＞0時，應該使用DCQ算法來對文檔進行收集打分。

3.3 性能的回歸預測

3.3.1 回歸模型的提出

如果可以擬合出f(n,a,b)，那么就可以比較準確地決策DCQ算法的使用時機。

根據3.1節的分析可以看出，當p=0時，Lucene的時間復雜度為Θ(Nnlbn)，而DCQ的時間復雜度為Θ(Nn)。也就是說：

聯立式（6）、（11）、（12）1)f(x)∝g(x)表示f(x)與g(x)線性相關。，有：

因此，可以用一個關于lbn的線性函數去擬合f(n,a,b)：

為了驗證上述想法，隨機構建了一些滿足表達式（4）的查詢，并取一段連續自然數{ni}進行實驗，得到對應的{yi|yi=f(ni,a,b)}。

通過式（15）求出{lbni}與{yi}的相關系數：

發現min(cr)≥0.85，說明在a、b給定的情況下，{lbni}與{yi}呈強線性相關。

3.3.2 參數α、β的求解

現在的問題就是如何求解參數α和β。顯然，一定可以選取到一系列形式簡單的函數u1(a,b),u2(a,b),…,uK(a,b)，使得：

β同理（以下的討論將以α的計算為例子，β的計算采用完全相同的方法，不再贅述）。

為便于計算，這里選取K=4，即有：

令u(a,b)=＜u1(a,b),u2(a,b),u3(a,b),u4(a,b)＞,k=＜k1,k2,k3,k4＞T，則有：

現在的目標是求出向量k。由于向量k有4個參數，因此至少需要設置4組a、b的值，并通過實驗得出它們各自對應的α值。

本文隨機選定兩組詞項集來進行實驗：一組是高頻詞項集，其平均文檔頻數（document frequency）[16]為H；另一組是低頻詞項集，其平均文檔頻數為L。

由于H和L的值都比較大，不妨取它們的對數，令h=lbH，l=lbL。這樣就可以利用h和l生成4個組合。

把式（20）代入式（19）可以得到：

進而可以求得：

3.3.3 ui的選取

剩下的最后一個問題就是ui的選取，ui必須滿足下述兩個條件：

（1）必須使得矩陣U可逆，這是向量k可計算的首要條件；

（2）ui需要能反映出一定的物理意義，以使得本文方法是可解釋的。

鑒于此，選取如表1所示的4個函數。

其中，u1、u2覆蓋了a、b的任意線性組合；u3考慮了a、b在二次冪空間上的影響；u4實際上是a、b調和平均值的一半，用以表示a、b的調和程度對結果的影響。

Table 1 Selection ofui表1 ui的選取

把ui代入式（20），得到：

可以計算出U的逆矩陣：

顯然，因為h＞l，所以U-1是可計算的，即矩陣U可逆。進而，把式（24）代入式（22）就可以求解出向量k。

有了向量k以后，在查詢處理的過程中，根據3.2節的定義，可以計算出a、b，并根據表1求得ui(a,b)的值，進而代入式（20）、（21），求得α（β同理），得到式（14）所示的相對性能預測函數。

為了容許一些誤差，當相對性能函數大于某個略大于0的閾值時，才選取DCQ算法。本文設置該閾值為5。也就是說，只有當DCQ算法的預測性能比Lucene至少提高5%時，才會選擇使用DCQ算法進行文檔收集打分。

而針對查詢中同時包含MUST、MUST_NOT和SHOULD子句的情況，即式（2）的情況，會先把查詢拆分為如下形式進行預測：

（1）如果DCQ算法處理q1和q2的效率都比較高，則采用DCQ算法；

（2）如果DCQ算法處理q1和q2的效率都比較低，則采用Lucene現行算法；

（3）如果DCQ算法處理q1的效率比較高，而處理q2的效率比較低，則對q1采用DCQ算法，而對q2采用Lucene現行算法；

（4）如果DCQ算法處理q1的效率比較低，而處理q2的效率比較高，則對q1采用Lucene現行算法，而對q2采用DCQ算法。

4 實驗設置與結果分析

4.1 實驗工具、數據和評價指標

本文使用了著名開源搜索引擎Lucene來進行對比實驗。實驗中，采用了包含33 332 621個詞條的維基百科數據集，并按照高頻、中頻、低頻的頻數分別隨機抽取100個詞項，如表2所示。

Table 2 Statistics for sampled terms set表2 所抽取詞項集的統計信息

利用上述詞項，構建出如表3所示的若干種查詢。

Table 3 Constructing queries表3 構建查詢

根據3.3.3節的描述，同時包含MUST、MUST_ NOT和SHOULD子句的查詢，最終將歸結到式（25）所示的兩種查詢，故而本文僅對f1-must-p-f2-should和f1-must-n-f2-mustnot這兩種情況進行實驗。

取n、p從3到9，并為每個n、p值給定查詢結構，分別隨機生成50個查詢用于進行評測，并采用QPS作為評價指標：

其中|Q|=50。

4.2 DCQ算法的相對性能及其回歸預測

利用上述數據集分別對DCQ和Lucene進行實驗，求得各QPS值，并利用式（6）求得DCQ的相對性能perfDCQ|Lucene(q)，如圖1所示。

圖1的橫坐標是lbn（或者lbp），藍色的是相對性能曲線，可以觀察到每條曲線近似地呈直線增長。進一步采用最小二乘法，對每條曲線做線性回歸，并求出其各自的相關系數，如表4所示。

Table 4 Performance fitting表4 性能曲線的擬合

把線性回歸所求得的關于lbn的線性函數繪制在圖1上。直觀上看，回歸曲線（紅色的）非常接近原來的性能曲線。另外，還通過式（15）計算出各組數據的相關系數，發現最小的相關系數為0.853，說明lbn與f呈強線性相關。這就驗證了3.3節提出的相對性能線性假設的合理性。

把表4的數據代入式（22）、（24），求解得到各組k向量，并在查詢處理運行時刻套用式（19）、（21）求得在特定查詢下的α、β值，進而得到式（14）所示的相對性能回歸函數，即可預測出在該查詢下，DCQ算法是否更優。

Fig.1 Relative performance curve and linear fitting圖1 相對性能曲線與線性擬合

4.3 結合性能回歸預測器的總體性能

當相對性能的預測值超過5%時，采用DCQ算法進行文檔收集打分。本文使用了十折交叉驗證法（10-fold cross validation），求得最終的性能結果，如圖2和圖3所示。

Fig.2 Relative performance whenq=+s1-t21-t22…-t2n圖2 處理q=+s1-t21-t22…-t2n時的相對性能

Fig.3 Relative performance whenq=+s1t31t32…t3p圖3 處理q=+s1t31t32…t3p時的相對性能

可以觀察到，在各種查詢下，性能預測器都能很好地進行預測，并選用適當的文檔收集打分算法。n（或者p）越大，性能的提升越顯著。注意到在某些查詢下，帶預測器的復合算法性能有所下降（相對性能小于0），但下降幅度不大（-6%以內）。原因是：實驗中每次迭代都是先運行復合算法，再運行Lucene，這就使得在運行Lucene時，緩存（cache）中還留有一定的數據，進而讓Lucene看似有略高一點的性能。總體來說，帶預測器的復合算法在各種查詢情況下都不差于Lucene。

5 總結

在信息檢索的傳統領域，本文提出了一種針對復雜布爾查詢的優化方法——DCQ算法，通過利用這種查詢的一些重要特性，避免了在文檔收集打分過程中的堆調整，進而優化了查詢性能（特別是當SHOULD子句或者MUST_NOT子句較多時）。為了進一步完善本文方法，提出了一種對相對性能的回歸預測機制，能比較準確地預測DCQ算法的使用時機。通過評測發現，帶性能預測器的復合算法能夠大大地提高Lucene的查詢性能。

[1]Manning C D,Raghavan P,Schütze H.Introduction to information retrieval[M].Cambridge:Cambridge University Press,2008:12-13.

[2]Salton G,Fox E A,Wu H.Extended Boolean information retrieval[J].Communications of the ACM,1983,26(11): 1022-1036.

[3]Sanderson M,Croft W B.The history of information retrieval research[J].Proceedings of the IEEE,2012,100(Special Centennial Issue):1444-1451.

[4]Chen Qiang,Ye Bing,Zhu Yu’e.Internet tutorial[M].2nd ed.Beijing:Tsinghua University Press,2005:209-212.

[5]Djurup R.Your guide to Google Web search[M].[S.l.]:Rebidu, 2010:143-144.

[6]Voorhees E M.Query expansion using lexical-semantic relations[C]//Proceedings of the 17th Annual International SIGIR Conference on Research and Development in Information Retrieval,Dublin,1994.London:Springer,1994:61-69.

[7]Xu Jinxi,Croft W B.Query expansion using local and global document analysis[C]//Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,Zurich,1996.New York: ACM,1996:4-11.

[8]Kim Y,Seo J,Croft W.B.Automatic boolean query suggestion for professional search[C]//Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval,Beijing,2011.New York: ACM,2011:825-834.

[9]Griffith C.WESTLAW’s WIN:not only natural,but new[J]. Information Today,1992,9(9):9-11.

[10]Wang Shihui,Jia Guanxin.Patent information retrieval by using SooPAT[J].Information Research,2012(1):94-96.

[11]Jiang Meng,Cui Peng,Liu Rui,et al.Social contextual recommendation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management, Maui,2012.New York:ACM,2012:45-54.

[12]Reips U D,Garaizar P.Mining twitter:a source for psychological wisdom of the crowds[J].Behavior Research Methods,2011,43(3):635-642.

[13]Ronen I,Guy I,Kravi E,et al.Recommending social media content to community owners[C]//Proceedings of the 37th International ACM SIGIR Conference on Research and Development in Information Retrieval,Gold Coast,2014. New York:ACM,2014:243-252.

[14]Croft W B,Metzler D,Strohman T.Search engines:information retrieval in practice[M].Reading,USA:Addison-Wesley,2010:168-171.

[15]Pugh W.Skip lists:a probabilistic alternative to balanced trees[J].Communications of theACM,1990,33(6):668-676.

[16]Leskovec J,Rajaraman A,Ullman J D.Mining of massive datasets[M].Cambridge:Cambridge University Press,2014: 1-17.

附中文參考文獻：

[4]陳強,葉兵,朱玉娥.Internet應用教程[M].2版.北京:清華大學出版社,2005:209-212.

[10]王世慧,賈冠昕.利用SooPAT檢索專利信息[J].情報探索,2012(1):94-96.

HUANG Da was born in 1991.He is an M.S.candidate at School of Electronics Engineering and Computer Science,Peking University.His research interests include information retrieval and Web data mining.

黃達（1991—），男，廣東梅州人，北京大學信息科學技術學院碩士研究生，主要研究領域為信息檢索，網絡數據挖掘。

YAN Hongfei was born in 1973.He received the Ph.D.degree in computer science from Peking University in 2002.Now he is an associate professor at Peking University.His research interests include information retrieval and distributed computing.

閆宏飛（1973—），男，黑龍江哈爾濱人，2002年于北京大學獲得博士學位，現為北京大學副教授，主要研究領域為信息檢索，分布式計算。發表學術論文50多篇，作為負責人承擔的國家級項目包括自然科學基金、核高基項目、863計劃等。

Optimization for Collecting and Scoring Documents for Complex Boolean Query*

HUANG Da+,YAN Hongfei2
School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China
+Corresponding author:E-mail:huangda@net.pku.edu.cn

Although Boolean query has been proposed very early in information retrieval,most research on Boolean query focuses on homogeneous Boolean operation.Few researchers paid attention to complex Boolean query,while such query is used more and more frequently,e.g.in text-based recommendation.In order to make complex Boolean query execute more efficiently,this paper proposes a new strategy,DCQ(DAAT for complex query)algorithm, which is based on DAAT(document-at-a-time)framework.By comparing DCQ algorithm with the well-known open-source search engine,Lucene,it shows a promising improvement on performance.Besides,this paper proposes a method for performance regression,which can decide when to use DCQ algorithm accurately.Experiments show that the compound algorithm with performance regression is much better than the algorithm for collecting and scoring documents used in Lucene.

complex Boolean query;optimizing query;performance regression

A

：TP391

10.3778/j.issn.1673-9418.1511044

*The National Basic Research Program of China under Grant No.2014CB340400(國家重點基礎研究發展計劃(973計劃));the National Natural Science Foundation of China under Grant Nos.61272340,61272340(國家自然科學基金).

Received 2015-10,Accepted 2015-12.

CNKI網絡優先出版:2015-12-16,http://www.cnki.net/kcms/detail/11.5602.TP.20151216.1021.002.html