算法|《自制搜索引擎》笔记算法|搜索

第1章搜索引擎是如何工作的搜索引擎的基础是应用于信息检索、数据库等领域的信息技术。
1-1 理解搜索引擎的构成
1-2 实现了快速全文搜索的索引结构利用全扫描进行全文搜索
grep就是从头到尾扫描作为检索对象的文档的。
利用索引进行全文搜索
先建立索引需要花费时间。
倒排索引的结构
例子：印在教程书后面的索引。
所谓倒排索引就是一张列出了“哪个单词出现在了哪一页”的表格。如下图：

倒排索引的构建方法

为了便于浏览，我们交换了上表的行和列，并将单词按字典序排序：

倒排索引中的术语
对于每种作为检索对象的数据，构建索引的单位都是不同的。
1-3 深入理解倒排索引倒排索引 = 词典 + 倒排文件

从倒排索引中查找单词
如何查找同时包含了多个单词的文档呢？
查找时只需要先从词典中找出各个单词，然后分别获取这些单词的倒排列表并加在一起，由此计算出包含在各个倒排列表中的文档编号的交集。
将单词的位置信息加入倒排文件中

文档级别的倒排文件。
单词级别的倒排文件。这种倒排文件中不仅带有有关单词出现在了哪个文档中的信息，还带有单词出现在了文档中的什么位置（从开头数是第几个单词）这一信息。如：

engine: D1; 4 Google: D2; 5 I: D1; 1,D2; 1

从倒排索引中查找短语
查找短语时还需要确认 search 和 engine 是否是相邻出现的。例如，虽然下面的文档也同样包含了 search 和 engine，但却与搜索引擎(search engine)无关。
I search for a gas station because my car’s engine doesn’t start.
1-4 制作中文文档的倒排索引分割中文句子的两种方法
对全文搜索引擎这段文本分割将得到不同的结果。
①词素解析分割法
将句子分割为“词素”序列的方法。词素是语言中含有意义的最小单位。一般采用的是机器学习的方法。分割结果：
全文　搜索　引擎
②N-gram分割法
N-gram 分割法是一种将句子分割成由 N 个字符组成的片段序列的方法，每个片段称作一个 N-gram。使用bi-gram分割结果：
全文　文搜　搜索　索引　引擎
权衡分割方法
由 N-gram 构成的倒排索引不会产生检索遗漏问题。
但是相比于词素解析，在同一个文档中使用 N-gram 产生的词元通常较多。
1-5 实现倒排索引实现词典
为了能够快速地获取到对应着单词的倒排列表，通常都会使用哈希表、树等数据结构。
用二叉查找树实现词典
在内存上实现词典

在二级存储器上实现词典

用B+树实现词典
HDD 或 SSD 等二级存储器一般被称作“块设备”，由于它们是以块为单位进行输入输出的 A ，所以即使只是读取块中 1 个字节的数据，也不得不对整个块进行输入输出操作。当要存储大型词典时，往往要使用适合块设备的 B+ 树等树形数据结构。

所有的记录都存储在树中的叶结点（Leaf Node）上，内部结点（Internal Node）上只以关键字的顺序存储关键字。
B+ 树通常以文件系统中页尺寸的常数倍为单位管理各结点，而由这样的结点来构成树，则有助于减少检索时对二级存储的输入输出次数。
实现倒排文件

倒排列表的物理布局

文档编号（DocID）
文档中的偏移列表（off1、off2…）
TF词频，用于计算检索结果的排名
对于之前例子中对应着 search 的倒排列表 (D1; 3,D2; 2)，就可以用如下的整数数列表示。
1,1,3,2,1,2

压缩倒排列表会保存经过压缩的倒排列表来缩短加载时间。
由于倒排列表一般都是整数数列，所以通常会采用适合整数数列的压缩方法。
1-6 使用倒排索引进行检索使用倒排索引的检索处理流程
① 获取查询中每个单词的倒排列表；
② 根据布尔检索，获取符合检索条件的文档编号；
③ ’ 计算符合检索条件的文档和查询的匹配度；
③ ” 获取对检索结果进行排序时使用的属性值；
④ 根据匹配度或用于排序的属性值，获取前 k 个文档。

