从零开发一个简单的搜索引擎-索引模块第一部分

你的名字 2021-11-14 14:22 265阅读 0赞

> 注：本模块会大量用到protobuf库、cppjieba库，不了解的读者可以先去简单了解一下这两个库怎么使用，这里就不赘述了。  
> （为了避免本模块的内容过长，笔者分两篇完成，第一篇讲搜索引擎索引的基础知识和这个项目中索引模块的基础架构，第二篇讲索引模块的具体技术实现细节。）

## 一、对Boost官网网页的预处理 ##

--------------------

> 注：这个过程用什么语言处理都可以  
> 附：[code][]

由于Boost官网的数据都是以网页的形式呈现的，但是制作索引的时候直接对网页进行操作就比较麻烦，所以这个阶段就是对Boost官网的网页数据先做一个预处理，将它变成制作索引的时候容易处理的形式。

这里采用将每一个网页处理成一行数据，然后每个网页的标题、url以及正文用一个分隔符隔开的形式：`url\3title\3content`。这个分隔符之所以选择一个不可见字符（`\3`）是因为，如果分隔符选择可见字符，可能会和文档中包含的内容冲突。

## 二、有关索引结构的设计 ##

--------------------

> 在实现之前，先介绍一下“索引”的概念。

### 2.1 单词-文档矩阵 ###

单词文档矩阵时表达两者之间所具有的一种包含关系的概念模型。通常逻辑上就像这样：

从纵向即文档这个维度来看，每列表示文档包含了哪些单词，比如：文档1包含词汇1和词汇3，而不包含其他单词。从横向即词汇这个维度来看，每行代表了哪些文档包含这个单词。比如对于词汇1来说，文档1和文档3包含这个词汇，而其他文档不包含这个词汇。矩阵的其他行列同上解读。

搜索引擎的索引其实就是实现单词-文档矩阵的具体数据结构。这个可以有不同的方式来实现上述概念模型，倒排索引是经过实验数据验证表示单词到文档的映射关系的最佳实现方式。除了倒排索引外，还可以用签名文件、后缀树等方式实现，这里主要讲用倒排索引实现的技术细节（TODO：这里后面会有一个链接~）。

### 2.2 倒排索引相关的基本概念 ###

*  文档：这里的文档就是Boost网站的HTML格式的网页；
 *  文档编号：为了方便内部处理，为文档集合内每一个文档赋予一个唯一的内部编号，以此编号作为这个文档的唯一标识。
 *  倒排列表：倒排列表记载了出现过某个单词的所有文档的文档列表。

### 2.3 倒排索引的基本概念 ###

倒排索引是实现单词-文档矩阵映射关系的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。

通过概念可以看出倒排索引由两部分构成：单词和倒排列表。

下面通过一个例子来详细说明倒排索引的结构：

假设有一个文档集合包含5个文档：

<table> 
 <thead> 
  <tr> 
   <th>文档编号</th> 
   <th>文档内容</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>谷歌地图之父跳槽Facebook</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>谷歌地图之父加盟Facebook</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>谷歌地图创始人拉斯离开谷歌加盟Facebook</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>谷歌地图之父跳槽Facebook与Wave项目取消有关</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>谷歌地图之父拉斯加盟社交网站Facebook</td> 
  </tr> 
 </tbody> 
</table>

由于文档内容都是由很多单词构成的，而我们在建立倒排索引的时候首先要将其切分为很多单词，这里就涉及到分词技术，这里不详述，后面会介绍。经过一系列构建过程后，建成的倒排索引结构就是下面这样子的：

> 下面这个是最简单的倒排索引结构，但是足以说明问题。
> 
> 细心的读者在对照上面的原始文档集合和下面的倒排索引时会发现文档中有一部分内容不见了，这里涉及到分词技术的具体细节，我后面会讲，这里先重点理解倒排索引结构。

