全文搜索，與機(jī)器學(xué)習(xí)領(lǐng)域其他大多數(shù)問(wèn)題不同，是一個(gè) Web 程序員在日常工作中經(jīng)常遇到的問(wèn)題。客戶可能要求你在某個(gè)地方提供一個(gè)搜索框，然后你會(huì)寫(xiě)一個(gè)類似 WHERE title LIKE %:query% 的 SQL 語(yǔ)句實(shí)現(xiàn)搜索功能。一開(kāi)始，這是沒(méi)問(wèn)題，直到有一天，客戶找到你跟你說(shuō)，“搜索出錯(cuò)啦！”

當(dāng)然，實(shí)際上搜索并沒(méi)有“出錯(cuò)”，只是搜索的結(jié)果并不是客戶想要的。一般的用戶并不清楚如何做精確匹配，所以得到的搜索結(jié)果質(zhì)量很差。為了解決問(wèn)題，你決定使用全文搜索。經(jīng)過(guò)一陣枯燥的學(xué)習(xí)，你開(kāi)啟了 MySQL 的 FULLTEXT 索引，并使用了更高級(jí)的查詢語(yǔ)法，如 “MATCH() … AGAINST()” 。

好了，問(wèn)題解決，完結(jié)撒花！數(shù)據(jù)庫(kù)規(guī)模不大的時(shí)候是沒(méi)問(wèn)題了。

但是當(dāng)你的數(shù)據(jù)越來(lái)越多時(shí)，你會(huì)發(fā)現(xiàn)你的數(shù)據(jù)庫(kù)也越來(lái)越慢了。MySQL 不是一個(gè)非常好用的全文搜索工具。所以你決定使用 ElasticSearch，重構(gòu)代碼，并部署 Lucene 驅(qū)動(dòng)的全文搜索集群。你會(huì)發(fā)現(xiàn)它工作的非常好，又快又準(zhǔn)確。

這時(shí)你不禁會(huì)想：為什么 Lucene 這么牛逼呢？

本篇文章(主要介紹 TF-IDF，Okapi BM-25 和普通的相關(guān)性評(píng)分 )和 下一篇文章 （主要介紹索引）將為你講述全文搜索背后的基本概念。

相關(guān)性

對(duì)每一個(gè)搜索查詢，我們很容易給每個(gè)文檔定義一個(gè)“相關(guān)分?jǐn)?shù)”。當(dāng)用戶進(jìn)行搜索時(shí)，我們可以使用相關(guān)分?jǐn)?shù)進(jìn)行排序而不是使用文檔出現(xiàn)時(shí)間來(lái)進(jìn)行排序。這樣，最相關(guān)的文檔將排在第一個(gè)，無(wú)論它是多久之前創(chuàng)建的（當(dāng)然，有的時(shí)候和文檔的創(chuàng)建時(shí)間也是有關(guān)的）。

有很多很多種計(jì)算文字之間相關(guān)性的方法，但是我們要從最簡(jiǎn)單的、基于統(tǒng)計(jì)的方法說(shuō)起。這種方法不需要理解語(yǔ)言本身，而是通過(guò)統(tǒng)計(jì)詞語(yǔ)的使用、匹配和基于文檔中特有詞的普及率的權(quán)重等情況來(lái)決定“相關(guān)分?jǐn)?shù)”。
 

這個(gè)算法不關(guān)心詞語(yǔ)是名詞還是動(dòng)詞，也不關(guān)心詞語(yǔ)的意義。它唯一關(guān)心的是哪些是常用詞，那些是稀有詞。如果一個(gè)搜索語(yǔ)句中包括常用詞和稀有詞，你最好讓包含稀有詞的文檔的評(píng)分高一些，同時(shí)降低常用詞的權(quán)重。

這個(gè)算法被稱為Okapi BM25。它包含兩個(gè)基本概念 詞語(yǔ)頻率(term frequency) 簡(jiǎn)稱詞頻(“TF”) 和 文檔頻率倒數(shù)(inverse document frequency) 簡(jiǎn)寫(xiě)為(“IDF”). 把它們放到一起，被稱為 “TF-IDF”，這是一種統(tǒng)計(jì)學(xué)測(cè)度，用來(lái)表示一個(gè)詞語(yǔ) (term) 在文檔中有多重要。

TF-IDF

詞語(yǔ)頻率( Term Frequency), 簡(jiǎn)稱 “TF”, 是一個(gè)很簡(jiǎn)單的度量標(biāo)準(zhǔn)：一個(gè)特定的詞語(yǔ)在文檔出現(xiàn)的次數(shù)。你可以把這個(gè)值除以該文檔中詞語(yǔ)的總數(shù)，得到一個(gè)分?jǐn)?shù)。例如文檔中有 100 個(gè)詞， ‘the' 這個(gè)詞出現(xiàn)了 8 次，那么 'the' 的 TF 為 8 或 8/100 或 8%（取決于你想怎么表示它）。

