【迅搜13】搜索技巧（三）排序与评分算法

标签：search 13 算法文档 IDF 排序 id

搜索技巧（三）排序与评分算法

今天要学习的，第一部分是排序相关的功能，第二部分则是跟排序密切相关的另一块功能，评分算法。又是算法了，也就是说，又是一大块的理论知识了。今天的文章不长，因为我们的功能测试非常少，但却很重要，因为我们要讲到的理论算法是现在最主流的，也是各种搜索引擎的都在使用的核心算法。如果真的踫到懂行的，确实是用过搜索引擎的面试官，这一块内容绝对是必问内容之一，这么说是不是就很兴奋啦？

排序

先来说下我们指定字段排序，使用的就是 setSort() 这个方法。

echo $search->setSort('pub_time', true)->setLimit(1)->search()[0]->id, PHP_EOL; // 1
echo $search->setSort('pub_time', false)->setLimit(1)->search()[0]->id, PHP_EOL; // 844
echo $search->setSort('pub_time')->setLimit(1)->search()[0]->id, PHP_EOL; // 844

这个方法有三个参数，第一个参数是字段名称，第二个参数是正序还是倒序，默认值是 false ，表示倒序。第三个参数表示是否按优先相关性排序，默认为否，这个优先相关性的问题我们下一节会详细来说。

字符串排序问题

先来填一个坑，上面我们使用的是 pub_time 这个字段，它是 date 类型的。但是通常大家可能会习惯使用 id 来排序。之前我们提到过 XS 中的主键不是唯一的，另外一点就是它是 string 类型的。对于 string 类型字段的排序，XS 中，或者说 Xapian 是以字典序的，这是啥意思？就是将字符一个一个拆开，一个一个比对。

echo $search->setSort('id', true)->setLimit(1)->search()[0]->id,PHP_EOL; // 1
echo $search->setSort('id', false)->setLimit(1)->search()[0]->id, PHP_EOL; // 99

看出来使用 id 排序的问题了吧，倒序之后，返回的最大的 id 竟然是 99 。不对呀，上面我们按 pub_time 排序最大的返回 id 都有 844 呢。这个呀，就是字符串排序最典型的一个特点了。因为我们会将字符串的字符一个一个拆开，比如第一个字符，最大是 9 的，那么就接着比第二个，最大还是 9 ，在前两位中，没有比这两个 9 更大的字符串了。同时，我们也没有到 991 这样的 id ，所以也就没有第三位数的对比了。因此，99 就是当前最大的字符串了。

这一块有点绕是吧，其实我们用一个静态语言来演示就很清楚了，比如说 Go 语言。

import "fmt"

func main() {
 fmt.Println("99" > "844") // true
}

很明显，Go 语言中，如果是字符串类型，99 是比 844 要大的。这一块 PHP 用 99 不好演示，因为 PHP 在比较时，会进行自动类型转换。

因此，如果你的数据 id 是纯数字类型，那么想要根据 id 来进行排序的话，效果可能不会如你所愿。那么要怎么解决这个问题呢？其实呀非常简单，XS 对于 date 和 numberic 类型的排序效果是按照数字类型的。也就是说，只要我们冗余一个字段，设置为 numberic 类型，然后使用这个字段来排序就可以实现根据 id 排序的效果啦。

多字段排序

和数据库的效果类似，在 XS 中也可以进行多字段的排序，不过使用的是另一个 setMultiSort() 方法。

echo $search->setMultiSort(['pub_time'=>true,'id'=>false])->setLimit(1)->search()[0]->id, PHP_EOL; // 99
echo $search->setMultiSort(['pub_time','id'])->setLimit(1)->search()[0]->id, PHP_EOL; // 844
echo $search->setMultiSort(['pub_time','id'], true)->setLimit(1)->search()[0]->id, PHP_EOL; // 1

第一行代码，我们根据 pub_time 正序，然后再根据 id 倒序。第二行，按默认值，两个都是倒序。第三行，使用第二个参数来指定字段的默认值都是正序。

可以看到 setMultiSort() 方法非常灵活，第一个参数是排序字段数组，我们可以通过 K/V 形式指定字段对应的排序规则，也可以不指定按第二个参数的默认值来排序。

