搜索引擎-處理查詢

 我們從用戶的角度來看，用戶不關心什么索引結構是倒排還是簽名文件，也不需要知道相關排序算法。用戶提交了查詢，就需要獲取滿意的搜索結果。這個搜索結果就是搜索引擎是否提供有效的服務。

1.查詢流程

查詢流程圖：

1）用戶提交查詢

2）分析查詢

     查詢預處理：

     1. 一般過濾掉助詞或者標點符號之類，如中文的“的”，英文'The' . 另外對中文做分詞處理獲取檢索組合，

     2）對于中文等搜索，需要分詞。

     3）單詞去重等。但是不同的搜索引起處理方式可能不一樣。

    查詢詞格式化：

    把詞匯轉換成wordID

3)  根據查詢詞從倒排索引庫獲取匹配的檢索結果

4）根據特定相關度排序算法進行排序，生成最后搜索結果。

當然了，這個流程還會涉及到緩存的過程。

我們主要說明第3步和第4步的內容：

       第3步是基于倒排索引的查詢處理。即對已生成的倒排索引，處理其中的數據產生查詢結果。

      第4步就是相關度排序算法了，由相關檢索理論模型來決定。

      搜索引擎的信息查詢一般都是遵循一定的理論模型，最常用的主要有布爾模型，向量模型，概率檢索模型，語言模型，機器學習模型等。在搜索引擎中，需要考慮更多的因素才能為用戶提供更符合的結果，廣泛的采用了向量模型。實際的搜索引擎查詢實現方法一般采用了向量檢索模型和布爾模型相結合的方式。

       目前機器學習模型逐漸流行起來。前baidu科學家 張棟是這方面的專家（weibo：http://weibo.com/machinelearning）。據說360推出的搜索有兩套系統，一套是360搜索團隊研發的，另外一套是張棟研發的，張棟研發的這套搜索系統的檢索模型應該是基于機器學習的。

      這檢索模型后面在做介紹。我們這里簡單說明查詢處理機制。

2. 基于索引的查詢處理

  目前有兩種常見的查詢處理機制和跳躍指針的結構化查詢優化：

   2.1 一次一文檔 (Document at a time)

   2.2 一次一單詞 (Term at a time)

   2.3 結構化查詢，即跳躍指針。

   下面詳細說明這些機制。舉個例子：

    假設用戶輸入“搜索引擎 技術” 而“搜索引擎”這個Term對應的倒排列表文檔 DocID一次為{1,3,4},“技術” Term對應的倒排列表中文檔DocID列表為{1,2,4} 我們從中可以看出同時包含整個查詢的文檔是{1,4}.

3. 一次一文檔 (Document at a time)

        搜索引擎接收到用戶的査詢后，首先將兩個單詞的倒排列表從磁盤讀入內存。所謂的一次一文檔，就是以倒排列表中包含的文檔為單位每次將其中某個文檔與査詢的最終相似性得分 計算完畢，然后開始計算另外一個文檔的最終得分，直到所有文檔的得分都計算完畢為止。

        圖3-1是一次一文檔的計算機制示意圖，為了便于理解，圈中對于兩個單詞的倒排列表 中的公共文檔（文檔1和文檔4)進行了對齊。圖中虛線箭頭標出了查詢處理計算的行進方向。

                                                          圖3-1 —次一文檔

處理流程：                                                                           

       1)  對于文檔1來說，因為兩個單詞的倒排列表中都包含這個文檔，所以可以根據各自的TF和IDF等參數計算文檔和查詢單詞的相似性（具體相似性計算有很多種，此處對相似性計算做了簡化處理，TF * IDF就是分數)，之后將兩個分數相加獲得了文檔1和用戶查詢的相似性得分: IDF=2, TF=2 , Score=4。
       2)  隨后搜索系統開始處理文檔2， 因為文檔2只在"技術"這個詞匯的倒排列表中，所以 根據相應的TF和IDF計算相似性后，即可得出文擋2和用戶查詢的相似性得分。
       3)  用類似的方 法依次處理文檔3和文檔4。
       4)  所有文檔都計算完畢后，根據文檔得分進行大小排序，輸出得分 最聞的K個文檔作為搜索結果輸出，即完成了一次用戶查詢的響應。 

            結果的排序：D4，D1，D3，D4 

       因為搜索系統的輸出結果往往是限定個數的，比如指定輸出10個結果，所以在實際實現 一次一文檔方式時，不必保存所有文檔的相關性得分，而只需要在內存中維護一個大小為K 的優先級別隊列，用來保存目前計算過程中得分最高的k個文檔即可，這樣可以節省內存和計 算時間，一般會采用根堆數據結構來實現這個優先級別隊列，在計算結束時，按照得分大小輸出就可以實現搜索目標。

4. 一次一單詞 (Term at a time)

       一次一單詞的計算過程與一次一文檔不同：
        一次一文檔可以直觀理解為在單詞一文檔矩陣中，以文檔為單位，縱向進行分數累計，之后移動到后續文檔接著計算，即計算過程是"先縱 向再橫向"；
       而一次一單詞則是來取"先橫向再縱向"的方式，即首先將某個單詞對應的倒排 列表中的每個文檔ID都計算一個部分相似性得分，也就是說，在單詞一文檔矩陣中首先進行 橫向移動，在計算完畢某個單詞倒排列表中包含的所有文檔后，接著計算下一個單詞倒排列表 中包含的文檔ID， 即進行縱向計算，如果發現某個文檔m已經有了得分，則在原先得分基礎 上進行累加。當所有單詞都處理完畢后，每個文檔最終的相似性得分計算結束，之后按照大小 排序，輸出得分最高的乂個文檔作為搜索結果。
    圖4-2是一次一單詞的運算機制圖示說明，圖中虛線箭頭指示出了計算的行進方向，為了保存數據，在內存中使用哈希表來保存中間結果及最終計算結果。

                            圖4-2是一次一單詞

處理流程：           
       1）搜索系統首先對包含"搜索引擎"的所有文檔進行部分得分計算，比如對于文檔1， 可以根據TF和1DF等參數計算這個文檔對"搜索引擎"這個查詢詞的相似性得分，之后根據文檔ID在哈希表中查找，并把相似性得分保存在哈希表中。
       2）依次對文檔3和文檔4進行類似的計算。
       3）當"搜索引擎"這個單詞 的所有文檔都計算完畢后，開始計算"技術"這個單詞的相似性得分，對于文檔1來說，同樣 地，根據TF和IDF等參數計算文檔1和"技術"這個單詞的相似性得分，之后查找哈希表， 發現文檔1已經存在得分（"搜索引擎"這個單詞和文檔1的相似性得分)，則將哈希表對應的 得分和剛剛計算出的得分相加作為最終得分，并更新哈希表中文檔1對應的得分分值，獲得了 文檔1和用戶查詢最終的相似性得分，
       4）之后以類似的方法，依次計算文檔2和文檔4的得分。 
       5）當全部計算完畢時，哈希表中存儲了每個文檔和用戶査詢的最終相似性得化排序后輸出得分 最高的K個文檔作為搜索結果。

轉自：http://blog.csdn.net/hguisu/article/details/7978451