逆向文件頻率（Inverse Document Frequency）, 簡(jiǎn)稱 “IDF”，要復(fù)雜一些：一個(gè)詞越稀有，這個(gè)值越高。它由總文件數(shù)目除以包含該詞語(yǔ)之文件的數(shù)目，再將得到的商取對(duì)數(shù)得到。越是稀有的詞，越會(huì)產(chǎn)生高的 “IDF”。

如果你將這兩個(gè)數(shù)字乘到一起 (TF*IDF), 你將會(huì)得到一個(gè)詞語(yǔ)在文檔中的權(quán)重?！皺?quán)重”的定義是：這個(gè)詞有多稀有并且在文檔中出現(xiàn)的多么頻繁？

你可以將這個(gè)概念用于文檔的搜索查詢。在查詢中的對(duì)于查詢中的每個(gè)關(guān)鍵字，計(jì)算他們的 TF-IDF 分?jǐn)?shù)，并把它們相加。得分最高的就是與查詢語(yǔ)句最符合的文檔。

很酷吧！

Okapi BM25

上述算法是一個(gè)可用的算法，但并不太完美。它給出了一個(gè)基于統(tǒng)計(jì)學(xué)的相關(guān)分?jǐn)?shù)算法，我們還可以進(jìn)一步改進(jìn)它。

Okapi BM25 是到目前為止被認(rèn)為最先進(jìn)的排名算法之一（所以被稱為 ElasticSearch ）。Okapi BM25 在 TF-IDF 的基礎(chǔ)上增加了兩個(gè)可調(diào)參數(shù)，k1 和 b，, 分別代表 “詞語(yǔ)頻率飽和度（term frequency saturation）” 和 “字段長(zhǎng)度規(guī)約”。這是什么鬼？

為了能直觀的理解“詞語(yǔ)頻率飽和度”，請(qǐng)想象兩篇差不多長(zhǎng)度的討論棒球的文章。另外，我們假設(shè)所有文檔(除去這兩篇)并沒(méi)有多少與棒球相關(guān)的內(nèi)容，因此 “棒球” 這個(gè)詞將具有很高的 IDF - 它極稀少而且很重要。 這兩篇文章都是討論棒球的，而且都花了大量的篇幅討論它，但是其中一篇比另一篇更多的使用了“棒球”這個(gè)詞。那么在這種情況，是否一篇文章真的要比另一篇文章相差很多的分?jǐn)?shù)呢？既然兩個(gè)兩個(gè)文檔都是大篇幅討論棒球的，那么“棒球”這個(gè)詞出現(xiàn) 40 次還是 80 次都是一樣的。事實(shí)上，30 次就該封頂啦！

這就是 “詞語(yǔ)頻率飽和度。原生的 TF-IDF 算法沒(méi)有飽和的概念，所以出現(xiàn) 80 次“棒球”的文檔要比出現(xiàn) 40 次的得分高一倍。有些時(shí)候，這時(shí)我們所希望的，但有些時(shí)候我們并不希望這樣。

此外，Okapi BM25 還有個(gè) k1 參數(shù)，它用于調(diào)節(jié)飽和度變化的速率。k1 參數(shù)的值一般介于 1.2 到  2.0 之間。數(shù)值越低則飽和的過(guò)程越快速。（意味著兩個(gè)上面兩個(gè)文檔有相同的分?jǐn)?shù)，因?yàn)樗麄兌及罅康摹鞍羟颉边@個(gè)詞語(yǔ)）

字段長(zhǎng)度歸約（Field-length normalization）將文檔的長(zhǎng)度歸約化到全部文檔的平均長(zhǎng)度上。這對(duì)于單字段集合（single-field collections）（例如 ours）很有用，可以將不同長(zhǎng)度的文檔統(tǒng)一到相同的比較條件上。對(duì)于雙字段集合（例如 “title” 和 "body"）更加有意義，它同樣可以將 title 和 body 字段統(tǒng)一到相同的比較條件上。字段長(zhǎng)度歸約用 b 來(lái)表示，它的值在 0 和 1 之間，1 意味著全部歸約化，0 則不進(jìn)行歸約化。

算法

在Okapi BM25 維基百科中你可以了解Okapi算法的公式。既然都知道了式子中的每一項(xiàng)是什么，這肯定是很容易地就理解了。所以我們就不提公式，直接進(jìn)入代碼：
 

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

我們定義了一個(gè)簡(jiǎn)單的靜態(tài)方法Tokenize()，目的是為了解析字符串到tokens的數(shù)組中。就這樣，我們小寫(xiě)所有的tokens（為了減少熵）。我們運(yùn)行Porter Stemmer 算法來(lái)減少熵的量同時(shí)也提高匹配程度（“walking”和"walk"匹配是相同的）。而且我們也過(guò)濾掉停用詞（很普通的詞）為了更近一步減少熵值。在我所寫(xiě)的概念深入之前，如果我過(guò)于解釋這一節(jié)就請(qǐng)多擔(dān)待。
 

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()這種方法會(huì)奇跡般出現(xiàn)的地方。我們基本上建立和維護(hù)兩個(gè)類似的數(shù)據(jù)結(jié)構(gòu):this.documents.和this.terms。
 

