检索系统FAQ
Q1：不到1秒的时间怎么在网上检索到那么多的东东？
A： 检索所需的信息，需要完成收集信息、分析信息和查询信息三个工作，我们的检索系统也不例外。
收集信息： 通常通过 spider（或 crawler）根据网络上的各种链接遍历 Web 空间采集网页资料。不同的应用，信息的采集方式也不尽相同。
分析信息： 通常需要完成三件事情：
- 解析网页（见网页解析 FAQ）
- 相关性因素的分析或计算
- 建立倒排索引
查询信息： 根据关键词，通过倒排索引查找与关键词匹配的数据集，按照相关性将最终结果有序输出即可。
收集信息的全部工作和分析信息的绝大部分工作已经被检索系统预先做好了，我们平时的检索主要进行的是最后一步工作，速度自然很快。这是目前百度所采用的搜索引擎模型，也被人称为全文搜索引擎（FullText Search Engine）。
Q2：什么是倒排索引？
A： 顾名思义，倒排就是将对象到描述的这种”正排”关系”倒”过来成为描述到对象的”倒排”关系，这样利用这种关系我们就可以通过描述信息检索到对象了，倒排索引就记录了这种关系。
例如，网页1、网页2的描述信息如下：
- 网页1：中国人民的大学
- 网页2：中国人民大学
对描述信息进行切词：
- 网页1：中国|人民|的|大学
- 网页2：中国|人民|大学
可以得到描述信息到两个网页对象的倒排关系：
- 中国 → 1，2
- 人民 → 1，2
- 的 → 1
- 大学 → 1，2
倒排关系的记录方式，即倒排索引，随应用环境的不同而各异。一般在建立倒排关系的过程中，为了方便动态追加，在内存中采用链式结构；存储到硬盘上时，为了高效读取，采用顺序存储。习惯上把倒排索引数据称之为倒排拉链或索引拉链。
Q3：像mp3、image这种非文本对象怎么建立倒排索引？
A： 目前 ns 的产品线检索系统都是基于文本的，还没有基于内容的系统。MP3、image 这种非文本对象，在网页解析时，需要根据 HTML 页面的 tag 等解析与对象相关的文本（歌曲名、图像周围文字等），解析出文本之后，建立倒排索引的过程与文本对象一致。
Q4：为什么要进行切词？怎么进行切词？
A： 中文词汇之间没有天然的分隔符，如果按照单字建立倒排索引，将会带来两方面的问题：
- 单字的平均索引拉链过长，每次查询需要进行合并的拉链数过多
- TF-IDF、人名书名识别等与相关性有关的因素难以考虑
目前 ns 都是调用 NLP 组提供的切词接口。需要注意的是，后端建倒排索引时的切词要求保证召回率（recall），前端查询时的切词要求保证准确率（precise），因此需要对切词结果按不同策略进行处理或者调用不同的切词接口。通常把切词接口给出的一个基本单元叫做一个 term。
Q5：检索系统是怎么实现Q1中所说的检索过程的？
A： 目前检索系统架构上大同小异，大体上分两大类程序来实现检索：
后端建库程序： 完成收集信息工作和分析信息的绝大部分工作。根据不同的应用，有的直接从大搜索网页库中取数据（mp3、image），有的需要从web站点抓取数据（news、mp3），有的直接获取用户提交的数据（tieba、iknown、space）。得到数据之后，建索引模块建立倒排索引，生成索引数据。
前端检索服务： 由若干个程序合作，完成对用户检索串的解析、倒排索引数据的匹配查找、摘要的生成、最终结果的组装等工作。
Q6：前端检索服务程序之间是怎么分工合作的？
A： 各前端检索服务程序的功能如下：
- Apache： Web 服务器，接受用户检索请求，返回检索结果
- UI： User Interface，根据检索结果生成页面
- AS： Advanced Search，从 UI 接收检索请求，将请求分发到一个或多个 BS，并对 BS 返回的结果进行合并除重等操作，根据 BS 的结果向 DI 获取 DI 信息，最后将整个检索的最终结果返回给 UI
- BS： Basic Search，解析 AS 的检索请求，得到对应的 term 以及他们之间的逻辑关系，读取各 term 的索引拉链并根据他们之间的逻辑关系得到满足检索请求的索引集合，计算结果集合中每个元素的相关性权值，按权值对最终结果排序并返回给 AS
- DI： Display Information，接受 AS 的请求，返回给 AS 一些检索结果中需要展示的信息，比如摘要、标题、URL 等
根据上述各个服务程序的功能，一个典型检索的流程为：
1 | 用户检索请求 → apache → ui → as → bs → as → di → as → ui → apache → 检索结果 |
Q7：as、bs、di的检索架构有什么好处？
A： 这种架构有如下一些优点：
- 方便数据扩容 - 采用分层（组）的方式，将数据分层（组），每层（组）数据有相应的bs和di。一旦系统的数据容量达到上限，新增数据层（组），即可实现扩容
- 索引数据和di数据相分离 - Di数据相对索引数据比较大，在该架构下只有前端需要展现的数据才去di服务获取相应数据，避免检索过程中读入过多无用数据
- 便于服务合理配置优化 - bs和di需要从硬盘读取数据，比较耗io资源；as需要居中调度，比较耗cpu和内存资源。可以利用这些特点合理的在不同配置的服务器上分布服务
Q8：建索引模块如何获取上游模块数据？
A： 从获取数据的主动性角度，分为两种：
- 主动获取 - 建索引模块启动时，主动以上游模块的输出做为自己的输入。数据量较大，时效性要求不高时多采用这种方式
- 被动获取 - 被动接受上游模块（transfer）分发过来的数据
Q9：大规模的数据如何高效的建立倒排索引？
A： 要做到这一点，需要考虑两个方面的因素：
- 分层次完成建索引的过程 - 首先，以一定数目的对象为一组建索引，保证对每组对象建索引的过程能够在内存中完成而不需要存取中间数据到硬盘；然后，将各组结果进行合并，得到最终的倒排索引数据
- 注意内存的使用和硬盘数据的存取 - 尽量申请足够的大内存块，然后在整个进程周期内重复使用。为了方便对各组索引合并，每组数据输出到硬盘时，将term表排序，索引拉链进行顺序存储
Q10：对实时更新的数据如何快速的建立倒排索引？
A： 对该问题，目前ns通用内存索引机制进行解决。该方案的核心思想就是，处理实时数据的建索引模块只负责少量数据，保证建索引过程能够在内存中完成而不需要到硬盘存取中间数据，这样就能快速的处理实时数据，并且根据时效性要求，将内存中的索引数据定期存到硬盘，以供相应的bs模块查询。
Q11：如何为标题检索、站点搜索这样一些特殊的检索考虑倒排索引？
A： 把标题中的term、站点域名等这些特殊的词按照特殊的格式建到索引中，在检索的时候还按照这种特殊格式去检索，就能够完成检索。
例如标题检索，某篇文章标题中有”百度”，建立倒排时，对来源于标题的term”百度”增加前缀”T_”，即对term”T_百度”建立倒排索引，检索时，如果查询标题中含有”百度”的文章，检索程序（一般是bs）会根据要求自动将检索term修改为”T_百度”。
Q12：bs如何高效的处理索引拉链？
A： 在 ns 组的实践中，有一些经验能够保证这一点：
- 先读取索引拉链最短 term 的拉链，因为最终归并结果肯定短于该拉链长度
- 利用 A∩B∩C=（A∩B）∩C，将多路归并转化为多个二路归并，避免过多的读取无用数据
- 读取索引拉链时按块读取，每归并完一块再读取下一块
- 合理选择排序算法。比如权值空间在百量级时采用基数排序；过大的话采用堆排序
Q13：相关性需要考虑哪些因素？
A： 只能具体应用具体分析，针对ns的产品，可以考虑如下一些角度：
- 长文本： tf-idf、offset、文本质量等
- 短文本： 不同类型给予不同权重、检索串与匹配文本的基本词数比例、不同term的切词属性、覆盖关系等
- query特点： query中心词提取、term权重标识等
- 具体产品的特点： mp3的下载速度、image的图片质量、news的实效性等
Q14：实时信息的检索是如何实现的？
A： 对于动态数据类检索（比如tieba，zhidao），用户实时提交的信息需要能够及时的检索到，这通常是通过使用两种类型的索引库来实现的：
- 实时库（day库） - 该库会以较高的频率进行重建（通常5分钟~半小时），使得新提交的信息能够及时的合并入该索引，并提供检索
- 历史库（mon库） - 该库维护了历史以来的所有数据（除了当天的实时数据），每天夜里合并实时库时重建一遍
Q15：什么是offset索引，有什么用？
A： offset索引就是在索引单元中记录了term在文本中出现位置信息的索引。某些term会大量在文本中出现，所以通常会控制记录的位置数（比如只记录出现的前16个位置），以控制索引数据的大小。
offset索引在长文本检索系统中对于调权的意义很重大，通过offset信息可以发现匹配”最好”的结果。
Q16：有哪些用于提高性能的索引技术？
A： 当一个检索系统的数据规模变大以后，利用普通索引来检索会导致性能下降。为了提高检索效率，通常可以有如下的一些索引组织方式：
- 位图索引（bitmap索引） - 主要针对DF（文档频率）非常高的term
- 压缩索引 - 通常针对于索引较长的term，将其中次要的一些信息剔除
- 差分索引 - 采用记录差值来代替记录 ID，并使用特定的编码
- 截断索引 - 保留一定长度的记录了详细信息的索引
- 预索引 - 将检索高频词预先检索一遍，得到结果并存储为新的索引文件
Q17：对于可修改的信息如何建立实时索引？
A： 在某些类型的动态数据检索系统中，需要提供某个文档可修改的功能。通常可以采用的方法有：
- 记录修改次数 - 一个全局的位图结构记录每个文档的当前修改次数，每次修改该次数增1
- 大小ID编号方法 - 小ID表示全局ID，大ID表示检索系统内部ID，通过位图结构记录大ID当前是否有效