DIV CSS 佈局教程網

用 JavaScript 實作全文搜索的相關度評分機制
編輯:JavaScript基礎知識     

全文搜索與機器學習領域的大多數問題不同,它是 Web 程式設計師在日常工作中經常遇到的課題。客戶可能要求你在某處提供一個搜尋框,於是你就寫了一個類似 WHERE title LIKE %:query% 的 SQL 語句來實現搜尋。一開始這沒問題,直到某天客戶跑來跟你說:「搜尋出錯啦!」

當然,實際上搜尋並沒有「出錯」,只是結果並不是客戶想要的。一般用戶並不清楚如何做精確匹配,所以得到的結果品質很差。為了解決問題,你決定改用全文搜索。經過一陣枯燥的學習,你開啟了 MySQL 的 FULLTEXT 索引,並使用更高級的查詢語法,如「MATCH() … AGAINST()」。

好了,問題解決,完結撒花!資料庫規模不大的時候確實沒問題了。但當你的資料越來越多,你會發現資料庫也越來越慢——MySQL 並不是一個非常好用的全文搜索工具。於是你決定改用 ElasticSearch,重構程式碼,並部署 Lucene 驅動的全文搜索叢集。你會發現它運作得非常好,又快又準。

這時你不禁會想:為什麼 Lucene 這麼厲害呢?本篇文章(主要介紹 TF-IDF、Okapi BM-25 與普通的相關性評分)和下一篇文章(主要介紹索引)將為你講述全文搜索背後的基本概念。

相關性

對每一個搜尋查詢,我們很容易為每個文件定義一個「相關分數」。當用戶進行搜尋時,我們就能用相關分數來排序,而不是用文件出現的時間來排序。這樣,最相關的文件會排在第一個,無論它是多久之前建立的(當然,有的時候文件的建立時間也是有關的)。

計算文字之間相關性的方法有很多種,但我們要從最簡單的、基於統計的方法說起。這種方法不需要理解語言本身,而是透過統計詞語的使用、匹配,以及基於文件中特有詞普及率的權重等情況,來決定「相關分數」。

這個演算法不關心詞語是名詞還是動詞,也不關心詞語的意義。它唯一關心的是哪些是常用詞、哪些是稀有詞。如果一個搜尋語句中包含常用詞和稀有詞,你最好讓包含稀有詞的文件評分高一些,同時降低常用詞的權重。

這個演算法被稱為 Okapi BM25。它包含兩個基本概念:詞語頻率(term frequency),簡稱詞頻(TF);以及文件頻率倒數(inverse document frequency),簡寫為 IDF。把它們放在一起,就被稱為「TF-IDF」,這是一種統計學測度,用來表示一個詞語(term)在文件中有多重要。

TF-IDF

詞語頻率(Term Frequency),簡稱 TF,是一個很簡單的度量標準:一個特定的詞語在文件中出現的次數。你可以把這個值除以該文件中詞語的總數,得到一個分數。例如文件中有 100 個詞,「the」這個詞出現了 8 次,那麼「the」的 TF 就是 8 或 8/100 或 8%(取決於你想怎麼表示它)。

逆向文件頻率(Inverse Document Frequency),簡稱 IDF,要複雜一些:一個詞越稀有,這個值越高。它由總文件數目除以包含該詞語之文件的數目,再將得到的商取對數得到。越是稀有的詞,越會產生高的 IDF。

如果你把這兩個數字相乘(TF*IDF),就會得到一個詞語在文件中的權重。「權重」的定義是:這個詞有多稀有,並且在文件中出現得多麼頻繁?

你可以把這個概念用於文件的搜尋查詢。對於查詢中的每個關鍵字,計算它們的 TF-IDF 分數並相加,得分最高的就是與查詢語句最符合的文件。

很酷吧!

Okapi BM25

上述演算法是一個可用的演算法,但並不太完美。它給出了一個基於統計學的相關分數演算法,我們還可以進一步改進它。

Okapi BM25 是到目前為止被認為最先進的排名演算法之一(所以它被 ElasticSearch 採用)。Okapi BM25 在 TF-IDF 的基礎上增加了兩個可調參數,k1 和 b,分別代表「詞語頻率飽和度(term frequency saturation)」和「欄位長度規約」。這是什麼意思呢?

