IR
IR
Resources
- 有赞搜索引擎实践（工程篇）
- 有赞搜索引擎实践（算法篇）
- 剖析 Elasticsearch 集群系列第一篇 Elasticsearch 的存储模型和读写操作
- 剖析 Elasticsearch 集群系列第二篇 分布式的三个 C、translog 和 Lucene 段
- 剖析 Elasticsearch 集群系列第三篇 近实时搜索、深层分页问题和搜索相关性权衡之道
这就是搜索引擎-核心技术讲解 笔记
第3章 搜索引擎索引
- 文档：Document
- 文档集合：Document collection
- 文档编号：Document ID
- 单词编号：Word ID
- 倒排索引：Inverted Index
- 单词词典：Lexicon
- 倒排列表：Posting List，记录某个单词出现过的所有文档列表及单词在该文档中出现的位置信息，每条记录为一个倒排项（Posting）
倒排文件：Inverted File
- 单词词典的数据结构
- 哈希+链表：哈希表作为主体，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表里，相同哈希值的单词形成链表结构。字典项无需排序。
- 树形结构：B树（B+树），需要字典项按照大小排序（数字和字符）。中间节点用于指出一定顺序范围的词典项目存储在哪个子树中。
- 倒排列表 Posting List
- 以文档编号差值（D-Gap）存储文档编号，以更好地对数据进行压缩。
- 建立索引
- 两遍文档遍历法 2-Pass In-Memory Inversion
- 第一遍，收集全局信息，单词数量和频次，大概可以知道最终建立索引需要的内存大小，完成资源准备
- 第二遍，真正开始建立倒排列表信息。
- 问题：完全在内存中完成，对内存大小要求高；两遍遍历，慢。
- 排序法：始终在内存中分配固定大小的空间，用来存放词典信息和索引的中间结果，当分配的空间消耗完时，把中间结果写入磁盘
- 中间结果内存排序：（单词ID、文档ID、单词频率），排序原则是主键为单词ID，次键是文档ID，将排序好的三元组写入磁盘临时文件中，腾空内存。但是，词典所占内存会愈来愈大，因此剩给三元组的可用内存会越来越小。
- 合并中间结果：所有文档处理完后，磁盘会有多个中间结果文件，需要将其合并。每个中间结果在内存中开辟一个数据缓冲区，且是有序的。将不同缓冲区的包含同一单词ID的三元组进行合并，合并完成写入最终索引，并清空缓冲区中有这个单词ID的三元组。
- 归并法：大体流程思路与排序法一直，具体细节不同
- 在内存中建立完整的内存索引结构
- 将中间结果写入磁盘临时文件时，将整个内存的倒排索引写入临时文件；对于某个单词的倒排列表在写入磁盘文件时，将词典项放在列表最前端，跟随相应的倒排列表，依次将单词和对应的倒排列表写入磁盘文件，随后彻底清空所占内存。
- 最后将各个文件的倒排列表合并，并形成最终的词典信息。
- 两遍文档遍历法 2-Pass In-Memory Inversion
- 动态索引
- 临时索引：当有新文档进入时，将其加入临时索引中，有文档被删除时，加入删除文档队列。被更改时，将原文档放入删除对列，解析更改后的文档内容，加入临时索引中。满足实时性要求。用户输入查询请求，搜索引擎同时从倒排和临时索引中读取用户查询单词的倒排列表，找到包含查询的文档集合，对结果进行合并，利用删除文档列表进行过滤。
- 索引更新策略
- 完全重建策略：新增文档达到一定数量，将新增文档和老文档合并，重建索引。适合小文档集合，重建代价较高。主流商业搜索引擎都是采用此方式维护索引更新。
- 再合并策略：新文档进入时，在内存维护临时倒排索引记录信息（增量索引）。当新增文档到达一定数量时，或指定大小内存被消耗，把临时索引和老文档倒排合并，生成新索引。用两个指针来进行合并。
- 原地更新策略：将增量索引里的单词的倒排列表追加到老索引相应位置的末尾。为了支持追加操作，在初始建立的索引中，会在每个单词的倒排末位预留一定磁盘空间。
- 混合策略：对不同类别的单词采取不同的索引更新方式。。比如可以分为长倒排列表单词和短倒排列表单词。前者原地更新，后者再合并。前者节省磁盘读写次数，后者读写开销不算太大，顺序读写优势也能被充分利用。
- 查询处理
- 一次一文档
- 查询所含单词的倒排列表，每次将其中某个文档与查询的最终相似性得分计算完毕，再开始计算另一个文档的得分。可以只维护一个大小为K的优先级别对列，用来保存目前得分最高的K个文档。根堆。
- 一次一单词
- 先计算每个单词对应的倒排列表中的文档ID的文档相似度。
- 跳跃指针
- 将一个倒排列表数据化整为零，切分为若干个固定大小的数据块，对每个数据块，增加元信息记录这个块的信息。只需要在定位后对一个数据块进解压缩和文档编号查找就可获得结果。实践证明，假设倒排列表长度为L，使用L^(1/2)作为块大小效果较好。
- 一次一文档
- 多字段索引
- 多索引方式：对不同字段分别建立索引
- 倒排列表方式：用比特位表示关键词是否在某个字段出现过。
- 扩展列表方式：为每个字段集哪里列表，记载每个文档这个字段对应的出现位置信息。
- 短语查询
- 位置信息索引 Position Index
- 双词索引 Nextword Index：如二词词语，建立首词的下词词典。一般只对计算代价高的词语建立双词索引。
- 短语索引：直接加入多词词语并维护短语的倒排列表。挖掘热门短语。
- 混合方法：位置索引适合处理常规短语查询，双词索引适合计算代价较高的短语查询，短语索引适合热门短语或高频词语。
- 分布式索引
- 按文档划分：将整个文档集合切割成若干子集合，每台机器对某个子集合建立索引。
- 按单词划分：每个索引服务器负责词典中部分单词的倒排列表建立和维护。
- 对比：按文档划分更常用，可扩展性更强，负载更均衡，容错性更强。
第4章 索引压缩
- 词典压缩
- 将单词连续存储在某个内存区域，原先存储单词内容给的部分由指向这个单词起始位置的指针代替，单词结尾可以用词典中下一个单词的指针所指向位置来做判断。
- 倒排列表压缩算法：存储文档编号和单词位置的差值，从大数字转换成大量的小整数
- 评价索引压缩算法的指标：压缩率、压缩速度、解压速度（最重要，用户直接感受到）
- 一元编码（Unary Code）与二进制编码（Binary Code）
- 一元编码：对整数X来说，使用X-1个二进制数字1和末位一个0来表示；问题在于，对大数字而言空间不经济
- 二进制编码：比特宽度
- Elias Gamma算法与Elias Delta算法
- x = 2^e + d，对因子e+1采用一元编码表示，对d采用比特宽度为e的二进制编码表示
- 进一步，可继续对e+1采用Elias Gamma算法获得编码，然后与d的二进制编码进行拼接
- Elias Delta算法对于大数值的压缩效果优于Elias Gamma
- Golomb算法与Rice算法
- 因子1 = (X-1)/b 向下取整，加1，一元编码压缩
- 因子2 = (X-1) mod b，二进制编码压缩
- Golomb：b = 0.69 * Avg
- Rice：b一定要为2的整数次幂，b必须是所有小于平均值Avg的2的整数次幂的数值中最接近Avg的数值
- Rice由于设定b为2的整数次幂，所以在具体实现算法时能够采取掩码或者比特位移操作等快速运算方式，因此运算效率高于Golomb
- 对于b，其适用范围可以是局部的也可以是全局的；如果索引非常庞大，采取局部b更好，可以进行自适应调整，提升压缩效率效果
- 变长字节算法（Variable Byte）
- 以字节为基本存储单位
- 需要利用字节中一个比特位作为边界判断符号，如果边界判断符号为0，则认为这个字节是数字压缩编码的最后一个字节，如果是1，说明后续字节仍属于当前压缩数据数字——7个比特位采用二进制编码存储压缩数据，1个做边界，每个字节的数值表示范围为128个数字
- e.g. 33549 = 2 * 128 * 128 + 6 * 128 + 13 -» 1 0000010 1 0000110 0 0001101
- SimpleX系列算法
- Simple9：字对齐算法；利用32个比特位作为一个压缩单位，给定固定大小的压缩单位后，每个压缩单位试图存储多个待压缩的数字。4比特类型指示位用来指示后续数据存储属于哪种类型，B则指出后续数据存储区的基本单元的比特宽度。当B为1，后续存储区基本单元比特宽度为1，数据存储区一共有28个比特，所以这32个比特字一共可以存储28个范围在0到1的数字。当B为2，比特宽度为2，由14个2比特位组成，所以能够存储14个范围在0到3的数字。对于有些宽度，不能被28整除，所以会浪费一些字节。
- PForDelta算法
- 解压速度最快
- 尽可能一次性压缩和解压多个数值
- 在压缩率和压缩解压速度找到平衡点，使得算法可以一次压缩解压多个数值
- 对于待编码的连续K个数值（一般K为128），找出其中10%比例的大数，根据剩下90%的数值范围来定应采取的比特宽度，而10%的大数当作异常数据单独存储。压缩后的数据划分为3块：异常数据存储区、常规数据存储区和异常链表头。
- 大数不做压缩，用4个字节存储，放在静态结构尾端，存储顺序与其在原始数据序列的顺序相反。
- 在常规数据存储区维护了异常大数的一个顺序链表，比如对于某大数A，其在常规数据存储区有对应数值3，则指跳过后面3个值即是另一个异常大数的位置。
- 文档编号重排序（DocID Reordering）