DIV CSS 佈局教程網

全文搜尋如何排序:從 TF-IDF 到 Okapi BM25 的實作解析
編輯:JavaScript綜合知識     

全文搜尋在機器學習領域裡算異數——它是 web 開發者幾乎一定會碰到的問題。客戶說「這裡加個搜尋框」,你寫一句 WHERE title LIKE %:query% 交差。起初一切正常,直到某天客戶回來說:「搜尋結果不對啊。」

其實程式沒壞,只是結果不合期待。一般使用者不會打精確關鍵字,模糊比對自然撈出一堆雜訊。於是你轉向全文索引,開啟 FULLTEXT、改用 MATCH() ... AGAINST(),問題暫時消失。但資料量繼續長大,資料庫也跟著變慢,最後你部署了 Lucene 驅動的搜尋叢集,又快又準。

然後你會開始好奇:Lucene 憑什麼這麼強?本文說明排名背後的核心概念,也就是 相關性評分。

什麼是相關性

對每一筆查詢,我們可以替每個文件算出一個「相關分數」,再用它排序,而不是用建立時間排序。最相關的排最前面,不管它是昨天還是三年前寫的。

計算方式有很多種,我們從最單純的統計取向說起。這類方法完全不需要理解語言本身,只統計詞的使用與匹配情形。它不關心一個詞是名詞還是動詞,也不關心詞義,只關心常見還是罕見。當查詢同時包含常見詞與罕見詞時,含罕見詞的文件應該拿到更高分,常見詞的權重則要壓低。

這套想法有兩個基本量測:詞頻(Term Frequency, TF)與逆向文件頻率(Inverse Document Frequency, IDF),合稱 TF-IDF。

TF-IDF

TF 很好懂:某個詞在文件中出現幾次。除以文件總詞數可以正規化。一份 100 詞的文件裡 the 出現 8 次,TF 就是 8%,或寫成 0.08。

IDF 稍複雜:詞越罕見,值越高。算法是總文件數除以「含該詞的文件數」,取對數。

兩者相乘,得到該詞在該文件中的權重——它有多罕見,同時在文件裡出現得多頻繁?把查詢中每個關鍵字的 TF-IDF 加總,分數最高的文件就是最佳答案。

Okapi BM25:兩個關鍵調整

TF-IDF 堪用,但不完美。BM25 在它之上加了兩個參數 k1 與 b,分別對應「詞頻飽和」與「欄位長度正規化」。

詞頻飽和:想像兩篇長度相近、都在談棒球的文件,而語料庫中其他文件幾乎不提棒球,所以「棒球」的 IDF 很高。其中一篇用了 40 次「棒球」,另一篇用了 80 次。真的該讓後者得分加倍嗎?既然兩篇都在大量討論同一主題,出現 40 次和 80 次的意義差別不大——老實說,30 次就該到頂了。

原始 TF-IDF 沒有這個「到頂」的概念。參數 k1 控制飽和的速度,一般落在 1.2 到 2.0 之間,數值越低越快飽和。

欄位長度正規化:把文件長度換算到全語料庫的平均長度上。對單欄位集合來說,這讓長短不一的文件能在同一基準上比較;對「標題 + 內文」這類多欄位集合更有意義,因為標題裡出現一次某詞的分量,遠大於內文裡出現一次。參數 b 介於 0 與 1,1 表示完全正規化,0 表示不做。

分詞:一切的前置作業

在算分之前,得先把文字切成詞元(token)。這一步做了三件事,都是為了降低雜訊:

BM25.Tokenize = function (text) {
  text = text
    .toLowerCase()
    .replace(/[^\w]/g, ' ')
    .replace(/\s+/g, ' ')
    .trim()
    .split(' ')
    .map(function (a) { return stemmer(a); });

  // 過濾停用詞
  var out = [];
  for (var i = 0, len = text.length; i < len; i++) {
    if (stopStems.indexOf(text[i]) === -1) {
      out.push(text[i]);
    }
  }
  return out;
};

轉小寫、跑 Porter 詞幹演算法(讓 walking 與 walk 視為同義)、去掉 the 這類停用詞。三招都在削減雜訊、提高匹配率。

建立索引

