《自制搜索引擎》笔记


第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_file

options:
  -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 search

compress_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 (diff   0.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;
}

介绍几个轮子

  • utarry:a dynamic array implementation using macros.
  • uthash:处理关联数组。
  • buffer:在util.h中定义的支持动态扩容的缓冲区。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端杂货铺

typeof的一些兼容性问题

typeof存在一些兼容性的问题,在IE6,7,8中的DOM和BOM元素及其对象上的方法的判定会出现误差,在safari上对NodeList实例 的判定,对Ex...

33915
来自专栏余林丰

7.哈希

  哈希(Hash)又称散列,它是一个很常见的算法。在Java的HashMap数据结构中主要就利用了哈希。哈希算法包括了哈希函数和哈希表两部分。我们数组的特性可...

2059
来自专栏韩伟的专栏

框架设计原则和规范(三)

此文是《.NET:框架设计原则、规范》的读书笔记,本文内容较多,共分九章,将分4天进行推送,今天推送6-7章。 1. 什么是好的框架 2. 框架设计...

3506
来自专栏MyBlog

Effective Java 读书笔记(7)避免finalizer

对于Finalizers他们的使用可能会造成错误的产生,糟糕的性能以及移植性的问题,当然Finalizers有着一些有用的优点,我们会在后续介绍这些,但是作为首...

792
来自专栏C/C++基础

C++ 模板元编程简介

模板元编程(Template Metaprogramming,TMP)是编写生成或操纵程序的程序,也是一种复杂且功能强大的编程范式(Programming Pa...

1083
来自专栏Python专栏

Python | 判定IP地址合法性的三种方法

IP合法性校验是开发中非常常用的,看起来很简单的判断,作用确很大,写起来比较容易出错,今天我们来总结一下,看一下3种常用的IP地址合法性校验的方...

833
来自专栏光变

你所不知道的Java之HashCode

以下内容为作者辛苦原创,版权归作者所有,如转载演绎请在“光变”微信公众号留言申请,转载文章请在开始处显著标明出处。

1200
来自专栏企鹅号快讯

《数据库系统概念》12-文件的组织

一个数据库被映射到多个不同的文件,这些文件由底层的操作系统来维护。每个文件分成定长的存储单元,称为块(bolck),块是存储分配和数据传输的基本单元。数据库默认...

2539
来自专栏PHP技术

PHP 简短而安全的数组遍历

但是其实这样会引起一个重要的问题:如果 $definition['keys'] 没有定义的话,这个时候的数组变量(也就是 foreach)就会出现错误。

942
来自专栏IT笔记

如何限制input输入类型

1.只能输入和粘贴汉字 <input onkeyup="value=value.replace(/1/g,'')" onbeforepaste="clipbo...

3267

扫码关注云+社区