this.documentsis 是一個(gè)保存著所有文檔的數(shù)據(jù)庫(kù)，它保存著文檔的全部原始文字，文檔的長(zhǎng)度信息和一個(gè)列表，列表里面保存著文檔中的所有詞語(yǔ)和詞語(yǔ)的數(shù)量與出現(xiàn)頻率。使用這個(gè)數(shù)據(jù)結(jié)構(gòu)，我們可以很容易的和快速的（是的，非?？焖?，只需要時(shí)間復(fù)雜度為O(1)的哈表查詢時(shí)間）回答如下問(wèn)題：在文檔 #3 中，'walk' 這個(gè)詞語(yǔ)出現(xiàn)了多少次？

我們?cè)谶€使用了另一個(gè)數(shù)據(jù)結(jié)構(gòu)，this.terms。它表示語(yǔ)料庫(kù)中的所有詞語(yǔ)。通過(guò)這個(gè)數(shù)據(jù)結(jié)構(gòu)，我們可以在O(1)時(shí)間內(nèi)回答如下問(wèn)題：'walk' 這個(gè)詞在多少個(gè)文檔中出現(xiàn)過(guò)？他們的 id 是什么？

最后，我們記錄了每個(gè)文檔的長(zhǎng)度，并記錄了整個(gè)語(yǔ)料庫(kù)中文檔的平均長(zhǎng)度。

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

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

這是一個(gè)非常簡(jiǎn)單的函數(shù)，但是由于它需要遍歷整個(gè)語(yǔ)料庫(kù)中的所有詞語(yǔ)，并更新所有詞語(yǔ)的值，這就導(dǎo)致它工作的就有點(diǎn)慢。這個(gè)方法的實(shí)現(xiàn)采用了逆向文檔頻率 (inverse document frequency) 的標(biāo)準(zhǔn)公式（你可以在 Wikipedia 上找到這個(gè)公式）—  由總文件數(shù)目除以包含該詞語(yǔ)之文件的數(shù)目，再將得到的商取對(duì)數(shù)得到。我做了一些修改，讓返回值一直大于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() 方法遍歷所有的文檔，并給出每個(gè)文檔的 BM25 分?jǐn)?shù)，然后按照由大到小的順序進(jìn)行排序。當(dāng)然了，在搜索過(guò)程中遍歷語(yǔ)料庫(kù)中的每個(gè)文檔實(shí)是不明智。這個(gè)問(wèn)題在 Part Two （反向索引和性能）中得到解決。

上面的代碼已經(jīng)做了很好的注釋，其要點(diǎn)如下：為每個(gè)文檔和每個(gè)詞語(yǔ)計(jì)算 BM25 分?jǐn)?shù)。詞語(yǔ)的 idf 分?jǐn)?shù)已經(jīng)預(yù)先計(jì)算好了，使用的時(shí)候只需要查詢即可。詞語(yǔ)頻率作為文檔屬性的一部分也已經(jīng)預(yù)先計(jì)算好了。之后只需要簡(jiǎn)單的四則運(yùn)算即可。最后給每個(gè)文檔增加一個(gè)臨時(shí)變量 _score，然后根據(jù) score 做降序排列并返回前 10 個(gè)結(jié)果。
示例，源代碼，注意事項(xiàng)和下一步計(jì)劃

上面的示例有很多方法進(jìn)行優(yōu)化，我們將在 “全文搜索”的第二部分中介紹它們，歡迎繼續(xù)收看。我希望我能在幾個(gè)星期之后完成它。下面列了下次將要提到的內(nèi)容：

•     反向索引和快速搜索
•     快速索引
•     更好的搜索結(jié)果

為了這個(gè)演示，我編了一個(gè)小的維基百科爬蟲(chóng)，爬到相當(dāng)多（85000）維基百科文章的第一段。由于索引到所有85K文件需要90秒左右，在我的電腦我已經(jīng)削減了一半。不想讓你們僅僅為了一個(gè)簡(jiǎn)單的全文本演示浪費(fèi)你的筆記本電腦電量。

因?yàn)樗饕且粋€(gè)繁重的、模塊化的CPU操作，我把它當(dāng)成一個(gè)網(wǎng)絡(luò)工作者。索引運(yùn)行在一個(gè)后臺(tái)線程上--在這里你可以找到完整的源代碼。你也會(huì)發(fā)現(xiàn)到詞干算法和我的停用詞列表中的源代碼參考。至于代碼許可，還是一如既往為教育目的而免費(fèi)，而不用于任何商業(yè)目的。

最后是演示。一旦索引完成，嘗試尋找隨機(jī)的東西和短語(yǔ)，維基百科會(huì)知道的。注意，只有40000段的索引，所以你可能要嘗試一些新的話題。

最新評(píng)論