关键词推荐工具中的用户引导机制之二：suggestion架构
在《关键词推荐工具中的用户引导机制之一》 我们分析了用户用到机制对搜索引擎/关键词工具的重要性，同时也提到按照用户在搜索引擎/或者关键词工具上交互的阶段，可以按交互前，交互中和交互后为用户分别提供种子query，suggestion和相关搜索词对用户进行引导。 种子query是比较经典的推荐问题， 对于‘相关搜索’，后续会有博文专门介绍， 该文以下内容主要介绍如何构造高效的suggestion服务。包括架构及内部检索逻辑。
suggestion到底有多大作用呢， 在很多搜索引擎中， 一方面，从自然搜索结果的角度，suggestion能够引导客户将输入表现的更利于搜索引擎理解用户的意图，得到更优质的搜索结果； 另一方面， 从商业变现的角度看， 大的suggestion策略的上线， 往往能够带来搜索引擎几个点cpm的提升， 这可是非常了不起的贡献。 所以对于搜索引擎， 和关键词推荐工具这样的基于搜索的系统， suggestion的作用就至关重要。
图： 百度suggestion效果
图：关键词推荐系统suggestion
基本概念
要了解suggestion的设计细节，需要先定义以下名词：
- Query片段：特指query的前缀，例如用户输入的query为“鲜花快递”，其全部query片段为‘鲜’，‘鲜花’，‘鲜花快’，‘鲜花快递’。
- 拼音片段：本文中特指query片段对应的拼音片段，例如用户输入query为‘鲜花’，则全部拼音片段为‘x’，‘xi’，‘xia’，‘xian’，‘xianh’，‘xianhu’，‘xianhua’。
- 候选query：指挖掘出的候选种子query。
- wcode：建立suggestion 索引时，为每个候选query的编号，该编号值表示对应字面在数组结构中的下标位置，为无符号整型。
- 个性化suggestion：根据客户帐户信息进行推荐的query suggestion。
- 通用suggestion:与个性化suggesion对应，所有客户都适用的query suggestion。
解决方案的权衡
索引方式
suggestion可以做得比较简单， 也可以比较复杂，例如在搜索引擎搜索框中， 可以输入汉字， 拼音， 或者输入几个汉字后，又将输入法切换为拼音进行输入， 或是正好反过来。 这样对于suggestion，就需要考虑是只对汉字输入query提供suggestion结果， 还是需要对混合输入（拼音+汉字）query提供结果。 不同的功能会导致实现不一样。
图：全拼音模式suggestion
图：汉字+拼音混合模式suggestion
经过统计，候选query平均长度为13.9字节（约7汉字），其对应的拼音平均22.1个字母。如果仅对汉字建立索引，则可假设每个候选query对应7个query片段索引片段，而如果要对汉字+拼音建立索引，则每个候选query需要对应约30个索引片段（7+22=29）。但建立拼音片段能够支持用户拼音输入，或是中英文混合的情况，所以要达到较好的用户体验， 最好是实现： 索引结构支持拼音+汉字方式
性能
作为引导机制，suggestion的性能必须足够快， 应该做到迅雷不及掩耳的速度，否则在用户灵活的手指配上高效的输入法下出现任何一顿一顿的感觉， 都会异常影响用户体验， 所以在内存允许的情况下， 所有数据常驻单机内存，是比较理想的情况， 如果单机内存存放不下， 那么可能的选择是使用资源定位系统，将数据进行水平拆分（最简单的方式， 按照query签名作为key，然后取模）
P.S. 对于如何对数据进行扩展， 推荐大家仔细揣摩《ebay网站架构原则》， 每一条原则都值得细心思考体会。
图： 水平拆分，例如按照key签名取模
使用该方式， 请求可轻松达到1w+/s
结果merge及rank
suggestion返回结果由个性化suggestion(针对每个用户单独挖掘)与通用suggestion结果组成，个性化结果在前，通用结果在后的方式，当个性化结果不足时由通用结果补足。
其中，不管个性化结果，还是通用结果，由两部分组成：原始query片段索引结果与拼音query片段索引结果。对于二者的merge方式存在两种思路：
- 原始query片段索引结果与拼音query片段索引结果merge，按权重从高到低排序，返回前N个结果。
- 优先返回原始query片段索引结果，数量不足时由高权重的拼音query片段索引结果补充。
从用户体验与效率考虑，原始query片段索引结果与拼音query片段索引结果的merge方式采用思路2。
思路2还有一个问题需要考虑，原始query片段索引结果数量不足时，进行字音转换成拼音串后，存在拼音串片段检索结果与用户输入query的汉字串前缀不一致的情况。例如：query为“鲜花”，转换成拼音串“xianhua”后的检索结果可能有“鲜花”，“仙花”，“闲话”，这时候的检索结果可能包含“仙花”，“闲话”同音但不同字的suggestion结果。从检索逻辑复杂性、效率、数量量考虑，针对纯汉字串片段索引结果数量不足时，不进行字音转换后的拼音片段索引检索。
针对非纯汉字串，原始query片段索引结果数量不足时，通过字音转换成拼音串片段进行检索。在检索过程中，考虑最大汉字前缀匹配的方式。例如：query为“鲜hua”，转换成拼音串“xianhua”后的检索结果可能有“鲜花”，“仙花”，“闲话”。在此例子中，会使用汉字前缀“鲜”去与候选query进行匹配，最终得到候选query“鲜花”。
使用上述方式， 可以在保证结果个性化（个性化结果需要在离线进行挖掘）的同时，保持suggestion应有的高效。
内存数据结构
在决定了使用全内存的存储方式后， 就需要考虑内部数据结构的设计了。 要想让效率最高，最快的方式就是直接使用hash进行query片段签名查找。
图： hash方式进行倒排查找。
索引中主要包括以下结构：
片段索引字典：存储片段签名到片段推荐词倒排的偏移地址。使用bsl::hashmap存储
片段至推荐词倒排索引：存储每个片段到候选关键词wcode的倒排索引。使用hashmap存储。通用拉链与个性化拉链倒排拉链合并存储，区别在于个性化拉链不仅包含关键词wcode，还包含关键词的个性化weight。两种结构根据标志位flag进行区分。为了提高在线服务时，合并字面返回的效率，针对每个索引的拉链会有序(weight从大到小)存储。
字面队列：存储具体wcode字面与字面权重，使用bsl::deque存储，片段至推荐词倒排索引中的wcode值即为该队列索引下标。
在线检索流程
当用户在搜索框进行suggestion请求时，会经过对片段进行归一化，查找汉字索引片段，查找拼音片段及merge结果阶段，结果merge及rank主要的原则是汉字片段结果排在拼音结果前， 各类结果内部按照线下挖掘的权值进行rank。 线下挖掘在业界及学术界的方法参见后续博文。 附上一个流程图， 类似的画法是在工作中逐渐形成的习惯， 其中将function和data structure单独分开表示， 虚线表示数据依赖， 实现表示处理逻辑依赖。 该方式自己觉得比较清晰， 特别是对照着文档写代码的过程中：）
更多内容可参见：
《eBay网站的架构原则》 ： 网上都有，每一条扩展原则都值得细心揣摩及体会，各大搜索引擎大数据的支持原则异曲同工百度关键词工具介绍参见：http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
也可关注我的微博： weibo.com/dustinsea
或是直接访问： http://semocean.com