关联度的计算方法
在计算余弦相似度时，需要把文档和查询映射到以单词（Term）为维度的向量空间上，文档向量和查询向量的夹角（内积）越小，说明文档和查询的关联度越高。
信息检索中的检索
在检索处理中，文档是否包含查询无关紧要，重要的是通过计算查询和整个文档的关联度，把关联度高的文档作为检索结果。
1-7 构建倒排索引使用内存构建倒排索引
完全可以按照1-2节中的方法构建，先在内存上生成与文档编号对应的单词表（二维数组），然后用相同的方法倒排该表。
但是这样做，生成都是非常稀疏的表，会消耗大量内存。
使用二级存储构建倒排索引
基于排序的索引构建法
基于合并的索引构建法
从后面的代码可以看到就是用来sqlite数据库。
静态索引构建和动态索引构建
动态索引构建不但可以使索引结构时刻处于可供检索的状态，还可以一边实时更新索引，一边构建索引。这种方法多用于信息的时效性非常重要的文档。
1-8 准备要检索的文档数据规范化
在规范 HTML 文件时，就要删除标签并提取出作为检索对象的文章（内容）。
第2章准备全文搜索引擎的检索样本 2-1 全文搜索引擎wiser
2-2 安装wiser 2-3 运行wiser 先来看下使用说明：

$ ./wiser usage: ./wiser [options] db_fileoptions: -c compress_method: compress method for postings list -x wikipedia_dump_xml: wikipedia dump xml path for indexing -q search_query: query for search -m max_index_count: max count for indexing document -t ii_buffer_update_threshold : inverted index buffer merge threshold -s: don't use tokens' positions for searchcompress_methods: none: don't compress. golomb : Golomb-Rice coding(default).

构建倒排索引

$ ./wiser -x ../../1000.xml -m 1000 wikipedia_1000.db [time] 2017/02/26 21:57:34.000007 count:1 title: Wikipedia:Upload log count:2 title: Wikipedia:删除纪录/档案馆/2004年3月 count:3 title: 数学 count:4 title: Help:目录 count:5 title: 哲学 ...

生成的数据库表如下：

使用倒排索引查询

$ ./wiser -q "顾城" wikipedia_1000.db [time] 2017/02/26 22:10:43.000008 document_id: 991 title: 顾城 score: 199.315686 Total 1 documents are found! [time] 2017/02/26 22:10:43.000008 (diff0.001520)

第3章构建倒排索引 3-1 复习有关倒排索引的知识提取词元
考虑UTF-8字符编码特性。
在 UTF-8 中，是用 1 到 4 个字节的长度来表示 1 个字符的。例如，像数字和拉丁字母等在英文中使用的字符都是用 1 个字节表示的，而在中文中使用的字符则多半要用 3 个字节才能表示。
例如，对于“Web 检索”这个字符用如下的字节序列表来表示：
0x57 0x65 0x62 0xe6 0xa3 0x80 0xe7 0xb4 0xa2

在 wiser 中，为了避开由使用 UTF-8 带来的处理上的麻烦，我们在每次获取 N-gram 时，都会先将字符串的编码从 UTF-8 转换成 UTF-32。 UTF-32 是一种以 4 字节（32 bit）的数值为单位表示 Unicode 字符的编码方式。由于 Unicode 的字符与表示该字符的数值是一一对应的，所以在 UTF-32 中，由 N-gram 分割而成的词元所含有的字节数就变成固定的了，这样就简化了程序上的处理过程。
为每个词元创建倒排列表
单词级别的倒排列表：是由文档编号和词元在文档中出现的位置构成的二元组的集合。
3-2 构建倒排索引在存储器上创建倒排列表
最直接的方法就是不断地将倒排项（文档编号和位置信息）添加到存储器上的倒排列表的末尾。
倒排列表和倒排文件的数据结构

/* 倒排列表（以文档编号和位置信息为元素的链表结构）*/ typedef struct _postings_list { int document_id; /* 文档编号 */ UT_array *positions; /* 位置信息的数组 */ int positions_count; /* 位置信息的条数 */ struct _postings_list *next; /* 指向下一个倒排列表的指针 */ } postings_list;