為了直觀地理解「詞語頻率飽和度」,請想像兩篇差不多長度、討論棒球的文章。另外,我們假設所有文件(除去這兩篇)並沒有多少與棒球相關的內容,因此「棒球」這個詞將具有很高的 IDF——它極稀少而且很重要。這兩篇文章都在討論棒球,而且都花了大量篇幅談論它,但其中一篇比另一篇更多地使用了「棒球」這個詞。那麼在這種情況下,是否一篇文章真的要比另一篇相差很多分數呢?既然兩篇文件都在大篇幅討論棒球,那麼「棒球」這個詞出現 40 次還是 80 次都一樣——事實上,30 次就該封頂啦!

這就是「詞語頻率飽和度」。原生的 TF-IDF 演算法沒有飽和的概念,所以出現 80 次「棒球」的文件要比出現 40 次的得分高一倍。有些時候這是我們所希望的,但有時候我們並不希望這樣。

此外,Okapi BM25 還有個 k1 參數,它用於調節飽和度變化的速率。k1 參數的值一般介於 1.2 到 2.0 之間,數值越低則飽和的過程越快速(意味著上面兩篇文件會有相同的分數,因為它們都包含大量的「棒球」這個詞語)。

欄位長度歸約(Field-length normalization)會把文件的長度歸約化到全部文件的平均長度上。這對於單欄位集合(single-field collections)很有用,可以將不同長度的文件統一到相同的比較條件上;對於雙欄位集合(例如「title」和「body」)則更有意義,它同樣可以將 title 和 body 欄位統一到相同的比較條件上。欄位長度歸約用 b 來表示,它的值在 0 和 1 之間,1 意味著全部歸約化,0 則不進行歸約化。

演算法實作

在 Okapi BM25 的維基百科條目中你可以了解 Okapi 演算法的公式。既然都知道了式子中的每一項是什麼,理解起來肯定很容易,所以我們就不提公式,直接進入程式碼:

 BM25.Tokenize = function(text) { text = text .toLowerCase() .replace(/\W/g, ' ') .replace(/\s+/g, ' ') .trim() .split(' ') .map(function(a) { return stemmer(a); }); // Filter out stopStems var out = []; for (var i = 0, len = text.length; i < len; i++) { if (stopStems.indexOf(text[i]) === -1) { out.push(text[i]); } } return out; }; 

我們定義了一個簡單的靜態方法 Tokenize(),目的是把字串解析成 tokens 的陣列。就這樣,我們把所有 tokens 轉為小寫(為了減少熵),執行 Porter Stemmer 演算法來降低熵的量、同時提高匹配程度(讓「walking」和「walk」匹配為相同),並過濾掉停用詞(很普通的詞)以進一步降低熵值。

 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.'); }; // Raw tokenized list of words var tokens = BM25.Tokenize(doc.body); // Will hold unique terms and their counts and frequencies var _terms = {}; // docObj will eventually be added to the documents database var docObj = {id: doc.id, tokens: tokens, body: doc.body}; // Count number of terms docObj.termCount = tokens.length; // Increment totalDocuments this.totalDocuments++; // Readjust averageDocumentLength this.totalDocumentTermLength += docObj.termCount; this.averageDocumentLength = this.totalDocumentTermLength / this.totalDocuments; // Calculate term frequency // First get terms count 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++; } // Then re-loop to calculate term frequency. // We'll also update inverse document frequencies here. var keys = Object.keys(_terms); for (var i = 0, len = keys.length; i < len; i++) { var term = keys[i]; // Term Frequency for this document. _terms[term].freq = _terms[term].count / docObj.termCount; // Inverse Document Frequency initialization if (!this.terms[term]) { this.terms[term] = { n: 0, // Number of docs this term appears in, uniquely idf: 0 }; } this.terms[term].n++; }; // Calculate inverse document frequencies // This is SLOWish so if you want to index a big batch of documents, // comment this out and run it once at the end of your addDocuments run // If you're only indexing a document or two at a time you can leave this in. // this.updateIdf(); // Add docObj to docs db docObj.terms = _terms; this.documents[docObj.id] = docObj; }; 

addDocument() 基本上建立並維護了兩個類似的資料結構:this.documents 和 this.terms。

this.documents 是一個保存著所有文件的資料庫,它保存著文件的全部原始文字、長度資訊,以及一個清單,清單裡保存著文件中所有詞語及其數量與出現頻率。使用這個資料結構,我們可以輕鬆而快速(是的,非常快速,只需時間複雜度為 O(1) 的雜湊表查詢時間)回答這樣的問題:在文件 #3 中,「walk」這個詞語出現了多少次?

我們還使用了另一個資料結構 this.terms,它表示語料庫中的所有詞語。透過這個資料結構,我們可以在 O(1) 時間內回答:'walk' 這個詞在多少個文件中出現過?它們的 id 是什麼?

最後,我們記錄了每個文件的長度,以及整個語料庫中文文件的平均長度。

注意,上面的程式碼中 idf 被初始化為 0,而且 updateIdf() 方法被註釋掉了。這是因為這個方法運行得非常慢,並且只需在建立索引之後運行一次即可。既然運行一次就能滿足需求,就沒必要運行 5000 次。先把它註釋掉,然後在大批量索引操作之後運行,就能節省很多時間。以下是這個函式的程式碼:

 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); } }; 

