JavaScript全文搜索如何實現

本文小編為大家詳細介紹“JavaScript全文搜索如何實現”，內容詳細，步驟清晰，細節處理妥當，希望這篇“JavaScript全文搜索如何實現”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。

相關性

對每一個搜索查詢，我們很容易給每個文檔定義一個“相關分數”。當用戶進行搜索時，我們可以使用相關分數進行排序而不是使用文檔出現時間來進行排序。這樣，最相關的文檔將排在***個，無論它是多久之前創建的（當然，有的時候和文檔的創建時間也是有關的）。

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

這個算法不關心詞語是名詞還是動詞，也不關心詞語的意義。它唯一關心的是哪些是常用詞，那些是稀有詞。如果一個搜索語句中包括常用詞和稀有詞，你***讓包含稀有詞的文檔的評分高一些，同時降低常用詞的權重。

這個算法被稱為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）（例如  ours）很有用，可以將不同長度的文檔統一到相同的比較條件上。對于雙字段集合（例如 “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) { returnstemmer(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]);  }  }

我 們定義了一個簡單的靜態方法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 forthis 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 ifyou 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 timeyou 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.documentsis   是一個保存著所有文檔的數據庫，它保存著文檔的全部原始文字，文檔的長度信息和一個列表，列表里面保存著文檔中的所有詞語和詞語的數量與出現頻率。使用這 個數據結構，我們可以很容易的和快速的（是的，非常快速，只需要時間復雜度為O(1)的哈表查詢時間）回答如下問題：在文檔 #3 中，'walk'  這個詞語出現了多少次？

我們在還使用了另一個數據結構，this.terms。它表示語料庫中的所有詞語。通過這個數據結構，我們可以在O(1)時間內回答如下問題：'walk' 這個詞在多少個文檔中出現過？他們的 id 是什么？

***，我們記錄了每個文檔的長度，并記錄了整個語料庫中文檔的平均長度。

注 意，上面的代碼中， idf 被初始化 0，而且 updateidf  方法被注釋掉了。這是因為這個方法運行的非常慢，并且只需在建立索引之后運行一次就可以了。既然運行一次就能滿足需求，就沒有必要運行5000次。先把它 注釋掉，然后在大批量的索引操作之后運行，就可以節省很多時間。下面是這個函數的代碼：

BM25.prototype.updateIdf = function {  varkeys = Object.keys(this.terms);  for(vari = 0, len = keys.length; i < len; i++) {  varnum = (this.totalDocuments - this.terms[term].n + 0.5);  vardenom = (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) {  varqueryTerms = BM25.Tokenize(query);  varresults = ;  // Look at each document in turn. There are better ways to do this with inverted indices.  varkeys = Object.keys(this.documents);  for(varj = 0, nDocs = keys.length; j < nDocs; j++) {  varid = 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(vari = 0, len = queryTerms.length; i < len; i++) {  varqueryTerm = 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(typeofthis.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(typeofthis.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.  varidf = this.terms[queryTerm].idf;  // Numerator of the TF portion.  varnum = this.documents[id].terms[queryTerm].count * (this.k1 + 1);  // Denomerator of the TF portion.  vardenom = 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) { returnb._score - a._score; });  returnresults.slice(0, 10);  };

***，search 方法遍歷所有的文檔，并給出每個文檔的 BM25 分數，然后按照由大到小的順序進行排序。當然了，在搜索過程中遍歷語料庫中的每個文檔實是不明智。這個問題在 Part Two （反向索引和性能）中得到解決。

上 面的代碼已經做了很好的注釋，其要點如下：為每個文檔和每個詞語計算 BM25 分數。詞語的 idf  分數已經預先計算好了，使用的時候只需要查詢即可。詞語頻率作為文檔屬性的一部分也已經預先計算好了。之后只需要簡單的四則運算即可。***給每個文檔增加 一個臨時變量 _score，然后根據 score 做降序排列并返回前 10 個結果。

讀到這里，這篇“JavaScript全文搜索如何實現”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。