11｜精准Top K检索：搜索结果是怎么进行打分排序的？

编辑回复: 作者回复：并不是typo，你其实提了一个好问题，使用堆来完成Top K检索，时间代价是什么呢？其实有两种不同的方法，对应了两个时间代价！ 一种方法，是先对前k个元素建一个堆，这时候时间代价是O(k)。然后接下来，对于每个新加入元素，判断要将堆里的哪个元素替换掉，判断和处理的时间代价是O(logk)。这样这个堆就一直是保持有k个元素。处理完了n个元素以后，时间代价就是O(n logk)。 而另一种方法，是先对n个元素建一个堆，这时候时间代价是O(n)，然后接下来，我们在这个堆中，进行k次操作，将堆顶的最大值取出。每次取出堆顶元素，调整的时间代价是O(log n)。因此，处理完k个元素，时间代价就是O(k log n) 你会看到，我在文章中说的O(n) + O(k log n)的方法，其实就是第二种方法，我其实也简单做了描述。至于它和第一种方法相比，哪个更快，你会发现，当n很大的时候，第二种方法，其实时间代价是接近O(n)的，会比第一种方法O(n log k)快上接近log k倍。 此外，如果不使用堆的话，我们还可以使用快速选择排序（注意，不是快排，但是使用了快排的partition思想），也是可以在O（n）的时间代价完成top K的检索的。

作者回复: 其实这道题的核心有几个个: 1.分治处理 2.哈希统计 3.堆 4.内存与磁盘利用 首先，由于内存有限，肯定是要分批处理的。但是分批也有多种分法，比如你说的平均分为100个小文件，然后每个小文件统计其中每个url的个数。(这里其实就有细化问题:小文件怎么统计url出现次数，是做url排序，还是用hash表)。 但是，我也可以提供其他思路，比如我顺序读取文件，直接往内存的hash表中放，统计相同的url的个数，当hash表满时(到达内存上限)，我再将hash表以key-value形式写入小文件。这样可以生成n个k-v小文件。这是另一种分法。 然后对多个小文件合并，小文件中的key可能会重复，如果每个小文件的key都是有序的，那么可以用归并排序，快速进行key的合并。可以写成合并成一个有序大文件，文件内容是有序的key-value。 最后使用堆，读取该文件，保留top 100。

作者回复: 我当初在写这一篇的时候也很纠结，不确定是否应该保留还是删除。不过最后出于知识体系的完整性，我还是保留了这一篇，并尽可能用通俗的语言来描述。 不过不用担心，这是唯一一篇有公式的文章，如果公式不好理解也没关系，你只要知道，打分排序的代价很大就好了。下一篇就会恢复熟悉的味道。 还有，对于不清楚的地方，其实你可以找些时间，重新多读几次，也许哪天你就能取得意想不到的突破。

作者回复: 如果是or的话，那么其实也可以加权再相加。你会发现，由人工来制定规则的确会头大，因此不如交给机器学习打分，直接预估每个文档的点击率就好。 至于为什么写这一篇，我也补充几点: 1.对于一个完整的检索系统，检索结果的排序是无法回避的问题，包括在前面的课程中，留言已经有人提问，说如果检索出来的结果很多该怎么办？因此，这一篇文章能补全这个知识点，让我们知道搜索引擎，广告引擎和推荐系统是如何处理检索结果的。 2.索引构建和打分机制其实是有关系的。如果你在使用elastic search，并且使用了基于文档的索引拆分，然后又选择了系统自带的tf-idf或者bm25进行相关性打分，那么如果处理不当，相关性计算会变差。(因为idf没有在全局被更新)。 3.在下一篇讲如何加速检索的方案，你会发现好些内容会和这篇文章有关。敬请期待。

作者回复: 好的。这里要注意一点:tf和idf值其实在索引构建的时候就可以统计好的。你可以看一下索引构建那一章，在完整的索引里，doc的信息会包含了tf值。然后idf的信息可以存在token里。因此，完整的流程如下: 1.在索引构建时，在建立posting list时，在doc信息中存入tf的值，在token存入idf值。 2.在四个posting list做了归并以后，这时候我们会得到符合检索条件的候选doc列表。在归并的时候，同时累加tf*idf的值。就能得到每个doc的打分结果。 3.接下来，对于打好分的文档进行排序。就是最终结果。

作者回复: 你看得很细致也很严谨。的确严格来说，log是要标明底数的。但是你也会发现，许多场合都会直接写log n，因为在时间代价分析中，我们更看重的是量级，而不是常数级的倍数差异。因此以2为底还是以10为底，不会影响结论。另一方面，其实log不写底数时，大家约定俗成有默认底数(10或2都有，看具体上下文场景)。但的确写上会更清晰。谢谢你的细心指出，我看看后续优化一下。

作者回复: 打分的确是非常耗时的过程，因此，我们需要有更多的手段来加速打分过程。GPU的发展，还有矩阵运算等都是可用的手段。 还有，你提到了不少资料都把深度学习称为“用数据编程”。不过，我更愿意称为“用数据推导规则”。实际上，无论是机器学习还是深度学习，目前其实离我们真正期待的智能还有一段距离，从文中的简单例子你可以看到，机器学习更多是基于巨大的算力，用数据去拟合出一个有限的规则表达式，这个学习出来的规则其实还有许多可完善的地方，比如说人脸识别，有人就做过实验，给一个五官完整，但是比例和位置一看就不对的人脸图像给模型识别，结果模型识别为“真人”。因此，在人工智能方向上，我们还需要再往前走。

作者回复: 你的问题很好！ 1.对于df，的确会随着文档的增加而变化。因此是需要更新的。在倒排索引中，由于idf是和key存在一起的，因此，我们可以在文档变化时，对增量倒排索引的key中的idf值进行更新就可以了。不过要注意:如果使用了基于文档的水平拆分，那么增量索引只会在一个分片中生效。这样如果持续久了，idf值会不准，相关性计算精度会下降。因此，需要周期性地重构全量索引。 2.机器学习的模型也是需要频繁更新的。一般来说是每天都会更新，还有系统为了更新及时，还会使用在线学习进行更实时的模型更新。不过，我前面说的“机器学习模型更新”，指的是因子和对应权重的更新，并不是你问题中说的“重新计算分数”。因为对一个文档和当前查询词的相关性打分过程，本来就是在查询发生时实时进行的，而不是离线算好的。因此不存在“重复计算分数”这个问题。

作者回复: 你说得很对。其实我在文中也提到了，机器学习打分，会考虑更多的维度了，包括“用户的历史点击行为”，这其实就是你说的“考虑用户”了。 而关于搜索和推荐，它们的许多底层技术是相通的，区别在于两者的约束条件和目标不同。搜索引擎由于有着明确的用户输入和意图，因此对于query相关性的要求很高。而推荐引擎由于没有明确的用户输入信号，因此自由度会更大，可以从更多的维度去考虑检索和排序问题。

作者回复: 1.的确，最耗时的步骤其实是打分，因此，我们如果想加快检索效率的话，如何优化打分过程就是一个很重要的方向。 2.机器学习打分的例子，的确文中没有说得太详细。其实机器学习的关键就是寻找因子(也就是特征)，以及学习权重的过程。对于机器学习和特征工程方向，这其实是另一个领域，也许有机会可以在其他地方再具体描述一下。