BM25.prototype.addDocument = function (doc) {
  if (typeof doc.id === 'undefined') {
    throw new Error(1000, 'ID is a required property of documents.');
  }
  if (typeof doc.body === 'undefined') {
    throw new Error(1001, 'Body is a required property of documents.');
  }

  var tokens = BM25.Tokenize(doc.body);
  var _terms = {};
  var docObj = { id: doc.id, tokens: tokens, body: doc.body };

  docObj.termCount = tokens.length;

  this.totalDocuments++;
  this.totalDocumentTermLength += docObj.termCount;
  this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments;

  // 先統計各詞出現次數
  for (var i = 0, len = tokens.length; i < len; i++) {
    var term = tokens[i];
    if (!_terms[term]) _terms[term] = { count: 0, freq: 0 };
    _terms[term].count++;
  }

  // 再算 TF,同時更新 IDF 的 n(含此詞的文件數)
  var keys = Object.keys(_terms);
  for (var i = 0, len = keys.length; i < len; i++) {
    var term = keys[i];
    _terms[term].freq = _terms[term].count / docObj.termCount;

    if (!this.terms[term]) {
      this.terms[term] = { n: 0, idf: 0 };
    }
    this.terms[term].n++;
  }

  docObj.terms = _terms;
  this.documents[docObj.id] = docObj;
};

這段程式維護兩個核心資料結構:

  • this.documents:文件庫。保存原始內文、長度,以及每個詞的次數與頻率。有了它,能在 O(1) 時間回答「文件 #3 裡 walk 出現幾次?」
  • this.terms:語料庫詞表。記錄每個詞出現在幾份文件裡。同樣 O(1) 回答「walk 出現在哪些文件中?」

IDF 的計算被刻意獨立出來,因為它得掃過整個詞表,跑起來慢:

BM25.prototype.updateIdf = function () {
  var keys = Object.keys(this.terms);
  for (var i = 0, len = keys.length; i < len; i++) {
    var term = keys[i];
    var num = (this.totalDocuments - this.terms[term].n + 0.5);
    var denom = (this.terms[term].n + 0.5);
    this.terms[term].idf = Math.max(Math.log10(num / denom), 0.01);
  }
};

實務上的做法是:批次建立索引時先把這行呼叫註解掉,全部寫完再跑一次。Math.max(..., 0.01) 是為了避免對數出現負值或零。

查詢與排序

BM25.prototype.search = function (query) {
  var queryTerms = BM25.Tokenize(query);
  var results = [];

  var keys = Object.keys(this.documents);
  for (var j = 0, nDocs = keys.length; j < nDocs; j++) {
    var id = keys[j];
    this.documents[id]._score = 0;

    for (var i = 0, len = queryTerms.length; i < len; i++) {
      var queryTerm = queryTerms[i];

      // 從沒見過這個詞,直接跳過
      if (typeof this.terms[queryTerm] === 'undefined') continue;
      // 這個文件沒有這個詞,貢獻為 0
      if (typeof this.documents[id].terms[queryTerm] === 'undefined') continue;

      // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength))
      var idf = this.terms[queryTerm].idf;
      var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1);
      var denom = this.documents[id].terms[queryTerm].count +
        (this.k1 * (1 - this.b +
          (this.b * this.documents[id].termCount / this.averageDocumentLength)));

      this.documents[id]._score += idf * num / denom;
    }

    if (!isNaN(this.documents[id]._score) && this.documents[id]._score > 0) {
      results.push(this.documents[id]);
    }
  }

  results.sort(function (a, b) { return b._score - a._score; });
  return results.slice(0, 10);
};

流程是:分詞查詢 → 遍歷文件 → 對每個查詢詞套用 BM25 公式並累加 → 篩掉 0 分 → 降冪排序 → 取前十名。IDF 與 TF 都是索引階段預先算好的,查詢時只剩四則運算。

還缺什麼

這份實作有個明顯的弱點:查詢時遍歷所有文件。文件量小時無所謂,量一大就會崩。真正的解法是反向索引——不掃文件,而是拿查詢詞直接查到「哪些文件含這個詞」的清單,只對這些候選文件計分。這是搜尋引擎效能的關鍵所在,也是後續要談的主題。

其他值得改進的方向還包括:索引的增量更新與批次化、以 Web Worker 把索引搬到背景執行緒避免凍結 UI、加入片語比對與欄位權重以改善結果品質,以及拼字建議與同義詞擴充。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved