终于把序号写到了第十篇（其实已经是第13篇了），前面写了几个外篇，我看上篇机器学习的那篇看的人很多，后面会再找一两个点再写写，后面可能会算法部分和架构部分穿插着写了，想到哪里就写哪里了，今天我们继续我们的搜索引擎架构部分，主要来说说数据的检索。

对之前文章感兴趣的话，可以点击下面的链接，或者直接在SF上看整个专栏--吴说
搜索架构
用Golang写一个搜索引擎（0x00）从零开始
用Golang写一个搜索引擎（0x01）基本概念
用Golang写一个搜索引擎（0x02）倒排索引技术
用Golang写一个搜索引擎（0x03）跳跃表，哈希表
用Golang写一个搜索引擎（0x04）B+树
用Golang写一个搜索引擎（0x06）索引构建
用Golang写一个搜索引擎（0x07）正排索引
用Golang写一个搜索引擎（0x08）索引的段
用Golang写一个搜索引擎（0x09）数据增删改
搜索算法
用Golang写一个搜索引擎（0x05）文本相关性排序
用Golang写一个搜索引擎（0xFF）搜索排序
搜索引擎（0xFE）--- 用机器学习再谈排序

之前我们说完了数据的增，删，改，还剩下一个查没有写，今天来写写查。

搜索引擎最核心的东西就是查了，在查上面，也有很多好玩的数据结构和算法，我们一个一个来说说。

之前说了搜索引擎的核心底层数据结构包括两个：倒排索引和正排索引，倒排索引主要用来检索，正排索引主要用来过滤，我们就以一个搜索请求来说说搜索引擎的检索。

比如我们有最近3个月新浪微博的数据在搜索引擎中，数据有发布者昵称，微博内容，微博发布时间，要搜索的关键词是长沙雅礼中学，而且只要看最近10天的数据，那么这么一个典型的搜索场景是怎么来进行的呢？我们先假设我们数据是这样的4条数据

"nickname" : "长沙天气预报" "content":"今天天气真好" "datetime":"2016-05-06"
"nickname" : "路人甲" "content":"长沙天气真好，我现在在雅礼中学" "datetime":"2016-01-21"
"nikename" : "雅礼中学官微" "content":"长沙天气真好" "datetime":"2016-05–05"

Query分析

首先关键词来了以后要进行的第一步是query分析，query分析相当复杂，也直接影响到搜索效果，有很多算法上的东西，这个需要单独说，呵呵。

当然，最简单的query分析就是切词了，我们这里不讲算法，所以query分析直接就是切词了，切词完了以后变成了长沙/雅礼/中学，后面的10天这个约束条件就变成了range(2016-05-01，2016-05-10)，好了，query分析就完了。

数据检索

1.获取倒排链

query分析完了以后，就开始进行倒排检索了，倒排检索就是按照切词的结果，一个term一个term的从倒排文件中拉取倒排链，简单来说是这样的

//从B+树中获取关键字倒排链的文件偏移offset
ok, offset := this.btree.Search(this.fieldName, keystr)
if !ok {
  return nil, false
}
//文件偏移的第一个位置保存的倒排链的长度
lens := this.idxMmap.ReadInt64(int64(offset))
//通过offset和倒排链的长度获取整个倒排链
res := this.idxMmap.ReadDocIdsArry(uint64(offset+8), uint64(lens))
return res, true

这样，通过三次调用就得到3个倒排链了，然后开始检索的第二步。

上面的数据中，我们要检索长沙/雅礼/中学，我们发现，三条数据都满足这个条件，不一样的是第一条和第二条是单个字段就满足，第三条是跨字段了，需要两个字段合起来才满足匹配条件，所以，我们的检索过程并不是简单的求倒排链的交集，而是一个求并求交的组合过程。

先单个的term在多个字段求并集，然后再多个term之间求交集，这样能满足找到所有符合条件的结果。

2.单term多字段间求并

多路求并也叫K路并归，比如长沙这个term，在检索nickname的时候，找到docid为[1]，检索content的时候，找到docid为[2,3]，两个docid链求并集，得到[1,2,3]，就是我们最后要求的结果。

这里只是一个两路的求并集，比较简单，如果是更多的字段检索，那么就会有超过两个的多路求并，一般我们使用胜者树或者败者树来进行K路求并的操作。

胜者树，败者树

所谓胜者树，是一种外部归并排序经常使用的数据结构，我们这里用他来做多路的求并集操作，因为我们的倒排链是以mmap的形式进行存储的，其实也是一种外部存储。

简单的说，胜者树就是以K路的数据作为叶子节点，建立一棵完全二叉树，然后叶子节点两两比较，胜利者进入上一层节点中，指导最后得到一个最后的胜利者输出，输出以后将对应的数据更新，光这么说太抽象了，我们看个图就明白了，比如我们目前有4路求并集，4路的数据分别是[0,2,3]，[1,2]，[0,3]，[3,4]，那么整个胜者树的过程就是下面的这个图，从左到右表示胜者树的求并过程。

上面那个图中

• 首先，有4个数组，那么建立一个有四个叶子节点的平衡完全二叉树，每个叶子节点存储一个倒排链，把每个倒排链的第一个元素拿出来准备进行比较

• 两两比较，较小的那个进入上一层节点，然后上一层节点继续两两比较，较小的那个进入上一层节点，直到最后到达根节点，图中的红色部分

• 把最后战斗到根节点的元素输出到最终结果中（如果最终结果中最后一个元素和这个根节点元素一样，丢弃这个元素）

• 将最后获胜的元素的倒排链指针后移一位，将该链的后一个元素拿出来进行比较

这样的话，在时间复杂度为O(nlogk)的情况下，我们就把并集求好了。

求并集的方法也有很多，我们这里只举出了比较常见的，胜者树这种结构比较好理解，但在实现的时候，一般采用胜者树的变体败者树，败者数的原理和胜者树一样，有区别的地方是，两两比较的时候败者树保存的是败者的信息，而胜者接着往上层进行战斗，直到根节点位置，最后输出的还是胜者。

败者树的过程我也画了个图，在下面

败者树的优势在于新进来的元素，只需要跟他的父节点进行比较就行了（只需要一次指针操作就可以找到父节点），胜者树的话还需要找临近节点比较（需要两次指针操作才能找到临近节点），然后更新父节点信息，所以败者树效率更优一点。

3.多term之间求交

上一步中拿到了各个term的倒排链以后，为了保证每个document中都含有所有词，就要对他们求交集了，因为倒排链是按照docid从小到大排列的，所以求交集实际上是对多个有序数组求交集。

如果是两个倒排链的话比较容易，拿两个指针分别指向两个倒排链的首部，然后比较大小，哪个小，那么把这个指针后移一位，如果两个相等，那么把这个docid取出来，直到某一条倒排链遍历完，时间复杂度O(n+m)，最好的情况是O(min(n,m))，代码也很简单，核心的就这么几行：

ia,ib:=0,0
for ia < lena && ib < lenb {
    if a[ia].Docid == b[ib].Docid {
        c[lenc] = a[ia]
        lenc++
        ia++
        ib++
        continue
    }
    if a[ia].Docid < b[ib].Docid {
        ia++
    } else {
        ib++
    }
}
return c

这是两个倒排链求交集，如果是多个倒排链求交集的话，可以两两求交，最后就完成了。

这样效率比较低，这里我们再介绍一种方法

• 因为求交集最后的结果长度肯定不会超过最短的倒排链的长度，所以我们首先找到长度最短的倒排链，作为标称数组。

• 从标称数组中依次取出每个元素，查看元素是不是在其他的每一个倒排链中

• 如果这个元素在其他所有倒排链中都存在，那么就把这个元素放入最终结果集中。

上面的第二步又可以从以下几个方面优化一下

• 如果发现某个元素不在某个倒排链中，那么他肯定不在最终结果中，直接跳出，不用继续比较了。

• 如果某个倒排链被查找完了，那么也可以跳出了。

