具體介紹JavaScript全文搜尋之相關度評分的範例程式碼-js教程-PHP中文網

全文搜索，與機器學習領域其他大多數問題不同，是一個 Web 程式設計師在日常工作中經常遇到的問題。客戶可能會要求你在某個地方提供一個搜尋框，然後你會寫一個類似 WHERE title LIKE %:query% 的 SQL 語句實作搜尋功能。一開始，這是沒問題，直到有一天，客戶找到你跟你說，“搜索出錯啦！”

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

好了，問題解決，完結撒花！資料庫規模不大的時候是沒問題了。

但是當你的資料越來越多時，你會發現你的資料庫也越來越慢了。 MySQL 不是一個非常好用的全文搜尋工具。所以你決定使用 ElasticSearch，重構程式碼，並部署 Lucene 驅動的全文搜尋叢集。你會發現它工作的非常好，又快又準確。

這時你不禁會想：為什麼 Lucene 這麼屌呢？

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

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 次的得分高一倍。有些時候，此時我們所希望的，但有些時候我們並不希望這樣。之間。 Field-length normalization）將文件的長度歸約化到全部文件的平均長度上。上。和1 之間，1 意味著全部歸約化，0 則不進行歸約化。知道了式子中的每一項是什麼，這肯定是很容易就理解了。

方法Tokenize()，目的是為了解析

字串

到tokens的

陣列

中。演算法來減少熵的量同時也提高匹配程度（“walking”和”walk”匹配是相同的）。寫的概念深入之前，如果我過於解釋這一節就請多擔待。資料結構:this.documents.和this.terms。著文檔中的所有詞語和詞語的數量與出現頻率。回答以下問題：在文件#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&#39;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&#39;t in any document.
            if (typeof this.terms[queryTerm] === &#39;undefined&#39;) {
                continue;
            }

            // This term isn&#39;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] === &#39;undefined&#39;) {
                continue;
            }

            // The term is in the document, let&#39;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 个结果。