全文搜尋在機器學習領域裡算異數——它是 web 開發者幾乎一定會碰到的問題。客戶說「這裡加個搜尋框」,你寫一句 WHERE title LIKE %:query% 交差。起初一切正常,直到某天客戶回來說:「搜尋結果不對啊。」
其實程式沒壞,只是結果不合期待。一般使用者不會打精確關鍵字,模糊比對自然撈出一堆雜訊。於是你轉向全文索引,開啟 FULLTEXT、改用 MATCH() ... AGAINST(),問題暫時消失。但資料量繼續長大,資料庫也跟著變慢,最後你部署了 Lucene 驅動的搜尋叢集,又快又準。
然後你會開始好奇:Lucene 憑什麼這麼強?本文說明排名背後的核心概念,也就是 相關性評分。
對每一筆查詢,我們可以替每個文件算出一個「相關分數」,再用它排序,而不是用建立時間排序。最相關的排最前面,不管它是昨天還是三年前寫的。
計算方式有很多種,我們從最單純的統計取向說起。這類方法完全不需要理解語言本身,只統計詞的使用與匹配情形。它不關心一個詞是名詞還是動詞,也不關心詞義,只關心常見還是罕見。當查詢同時包含常見詞與罕見詞時,含罕見詞的文件應該拿到更高分,常見詞的權重則要壓低。
這套想法有兩個基本量測:詞頻(Term Frequency, TF)與逆向文件頻率(Inverse Document Frequency, IDF),合稱 TF-IDF。
TF 很好懂:某個詞在文件中出現幾次。除以文件總詞數可以正規化。一份 100 詞的文件裡 the 出現 8 次,TF 就是 8%,或寫成 0.08。
IDF 稍複雜:詞越罕見,值越高。算法是總文件數除以「含該詞的文件數」,取對數。
兩者相乘,得到該詞在該文件中的權重——它有多罕見,同時在文件裡出現得多頻繁?把查詢中每個關鍵字的 TF-IDF 加總,分數最高的文件就是最佳答案。
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、加入片語比對與欄位權重以改善結果品質,以及拼字建議與同義詞擴充。