• 查找元素是否在某个倒排链中，可以使用下面几个方式来优化

  • 一是可以使用二分查找来找，这样复杂度可以降低一个数量级。

  • 因为我们的docid是连续的，所以可以设定一个哨兵指针，然后从哨兵指针往后遍历，遍历到倒排链中的元素大于当前元素就停止，然后把哨兵移动到这个元素位置就行，这样的话只是给每个倒排链表加了个哨兵，复杂度上却降低了一个数量级了。

如果用二分查找的话，假如每个倒排链长度为N，一共有K个倒排链，那么整体最坏情况下复杂度是O(N*K*logN)，如果用哨兵的方法的话，一般比这个还要快一点。

下面这个图是优化后的多路求交，绿色的是标称数组中的元素，红色的是哨兵，黄色的是命中的元素。

4.正排过滤

到这一步，通过倒排文件能找到的元素就都找到了，像上面那个例子，我们找到了2和3两条记录，然后就要用第二个条件最近10天的数据来进行过滤操作了。

过滤操作比较简单，需要遍历一边结果集，然后用正排文件的值判断是否满足条件，这么遍历一下，就只剩下记录3了，这也是我们最后得到的结果。

在这里再说一下，之前我们说数据的增删改的时候说了，删除数据或者修改数据的时候实际上只是在bitmap上做了一个标记，表示这个数据删除了，所以最后检索的时候需要把已经删除的数据去掉，这一步也是在这里做，在遍历整个结果集做正排过滤的时候可以一起判断这个文档是否被删除了，只有满足过滤条件并且没有被删除的文档才能留下来。

由于正排文件的保存是按照docid来做数组下表保存的，所以查找的复杂度是O(1)，时间基本上就是遍历一边结果集加上条件判断的时间。

统计汇总

上面这些都做完了以后，就得到了最终的完整结果集，这时候在对结果集进行统计汇总之类的操作就简单了，这个可以根据业务的要求，做任何形式的统计汇总需求了，文本相关性的打分一般在求交集和求并集的时候就做完了，之前说的精细化的排序也在这一步来进行。

结束

好了，上面就是一次完整的检索过程中所涉及到的各种东西，关于query分析部分需要单独说，这一篇就不展开了。希望大家看得开心。

欢迎关注我的公众号，文章会在这里首先发出来：）扫描或者搜索微信号XJJ267或者搜索中文西加加语言就行

平时接触的开源产品如Redis、ACE，事件模型都使用的Reactor模式；而同样做事件处理的Proactor，由于操作系统的原因，相关的开源产品也少；这里学习下其模型结构，重点对比下两者的异同点；

反应器Reactor

Reactor模式结构

Reactor包含如下角色：

• Handle 句柄；用来标识socket连接或是打开文件；
• Synchronous Event Demultiplexer：同步事件多路分解器：由操作系统内核实现的一个函数；用于阻塞等待发生在句柄集合上的一个或多个事件；（如select/epoll；）
• Event Handler：事件处理接口
• Concrete Event HandlerA：实现应用程序所提供的特定事件处理逻辑；
• Reactor：反应器，定义一个接口，实现以下功能：
  1）供应用程序注册和删除关注的事件句柄；
  2）运行事件循环；
  3）有就绪事件到来时，分发事件到之前注册的回调函数上处理；

“反应”器名字中”反应“的由来：

“反应”即“倒置”，“控制逆转”

具体事件处理程序不调用反应器，而是由反应器分配一个具体事件处理程序，具体事件处理程序对某个指定的事件发生做出反应；这种控制逆转又称为“好莱坞法则”（不要调用我，让我来调用你）

业务流程及时序图

1. 应用启动，将关注的事件handle注册到Reactor中；
2. 调用Reactor，进入无限事件循环，等待注册的事件到来；
3. 事件到来，select返回，Reactor将事件分发到之前注册的回调函数中处理；

Proactor模式

Proactor模式结构

Proactor主动器模式包含如下角色

• Handle 句柄；用来标识socket连接或是打开文件；
• Asynchronous Operation Processor：异步操作处理器；负责执行异步操作，一般由操作系统内核实现；
• Asynchronous Operation：异步操作
• Completion Event Queue：完成事件队列；异步操作完成的结果放到队列中等待后续使用
• Proactor：主动器；为应用程序进程提供事件循环；从完成事件队列中取出异步操作的结果，分发调用相应的后续处理逻辑；
• Completion Handler：完成事件接口；一般是由回调函数组成的接口；
• Concrete Completion Handler：完成事件处理逻辑；实现接口定义特定的应用处理逻辑；

业务流程及时序图

1. 应用程序启动，调用异步操作处理器提供的异步操作接口函数，调用之后应用程序和异步操作处理就独立运行；应用程序可以调用新的异步操作，而其它操作可以并发进行；
2. 应用程序启动Proactor主动器，进行无限的事件循环，等待完成事件到来；
3. 异步操作处理器执行异步操作，完成后将结果放入到完成事件队列；
4. 主动器从完成事件队列中取出结果，分发到相应的完成事件回调函数处理逻辑中；

对比两者的区别

主动和被动

以主动写为例：

• Reactor将handle放到select()，等待可写就绪，然后调用write()写入数据；写完处理后续逻辑；
• Proactor调用aoi_write后立刻返回，由内核负责写操作，写完后调用相应的回调函数处理后续逻辑；

可以看出，Reactor被动的等待指示事件的到来并做出反应；它有一个等待的过程，做什么都要先放入到监听事件集合中等待handler可用时再进行操作；
Proactor直接调用异步读写操作，调用完后立刻返回；

实现

Reactor实现了一个被动的事件分离和分发模型，服务等待请求事件的到来，再通过不受间断的同步处理事件，从而做出反应；

Proactor实现了一个主动的事件分离和分发模型；这种设计允许多个任务并发的执行，从而提高吞吐量；并可执行耗时长的任务（各个任务间互不影响）

优点

Reactor实现相对简单，对于耗时短的处理场景处理高效；
操作系统可以在多个事件源上等待，并且避免了多线程编程相关的性能开销和编程复杂性；
事件的串行化对应用是透明的，可以顺序的同步执行而不需要加锁；
事务分离：将与应用无关的多路分解和分配机制和与应用相关的回调函数分离开来，

Proactor性能更高，能够处理耗时长的并发场景；

缺点

Reactor处理耗时长的操作会造成事件分发的阻塞，影响到后续事件的处理；

Proactor实现逻辑复杂；依赖操作系统对异步的支持，目前实现了纯异步操作的操作系统少，实现优秀的如windows IOCP，但由于其windows系统用于服务器的局限性，目前应用范围较小；而Unix/Linux系统对纯异步的支持有限，应用事件驱动的主流还是通过select/epoll来实现；

适用场景

Reactor：同时接收多个服务请求，并且依次同步的处理它们的事件驱动程序；
Proactor：异步接收和同时处理多个服务请求的事件驱动程序；

参考

《面向模式的软件体系结构 卷2》
《面向模式的软件架构 卷4》

Posted by: 大CC | 28APR,2015
博客：blog.me115.com [订阅]
微博：新浪微博

平时接触的开源产品如Redis、ACE，事件模型都使用的Reactor模式；而同样做事件处理的Proactor，由于操作系统的原因，相关的开源产品也少；这里学习下其模型结构，重点对比下两者的异同点；

反应器Reactor

Reactor模式结构

Reactor包含如下角色：

• Handle 句柄；用来标识socket连接或是打开文件；
• Synchronous Event Demultiplexer：同步事件多路分解器：由操作系统内核实现的一个函数；用于阻塞等待发生在句柄集合上的一个或多个事件；（如select/epoll；）
• Event Handler：事件处理接口
• Concrete Event HandlerA：实现应用程序所提供的特定事件处理逻辑；
• Reactor：反应器，定义一个接口，实现以下功能：
  1）供应用程序注册和删除关注的事件句柄；
  2）运行事件循环；
  3）有就绪事件到来时，分发事件到之前注册的回调函数上处理；

