一個(gè)完整的搜索系統(tǒng) - God bless you - 博客園

一個(gè)完整的搜索系統(tǒng)

一個(gè)完整的搜索系統(tǒng)

層次型倒排索引

基于 前面非精確top K檢索 中的勝者表的思路，實(shí)際搜索系統(tǒng)可以建立多層索引結(jié)構(gòu)。

基本思路:建立多層索引，每層對(duì)應(yīng)索引詞項(xiàng)的重要性

查詢處理過(guò)程中，從最高層索引開(kāi)始。如果最高層索引已經(jīng)返回至少k (比如, k = 100)個(gè)結(jié)果，那么停止處理并將結(jié)果返回給用戶。如果結(jié)果 < k 篇文檔，那么從下一層繼續(xù)處理，直至索引用完或者返回至少k 個(gè)結(jié)果為止。

?

例子：兩層的系統(tǒng)
第1層: 所有標(biāo)題的索引
第2層: 文檔剩余部分的索引
標(biāo)題中包含查詢?cè)~的頁(yè)面相對(duì)于正文包含查詢?cè)~的頁(yè)面而言，排名更應(yīng)該靠前

注：很多人認(rèn)為，Google (2000/01)搜索質(zhì)量顯著高于其他競(jìng)爭(zhēng)者的一個(gè)主要原因是使用了多層次索引。(當(dāng)然還有PageRank、錨文本以及鄰近限制條件的使用)。

?

查詢?cè)~項(xiàng)的鄰近性限制

對(duì)于檢索中的查詢，特別是Web上的自由文本查詢來(lái)說(shuō)，用戶往往希望返回的文檔中與大部分或者全部查詢?cè)~項(xiàng)之間的距離比較近，因?yàn)檫@表明返回文檔中具有聚焦用戶查詢意圖的文本。

?

考慮一個(gè)由兩個(gè)或者多個(gè)查詢?cè)~項(xiàng)構(gòu)成的查詢t1, t2, . . . , tk。令文檔d中包含所有查詢?cè)~項(xiàng)的最小窗口大小為ω，其取值為窗口內(nèi)詞的個(gè)數(shù)。例如，假設(shè)某篇文檔僅僅包含一個(gè)句子The quality of mercy is not strained，那么查詢strained mercy 在此文檔中的最小窗口大小是4。直觀上講，ω的值越小，文檔d和查詢匹配程度更高。如果文檔中不包含所有的查詢?cè)~項(xiàng)，那么此時(shí)可以將ω設(shè)成一個(gè)非常大的數(shù)字。在計(jì)算時(shí)，還可以考慮各種可能的策略變化，比如在以單詞個(gè)數(shù)來(lái)計(jì)算窗口寬度ω時(shí)，可以不考慮停用詞的數(shù)目。

?

這種基于鄰近性（proximity）加權(quán)的評(píng)分函數(shù)已經(jīng)和純余弦相似度計(jì)算方法有所不同，而更接近于目前包括Google在內(nèi)的很多搜索引擎所提供并明顯在使用的“軟合取”（soft conjunctive）語(yǔ)義。

注：所謂“ 軟合取” 指的是在對(duì)一個(gè)包含多個(gè)詞項(xiàng)的查詢進(jìn)行檢索時(shí)，檢索中的文檔中只要出現(xiàn)大部分查詢?cè)~項(xiàng)即可，并不要求出現(xiàn)全部查詢?cè)~項(xiàng)。

?

查詢分析器

給定rising interest rates 之類的查詢，如何處理？更一般地，給定我們前面介紹過(guò)的各種能夠影響文檔得分的因素，如何對(duì)這些因素進(jìn)行組合？

上述問(wèn)題的答案當(dāng)然依賴于用戶數(shù)量、查詢分布及文檔集本身。通常情況下，會(huì)有一個(gè)查詢分析器（query parser）將用戶輸入的關(guān)鍵詞轉(zhuǎn)換成帶操作符的查詢，該查詢能夠基于底層的索引結(jié)構(gòu)進(jìn)行處理。有時(shí)，這種處理過(guò)程可能需要基于底層索引結(jié)果對(duì)多個(gè)查詢進(jìn)行處理，比如，查詢分析器可能會(huì)產(chǎn)生如下的一系列查詢。

1. 將用戶輸入的查詢字符串看成一個(gè)短語(yǔ)查詢。利用向量空間模型求解，此時(shí)輸入查詢向量是以rising interest rates 為基的1 維向量。
2. 如果包含短語(yǔ)rising interest rates 的文檔數(shù)目少于10 篇，那么會(huì)將原始查詢看成rising interest 和interest rates 兩個(gè)查詢短語(yǔ)，同樣通過(guò)向量空間方法來(lái)計(jì)算。
3. 如果結(jié)果仍然少于10 個(gè)，那么重新利用向量空間模型求解，這時(shí)候認(rèn)為3 個(gè)查詢?cè)~項(xiàng)之間是互相獨(dú)立的。

?

上面的每一步在調(diào)用的情況下都會(huì)產(chǎn)生一系列帶得分的文檔列表結(jié)果，而每個(gè)得分必須融合向量空間計(jì)算、靜態(tài)得分、鄰近度加權(quán)或其他可能的因素，特別地，一篇文檔可能在上述的多個(gè)步驟結(jié)果列表中同時(shí)出現(xiàn)。這時(shí)就要求有一個(gè)綜合得分函數(shù)能夠融合不同來(lái)源的得分。

?

綜上一個(gè)完整的搜索系統(tǒng)示意圖

一個(gè)完整的搜索系統(tǒng) - God bless you - 博客園