JavaScript全文搜索之相关度评分

1、JavaScript 全文搜索之相关度评分 全文搜索，与机器学习领域其他大多数问题不同，是一个 Web 程序员在日常工作中经常遇到的问题。客户可能要求你在某个地方提供一个搜索框，然后你会写一个类似 WHERE title LIKE %:query% 的 SQL 语句实现搜索功能。一开始，这是没问题，直到有一天，客户找到你跟你说，“搜索出错啦！”当然，实际上搜索并没有“出错”，只是搜索的结果并不是客户想要的。一般的用户并不清楚如何做精确匹配，所以得到的搜索结果质量很差。为了解决问题，你决 定使用全文搜索。经过一阵枯燥的学习，你开启了 MySQL 的 FULLTEXT 索引，并使用了更高级的查询语

2、法，如 “MATCH AGAINST ” 。好了，问题解决，完结撒花！数据库规模不大的时候是没问题了。但是当你的数据越来越多时，你会发现你的数据库也越来越慢了。MySQL 不是一个非常好用的全文搜索工具。所以你决定使用 ElasticSearch ，重构代码，并部署 Lucene 驱动的全文搜索集群。你会发现它工作的非常好，又快又准确。这时你不禁会想：为什么 Lucene 这么牛逼呢？本篇文章(主要介绍 TF-IDF ，Okapi BM-25 和普通的相关性评分 和 下一篇文章 （主要介绍索引）将为你讲述全文搜索背后的基本概念。相关性对每一个搜索查询，我们很容易给每个文档定义一个“相关分数”。

3、当用户进行搜索时，我们可以使用相关分数进行排序而不是使用文档出现时间来进行排序。这样，最相关的文档将排在第一个，无论它是多久之前创建的（当然，有的时候和文档的创建时间也是有关的）。 有很多很多种计算文字之间相关性的方法，但是我们要从最简单的、基于统计的方法说起。这种方法不需要理解语言本身，而是通过统计词语的使用、匹配和基于文档中特有词的普及率的权重等情况来决定“相关分数”。这个算法不关心词语是名词还是动词，也不关心词语的意义。它唯一关心的是哪些是常用词，那些是稀有词。如果一个搜索语句中包括常用词和稀有词，你最好让包含稀有词的文档的评分高一些，同时降低常用词的权重。这个算法被称为Okapi BM

4、25。它包含两个基本概念 词语频率(term frequency 简称词频(“TF ” 和 文档频率倒数(inverse document frequency 简写为(“IDF ”. 把它们放到一起，被称为 “TF-IDF ”，这是一种统计学测度，用来表示一个词语 (term 在文档中有多重要。 TF-IDF词语频率(Term Frequency, 简称“TF ”, 是一个很简单的度量标准：一个特定的词语在文档出现的次数。你可以把这个值除以该文档中词语的总数，得到一个分数。例如文档中有 100 个词， the 这个词出现了 8 次，那么 'the' 的 TF 为 8 或 8/1

5、00 或 8%（取决于你想怎么表示它）。逆向文件频率（Inverse Document Frequency ）, 简称“IDF ”，要复杂一些：一个词越稀有，这个值越高。它由总文件数目除以包含该词语之文件的数目，再将得到的商取对数得到。越是稀有的词，越会产生高的 “IDF ”。如果你将这两个数字乘到一起 (TF*IDF, 你将会得到一个词语在文档中的权重。“权重”的定义是：这个词有多稀有并且在文档中出现的多么频繁？你可以将这个概念用于文档的搜索查询。在查询中的对于查询中的每个关键字，计算他们的 TF-IDF 分数，并把它们相加。得分最高的就是与查询语句最符合的文档。Okapi BM25上述算法

6、是一个可用的算法，但并不太完美。它给出了一个基于统计学的相关分数算法，我们还可以进一步改进它。Okapi BM25 是到目前为止被认为最先进的排名算法之一（所以被称为ElasticSearch ）。Okapi BM25 在 TF-IDF 的基础上增加了两个可调参数，k1 和 b ，, 分别代表 “词语频率饱和度（term frequency saturation）” 和 “字段长度规约”。这是什么鬼？为 了能直观的理解“词语频率饱和度”，请想象两篇差不多长度的讨论棒球的文章。另外，我们假设所有文档(除去这两篇 并没有多少与棒球相关的内容，因此 “棒球” 这个词将具有很高的 IDF - 它极稀少

7、而且很重要。 这两篇文章都是讨论棒球的，而且都花了大量的篇幅讨论它，但是其中一篇比另一篇更多的使用了“棒球”这个词。那么在这种情况，是否一篇文章真的要比另一篇 文章相差很多的分数呢？既然两个两个文档都是大篇幅讨论棒球的，那么“棒球”这个词出现 40 次还是 80 次都是一样的。事实上，30 次就该封顶啦！ 这就是 “词语频率饱和度。原生的 TF-IDF 算法没有饱和的概念，所以出现 80 次“棒球”的文档要比出现 40 次的得分高一倍。有些时候，这时我们所希望的，但有些时候我们并不希望这样。此外，Okapi BM25 还有个 k1 参数，它用于调节饱和度变化的速率。k1 参数的值一般介于1.2

8、 到 2.0 之间。数值越低则饱和的过程越快速。（意味着两个上面两个文档有相同的分数，因为他们都包含大量的“棒球”这个词语）字 段长度归约（Field-length normalization）将文档的长度归约化到全部文档的平均长度上。这对于单字段集合（single-field collections ）（例如 ours ）很有用，可以将不同长度的文档统一到相同的比较条件上。对于双字段集合（例如 “title ” 和 "body" ）更加有意义，它同样可以将 title 和 body 字段统一到相同的比较条件上。字段长度归约用 b 来表示，它的值在 0 和 1 之间，1 意

9、味着全部归约化，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 stopStemsvar out = ;for

10、(var i = 0, len = text.length; i < len; i+ if (stopStems.indexOf(texti = -1 out.push(texti;我 们定义了一个简单的静态方法Tokenize ，目的是为了解析字符串到tokens 的数组中。就这样，我们小写所有的tokens （为了减少熵）。我们运 行Porter Stemmer 算法来减少熵的量同时也提高匹配程度（“walking ”和"walk" 匹配是相同的）。而且我们也过滤掉停用词（很普通的词）为了更近一步减少熵值。在 我所写的概念深入之前，如果我过于解释这一节就请多担待。

11、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 wordsvar tokens = BM25.Tokenize(doc.body;/Will h

12、old unique terms and their counts and frequenciesvar _terms = ;/docObj will eventually be added to the documents databasevar docObj = id: doc.id, tokens: tokens, body: doc.body;/Count number of termsdocObj.termCount = tokens.length;/Increment totalDocumentsthis .totalDocuments+;/Readjust averageDocu

13、mentLengththis .totalDocumentTermLength += docObj.termCount;this .averageDocumentLength = this .totalDocumentTermLength / this . totalDocuments;/Calculate term frequency/First get terms countfor (var i = 0, len = tokens.length; i < len; i+ var term = tokensi;if (!_termsterm _termsterm = count: 0,

14、freq: 0;_termsterm.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 = keysi;/Term Frequency forthis document._termsterm.freq = _termsterm.count / docObj.t

15、ermCount;/Inverse Document Frequency initializationif (!this .termsterm this .termsterm = n: 0, /Number of docs this term appears in, uniquelyidf: 0;this .termsterm.n+;/Calculate inverse document frequencies/This is SLOWish so ifyou want to index a big batch of documents,/comment this out and run it

16、 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 dbdocObj.terms = _terms;this .documentsdocObj.id = docObj;this.documentsis 是一个保存着所有文档的数据库，它保存着文档的全部原始文字，文档的长度信息和一个列表，列表里面保存着文档中的所有词语和词语的数量与出现频率。使

17、用这 个数据结构，我们可以很容易的和快速的（是的，非常快速，只需要时间复杂度为O(1的哈表查询时间）回答如下问题：在文档 #3 中，'walk' 这个词语出现了多少次？/ Calculate the score for each query term for(vari = 0, len = queryTerms.length; i < len; i+ varqueryTerm = queryTermsi; / We've never seen this term before so IDF will be 0. / Means we can skip the wh

18、ole term, it adds nothing to the score / and isn't in any document. if(typeofthis.termsqueryTerm = 'undefined' continue; / This term isn't in the document, so the TF portion is 0 and th is / term contributes nothing to the search score. if(typeofthis.documentsid.termsqueryTerm = '

19、;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 / av gDocLength / IDF is pre-calculated for the whole docset. varidf = this.termsqueryTerm.idf; / Numerator of the TF portion. varnum = this.document

20、sid.termsqueryTerm.count * (this.k1 + 1 ; / Denomerator of the TF portion. vardenom = this.documentsid.termsqueryTerm.count + (this.k1 * (1 - this.b + (this.b * this.documentsid.termCount / this.averageDocumentLength; / Add this query term to the score this.documentsid._score += idf * num / denom; i

21、f(!isNaN(this.documentsid._score && this.documentsid._score > 0 results.push(this.documentsid; results.sort(function(a, b returnb._score - a._score; ; returnresults.slice(0, 10; ; 最后，search 方法遍历所有的文档，并给出每个文档的 BM25 分数，然后按照由大到小的 顺序进行排序。当然了，在搜索过程中遍历语料库中的每个文档实是不明智。这个问题在 Part Two （反向索引和性能）中得到解决。 上 面的代码已经做了很好的注释，其要点如下：为每个文档和每个词语计算 BM25 分数。 词语的 idf 分数已经预先计算