“反应”器名字中”反应“的由来：

“反应”即“倒置”，“控制逆转”

具体事件处理程序不调用反应器，而是由反应器分配一个具体事件处理程序，具体事件处理程序对某个指定的事件发生做出反应；这种控制逆转又称为“好莱坞法则”（不要调用我，让我来调用你）

业务流程及时序图

1. 应用启动，将关注的事件handle注册到Reactor中；
2. 调用Reactor，进入无限事件循环，等待注册的事件到来；
3. 事件到来，select返回，Reactor将事件分发到之前注册的回调函数中处理；

Proactor模式

Proactor模式结构

Proactor主动器模式包含如下角色

• Handle 句柄；用来标识socket连接或是打开文件；
• Asynchronous Operation Processor：异步操作处理器；负责执行异步操作，一般由操作系统内核实现；
• Asynchronous Operation：异步操作
• Completion Event Queue：完成事件队列；异步操作完成的结果放到队列中等待后续使用
• Proactor：主动器；为应用程序进程提供事件循环；从完成事件队列中取出异步操作的结果，分发调用相应的后续处理逻辑；
• Completion Handler：完成事件接口；一般是由回调函数组成的接口；
• Concrete Completion Handler：完成事件处理逻辑；实现接口定义特定的应用处理逻辑；

业务流程及时序图

1. 应用程序启动，调用异步操作处理器提供的异步操作接口函数，调用之后应用程序和异步操作处理就独立运行；应用程序可以调用新的异步操作，而其它操作可以并发进行；
2. 应用程序启动Proactor主动器，进行无限的事件循环，等待完成事件到来；
3. 异步操作处理器执行异步操作，完成后将结果放入到完成事件队列；
4. 主动器从完成事件队列中取出结果，分发到相应的完成事件回调函数处理逻辑中；

对比两者的区别

主动和被动

以主动写为例：

• Reactor将handle放到select()，等待可写就绪，然后调用write()写入数据；写完处理后续逻辑；
• Proactor调用aoi_write后立刻返回，由内核负责写操作，写完后调用相应的回调函数处理后续逻辑；

可以看出，Reactor被动的等待指示事件的到来并做出反应；它有一个等待的过程，做什么都要先放入到监听事件集合中等待handler可用时再进行操作；
Proactor直接调用异步读写操作，调用完后立刻返回；

实现

Reactor实现了一个被动的事件分离和分发模型，服务等待请求事件的到来，再通过不受间断的同步处理事件，从而做出反应；

Proactor实现了一个主动的事件分离和分发模型；这种设计允许多个任务并发的执行，从而提高吞吐量；并可执行耗时长的任务（各个任务间互不影响）

优点

Reactor实现相对简单，对于耗时短的处理场景处理高效；
操作系统可以在多个事件源上等待，并且避免了多线程编程相关的性能开销和编程复杂性；
事件的串行化对应用是透明的，可以顺序的同步执行而不需要加锁；
事务分离：将与应用无关的多路分解和分配机制和与应用相关的回调函数分离开来，

Proactor性能更高，能够处理耗时长的并发场景；

缺点

Reactor处理耗时长的操作会造成事件分发的阻塞，影响到后续事件的处理；

Proactor实现逻辑复杂；依赖操作系统对异步的支持，目前实现了纯异步操作的操作系统少，实现优秀的如windows IOCP，但由于其windows系统用于服务器的局限性，目前应用范围较小；而Unix/Linux系统对纯异步的支持有限，应用事件驱动的主流还是通过select/epoll来实现；

适用场景

Reactor：同时接收多个服务请求，并且依次同步的处理它们的事件驱动程序；
Proactor：异步接收和同时处理多个服务请求的事件驱动程序；

参考

《面向模式的软件体系结构 卷2》
《面向模式的软件架构 卷4》

Posted by: 大CC | 28APR,2015
博客：blog.me115.com [订阅]
微博：新浪微博

欢迎大家前往腾讯云+社区，获取更多腾讯海量技术实践干货哦~

本文由jj发表于云+社区专栏

一、推荐系统概述

1.1 概述

推荐系统目前几乎无处不在，主流的app都基本应用到了推荐系统。例如，旅游出行，携程、去哪儿等都会给你推荐机票、酒店等等；点外卖，饿了么、美团等会给你推荐饭店；购物的时候，京东、淘宝、亚马逊等会给你推荐“可能喜欢”的物品；看新闻，今日头条、腾讯新闻等都会给你推送你感兴趣的新闻....几乎所有的app应用或网站都存在推荐系统。

究其根本的原因，推荐系统的流行是因为要去解决一个问题：物品越来越多，信息越来越多，而人的精力和时间是有限的，需要一个方式去更有效率地获取信息，链接人与信息。

推荐系统就是为了解决这一问题而诞生的，在海量的物品和人之间，架起来一条桥梁。它就像一个私人的专属导购，根据你的历史行为、个人信息等等，为每个人diy进行推荐，千人前面，帮助人们更好、更快地选择自己感兴趣的、自己需要的东西。今日头条系的feed流在推荐算法的加持下，短短几年的用户增长速度和使用时长数据令人咂舌，受到了市场的追捧和高估值。一夜之间，几乎所有的app都开始上feed流、上各种推荐，重要性可见一斑。

1.2 基本架构

我们先把推荐系统简单来看，那么它可以简化为如下的架构。

图1 推荐系统一般流程

不管是复杂还是简单的推荐系统，基本都包含流程：

• 1）结果展示部分。不管是app还是网页上，会有ui界面用于展示推荐列表。
• 2）行为日志部分。用户的各种行为会被时刻记录并被上传到后台的日志系统，例如点击行为、购买行为、地理位置等等。这些数据后续一般会被进行ETL（extract抽取、transform转换、load加载），供迭代生成新模型进行预测。
• 3）特征工程部分。得到用户的行为数据、物品的特征、场景数据等等，需要人工或自动地去从原始数据中抽取出特征。这些特征作为输入，为后面各类推荐算法提供数据。特征选取很重要，错的特征必定带来错误的结果。
• 4）召回部分。 有了用户的画像，然后利用数据工程和算法的方式，从千万级的产品中锁定特定的候选集合，完成对推荐列表的初步筛选，其在一定程度上决定了排序阶段的效率和推荐结果的优劣。
• 5）排序部分。针对上一步的候选集合，会进行更精细化地打分、排序，同时考虑新颖性、惊喜度、商业利益等的一系列指标，获得一份最终的推荐列表并进行展示。

完整的推荐系统还会包括很多辅助模块，例如线下训练模块，让算法研究人员利用真实的历史数据，测试各类不同算法，初步验证算法优劣。线下测试效果不错的算法就会被放到线上测试，即常用的A/B test系统。它利用流量分发系统筛选特定的用户展示待测试算法生成的推荐列表，然后收集这批特定用户行为数据进行线上评测。

图2 蘑菇街推荐系统架构

推荐系统每个部分可大可小，从图2可知，各部分涉及的技术栈也较多。终端app每时每刻都在不断上报各类日志，点击、展示、时间、地理位置等等信息，这些海量信息需要依赖大数据相关软件栈支持，例如Kafka、spark、HDFS、Hive等，其中Kafka常被用于处理海量日志上报的消费问题。将数据进行ETL后存入Hive数据仓库，就可进行各类线上、线下测试使用。线下的算法会上线到线上环境进行ABtest，ABtest涉及完整的测试回路打通，不然拿不到结果，也无法快速开发迭代算法。线上推荐系统还要关注实时特征、离线特征，在性能和各类指标、商业目标间取均衡。

1.3 评测指标

一个东西做得好还是不好，能不能优化，首要前提是确定评测指标。只有确定了评测指标，才能有优化的方向。评测推荐系统的指标可以考虑以下几个方面：

1.3.1 用户满意度

