文章出處

前言

對于跳表，我想大家都不陌生吧，這里不多解釋，感興趣的小伙伴可以看我的這篇文章：http://www.cnblogs.com/haolujun/archive/2012/12/24/2830683.html。這段時間在做我們拍搜的優化，今天我就講講我是如何用跳表優化檢索系統的。

搜索引擎的夾角余弦計算

都知道，搜索引擎利用夾角余弦計算query與文檔的相似度，感興趣的小伙伴可以看我的這篇文章：http://www.cnblogs.com/haolujun/archive/2013/01/08/2847503.html，這里面需要計算兩個向量的余弦值。

假設查詢向量為：$ Q = [q_{1},q_{2},......,q_{n}] $
假設文檔向量為：$ D = [d_{1},d_{2},......,d_{n}] $

query與文檔的相似度為：$ sim(Q,D) = \frac{QD}{|Q||D|} $ 。這里面需要Q和D模長相乘做分母，對應分量相乘之和做分子。

模長的計算

對于query可以在每次查詢之前做統一的預處理，在預處理過程中計算模長；對于文檔，不能每次查詢都計算一遍模長，這樣效率很低，可以事先在建立索引的時候計算模長并保存。

向量相乘

在搜索引擎檢索過程中，首先需要對query進行分詞并得到查詢向量，之后我們用分出的詞從倒排表中拉取文檔，不熟悉倒排表的小伙伴可以看這篇文章：http://www.cnblogs.com/haolujun/archive/2013/01/06/2847510.html。通過倒排拉取出來的只是文檔的ID，而文檔本身包含的內容其實是以正排的方式存儲的：即key=文檔ID，$value=(word_{1}, word_{2}, ....word_{n}) $，實際上為了節省存儲空間，正排只存儲該文檔中出現過的詞。而今天的向量相乘就是利用正排與query進行兩個集合的求交計算（向量相乘只對同時出現在query以及文檔中的詞進行計算，其它的都計為0），那么這就引出一個新問題，如何求兩個集合的交集呢？聰明的小伙伴肯定想到了解決辦法：對Q和D分別按照字典序排序，之后求兩個有序列表的交集可以在線性時間內完成，示例代碼如下：

int i = 0, j = 0;
double sum = 0.0;
while(i < len_q && j < len_doc) {
    if(q[i] < d[j]) {
        i++; 
    } else if(q[i] > d[j]) {
        j++;
    } else {
        sum += sim(q[i], d[j]); 
    }
}

但是，還能再優化這個代碼么？答案是肯定的，那就是利用跳表。

對于搜索引擎來說，通常query較短，而文檔較長，我們估計排完序的文檔序列中會有一大段一大段的詞都不在query中，可以直接跳過這些段而不用一一遍歷，這就啟發我們可以用跳表進行加速，優化代碼如下：

double sum = 0.0;
int step = ceil(sqrt(len_doc)), i = 0, j = 0;
while(i < len_q && j < len_doc) {
   if(q[i] < d[j]) {
      int k = (j - step + 1) < 0 ? 0 : j - step + 1;
      while(k <= j && d[k] < q[i]) k++;
      if(d[k] == q[i]) {
        sum += sim(i, j); j = k + 1;  i++;
      } else {
        j = k; i++;
      }
    } else if(q[i] > d[j]) {
      j = j + step < len_doc ? j + step : j + 1;
    } else {
      sum += sim(i, j); 
      ++i;
      j = j + step < len_doc ? j + step : j + 1;
    }
  }
}

我們在這里選擇步長為 $ \sqrt[]{len_{doc}} $只是表示一種理論指導，實際中還需要不斷測試不同的步長從而找到實際最優解。

當然，優化這個問題并不一定用跳表，如果內存足夠大，我們可以為每個文檔建立哈希或者map，這樣只需用O(1)或者 O(log(len_doc))時間判斷文檔中是否包含一個詞。