具體介紹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 次的得分高一倍。有些時候，此時我們所希望的，但有些時候我們並不希望這樣。之間。 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 个结果。

示例，源代码，注意事项和下一步计划

上面的示例有很多方法进行优化，我们将在 “全文搜索”的第二部分中介绍它们，欢迎继续收看。我希望我能在几个星期之后完成它。下面列了下次将要提到的内容：

• 反向索引和快速搜索

• 快速索引

• 更好的搜索结果

为了这个演示，我编了一个小的维基百科爬虫，爬到相当多（85000）维基百科文章的第一段。由于索引到所有85K文件需要90秒左右，在我的电脑我已经削减了一半。不想让你们仅仅为了一个简单的全文本演示浪费你的笔记本电脑电量。

因为索引是一个繁重的、模块化的CPU操作，我把它当成一个网络工作者。索引运行在一个后台线程上–在这里你可以找到完整的源代码。你也会发现到词干算法和我的停用词列表中的源代码参考。至于代码许可，还是一如既往为教育目的而免费，而不用于任何商业目的。

最后是演示。一旦索引完成，尝试寻找随机的东西和短语，维基百科会知道的。注意，只有40000段的索引，所以你可能要尝试一些新的话题。

以上是具體介紹JavaScript全文搜尋之相關度評分的範例程式碼的詳細內容。更多資訊請關注PHP中文網其他相關文章！