用户作为推进系统的主要参与者，其满意度是评测系统的最重要指标。满意度可以通过做用户调查或线上实验获得。在在线系统中，一般通过对用户行为的统计得到，例如点击率、用户停留时间和转化率等指标度量用户的满意度。

1.3.2 预测精确度precision

预测准确度度量一个推荐系统或者推荐算法预测用户行为的能力。这个指标是最重要的离线评测指标。由于离线数据可计算，绝大部分科研人员都在讨论这个指标。

评分预测问题一般使用RMSE、MAE等，TopN预测问题一般使用Recall、Precision等。

图3 常见的指标准确率(Precision)、召回率(Recall)、误检率

其实目前国内很多地方和资料混淆了两个指标的叫法，把准确度对应英文precision指标。不过尽量还是用英文比较好。

准确度Accuracy = (TP + TN) / (TP + FP + TN + FN)

精确度Precision=TP/(TP+FP)

1.3.3 覆盖率coverage

覆盖率描述一个推荐系统对物品长尾的发掘能力。覆盖率有很多定义方法，最简单的计算就是推荐列表中的物品数量，除以所有的物品数量。

在信息论和经济学中有两个著名的指标用来定义覆盖率，一个是信息熵，一个是基尼系数。具体公式和介绍可以google。

ps：长尾在推荐系统中是个常见的名词。举个例子帮助大家理解，在商店里，由于货架和场地有限，摆在最显眼的地方的物品通常是出名的、热门的，从而销量也是最好的。很多不出名或者小知名度的商品由于在货架角落或者根本上不了货架，这些商品销量很差。在互联网时代，这一现象会被打破。电子商城拥有几乎无限长的“货架”，它可以为用户展现很多满足他小众需求的商品，这样总的销量加起来将远远超过之前的模式。

Google是一个最典型的“长尾”公司，其成长历程就是把广告商和出版商的“长尾”商业化的过程。数以百万计的小企业和个人，此前他们从未打过广告，或从没大规模地打过广告。他们小得让广告商不屑一顾，甚至连他们自己都不曾想过可以打广告。但Google的AdSense把广告这一门槛降下来了：广告不再高不可攀，它是自助的，价廉的，谁都可以做的；另一方面，对成千上万的Blog站点和小规模的商业网站来说，在自己的站点放上广告已成举手之劳。Google目前有一半的生意来自这些小网站而不是搜索结果中放置的广告。数以百万计的中小企业代表了一个巨大的长尾广告市场。这条长尾能有多长，恐怕谁也无法预知。无数的小数积累在一起就是一个不可估量的大数，无数的小生意集合在一起就是一个不可限量的大市场。

图4 长尾曲线

1.3.4多样性

用户的兴趣是多样的，推荐系统需要能覆盖用户各种方面的喜好。这里有个假设，如果推荐列表比较多样，覆盖了用户各种各样的兴趣，那么真实命中用户的兴趣概率也会越大，那么就会增加用户找到自己感兴趣的物品的概率。

1.3.5 新颖性

新颖的推荐是指给用户推荐那些他们以前没有听说过的物品。要准确地统计新颖性需要做用户调查。

1.3.6 惊喜度

如果推荐结果和用户的历史兴趣不相似，但却让用户觉得满意，那么就可以说推荐结果的惊喜度很高，而推荐的新颖性仅仅取决于用户是否听说过这个推荐结果。

1.3.7 信任度

用户对推荐系统的信任程度。如果用户信任推荐系统，那就会增加用户和推荐系统的交互。特别是在电子商务推荐系统中，让用户对推荐结果产生信任是非常重要的。同样的推荐结果，以让用户信任的方式推荐给用户就更能让用户产生购买欲，而以类似广告形式的方法推荐给用户就可能很难让用户产生购买的意愿。提高推荐系统的信任度主要有两种方法。首先需要增加推荐系统的透明度（transparency），而增加推荐系统透明度的主要办法是提供推荐解释。其次是考虑用户的社交网络信息，利用用户的好友信息给用户做推荐，并且用好友进行推荐解释。

1.3.8 实时性

在很多网站中，因为物品（新闻、微博等）具有很强的时效性，所以需要在物品还具有时效性时就将它们推荐给用户。因此，在这些网站中，推荐系统的实时性就显得至关重要。

推荐系统的实时性包括两个方面。首先，推荐系统需要实时地更新推荐列表来满足用户新的行为变化。实时性的第二个方面是推荐系统需要能够将新加入系统的物品推荐给用户。这主要考验了推荐系统处理物品冷启动的能力。

1.3.9 健壮性

衡量了一个推荐系统抗击作弊的能力。算法健壮性的评测主要利用模拟攻击。首先，给定一个数据集和一个算法，可以用这个算法给这个数据集中的用户生成推荐列表。然后，用常用的攻击方法向数据集中注入噪声数据，然后利用算法在注入噪声后的数据集上再次给用户生成推荐列表。最后，通过比较攻击前后推荐列表的相似度评测算法的健壮性。如果攻击后的推荐列表相对于攻击前没有发生大的变化，就说明算法比较健壮。

1.3.10 商业目标

很多时候，评测推荐系统更加注重商业目标是否达成，而商业目标和盈利模式是息息相关的。一般来说，最本质的商业目标就是平均一个用户给公司带来的盈利。不过这种指标不是很难计算，只是计算一次需要比较大的代价。因此，很多公司会根据自己的盈利模式设计不同的商业目标。

1.3.11 参考资料

推荐系统的评测问题有很多的相关研究和资料，预详细研究可阅读参考：

• 《推荐系统实战》
• 《Evaluating Recommendation Systems》
• What metrics are used for evaluating recommender systems?

二、常用算法

推荐算法的演化可以简单分为3个阶段，也是推荐系统由简单到复杂的迭代。

2.1 推荐算法演化

2.1.1 人工运营

这个阶段是随机的，人工根据运营目的，手工给特定类别的用户推送特定的内容。

优点是：

• 方便推广特定的内容；
• 推荐的内容易解释；

缺点是：

• 千人一面，推送的内容一样；
• 人工筛选，推送，耗费人力巨大；
• 运营根据自己的知识，主观性比较大；

2.1.2 基于统计的推荐

会基于一些简单的统计学知识做推荐，例如某个内别卖得最好的热门榜；再细致一些，将用户按个人特质划分，再求各种热度榜等。

优点是：

• 热门就是大部分用户喜好的拟合，效果好；
• 推荐的内容易解释；

缺点是：

• 千人一面，推送的内容一样；
• 马太效应，热门的会越来越热门，冷门的越来越冷门；
• 效果很容易达到天花板；

2.1.3 个性化推荐

当前阶段的推荐，会基于协同过滤算法、基于模型的算法、基于社交关系等，机器学习、深度学习逐渐引入，提高了推荐效果。

优点是：

• 效果要相对于之前，要好很多；
• 千人前面，每个人都有自己独特的推荐列表；

缺点是：

• 门槛较高，推荐系统搭建、算法设计、调优等等，都对开发者有较高的要求；
• 成本较高，而且是个长期迭代优化的过程，人力物力投入很高；

2.2 推荐算法汇总

内部一个分享这样分类常用的推荐算法：

图5 推荐算法分类

这里提到的Memory-based算法和Model-based算法的差别是什么？这也是我之前关注的问题，找到个资料，讲解得比较透彻。

Memory-based techniques use the data (likes, votes, clicks, etc) that you have to establish correlations (similarities?) between either users (Collaborative Filtering) or items (Content-Based Recommendation) to recommend an item i to a user u who’s never seen it before. In the case of collaborative filtering, we get the recommendations from items seen by the user’s who are closest to u, hence the term collaborative. In contrast, content-based recommendation tries to compare items using their characteristics (movie genre, actors, book’s publisher or author… etc) to recommend similar new items.