<table> 
 <thead> 
  <tr> 
   <th>单词</th> 
   <th>倒排列表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>谷歌</td> 
   <td>1，2，3，4，5</td> 
  </tr> 
  <tr> 
   <td>地图</td> 
   <td>1，2，3，4，5</td> 
  </tr> 
  <tr> 
   <td>之父</td> 
   <td>1，2，4，5</td> 
  </tr> 
  <tr> 
   <td>跳槽</td> 
   <td>1，4</td> 
  </tr> 
  <tr> 
   <td>Facebook</td> 
   <td>1，2，3，4，5</td> 
  </tr> 
  <tr> 
   <td>加盟</td> 
   <td>2，3，5</td> 
  </tr> 
  <tr> 
   <td>创始人</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>拉斯</td> 
   <td>3，5</td> 
  </tr> 
  <tr> 
   <td>离开</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>Wave</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>项目</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>取消</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>有关</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>社交</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>网站</td> 
   <td>5</td> 
  </tr> 
 </tbody> 
</table>

### 2.4 正排索引的基本概念 ###

正排索引也称为"前向索引"，它是创建倒排索引的基础。正排索引由文档集合组成，文档集合中的文档包含文档的部分信息。由于设计开发这个Boost搜索引擎的初衷是理解一个搜索引擎的大体设计流程，所以一些地方从简考虑，这里的文档包含的信息有：文档ID、文档标题、文档正文、跳转url、展示url以及标题和正文的分词结果。

详细的正排索引相关知识可以参考其他资料：[正排索引][Link 1]

### 2.5 具体设计 ###

> 对于海量网页数据，为其建立倒排索引往往需要耗费较大的磁盘空间，尤其是一些比较常见的单词，其对应的倒排列表可能大小有好几百M。如果搜索引擎在响应用户查询的时候，用户查询请求中包含常见词汇，就需要将大量的倒排列表信息从磁盘读入内存，之后进行查询处理给出搜索结果。由于磁盘I/O速度往往是性能瓶颈，所以包含常用词的用户查询，其响应速度可能会受到严重影响。

一方面为了减少索引占用的磁盘空间资源，另一方面为了尽量减少磁盘I/O数据量，加快用户查询的响应速度，我们需要对索引数据进行压缩。在这里用`protobuf`这个库，因为相比较`XML`和`json`它的压缩效率是最高的，不过相对应的就是经过`protobuf`压缩的数据可读性非常差，不过这问题不大， 因为这个并不影响我们的开发。

通过前面关于索引相关概念的介绍，这里直接用`protobuf`定义数据格式：

syntax="proto2"
    package doc_index_proto;
    
    //定义分词结果，分词结果结构的设计见后面索引构建过程讲解，这里读者先不用管为什么要定义分词结果
    message Pair {
    	//每个分词结果都是前闭后开区间
    	required uint32 beg = 1;
    	required uint32 end = 2;
    }
    
    //定义正排索引结构
    message DocInfo {
    	required uint64 id = 1;
    	required string title = 2;
    	required string content = 3;
    	required string show_url = 4;
    	required string jump_url = 5;
    	//保存分词结果，这两项先定义在这里，具体含义见后面索引构建过程讲解，这里读者先不用管这两项
    	repeated Pair title_token = 6;
    	repeated Pair content_token = 7;
    }
    
    //定义倒排列表结构
    message Weight {
    	required uint64 doc_id = 1;
    	//文档权重
    	required int32 weight = 2;
    	//该单词在正文中第一次出现的位置
    	required int32 first_pos = 3;
    }
    
    //定义倒排索引结构
    message KwdInfo {
    	//单词的字面值
    	required string key = 1;
    	//倒排列表
    	repeated Weight doc_list = 2;
    }
    
    //定义索引结构
    message Index {
    	//正排索引
    	repeated DocInfo forward_index = 1; //repeated可以理解为一个数组结构，表示这个数据结构包含多个元素
    	//倒排索引
    	repeated KwdInfo inverted_index = 2;
    }

