2024-04-27 21:12:15
搜索引擎是从文档集合中查找出匹配单词、问题等构成的信息需求的系统/软件的总称。
不过现代的搜索引擎的索引范围早已经超过文档，比如对邮件/专利信息的搜索引擎等。变化的是作为文档的对象，不变的是基础架构。
搜索引擎一般有四个部分：
这几部分的工作方式：文档作为索引构建器的输入，将输出内容交给索引管理器和文档管理器，最后，用户使用检索应用程序，后者和索引检查器交互，使用信息需求获得结果。
还有其他不是组成部分，但是相关的组件：
全文搜索分为：利用全扫描进行全文搜索，和利用索引进行全文搜索的方法。
第一种方法因为和grep使用的方法一致，也称为grep型搜索。优点是文档不需要事先处理，缺点是文档数量和检索时间成正相关。因此仅适用于少量/暂时性的文档。相关算法有KMP和BM等算法。
另一种是利用索引进行全文搜索的方法。事先需要为文档建立索引，然后利用索引搜索字符串。优点是搜索时间不会随文档数增多大幅下降，缺点是需要预先建立索引。
全文搜索的索引结构中，较为常用的结构是倒排索引。
倒排表和书籍后的关键词索引原理一致。将关键词列出在书籍最后，并在每个关键词后面标注它出现的地方，并将这个表按照关键词首字母顺序排序。
它的构建方法大致如下：首先需要一个二维数组，行为所有出现过的单词（需要将这个维度压缩地尽可能小，比如忽略复数形式，忽略大小写等），列是页码。数组单元则是某页出现某单词的记录。
完成后，将行列反转，得到每个单词出现在每一页上的表。这个操作称为倒排，完成后的表格称为倒排表（Postings List），能用于关键字全文检索。
另，所谓的页码实际上是和网页编号对应的。一行记录称为一个倒排项（Posting）。
倒排索引，是单词的集合“词典”和倒排列表的集合“倒排文件”构成的。二者对应关系大致相当于：
倒排词典 -> 倒排文件
-----------------------
Google -> 2
I -> 1,2
... -> ...这是一个松散的结构，每个单词的倒排文件可以从该单词的元信息获取。
查找的单词有多个时，对各个单词分别执行索引，取结果交集即是查找结果。
单词级倒排文件：在记录文档单词信息之外，额外记录该单词在文档出现的编号。
短语查找：借助单词级倒排文件，可以查找短语级别的内容：在取完交集之后，过滤掉结果中search和engine相对偏移量不为-1的项目。
对于中文等语言而言，搜索引擎的构造方法一样，不同在于语义化分割（Tokenization）中文的连续的句子。
中文的句子单词序列化分割方法常用的有两种：
M-N+1个N-gram。二者的优缺点都很明确，前者精准且节省空间，从而检索速度也快，但是可能会发生检索遗漏的问题。后者的优点是结果完整，因此检索速度相对较慢。并且可能会检索到无关词汇，比如检索华山得到九华山。
一般使用哈希表、树等结构，常用的属性结构有二叉查找树BST、字典树Trie，B+树等。
这部分之所以使用超过一种数据结构，一个是因为存储金字塔结构：往往不能一次性将词典完整加载到内存中，另一个是因为块设备的读写单位是块，并且耗时很高，需要针对读写慢但是一次读写量大专门优化的数据结构。
检索模型指代各种检索方法/机制。使用逻辑谓词AND/OR/NOT指导的检索就是布尔检索。
该模型的检索流程：
因为逻辑比较简单，伪代码就不贴了
策略一般是按照文档与查询的关联度对检索结果进行排序。算法则有：
信息检索是全文搜索的学术领域，这个检索领域目的是找出与信息需求匹配的文档，故可认定匹配的文章不必包含查询，只需要计算整个文档的关联度，将高关联度文档作为作为检索结果即可。
关联度计算是计算密集任务，因此有必要先得到符合检索条件的子集后再计算关联度进行排序。从而，针对不同的检索应用，设计不同的检索模型能提高性能和质量。
因为数据的稀疏性质，它适用于使用链表进行存储。当内存用量过大时，可以使用二级链表进行存储。