In a nutshell, memory-based techniques rely heavily on simple similarity measures (Cosine similarity, Pearson correlation, Jaccard coefficient… etc) to match similar people or items together. If we have a huge matrix with users on one dimension and items on the other, with the cells containing votes or likes, then memory-based techniques use similarity measures on two vectors (rows or columns) of such a matrix to generate a number representing similarity.

Model-based techniques on the other hand try to further fill out this matrix. They tackle the task of “guessing” how much a user will like an item that they did not encounter before. For that they utilize several machine learning algorithms to train on the vector of items for a specific user, then they can build a model that can predict the user’s rating for a new item that has just been added to the system.

Since I’ll be working on news recommendations, the latter technique sounds much more interesting. Particularly since news items emerge very quickly (and disappear also very quickly), it makes sense that the system develops some smart way of detecting when a new piece of news will be interesting to the user even before other users see/rate it.

Popular model-based techniques are Bayesian Networks, Singular Value Decomposition, and Probabilistic Latent Semantic Analysis (or Probabilistic Latent Semantic Indexing). For some reason, all model-based techniques do not enjoy particularly happy-sounding names.

《携程个性化推荐算法实践》一文中梳理了工业界应用的排序模型，大致经历三个阶段：

图6 排序模型演进

本文不对上面的这些算法进行详细的原理探讨，会比较复杂，有兴趣可以再自行学习。

2.3 CF算法示例

为了学习这块的技术知识，跟着参加了下内部举办的srtc推荐比赛。重在参与，主要是学习整个基本流程，体会下推荐场景，了解腾讯内部做得好的团队和产品是什么样子。

2.3.1（内部敏感资料，删除）

2.3.2 CF算法

在web平台上点一点，可能失去了学习的意义。所以本着学习的态度，我在线下自己的机器上实现了一些常用的算法，例如CF等。

推荐算法里CF算是比较常见的，核心还是很简单的。

• user-cf基本原理

A.找到和目标用户兴趣相似的的用户集合； B.找到这个集合中的用户喜欢的，且目标用户没听过的物品推荐给目标用户。

• item-cf基本原理

A.计算物品之间的相似度； B.根据物品的相似度和用户的历史行为给用户生成推荐列表。

结合前面总结的，cf属于memory-base的算法，很大一个特征就是会用到相似度的函数。这个user-cf需要计算用户兴趣的相似度，item-cf需要计算物品间的相似度。基于相似度函数的选择、编程语言的选择、实现方式的选择、优化的不同，结果和整个运行时间会很大不同。当时就简单用python实现的，8个process跑满cpu同时处理，需要近10个小时跑完。后面了解到有底层进行过优化的pandas、numpy等，基于这些工具来实现速度会快很多。

2.3.3 收获

哈哈，第一次参加这种比赛，虽然成绩很差，但自己觉得很是学到很多东西，基本达到了参赛的目的。在真实的场景和数据下去思考各种影响因素，体会各种算法从设计、实现、训练、评价等各阶段，很多东西确实比看资料和书来得更深入。果然实践才是学习的最好手段。如果想更深入去搞推荐算法这块，感觉需要继续学习目前各种热门算法的原理、潜规则，kaggle上多练手，以及锻炼相关的平台及工程化能力。

三、业界推荐系统调研

收集、研究了下网上一些推荐系统落地总结的文章，可以开拓视野，加深整体理解。

以下只是一些重要内容，有兴趣可以阅读原文：

• 《今日头条算法原理》，原文链接
• 《推荐算法在闲鱼小商品池的探索与实践》，原文链接
• 《饿了么推荐系统：从0到1》，原文链接
• 《爱奇艺个性化推荐排序实践》，原文链接
• 《携程个性化推荐算法实践》，原文链接
• 《蘑菇街推荐工程实践》，原文链接

3.1 今日头条推荐系统

今日头条算法架构师曹欢欢博士，做过一次 《今日头条算法原理》的报告。主要涉及4部分：系统概览、内容分析、用户标签、评估分析。

• 四类典型推荐特征

第一类是相关性特征，就是评估内容的属性和与用户是否匹配。 第二类是环境特征，包括地理位置、时间。这些既是bias特征，也能以此构建一些匹配特征。 第三类是热度特征。包括全局热度、分类热度，主题热度，以及关键词热度等。 第四类是协同特征，它可以在部分程度上帮助解决所谓算法越推越窄的问题。

• 模型的训练上，头条系大部分推荐产品采用实时训练

模型的训练上，头条系大部分推荐产品采用实时训练。实时训练省资源并且反馈快，这对信息流产品非常重要。用户需要行为信息可以被模型快速捕捉并反馈至下一刷的推荐效果。我们线上目前基于storm集群实时处理样本数据，包括点击、展现、收藏、分享等动作类型。模型参数服务器是内部开发的一套高性能的系统，因为头条数据规模增长太快，类似的开源系统稳定性和性能无法满足，而我们自研的系统底层做了很多针对性的优化，提供了完善运维工具，更适配现有的业务场景。

目前，头条的推荐算法模型在世界范围内也是比较大的，包含几百亿原始特征和数十亿向量特征。整体的训练过程是线上服务器记录实时特征，导入到Kafka文件队列中，然后进一步导入Storm集群消费Kafka数据，客户端回传推荐的label构造训练样本，随后根据最新样本进行在线训练更新模型参数，最终线上模型得到更新。这个过程中主要的延迟在用户的动作反馈延时，因为文章推荐后用户不一定马上看，不考虑这部分时间，整个系统是几乎实时的。

但因为头条目前的内容量非常大，加上小视频内容有千万级别，推荐系统不可能所有内容全部由模型预估。所以需要设计一些召回策略，每次推荐时从海量内容中筛选出千级别的内容库。召回策略最重要的要求是性能要极致，一般超时不能超过50毫秒。

• 用户标签工程挑战更大

内容分析和用户标签是推荐系统的两大基石。内容分析涉及到机器学习的内容多一些，相比而言，用户标签工程挑战更大。 今日头条常用的用户标签包括用户感兴趣的类别和主题、关键词、来源、基于兴趣的用户聚类以及各种垂直兴趣特征（车型，体育球队，股票等）。还有性别、年龄、地点等信息。性别信息通过用户第三方社交账号登录得到。年龄信息通常由模型预测，通过机型、阅读时间分布等预估。常驻地点来自用户授权访问位置信息，在位置信息的基础上通过传统聚类的方法拿到常驻点。常驻点结合其他信息，可以推测用户的工作地点、出差地点、旅游地点。这些用户标签非常有助于推荐。

当然最简单的用户标签是浏览过的内容标签。但这里涉及到一些数据处理策略。主要包括：一、过滤噪声。通过停留时间短的点击，过滤标题党。二、热点惩罚。对用户在一些热门文章（如前段时间PG One的新闻）上的动作做降权处理。理论上，传播范围较大的内容，置信度会下降。三、时间衰减。用户兴趣会发生偏移，因此策略更偏向新的用户行为。因此，随着用户动作的增加，老的特征权重会随时间衰减，新动作贡献的特征权重会更大。四、惩罚展现。如果一篇推荐给用户的文章没有被点击，相关特征（类别，关键词，来源）权重会被惩罚。当然同时，也要考虑全局背景，是不是相关内容推送比较多，以及相关的关闭和dislike信号等。

• Hadoop集群压力过大，上线 Storm集群流式计算系统

面对这些挑战。2014年底今日头条上线了用户标签Storm集群流式计算系统。改成流式之后，只要有用户动作更新就更新标签，CPU代价比较小，可以节省80%的CPU时间，大大降低了计算资源开销。同时，只需几十台机器就可以支撑每天数千万用户的兴趣模型更新，并且特征更新速度非常快，基本可以做到准实时。这套系统从上线一直使用至今。

• 很多公司算法做的不好，并非是工程师能力不够，而是需要一个强大的实验平台，还有便捷的实验分析工具

A/B test系统原理