> 注：由于Boost官网的数据量并不是很大，所以简单起见，这里的doc\_id并不以文档编号差值(D-Gap)的形式存储，而是直接存储倒排索引项中的实际文档编号，在实际比较成熟的搜索引擎系统中，doc\_id都是存储文档编号差值(D-Gap)。而这样做的原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。

定义完prorobuf数据格式，生成相应的cpp代码：

protoc index.proto --cpp_out=. # 这个操作后就会生成index.pb.h和index.pb.cc文件

## 三、设计索引核心类 ##

--------------------

### 3.1 构思 ###

#### 3.1.1 对外接口 ####

首先我们要构思这个类对外要提供什么方法，由于它是搜索引擎的索引类，所以至少要包含以下方法：

*  对之前预处理的数据进行解析，在内存中构建出供搜索模块使用的索引。简称构建功能；
 *  给定关键词，获取到和关键词相关的倒排列表。简称查倒排功能；
 *  给定文档ID，获取到文档的详细信息。简称查正排功能。

为了对索引进行压缩存储，还需要包含以下方法：

*  把内存中创建的索引结构进行序列化，保存到磁盘上。简称保存功能；
 *  把磁盘上的索引文件读取到内存中，进行反序列化，生成内存中的索引结构。简称加载功能。

为了更好的检验我们前面方法实现的正确性，还需要提供一个调试接口：

*  将内存中的索引结构按照一定格式打印出来，方便我们观察。简称反解功能。

综上可以得出结论，这个索引类对外提供的接口至少要包含六个：构建、查倒排、查正排、保存、加载、反解。

//TODO：这里其他的构思后面还会加

### 3.2 设计 ###

由于索引类的对象包含的数据量很大，如果在内存中有很多对象，就会造成很大的内存开销，尤其是频繁的创建和销毁，所以这个类可以用设计模式中的 **单例模式** 来创建，这样就可以确定这个类的基础架构。

懒汉模式：

class Index{ 
    public:
        Index();
        static Index* Instance() { 
            if (NULL == inst_) { 
                inst_ = new Index();
            }
        }
        //TODO
    private:
        static Index* inst_;
    	//TODO
    }

然后来看这个类都需要包含哪些成员对象。首先肯定是要包含正排索引和倒排索引的，除此之外，因为要对标题和正文进行分词，所以还需要包含cppjieba分词的一个分词句柄。现在考虑到的成员对象就先这些。根据前面构思的结果，再把对外接口（公有成员对象）加上，索引类的基本结构就成型了：

namespace doc_index {  //把索引模块的逻辑代码都放到自定义的命名空间doc_index里
        
    typedef doc_index_proto::DocInfo DocInfo; // 定义正排索引中文档信息结构的数据类型别名
    typedef doc_index_proto::Weight Weight; // 定义倒排列表中文档信息结构的数据类型别名
    typedef std::vector<DocInfo> ForwardIndex; // 定义正排索引数据类型
    typedef std::vector<Weight> InvertedList // 定义倒排列表数据类型
    typedef std::unordered_map<std::string, InvertedList> InvertedIndex; // 定义倒排索引数据类型
    
    class Index{ 
    public:
        Index();
        static Index* Instance() { 
            if (NULL == inst_) { 
                inst_ = new Index();
            }
        }
        bool Build(const std::string& input_path); // 构建
        const InvertedList* GetInvertedList(const std::string& key) const;// 查倒排
        const DocInfo* GetDocInfo(uint64_t doc_id) const; // 查正排
        bool Save(const std::string& ouput_path); // 保存
        bool Load(const std::string& index_path); // 加载
        bool Dump(const std::string& forward_dump_path, const std::string& inverted_dump_path); // 反解
        
    private:
        static Index* inst_;
        ForwardIndex forward_index_; //正排索引
        InvertedIndex inverted_index_; //倒排索引
        cppjieba::Jieba jieba_; //cppjieba句柄
    	//TODO
    };
    }

[code]: https://github.com/fenshitianyue/Boost-Search/tree/master/index/python
[Link 1]: http://book.51cto.com/art/201105/262902.htm