[發(fā)明專利]用于大文檔索引的匹配漏斗

有效

• 申請?zhí)枺?/td>: 201110373395.6
• 申請日: 2011-11-22
• 公開（公告）號: CN102567461A
• 公開（公告）日: 2012-07-11
• 發(fā)明（設計）人: K.M.里斯維克;M.霍普克洛夫特;J.G.貝內特;K.卡爾亞納拉曼;T.基林比;C.P.沃特斯;J.O.彼得森
• 申請（專利權）人: 微軟公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 黃維;劉鵬

背景技術

因特網(wǎng)上可用的信息和內容量繼續(xù)迅速增長。考慮到大量信息，已開發(fā)搜索引擎來便于搜索電子文檔。特別地，用戶可通過輸入包括用戶可能感興趣的一個或多個措詞的搜索查詢而搜索信息和文檔。在從用戶接收搜索查詢之后，搜索引擎基于該搜索查詢來識別文檔和/或網(wǎng)頁。由于其效用，網(wǎng)絡搜索，即找到針對用戶發(fā)布的搜索查詢的相關網(wǎng)頁和文檔的過程，可以說現(xiàn)在已經(jīng)變成了因特網(wǎng)上最流行的服務。

搜索引擎通過爬取（crawl）文檔和在搜索索引中對關于文檔的信息編索引來操作。當接收到搜索查詢時，搜索引擎采用搜索索引來識別與搜索查詢相關的文檔。以此方式使用搜索索引允許快速地檢索針對查詢的信息。在無搜索索引的情況下，搜索索引將需要搜索文檔的文集以尋找相關結果，這將花費不可接受量的時間。

隨著因特網(wǎng)繼續(xù)發(fā)展，可爬取且在搜索索引中編索引的可搜索文檔的數(shù)量變得極大。因此，搜索引擎對關于所有網(wǎng)絡文檔的信息編索引是不可行的。舉例而言，將需要過量硬件存儲。此外，從極大索引檢索結果所需的處理時間將是不可接受的。盡管如此，搜索引擎力圖對盡可能多的文檔編索引以提供任何查詢的搜索結果，同時節(jié)省成本且能在終端用戶可接受的時間量內提供相關結果。

發(fā)明內容

提供此發(fā)明內容以便以簡化形式引入概念的選擇，這些概念將在具體實施方式中詳述。此發(fā)明內容不預期標識要保護的主題的關鍵特征或基本特征，也不預期用作確定所保護的主題范圍的輔助。

本發(fā)明的實施例涉及一種通過在各個階段評估和修剪（prune）候選文檔來響應于搜索查詢提供搜索結果的分階段過程。最初，可通過識別文檔中的義原（atom）和預先計算文檔/義原對的評分來生成搜索索引。當接收到搜索查詢時，可通過識別搜索查詢中的義原和基于所識別的義原生成重新闡述的查詢而重新闡述該搜索查詢。搜索索引可使用重新闡述的查詢來查詢以識別匹配的文檔。可使用簡化的評分函數(shù)和存儲于索引中的預先計算的評分來生成匹配文檔的初步評分。可基于初步評分來保留文檔的修剪集合。在修剪集合中的文檔然后可使用全排序算法來評估以生成排序文檔集合，其用于生成響應于搜索查詢而返回的搜索結果。

附圖說明

將參看附圖在下文中詳細地描述本發(fā)明，在附圖中：

圖1是適用于實施本發(fā)明的實施例的示例性計算環(huán)境的方塊圖；

圖2是示出根據(jù)本發(fā)明實施例的用于檢索排序文檔集合以減少文檔候選者的智能漏斗（funnel）的示意圖；

圖3是其中可采用本發(fā)明的實施例的示例性系統(tǒng)的方塊圖；

圖4是示出根據(jù)本發(fā)明實施例響應于搜索查詢返回搜索結果的分階段過程的方法的流程圖；

圖5是示出根據(jù)本發(fā)明實施例的用于在預先計算/編索引階段期間生成搜索索引的方法的流程圖；

圖6是示出根據(jù)本發(fā)明實施例的用于在匹配時期識別匹配文檔的初始集合的方法的流程圖；以及

圖7是根據(jù)本發(fā)明實施例的用于在修剪時期從匹配文檔的初始集合修剪文檔的方法的流程圖。

具體實施方式

在本文中具體地描述了本發(fā)明的主題以滿足法定要求。但是，描述本身不預期限制本專利的范圍。而是，本發(fā)明人設想到所要求保護的主題也可以以其它方式實施，以結合其它目前或未來的技術包括不同步驟或類似于本文中所述步驟的步驟的組合。此外，盡管可在本文中使用措詞“步驟”和/或“方塊”來意味著所采用方法的不同要素，但措詞不應理解為暗示本文所公開的各種步驟之間的任何特定次序，除非且除了當明確地描述了各個步驟的次序時。

本發(fā)明的實施例提供編索引和搜索過程，其允許以節(jié)省成本的方式對大量文檔編索引和搜索且其滿足嚴格的延遲約束。根據(jù)本發(fā)明的實施例，采用以多個階段評估和修剪掉文檔候選者的過程。在概念上，該過程看起來類似漏斗，因為經(jīng)過這些階段，隨著分析變得更復雜，評估且修剪掉文檔候選者。隨著過程繼續(xù)經(jīng)過這些階段，應用花費更多的計算且候選文檔的數(shù)量減少多個數(shù)量級。在這些階段中的每個階段應用不同策略來允許快速且高效的方案來使得從大量文檔返回搜索結果。此外，在每個階段所用的策略可設計成補充在其它階段所用的策略以使得該過程更高效。