评分算法

好了，上面的内容是我们按指定的字段来排序。但是，搜索引擎的强大之处其实是体现在另外一个方面，那就是可以根据搜索词，以这个搜索分词后的结果，在文档中的比重来进行排序。这也称为一种检索评分算法。

我们先来看看这种算法在 XS 中的体现，这里就需要搬出查询结果返回的 XSDocument 对象中的元数据信息了。关于 XSDocument 对象和元数据的内容之前我们就讲过，不记得的小伙伴记得翻看一下之前的文章内容哦。

print_r($search->search('数据结构与算法')[0]);
    // XSDocument Object
    // (
    //     ………………
    //     [_meta:XSDocument:private] => Array
    //         (
    //             [docid] => 1
    //             [rank] => 1
    //             [ccount] => 0
    //             [percent] => 100
    //             [weight] => 5.3044538497925
    //         )
    // )

搜索内容还是我们熟悉的“数据结构与算法”这个短语，它会被切分为“数据结构”、“与”、“算法”这三个词，然后进行查询。从返回的数据文档中，我们可以看到元数据信息中的几个字段。

docid，文档在 Xapian 服务器生成的唯一ID
rank，本次查询的排名，比如现在我们看到的就是第一篇文档
ccount，之前在折叠搜索中见过它的作用，不是我们今天的重点
percent，百分比，一会我们再看它的含义
weight，权重，这篇文章在当前搜索词的所有结果中的权重评分，今天要学习的重点

好了，再拿一篇文章做对比。

print_r($search->search('数据结构与算法')[9]);
// XSDocument Object
// (
//     ……………………
//     [_meta:XSDocument:private] => Array
//         (
//             [docid] => 3
//             [rank] => 10
//             [ccount] => 0
//             [percent] => 95
//             [weight] => 5.0574460029602
//         )

// )

print_r($search->setLimit(10, 20)->search('数据结构与算法')[9]->rank()); // 30

第一个是我们本次查询的最后一篇文章，也就是第十篇文章。这里很明显了吧，rank 现在是 10 。下面还有一行代码，查找的还是相同的查询语句第三页的最后一条的 rank ，可以看到这个排名还是比较精准地能够反映文档在查询中的位置的。

接下来我们再看 percent 和 weight 的关系。其实 percent 就是以最顶上那一条的 5.3044538497925 为基准来比对后续文档与这个基准之间的比值。比如说，第一篇文档的权重评分是 5.3044538497925 ，它的 percent 自然就是 100% 。第十篇的权重评分是 5.0574460029602 ，那么我们就来算一下 5.0574460029602/5.3044538497925 = 0.95343387767584 。这下明白 percent 是啥意思了吧。

好了，最后最重要的就是这个 weight 又是怎么来的了。先看一下列表结果，第一页最后一条的文档 id 是 3 ，也就是说，有 id 为其它的数据比这篇文档的 weight 得分高，所以他们会排到前面去了。在没有关键词，也没有 setSort() 影响的情况下，查询出来的文档会以 docid 正序向后展示。而一旦有了关键词，检索就会以关键词和文档之间的关系进行评分，并记录到 weight 中，最后再根据这个 weight 来进行倒序排序。上面我们讲到的 setLimit() 和 setMultiSort() 方法中的是否按相关性排序的参数，就是说在指定的排序字段相等时，是否再以相关度 weight 的评分结果来对结果进行排序。

以评分权重为基础实现的就是非常经典的 TopK 排序功能，具体的排序算法就要说到搜索引擎最经典的评分排序算法问题了。我们主要看两个评分排序算法。

TF-IDF

这个算法是学习搜索引擎相关知识时，绕不过去的一个知识点。它是由两个缩写单词组合而成的。

TF（Term Frequency），表示词频，也就是一个单词，在文档中出现的频率。
IDF（Inverse Document Frequency），逆文档频率，表示一个单词，在多个文档中出现的频率的倒数。

