搜索引擎学习笔记

概览

搜索引擎是从文档集合中查找出匹配单词、问题等构成的信息需求的系统/软件的总称。

不过现代的搜索引擎的索引范围早已经超过文档，比如对邮件/专利信息的搜索引擎等。变化的是作为文档的对象，不变的是基础架构。

搜索引擎一般有四个部分：

• 索引管理器 Index Manager
  • 索引是一种该诉检索特化的数据结构，对其访问借助索引管理器完成
• 索引检查器 Index Searcher
  • 利用索引进行全文搜索处理的组件
• 索引构建器 Indexer
  • 从文本文档中生成索引的组件。它的行为是将文档分解为单词序列，再转换为索引结构
• 文档管理器 Document Manager
  • 管理作为检索对象的文档，并对于作为查询结果的文档进行摘要的生成

这几部分的工作方式：文档作为索引构建器的输入，将输出内容交给索引管理器和文档管理器，最后，用户使用检索应用程序，后者和索引检查器交互，使用信息需求获得结果。

还有其他不是组成部分，但是相关的组件：

• 爬虫-Crawler： 收集Web上HTML等文件的自动系统。
• 搜索排序系统： 给作为检索对象的文档打分的系统。

全文搜素

全文搜索分为：利用全扫描进行全文搜索，和利用索引进行全文搜索的方法。

第一种方法因为和grep使用的方法一致，也称为grep型搜索。优点是文档不需要事先处理，缺点是文档数量和检索时间成正相关。因此仅适用于少量/暂时性的文档。相关算法有KMP和BM等算法。

另一种是利用索引进行全文搜索的方法。事先需要为文档建立索引，然后利用索引搜索字符串。优点是搜索时间不会随文档数增多大幅下降，缺点是需要预先建立索引。

全文搜索的索引结构中，较为常用的结构是倒排索引。

倒排索引

倒排表和书籍后的关键词索引原理一致。将关键词列出在书籍最后，并在每个关键词后面标注它出现的地方，并将这个表按照关键词首字母顺序排序。

它的构建方法大致如下：首先需要一个二维数组，行为所有出现过的单词（需要将这个维度压缩地尽可能小，比如忽略复数形式，忽略大小写等），列是页码。数组单元则是某页出现某单词的记录。

完成后，将行列反转，得到每个单词出现在每一页上的表。这个操作称为倒排，完成后的表格称为倒排表（Postings List），能用于关键字全文检索。

另，所谓的页码实际上是和网页编号对应的。一行记录称为一个倒排项（Posting）。

倒排索引，是单词的集合“词典”和倒排列表的集合“倒排文件”构成的。二者对应关系大致相当于：

倒排词典    ->  倒排文件
-----------------------
Google      ->  2
I           ->  1,2
...         ->  ...

这是一个松散的结构，每个单词的倒排文件可以从该单词的元信息获取。

查找的单词有多个时，对各个单词分别执行索引，取结果交集即是查找结果。

单词级倒排文件：在记录文档单词信息之外，额外记录该单词在文档出现的编号。

短语查找：借助单词级倒排文件，可以查找短语级别的内容：在取完交集之后，过滤掉结果中search和engine相对偏移量不为-1的项目。

对于中文等语言而言，搜索引擎的构造方法一样，不同在于语义化分割（Tokenization）中文的连续的句子。

中文的句子单词序列化分割方法常用的有两种：

• 词素解析分割法
  • 将句子按照其中的语义，分割为词素（token）单元的方法，但是实现难度极高，近几年一般借助机器学习方法（隐马尔科夫模型/条件随机场等方法）处理。
• N-gram分割法
  • 将句子分割成由N个字符组成的片段序列的方法，每个片段称作一个N-gram。M字的句子进行N-gram分割方法，能产生M-N+1个N-gram。

二者的优缺点都很明确，前者精准且节省空间，从而检索速度也快，但是可能会发生检索遗漏的问题。后者的优点是结果完整，因此检索速度相对较慢。并且可能会检索到无关词汇，比如检索华山得到九华山。

词典的实现

一般使用哈希表、树等结构，常用的属性结构有二叉查找树BST、字典树Trie，B+树等。

这部分之所以使用超过一种数据结构，一个是因为存储金字塔结构：往往不能一次性将词典完整加载到内存中，另一个是因为块设备的读写单位是块，并且耗时很高，需要针对读写慢但是一次读写量大专门优化的数据结构。

检索

检索模型指代各种检索方法/机制。使用逻辑谓词AND/OR/NOT指导的检索就是布尔检索。

该模型的检索流程：

1. 获取所有检索单词的倒排列表
2. 根据布尔检索获取符合条件的文档编号
3. 计算符合条件的文档和查询匹配度
4. 根据匹配度/其他排序参数，获取前k个文档

因为逻辑比较简单，伪代码就不贴了

关联度计算

策略一般是按照文档与查询的关联度对检索结果进行排序。算法则有：

• 余弦相似度
  • 将文档和查询映射到以单词（token）为维度的向量空间，并计算二者向量的夹角，夹角越小则关联度越高
• Okapi BM25
  • 文档是否匹配查询是由概率决定：根据单词的出现频率计算关联概率。

信息检索是全文搜索的学术领域，这个检索领域目的是找出与信息需求匹配的文档，故可认定匹配的文章不必包含查询，只需要计算整个文档的关联度，将高关联度文档作为作为检索结果即可。

关联度计算是计算密集任务，因此有必要先得到符合检索条件的子集后再计算关联度进行排序。从而，针对不同的检索应用，设计不同的检索模型能提高性能和质量。

构建倒排索引

因为数据的稀疏性质，它适用于使用链表进行存储。当内存用量过大时，可以使用二级链表进行存储。