這是一個非常簡單的函式,但由於它需要遍歷整個語料庫中的所有詞語並更新所有詞語的值,就導致它運行得有點慢。這個方法採用了逆向文件頻率(inverse document frequency)的標準公式(你可以在 Wikipedia 上找到),也就是由總文件數目除以包含該詞語之文件的數目,再將商取對數得到。我做了一些修改,讓返回值一直大於 0。

 BM25.prototype.search = function(query) { var queryTerms = BM25.Tokenize(query); var results = []; // Look at each document in turn. There are better ways to do this with inverted indices. var keys = Object.keys(this.documents); for (var j = 0, nDocs = keys.length; j < nDocs; j++) { var id = keys[j]; // The relevance score for a document is the sum of a tf-idf-like // calculation for each query term. this.documents[id]._score = 0; // Calculate the score for each query term for (var i = 0, len = queryTerms.length; i < len; i++) { var queryTerm = queryTerms[i]; // We've never seen this term before so IDF will be 0. // Means we can skip the whole term, it adds nothing to the score // and isn't in any document. if (typeof this.terms[queryTerm] === 'undefined') { continue; } // This term isn't in the document, so the TF portion is 0 and this // term contributes nothing to the search score. if (typeof this.documents[id].terms[queryTerm] === 'undefined') { continue; } // The term is in the document, let's go. // The whole term is : // IDF * (TF * (k1 + 1)) / (TF + k1 * (1 - b + b * docLength / avgDocLength)) // IDF is pre-calculated for the whole docset. var idf = this.terms[queryTerm].idf; // Numerator of the TF portion. var num = this.documents[id].terms[queryTerm].count * (this.k1 + 1); // Denomerator of the TF portion. var denom = this.documents[id].terms[queryTerm].count + (this.k1 * (1 - this.b + (this.b * this.documents[id].termCount / this.averageDocumentLength))); // Add this query term to the score 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); }; 

最後,search() 方法遍歷所有文件,給出每個文件的 BM25 分數,然後按由大到小的順序排序。當然,在搜尋過程中遍歷語料庫中的每個文件實在不明智,這個問題會在 Part Two(反向索引與效能)中得到解決。

上面的程式碼已經做了很好的註釋,其要點如下:為每個文件和每個詞語計算 BM25 分數。詞語的 idf 分數已預先計算好,使用時只需查詢即可;詞語頻率作為文件屬性的一部分也已預先計算好;之後只需要簡單的四則運算。最後給每個文件加上一個臨時變數 _score,然後根據 score 做降序排列並返回前 10 個結果。

示例、原始碼與後續計劃

上面的示例還有很多優化的空間,我們將在「全文搜索」的第二部分中說明,歡迎繼續收看。後續將涵蓋:

  • 反向索引與快速搜索
  • 快速索引
  • 更好的搜尋結果

為了這個演示,我寫了一個小型的維基百科爬蟲,爬到相當多(85000)維基百科文章的第一段。由於索引到所有 85K 文件需要 90 秒左右,在我的電腦上我已經削減了一半,不想讓你們僅僅為了一個簡單的全文演示而浪費筆記型電腦的電量。

因為索引是一個繁重的、模組化的 CPU 操作,我把它當成一個 Web Worker,運行在一個背景執行緒上——你可以在這裡找到完整的原始碼,也會發現詞幹演算法與我的停用詞清單的程式碼參考。至於程式碼授權,一如既往地為教育目的免費,而不用於任何商業目的。

最後是演示。一旦索引完成,嘗試尋找隨機的東西和短語吧,維基百科會知道的。注意,只有 40000 段的索引,所以你可能要嘗試一些新話題。

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