这是头条A/B Test实验系统的基本原理。首先我们会做在离线状态下做好用户分桶，然后线上分配实验流量，将桶里用户打上标签，分给实验组。举个例子，开一个10%流量的实验，两个实验组各5%，一个5%是基线，策略和线上大盘一样，另外一个是新的策略。

实验过程中用户动作会被搜集，基本上是准实时，每小时都可以看到。但因为小时数据有波动，通常是以天为时间节点来看。动作搜集后会有日志处理、分布式统计、写入数据库，非常便捷。

3.2 推荐算法在闲鱼小商品池的探索与实践

• 闲鱼中个性化推荐流程

商品个性化推荐算法主要包含Match和Rank两个阶段：Match阶段也称为商品召回阶段，在推荐系统中用户对商品的行为称为用户Trigger，通过长期收集用户作用在商品上的行为，建立用户行为和商品的矩阵称为X2I，最后通过用户的Trigger和关系矩阵X2I进行商品召回。Rank阶段利用不同指标的目标函数对商品进行打分，根据推荐系统的规则对商品的多个维度进行综合排序。下面以闲鱼的首页feeds为例，简单介绍闲鱼的个性化推荐流程。

所示步骤1.1，利用用户的信息获取用户Trigger，用户信息包括用户的唯一标识userId，用户的设备信息唯一标识uttid。

所示步骤1.2，返回用户Trigger其中包括用户的点击、购买过的商品、喜欢的类目、用户的标签、常逛的店铺、购物车中的商品、喜欢的品牌等。

所示步骤1.3，进行商品召回，利用Trigger和X2I矩阵进行join完成对商品的召回。

所示步骤1.4，返回召回的商品列表，在商品召回中一般以I2I关系矩阵召回的商品为主，其他X2I关系矩阵召回为辅助。

步骤2.1，进行商品过滤，对召回商品进行去重，过滤购买过的商品，剔除过度曝光的商品。

所示步骤2.2，进行商品打分，打分阶段利用itemInfo和不同算法指标对商品多个维度打分。

步骤2.3，进行商品排序，根据规则对商品多个维度的分数进行综合排序。

步骤2.4，进行返回列表截断，截断TopN商品返回给用户。

闲鱼通过以上Match和Rank两个阶段八个步骤完成商品的推荐，同时从图中可以看出为了支持商品的个性化推荐，需要对X2I、itemInfo、userTrigger数据回流到搜索引擎，这些数据包含天级别回流数据和小时级别回流数据。

• 小商品的特点

小商品池存在以下几个特点。

实时性：在闲鱼搭建的小商品池中要求商品可以实时的流入到该规则下的商品池，为用户提供最新的优质商品。

周期性：在小商品池中，很多商品拥有周期属性，例如免费送的拍卖场景，拍卖周期为6小时，超过6小时后将被下架。

目前频道导购页面大多还是利用搜索引擎把商品呈现给用户，为了保证商品的曝光，一般利用搜索的时间窗口在商品池中对商品进一步筛选，但是仍存在商品曝光的问题，如果时间窗口过大，那么将会造成商品过度曝光，如果商品窗口过小那么就会造成商品曝光不足，同时还存在一个搜索无法解决的问题，同一时刻每个用户看到的商品都是相同的，无法针对用户进行个性化推荐，为了进一步提升对用户的服务，小商品池亟需引入个性化推荐。

• 推荐在小商品池的解决方案

在上文中利用全站X2I数据对小商品池的商品进行推荐过程中，发现在Match阶段，当小商品池过小时会造成商品召回不足的问题，为了提升小商品池推荐过程中有效召回数量，提出了如下三种解决方案。

提前过滤法：数据回流到搜索引擎前，小商品池对数据进行过滤，产生小商品池的回流数据，在商品进行召回阶段，利用小商品池的X2I进行商品召回，以此提升商品的召回率。

商品向量化法： 在Match阶段利用向量相似性进行商品召回，商品向量化是利用向量搜索的能力，把商品的特性和规则通过函数映射成商品向量，同时把用户的Trigger和规则映射成用户向量，文本转换向量常用词袋模型和机器学习方法，词袋模型在文本长度较短时可以很好的把文本用词向量标识，但是文本长度过长时受限于词袋大小，如果词袋过小效果将会很差，机器学习的方法是利用Word2Vector把文本训练成向量，根据经验值向量维度一般为200维时效果较好。然后利用向量搜索引擎，根据用户向量搜索出相似商品向量，以此作为召回的商品。如图5所示商品的向量分两部分，前20位代表该商品的规则，后200位代表商品的基本特征信息。

商品搜索引擎法： 在Match阶段利用商品搜索引擎对商品进行召回，如图6所示在商品进入搜索引擎时，对商品结构进行理解，在商品引擎中加入Tag和规则，然后根据用户的Trigger和规则作为搜索条件，利用搜索引擎完成商品的召回。搜索引擎的天然实时性解决了小商品池推荐强实时性的问题。

3.3 饿了么推荐系统：从0到1

对于任何一个外部请求, 系统都会构建一个QueryInfo(查询请求), 同时从各种数据源提取UserInfo(用户信息)、ShopInfo(商户信息)、FoodInfo(食物信息)以及ABTest配置信息等, 然后调用Ranker排序。以下是排序的基本流程(如下图所示)：

#调取RankerManager, 初始化排序器Ranker：

1. 根据ABTest配置信息, 构建排序器Ranker；
2. 调取ScorerManger, 指定所需打分器Scorer(可以多个); 同时, Scorer会从ModelManager获取对应Model, 并校验；
3. 调取FeatureManager, 指定及校验Scorer所需特征Features。

#调取InstanceBuilder, 汇总所有打分器Scorer的特征, 计算对应排序项EntityInfo(餐厅/食物)排序所需特征Features；

#对EntityInfo进行打分, 并按需对Records进行排序。

这里需要说明的是：任何一个模型Model都必须以打分器Scorer形式展示或者被调用。主要是基于以下几点考虑：

• 模型迭代：比如同一个Model，根据时间、地点、数据抽样等衍生出多个版本Version；
• 模型参数：比如组合模式(见下一小节)时的权重与轮次设定，模型是否支持并行化等；
• 特征参数：特征Feature计算参数，比如距离在不同城市具有不同的分段参数。

3.4 爱奇艺个性化推荐排序实践

我们的推荐系统主要分为两个阶段，召回阶段和排序阶段。

召回阶段根据用户的兴趣和历史行为，同千万级的视频库中挑选出一个小的候选集（几百到几千个视频）。这些候选都是用户感兴趣的内容，排序阶段在此基础上进行更精准的计算，能够给每一个视频进行精确打分，进而从成千上万的候选中选出用户最感兴趣的少量高质量内容（十几个视频）。

推荐系统的整体结构如图所示，各个模块的作用如下：

用户画像：包含用户的人群属性、历史行为、兴趣内容和偏好倾向等多维度的分析，是个性化的基石

特征工程：包含了了视频的类别属性，内容分析，人群偏好和统计特征等全方位的描绘和度量，是视频内容和质量分析的基础

召回算法：包含了多个通道的召回模型，比如协同过滤，主题模型，内容召回和SNS等通道，能够从视频库中选出多样性的偏好内容

排序模型：对多个召回通道的内容进行同一个打分排序，选出最优的少量结果。

除了这些之外推荐系统还兼顾了推荐结果的多样性，新鲜度，逼格和惊喜度等多个维度，更能够满足用户多样性的需求。

然后，介绍了推荐排序系统架构、推荐机器学习排序算法演进。

3.5 携程个性化推荐算法实践

推荐流程大体上可以分为3个部分，召回、排序、推荐结果生成，整体的架构如下图所示。

召回阶段，主要是利用数据工程和算法的方式，从千万级的产品中锁定特定的候选集合，完成对产品的初步筛选，其在一定程度上决定了排序阶段的效率和推荐结果的优劣。