/* 倒排索引（以词元编号为键，以倒排列表为值的关联数组） */ typedef struct { int token_id; /* 词元编号（Token ID）*/ postings_list *postings_list; /* 指向包含该词元的倒排列表的指针 */ int docs_count; /* 出现过该词元的文档数 */ int positions_count; /* 该词元在所有文档中的出现次数之和 */ UT_hash_handle hh; /* 用于将该结构体转化为哈希表 */ } inverted_index_hash, inverted_index_value;

通过为类型赋予别名使二者有所区别，用 inverted_index_hash 类型表示整个关联数组，用该类型的别名 inverted_ index_value 表示关联数组中的一个元素。
从源代码级别梳理倒排索引的构建顺序
就用我之前写过的这个方法来看代码，或者用Clion。
add_document() ① 从文档中取出词元。
② 为每个词元创建倒排列表并将该倒排列表添加到小倒排索引中。
③ 每当小倒排索引增长到一定大小，就将其与存储器上的倒排索引合并到一起。
第4章开始检索吧 4-1 检索处理的大致流程 ① 将查询分割为词元（如果使用的是 bi-gram，那么就会分割出“自制”“制搜”“搜索”“索引”“引擎”5 个词元）。
② 将分割出的各个词元，按照出现过该词元的文档数量进行升序排列。
③ 获取各个词元的倒排列表，并从中取出文档编号和该词元在文档中出现位置的列表。
④ 如果所有词元都出现在同一个文档中，并且这些词元的出现位置都是相邻的，那么就将该文档添加到检索结果中。
⑤ 计算已添加到检索结果中的各文档与查询的匹配度（在 wiser中，我们使用 TF-IDF 值作为匹配度）。
⑥ 将检索结果按照匹配度的降序排列。
⑦ 从经过排序的检索结果中取出排在前面的若干个文档作为检索结果返回。
4-2 使用倒排索引进行检索从源代码级别梳理检索处理的流程
调用split_query_to_tokens函数将查询字符串转换为词元序列inverted_index_hash。
使用具体示例加深对检索处理流程的理解
如果能够找到一个在所有倒排列表中都出现过的文档编号，那么就将它所指向的文档加入到候选检索结果中。

- 首先获取了词元 A 的文档编号，然后检查了其他的词元是否也带有相同的文档编号
- 如果没有发现带有相同文档编号的词元，那么接下来就继续向后读取词元 A 的倒排列表，直到遇到更大的文档编号为止。
相关的实现在search_docs中。
第5章压缩倒排索引 5-1 压缩的基础知识压缩倒排索引的好处
在使用倒排索引进行检索的过程中，总检索时间中的大部分时间往往花费在了从二级存储读取倒排索引上。于是，就经常可以看到在存储倒排索引前，对其进行压缩以减少从二级存储读取的时间，进而使检索处理得以高速运转的对策。
倒排索引的压缩方法
倒排文件的压缩方法
在一般的程序中，大多数情况下都会为整数分配 4 或 8 个字节等定长的编码，但是在处理倒排文件时，由于经常要处理大量数值较小的整数，所以为了使用更少的信息量来表示整数，通常都会采用长度可变而非固定的编码方式。
Golomb编码压缩的原理
5-2 实现wiser中的压缩功能了解无需进程压缩时的操作
【算法|《自制搜索引擎》笔记】encode_postings_none函数将倒排列表转换成字节序列。
该函数会先从倒排列表的各元素中取出文档编号、位置信息的数量以及位置信息的数组，然后再将这些数据以二进制的形式写入缓冲区。

/** * 将倒排列表转换成字节序列 * @param[in] postings 倒排列表 * @param[in] postings_len 倒排列表中的元素数 * @param[out] postings_e 转换后的倒排列表 * @retval 0 成功 */ static int encode_postings_none(const postings_list *postings, const int postings_len, buffer *postings_e) { const postings_list *p; LL_FOREACH(postings, p) { int *pos = NULL; append_buffer(postings_e, (void *)&p->document_id, sizeof(int)); append_buffer(postings_e, (void *)&p->positions_count, sizeof(int)); while ((pos = (int *)utarray_next(p->positions, pos))) { append_buffer(postings_e, (void *)pos, sizeof(int)); } } return 0; }

介绍几个轮子