什么意思呢？就是说，如果我的 TF 频率越高，那么这个关键词，在这篇文档上的得分也就越高。但是，这样就会有一个问题，那就是 SEO 中最出名的堆彻关键词影响排名的问题。也就说，我们在文章中，不停地增加关键词，就能让这篇文章的排名得分一直提升。这个肯定是有问题的，如果可以这样的话，那么我们直接就是不停地堆关键词就好了嘛，文章通顺与否，质量是否上乘就都不重要了。

因此，IDF 的作用就突显出来了。它表示的是逆文档词频。也就是说，一个关键词，如果在越多的文档中出现的次数越多，那么它的得分也就越低。或者说，一个词在很多文档中都有出现，那么它的重要性就没那么重要了。比如说我写文章就很爱说“我们”，那么“我们”在我的文章库的很多文章中就会出现很多次，这样的话，“我们”这个词其实就不是很重要的一个词。而“数据结构”或者“算法”，只在几十篇文章中出现过，那么它们肯定会比“我们”的得分要高一些。

TF 针对的是单一的一篇文档，而 IDF 针对的是所有文档。将 DF 变成一个倒数，也就是 n/df 这样就是 IDF（n表示文档总数），然后对他们俩进行计算，就可以得出指定的关键词，针对某一篇文档的具体得分。这就是 TF-IDF 算法。

这个算法的公式，如果用最简单的算法，就是 tf*log(1/df) 。比如我们有这样的几段内容。

数据结构与算法，算法，算法，算法
设计模式与算法，这俩很重要
关系型数据库，查询、添加、修改、删除
灵活运用数据结构与算法，再加上设计模式，你就是大佬了

在这其中，我们选取“算法”、“设计模式”、“数据库”这三个单词。

算法，DF 为 3 ，在三篇文章中出现
设计模式，DF 为 2 ，在两篇文章中出现
数据库，DF 为 1 ，在一篇文章中出现

然后搜索“算法”这个词。对于第一篇文章来说，它的得分就是。

文档一，TF = 4 出现4次“算法”，IDF = log(4/3) = 0.477 ，总的得分就是 4 * 0.477 = 1.908 。
文档二，TF = 1 出现1次“算法”，IDF = log(4/3) = 0.477 ，总的得分就是 1 * 0.477 = 0.477 。
文档三，TF = 0 出现0次“算法”，IDF = log(4/3) = 0.477 ，总的得分就是 0 * 0.477 = 0 。
文档四，TF = 1 出现0次“算法”，IDF = log(4/3) = 0.477 ，总的得分就是 1 * 0.477 = 0.477 。

最终出来的结果，文档一还是排在第一位，而文档三就会到最后面去了，它根本就没有得分，也根本不用出现。如果我们同时搜索多个关键词，那么就把它们的得分相加之后再进行排序。

上面这种算法，就是最最简单的一种 TF-IDF 算法，只是为了方便大家的理解。实际上的搜索引擎中使用的算法会更为复杂一些。如果只是我的例子这样简单的算法，那么大家做 SEO 就有各种空子可钻了（不过本身 SEO 也就是在找各种搜索引擎的算法规则来钻空子）。对于百度或者 Google 它们这些大型的通用搜索引擎，都会有自己的更为复杂的一套算法，也会有一些 AI 方面的机器学习计算来影响最终的得分排名（TF-IDF 和下面要讲的 BM25 都可以作为机器学习中的一个因子来影响最终排名计算）。

不过，不管是 ES 的 Lucene 还是 XS 的底层 Xapian ，其实都不是用得 TF-IDF ，而是它的升级版，BM25 算法。

BM25

BM25 算法是 Best Matching 25 的简称，是目前主要的信息检索引擎中最主流的文档相关性评分算法。25 指的是进行 25 次迭代。

传统的TF-IDF是自然语言搜索的一个基础理论，它符合信息论中的熵的计算原理，虽然作者在刚提出它时并不知道与信息熵有什么关系，但你观察IDF公式会发现，它与熵的公式是类似的。实际上IDF就是一个特定条件下关键词概率分布的交叉熵。

BM25在传统TF-IDF的基础上增加了几个可调节的参数，使得它在应用上更加灵活和强大，具有较高的实用性。BM25同样使用词频，逆文档频率以及字段长度归一化，但是每个因子的定义都有细微差别：