业内比较传统的算法，主要是CF1、基于统计的Contextual推荐和LBS，但近期来深度学习被广泛引入，算法性取得较大的提升，如：2015年Netflix和Gravity R&D Inc提出的利用RNN的Session-based推荐[5]，2016年Recsys上提出的结合CNN和PMF应用于Context-aware推荐[10]，2016年Google提出的将DNN作为MF的推广，可以很容易地将任意连续和分类特征添加到模型中[9]，2017年IJCAI会议中提出的利用LSTM进行序列推荐[6]。2017年携程个性化团队在AAAI会议上提出的深度模型aSDAE，通过将附加的side information集成到输入中，可以改善数据稀疏和冷启动问题[4]。

对于召回阶段得到的候选集，会对其进行更加复杂和精确的打分与重排序，进而得到一个更小的用户可能感兴趣的产品列表。携程的推荐排序并不单纯追求点击率或者转化率，还需要考虑距离控制，产品质量控制等因素。相比适用于搜索排序，文本相关性检索等领域的pairwise和listwise方法，pointwise方法可以通过叠加其他控制项进行干预，适用于多目标优化问题。

工业界的推荐方法经历从线性模型＋大量人工特征工程[11] -> 复杂非线性模型-> 深度学习的发展。Microsoft首先于2007年提出采用Logistic Regression来预估搜索广告的点击率[12]，并于同年提出OWLQN优化算法用于求解带L1正则的LR问题[13]，之后于2010年提出基于L2正则的在线学习版本Ad Predictor[14]。

Google在2013年提出基于L1正则化的LR优化算法FTRL-Proximal[15]。2010年提出的Factorization Machine算法[17]和进一步2014年提出的Filed-aware Factorization Machine[18]旨在解决稀疏数据下的特征组合问题，从而避免采用LR时需要的大量人工特征组合工作。

阿里于2011年提出Mixture of Logistic Regression直接在原始空间学习特征之间的非线性关系[19]。Facebook于2014年提出采用GBDT做自动特征组合，同时融合Logistic Regression[20]。

近年来，深度学习也被成功应用于推荐排序领域。Google在2016年提出wide and deep learning方法[21]，综合模型的记忆和泛化能力。进一步华为提出DeepFM[15]模型用于替换wdl中的人工特征组合部分。阿里在2017年将attention机制引入，提出Deep Interest Network[23]。

携程在实践相应的模型中积累了一定的经验，无论是最常用的逻辑回归模型（Logistic Regression），树模型（GBDT，Random Forest）[16]，因子分解机（FactorizationMachine），以及近期提出的wdl模型。同时，我们认为即使在深度学习大行其道的今下，精细化的特征工程仍然是不可或缺的。

基于排序后的列表，在综合考虑多样性、新颖性、Exploit & Explore等因素后，生成最终的推荐结果。

四、总结

之前没有接触过推荐系统，现在由于工作需要开始接触这块内容。很多概念和技术不懂，需要补很多东西。近期也去参加了内部推荐大赛真实地操作了一轮，同时开始学习推荐系统的基础知识，相关架构等，为下一步工作打下必要的基础。

推荐系统是能在几乎所有产品中存在的载体，它几乎可以无延时地以用户需求为导向，来满足用户。其代表的意义和效率，远远超过传统模式。毋庸置疑，牛逼的推荐系统就是未来。但这里有个难点就在于，推荐系统是否做得足够的好。而从目前来看，推荐算法和推荐系统并没有达到人们的预期。因为人的需求是极难猜测的。

又想到之前知乎看到一篇文章，说的是国内很多互联网公司都有的运营岗位，在国外是没有专设这个岗位的。还记得作者分析的较突出原因就是：外国人比较规矩，生活和饮食较单调，例如高兴了都点披萨。而中国不一样，从千千万万的菜品就能管中窥豹，国人的爱好极其广泛，众口难调。加上国外人工时很贵，那么利用算法去拟合用户的爱好和需求，自动地去挖掘用户需求，进行下一步的深耕和推荐就是一个替代方案。这也是国外很推崇推荐系统的侧面原因。而在中国，人相对来说是便宜的，加上国人的口味更多更刁钻，算法表现不好，所以会设很多专门的运营岗位。但慢慢也开始意识到这将是一个趋势，加上最近ai大热，各家大厂都在这块不断深耕。

回到推荐系统上，从现实中客观的原因就可以看到，真正能拟合出用户的需求和爱好确实是很困难的事情。甚至有时候用户都不知道自己想要的是啥，作为中国人，没有主见和想法是正常的，太有主见是违背标准答案的。但推荐系统背后代表的意义是：你的产品知道用户的兴趣，能满足用户的兴趣，那么必定用户就会离不开你。用户离不开的产品，肯定会占领市场，肯定就有极高的估值和想象空间。这也就是大家都在做推荐系统，虽然用起来傻傻的，效果也差强人意，依然愿意大力投入的根本原因。

几句胡诌，前期学习过后的简单总结，自己还有很多东西和细节需要继续学习和研究。能力有限，文中不妥之处还请指正~

（ps：文中一些截图和文字的版权归属原作者，且均已标注引用资料来源地址，本文只是学习总结之用，如有侵权，联系我删除）

问答
推荐系统如何实现精准推荐？
相关阅读
推荐系统基础知识储备
量化评估推荐系统效果
基于用户画像的实时异步化视频推荐系统
【每日课程推荐】机器学习实战！快速入门在线广告业务及CTR相应知识

此文已由作者授权腾讯云+社区发布，更多原文请点击

搜索关注公众号「云加社区」，第一时间获取技术干货，关注后回复1024 送你一份技术课程大礼包！

海量技术实践经验，尽在云加社区！

终于把序号写到了第十篇（其实已经是第13篇了），前面写了几个外篇，我看上篇机器学习的那篇看的人很多，后面会再找一两个点再写写，后面可能会算法部分和架构部分穿插着写了，想到哪里就写哪里了，今天我们继续我们的搜索引擎架构部分，主要来说说数据的检索。

对之前文章感兴趣的话，可以点击下面的链接，或者直接在SF上看整个专栏--吴说
搜索架构
用Golang写一个搜索引擎（0x00）从零开始
用Golang写一个搜索引擎（0x01）基本概念
用Golang写一个搜索引擎（0x02）倒排索引技术
用Golang写一个搜索引擎（0x03）跳跃表，哈希表
用Golang写一个搜索引擎（0x04）B+树
用Golang写一个搜索引擎（0x06）索引构建
用Golang写一个搜索引擎（0x07）正排索引
用Golang写一个搜索引擎（0x08）索引的段
用Golang写一个搜索引擎（0x09）数据增删改
搜索算法
用Golang写一个搜索引擎（0x05）文本相关性排序
用Golang写一个搜索引擎（0xFF）搜索排序
搜索引擎（0xFE）--- 用机器学习再谈排序

之前我们说完了数据的增，删，改，还剩下一个查没有写，今天来写写查。

搜索引擎最核心的东西就是查了，在查上面，也有很多好玩的数据结构和算法，我们一个一个来说说。

之前说了搜索引擎的核心底层数据结构包括两个：倒排索引和正排索引，倒排索引主要用来检索，正排索引主要用来过滤，我们就以一个搜索请求来说说搜索引擎的检索。

比如我们有最近3个月新浪微博的数据在搜索引擎中，数据有发布者昵称，微博内容，微博发布时间，要搜索的关键词是长沙雅礼中学，而且只要看最近10天的数据，那么这么一个典型的搜索场景是怎么来进行的呢？我们先假设我们数据是这样的4条数据

"nickname" : "长沙天气预报" "content":"今天天气真好" "datetime":"2016-05-06"
"nickname" : "路人甲" "content":"长沙天气真好，我现在在雅礼中学" "datetime":"2016-01-21"
"nikename" : "雅礼中学官微" "content":"长沙天气真好" "datetime":"2016-05–05"

Query分析

首先关键词来了以后要进行的第一步是query分析，query分析相当复杂，也直接影响到搜索效果，有很多算法上的东西，这个需要单独说，呵呵。

