搜索引擎学习笔记

概览

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

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

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

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

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

还有其他不是组成部分,但是相关的组件:

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

全文搜素

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

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

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

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

倒排索引

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

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

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

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

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

1
2
3
4
5
倒排词典    ->  倒排文件
-----------------------
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
    • 文档是否匹配查询是由概率决定:根据单词的出现频率计算关联概率。

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

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

构建倒排索引

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

作者

xeonds

发布于

2024-04-27

更新于

2024-06-15

许可协议

评论