TF-IDF没有考虑词频上限的问题，因为高频停用词已经被移除了
BM25 有一个上限，文档里出现5-10次的词会比那些只出现一两次的对相关度有显著影响

上面一堆网上找来的，看得懂点赞，看不懂也没关系。说人话的话，BM25多了可调节参数，公式也复杂了许多。在 Xapian 官网的 https://xapian.org/docs/bm25.html 这个页面上，有具体的 BM25 的说明和公式。我抄过来。

((k3 + 1)q)/((k3 + q)) * ((k1 + 1)f)/((K + f)) * log((r + 0.5)(N − n − R + r + 0.5))/((n − r + 0.5)(R − r + 0.5))
其中 K = k1(bL + (1 − b))

k1，k2，k3是常数，也是可调节因子，k2在 BM11的公式中，具体看 Xapian 的文档
b是比例因子，为文档长度对相关性影响的大小，b越大，K值越小
q是wqf，内部查询频率
f是wdf，内部文档频率
n是是集合中的总文档数量
r是是相关文档总数
L是标准化文档长度（即该文档的长度除以集合中文档的平均长度）。

是不是一脸懵逼，没事，我也是懵逼的。这个算法我就没办法给大家演示了，但是从这个算法中，我们也能看出它确实就是 TF-IDF 的一个升级，增加了可调节的 k1、k2、k3、b 参数，在自定义词典时，就有单词的 TF、IDF和词性的配置，和他们应该有关系（我猜得，实在没资料啊）。这几个参数在 Xapian 中的默认值是 k1 = 1、k2 = 0、k3 = 1、 b = 0.5 。

Xapian 中的 BM25 又是由 BM11 和 BM 15 组合而来的，在上面官方文档的介绍中都有说明。数学大佬们还是直接去官方文档好好研究一下吧，我只能到这里了。

ES 使用的也是 BM25 算法，它的官方文档 https://www.elastic.co/guide/cn/elasticsearch/guide/current/pluggable-similarites.html ，可调节因子是 k1 和 b （我猜 Xapain 应该也是以这两个为主了）。更详细的 BM25 算法的资料在这里：https://en.wikipedia.org/wiki/Okapi_BM25 。

另外大家还会经常听到的一个 Google 的 PR 算法，全名是 PageRank ，这个东西和我们今天学的东西不太算是一类。但它也是影响文档的评分的一种算法技术，主要是根据文档与文档之间的链接关系来决定文档的评分质量。百度也有一个对应的 BR ，这两块的内容如果是做过 SEO 或者在网络营销公司上过班的同学应该都不会陌生。

总结

今天的内容中，前面排序的部分还是比较简单的吧。而后面的 TF-IDF 和 BM25 的部分已经大大地超出我的能力范围水平了。因此，文章中也就是用我所理解的 TF-IDF 给大家拿一个最简单的例子来抛砖引玉，如有不正确的地方，也希望各位大佬能够及时指正（大方向应该是没问题的）。另外 BM25 的例子是实在拿不出来了，也请各位见谅。但是我们也知道了，它的基础还是 TF-IDF ，所以，掌握最基础的原理知识就可以了，正常的面试你能回答出这些概念和它们之间的区别也能吊打一大半的同行了。此外，在B站很多讲 ES 的课程中，有一些也有具体的 ES 算分步骤的讲解，具体的课程我也不记得了，反正当时看到过，大家可以自己去找一下。

好了，搜索方面的两个非常重要的算法讲完了，但是搜索相关的内容还没有结束哦，我们继续，下一篇是热门搜索词相关的功能学习，非常有意思哦。

测试代码：

https://github.com/zhangyue0503/dev-blog/blob/master/xunsearch/source/13.php

参考文档：

http://www.xunsearch.com/doc/php/guide/search.search

https://xapian.org/docs/bm25.html

https://www.elastic.co/guide/cn/elasticsearch/guide/current/pluggable-similarites.html

https://en.wikipedia.org/wiki/Okapi_BM25

标签：search,13,算法,文档,IDF,排序,id
From： https://blog.51cto.com/zhangyue0503/9080757