当然，最简单的query分析就是切词了，我们这里不讲算法，所以query分析直接就是切词了，切词完了以后变成了长沙/雅礼/中学，后面的10天这个约束条件就变成了range(2016-05-01，2016-05-10)，好了，query分析就完了。

数据检索

1.获取倒排链

query分析完了以后，就开始进行倒排检索了，倒排检索就是按照切词的结果，一个term一个term的从倒排文件中拉取倒排链，简单来说是这样的

//从B+树中获取关键字倒排链的文件偏移offset
ok, offset := this.btree.Search(this.fieldName, keystr)
if !ok {
  return nil, false
}
//文件偏移的第一个位置保存的倒排链的长度
lens := this.idxMmap.ReadInt64(int64(offset))
//通过offset和倒排链的长度获取整个倒排链
res := this.idxMmap.ReadDocIdsArry(uint64(offset+8), uint64(lens))
return res, true

这样，通过三次调用就得到3个倒排链了，然后开始检索的第二步。

上面的数据中，我们要检索长沙/雅礼/中学，我们发现，三条数据都满足这个条件，不一样的是第一条和第二条是单个字段就满足，第三条是跨字段了，需要两个字段合起来才满足匹配条件，所以，我们的检索过程并不是简单的求倒排链的交集，而是一个求并求交的组合过程。

先单个的term在多个字段求并集，然后再多个term之间求交集，这样能满足找到所有符合条件的结果。

2.单term多字段间求并

多路求并也叫K路并归，比如长沙这个term，在检索nickname的时候，找到docid为[1]，检索content的时候，找到docid为[2,3]，两个docid链求并集，得到[1,2,3]，就是我们最后要求的结果。

这里只是一个两路的求并集，比较简单，如果是更多的字段检索，那么就会有超过两个的多路求并，一般我们使用胜者树或者败者树来进行K路求并的操作。

胜者树，败者树

所谓胜者树，是一种外部归并排序经常使用的数据结构，我们这里用他来做多路的求并集操作，因为我们的倒排链是以mmap的形式进行存储的，其实也是一种外部存储。

简单的说，胜者树就是以K路的数据作为叶子节点，建立一棵完全二叉树，然后叶子节点两两比较，胜利者进入上一层节点中，指导最后得到一个最后的胜利者输出，输出以后将对应的数据更新，光这么说太抽象了，我们看个图就明白了，比如我们目前有4路求并集，4路的数据分别是[0,2,3]，[1,2]，[0,3]，[3,4]，那么整个胜者树的过程就是下面的这个图，从左到右表示胜者树的求并过程。

上面那个图中

• 首先，有4个数组，那么建立一个有四个叶子节点的平衡完全二叉树，每个叶子节点存储一个倒排链，把每个倒排链的第一个元素拿出来准备进行比较

• 两两比较，较小的那个进入上一层节点，然后上一层节点继续两两比较，较小的那个进入上一层节点，直到最后到达根节点，图中的红色部分

• 把最后战斗到根节点的元素输出到最终结果中（如果最终结果中最后一个元素和这个根节点元素一样，丢弃这个元素）

• 将最后获胜的元素的倒排链指针后移一位，将该链的后一个元素拿出来进行比较

这样的话，在时间复杂度为O(nlogk)的情况下，我们就把并集求好了。

求并集的方法也有很多，我们这里只举出了比较常见的，胜者树这种结构比较好理解，但在实现的时候，一般采用胜者树的变体败者树，败者数的原理和胜者树一样，有区别的地方是，两两比较的时候败者树保存的是败者的信息，而胜者接着往上层进行战斗，直到根节点位置，最后输出的还是胜者。

败者树的过程我也画了个图，在下面

败者树的优势在于新进来的元素，只需要跟他的父节点进行比较就行了（只需要一次指针操作就可以找到父节点），胜者树的话还需要找临近节点比较（需要两次指针操作才能找到临近节点），然后更新父节点信息，所以败者树效率更优一点。

3.多term之间求交

上一步中拿到了各个term的倒排链以后，为了保证每个document中都含有所有词，就要对他们求交集了，因为倒排链是按照docid从小到大排列的，所以求交集实际上是对多个有序数组求交集。

如果是两个倒排链的话比较容易，拿两个指针分别指向两个倒排链的首部，然后比较大小，哪个小，那么把这个指针后移一位，如果两个相等，那么把这个docid取出来，直到某一条倒排链遍历完，时间复杂度O(n+m)，最好的情况是O(min(n,m))，代码也很简单，核心的就这么几行：

ia,ib:=0,0
for ia < lena && ib < lenb {
    if a[ia].Docid == b[ib].Docid {
        c[lenc] = a[ia]
        lenc++
        ia++
        ib++
        continue
    }
    if a[ia].Docid < b[ib].Docid {
        ia++
    } else {
        ib++
    }
}
return c

这是两个倒排链求交集，如果是多个倒排链求交集的话，可以两两求交，最后就完成了。

这样效率比较低，这里我们再介绍一种方法

• 因为求交集最后的结果长度肯定不会超过最短的倒排链的长度，所以我们首先找到长度最短的倒排链，作为标称数组。

• 从标称数组中依次取出每个元素，查看元素是不是在其他的每一个倒排链中

• 如果这个元素在其他所有倒排链中都存在，那么就把这个元素放入最终结果集中。

上面的第二步又可以从以下几个方面优化一下

• 如果发现某个元素不在某个倒排链中，那么他肯定不在最终结果中，直接跳出，不用继续比较了。

• 如果某个倒排链被查找完了，那么也可以跳出了。

• 查找元素是否在某个倒排链中，可以使用下面几个方式来优化

  • 一是可以使用二分查找来找，这样复杂度可以降低一个数量级。

  • 因为我们的docid是连续的，所以可以设定一个哨兵指针，然后从哨兵指针往后遍历，遍历到倒排链中的元素大于当前元素就停止，然后把哨兵移动到这个元素位置就行，这样的话只是给每个倒排链表加了个哨兵，复杂度上却降低了一个数量级了。

如果用二分查找的话，假如每个倒排链长度为N，一共有K个倒排链，那么整体最坏情况下复杂度是O(N*K*logN)，如果用哨兵的方法的话，一般比这个还要快一点。

下面这个图是优化后的多路求交，绿色的是标称数组中的元素，红色的是哨兵，黄色的是命中的元素。

4.正排过滤

到这一步，通过倒排文件能找到的元素就都找到了，像上面那个例子，我们找到了2和3两条记录，然后就要用第二个条件最近10天的数据来进行过滤操作了。

过滤操作比较简单，需要遍历一边结果集，然后用正排文件的值判断是否满足条件，这么遍历一下，就只剩下记录3了，这也是我们最后得到的结果。

在这里再说一下，之前我们说数据的增删改的时候说了，删除数据或者修改数据的时候实际上只是在bitmap上做了一个标记，表示这个数据删除了，所以最后检索的时候需要把已经删除的数据去掉，这一步也是在这里做，在遍历整个结果集做正排过滤的时候可以一起判断这个文档是否被删除了，只有满足过滤条件并且没有被删除的文档才能留下来。

由于正排文件的保存是按照docid来做数组下表保存的，所以查找的复杂度是O(1)，时间基本上就是遍历一边结果集加上条件判断的时间。

统计汇总

上面这些都做完了以后，就得到了最终的完整结果集，这时候在对结果集进行统计汇总之类的操作就简单了，这个可以根据业务的要求，做任何形式的统计汇总需求了，文本相关性的打分一般在求交集和求并集的时候就做完了，之前说的精细化的排序也在这一步来进行。

结束

好了，上面就是一次完整的检索过程中所涉及到的各种东西，关于query分析部分需要单独说，这一篇就不展开了。希望大家看得开心。

欢迎关注我的公众号，文章会在这里首先发出来：）扫描或者搜索微信号XJJ267或者搜索中文西加加语言就行