【2017编程之美】搜索引擎总结

发表于 | 浏览 次
字数统计: 5,454 | 阅读时长 ≈ 19

本文主要回顾和总结2017编程之美决赛中校园聊天机器人后端搜索引擎的实现。

1. 项目简介

校园聊天机器人，针对用户的问题进行回答，当然，问题都是跟校园相关的一些问题。

收集校主页和论坛上的信息，招聘信息、征友信息、失物招领等信息，根据用户的需求返回合适的答案。

2. 爬虫

北邮人论坛格式相对工整，并不需要进行DFS爬取。论坛某个页面如下：

img

论坛格式基本如下：

1  [标题，最新回复时刻]
2  [标题，最新回复时刻]
...
10 [标题，最新回复时刻]
              第k页

因此只需要按页遍历即可。

2.1 数据库设计

爬取的内容建立一张表放入MySQL。由于每个帖子都有自己的唯一性ID，因此可以将这个ID作为主键。

文章ID（主键） 标题（已分词） 最后更新时刻 内容（已分词） 链接 已索引
758943 社招/神马/搜索/北京/资深/广告/算法/研发/工程师 20180302 165751 基于/大规模/用户/行为/效果/目标/建立/优化/推荐/系统/基础/算法/策略 …. https://bbs.byr.cn/#!article/JobInfo/758943 是/否
… … …

2.2 实时爬虫

由于北邮人论坛的【缘分天空】、【毕业生找工作】、【兼职实习信息】等板块很热火，几乎每小时都有新帖。因此可以不考虑资源浪费问题，直接采用定时爬虫进行信息更新和维护。

实时爬虫的流程如下：

img

对于每个页面，我们可以从页面目录快速获取【文章ID、标题、发帖时刻、回复量、最新回复时刻、文章链接】信息。因此当获取到本页面的10篇文章的ID和最新回复时刻TimeStamp后：

  1. 看库中是否存在此ID

    1. 如果存在：

      1. 此帖在近期有回复，更新最新回复时刻TimeStamp

      2. 此帖在近期无回复，有两种可能：

        1. 后面的帖子不再有新的回复，因此可以直接停止本版面的爬虫；
        2. 爬取第1页时，本帖在第1页；爬取第2页时，本帖被顶到第2页；

        为了不让情况2误认为是近期无更新的贴，因此我们设置50次阈值。当连续50篇文章都没有新的更新时，停止爬虫。

    2. 如果不存在，则爬取本页面并添加进数据库

对于每个版块的每个页面，执行以上循环操作。每个页面包含10篇左右文章。由于每篇文章打开需要约1秒，因此一页需要10多秒。北邮人论坛设置反爬虫机制，每连续访问10次后就要休息10秒才可以继续爬。而【毕业生找工作】等热门版面每日的更新量达300+条。那么完成一次此版面的爬取需要10分钟。三个版面的爬取大约需要20分钟。这个时间太长了，不利于后续的实施构建索引。

为了加速爬取速度，我们采用了多线程爬取技术。为了避免重复写入，因此每个线程只负责一个页面。当爬取完毕时，将数据扔到“待写入队列”里排队写入MySQL。

2.3 分词

利用jieba分词模块，对爬取的文档进行分词，首先按是否为汉字、数字、英文字符及标点符号对新闻内容进行梳理，去除掉信息缺失的数据，然后用jieba分词对标题及内容进行分词，并去掉停用词、生僻字等，得到文章的分词内容【这一步骤在爬虫模块已完成】。另外对于北邮人常用的找工作模块，需自定义计算机类技术栈关键词，如Python、Java、计算广告、推荐系统等。

分好词之后就可以存入数据库了。

jieba分词用到了哪些算法，文档里面如下介绍：

• 基于Trie树结构实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图（DAG）
• 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合
• 对于未登录词，采用了基于汉字成词能力的HMM模型，使用了Viterbi算法（隐马尔科夫模型）

日后需要补习

3. 索引构建&检索

3.1 向量空间模型

检索结果排序是搜索引擎最核心的部分，很大程度度上决定了搜索引擎的质量好坏及用户满意度。实际搜索结果排序的因子有很多，但最主要的两个因素是用户查询和网页内容的相关度，以及网页链接情况。这里我们主要总结网页内容和用户查询相关的内容。

​ 判断网页内容是否与用户査询相关，这依赖于搜索引擎所来用的检索模型。检索模型是搜索引擎的理论基础，为量化相关性提供了一种数学模型，是对查询词和文档之间进行相似度计算的框架和方法。其本质就是相关度建模。

常见检索模型：布尔模型，向量空间模型，概率模型，语言模型，机器学习排序算法

  1. 布尔模型

    苹果 AND 公司：表示搜索既包含“苹果”，又包含“公司”这两个词的文档。
    苹果 OR 公司：表示搜索包含“苹果”，或包含“公司”这两个词中任意一个的文档。
    特点：简单粗暴

  2. 向量空间模型

    苹果 AND 公司：表示搜索既包含“苹果”，又包含“公司”这两个词的文档。
    苹果 OR 公司：表示搜索包含“苹果”，或包含“公司”这两个词中任意一个的文档。
    特点：简单粗暴

    本文就是采用这样的方式

  3. 概率检索模型

    概率检索模型基于概率排序原理，是目前效果最好的模型之一，okapi BM25这一经典概率模型计算公式已经在商业搜索引擎的网页排序中广泛应用。

    I. 概率排序原理

    基本思想：给定一个用户查询，若搜索系统能在搜索结果排序时按照文档和用户查询的相关性由高到低排序，那么这个搜索系统的准确性是最优的。

    II. 实际实现

    1. 根据用户的查询将文档集合划分为两个集合：相关文档子集和不相关文档子集。
    2. 将相关性衡量转换为分类问题，对某个文档D来说，若其属于相关文档子集的概率大于属于不相关文档的概率，就认为它与查询相关。

    另P(R|D)代表给定一个文档D对应的相关性概率，而P(NR|D)代表该文档的不相关概率，若P(R|D)>P(NR|D)我们就认为此文档与查询相关。

    根据贝叶斯定理（详见贝叶斯公式推导及意义）,最终等价于计算:

    P(R|D)/P(NR|D)

    搜索系统无需分类，只需将文档按照上式大小降序排列即可。

    III. 估值公式
    基于二元独立模型（BIM）的二元假设和词汇独立性假设，得到最终的相关性估算公式：

    估算公式
    其中pi代表第i个单词在相关文档集合中出现的概率，si代表第i个单词在不相关文档集合中出现的概率。

    取log便于计算：
    这里写图片描述

  4. 统计语言模型

    基本思想：
    ​ 其他的检索模型的思考路径是从查询到文档，即给定用户查询，如何找出相关的文档，该模型的思路正好想法，是由文档到查询这个方向，即为每个文档建立不同的语言模型，判断由文档生成用户查询的可能性有多大，然后按照这种生成概率由高到低排序，作为搜索结果。语言模型代表了单词或者单词序列在文档中的分布情况；

    举个例子：

    先引入一个概念：抽取概率
    把一篇文档进行分词，统计其中每个词的出现频率进行计数，则一个词Word在文档Doc中的抽取概率为“Word词的计数/Doc中所有词的计数之和”。所谓抽取概率，就是在Doc中随机抽取一个词的话，Word被抽取到的概率。
    假设用户搜索“野鸟装备 跑步”，野鸟装备在文档Doc1中的抽取概率1%，跑步的抽取概率为2%，则该次搜索中，Doc1的相关性得分为1%*2%。依此可以计算出所有文档的相关性得分，并按相关性得分对搜索结果进行排序。

  5. 机器学习模型

    机器学习与前面的模型相比，有几个显著的不同：
    1、这里一般使用有监督的机器学习，因此需要对训练结果有监督反馈，用户对搜索结果的隐性评价（即点击）可以看作是一种监督反馈。
    2、传统搜索计算搜索结果相关性一般也就考虑关键词匹配、词频等少数几个维度的数据，使用前面提到的模型已经足够，只有当考察的数据维度比较多时，机器学习的优势才会体现出来。比如像百度、Google这种大型的商业搜索引擎，考察的数据维度要多很多，比如链入链出链接数、网站类型、网站权威度、用户地理位置、历史搜索习惯、设备类型等等，据说Google考察的数据维度多达几百个。
    特点：复杂度高，适合大型商业搜索引擎。

    机器学习排序之Learning to Rank简单介绍

3.2 TF-IDF

3.3 倒排索引构建

对每个词来说更新“词-文章序号”的倒排列表。倒排列表的结构如下：

ID 词 文档频率 倒排记录表
0 中国 3 1,3,4
1 招聘 1 4，
2 蜜蜂 2 1,2

3.4 计算各文档的向量

假如文档1包含的词有【中国，蜜蜂】，按照上字典序号对应的关系，词向量应该为[1,0,1][1,0,1] 。而用01表示词其实并不科学，这里每个词可以用TF-IDF来优化。那么词向量可能会变成[0.2,0,0.1][0.2,0,0.1]

计算每个文档的词向量（下表不必存储）：

文档 词 词向量
1 中国，蜜蜂 [0.2,0,1][0.2,0,1]
2 蜜蜂 [0,0,0.8][0,0,0.8]
3 中国 [0.7,0,0][0.7,0,0]
4 中国，招聘 [0.4,0.6,0][0.4,0.6,0]

将词向量模型更新添加进倒排索引：

词 文档频率 倒排记录表[文章ID，权重]
中国 3 [1,0.2] , [3,0.7] , [4,0.4]
招聘 1 [4,0.6]
蜜蜂 2 [1,0.1], [2,0.8]

其中每个文档中某个词的TF值只与该文档有关，但是IDF是与当前倒排表相关的，计算的时候这里需要主要

3.5 检索

当用户输入查询词时，例如查询【中国，招聘】这两个关键字时，由于关键字无权重，因此可以直接设查询向量qq为[1,1,0][1,1,0] 。按理来说应该直接对着【文档dd-词向量】表格直接依次计算余弦相似度q×dq×d，然后取相似度最高的前K个作为返回结果。但是这样太暴力了，也太慢了。

机智的人类发现，q是一个01向量， q×dq×d 也就是对于q中那些为1的词项，计算在文档d中这些词的权重值和。

因此我们利用倒排索引优化查询。步骤为：

  1. 在词典中定位【中国，招聘】这两个词，返回其倒排记录表。【中国 –> [1,0.2] , [3,0.7] , [4,0.4]】，【招聘 –> [4,0.6]】
  2. 文档4中，中国和招聘两个词的权重值和为1；而文档1的权重为0.2；文档3的权重为0.7

3.6 总结

  1. 索引构建/更新流程图

img

  1. 倒排索引数据库设计

将爬好的数据进行实时权重向量计算，填入下表，即是倒排表

词 文档频率 倒排记录表
中国 3 [1,0.2] , [3,0.7] , [4,0.4]
招聘 1 [4,0.6]
蜜蜂 2 [1,0.1], [2,0.8]

当时这个结构直接存储在了内存当中。但讲道理应该存储在MongoDB这一类KV数据库中。

4. 旧数据删除

​ 后续如果数据量不断增大，可以考虑将一些陈旧的帖子删除，比如保留最近半年有过更新的帖子，不过这还要考虑机器的容量。

本系统定义每天的凌晨4点进行旧数据清除工作。

​ 每个帖子是有有效期的。当某个帖子过了某个时间后信息量就会变得很少，不再有检索需求。因此需要将旧帖子删掉。由于机器硬盘限制，本系统设定当帖子的最后更新时刻与当前时刻超过10天时，此贴应该被从数据库与索引中删除。

​ 本系统定义每天的凌晨4点进行旧数据清除工作。

5. 优化

回头重新看这个问题时，我们发现如果有高并发等类似的请求时，系统还有很多地方需要优化：

5.1 检索模型角度

可以结合其他模型，比如概率模型、语言模型等，如果有一定的用户量之后可以结合learn to rank模型

5.2 字典优化角度

在实现字典时，通常会使用哈希表、树（二查查找树、字典树）等数据结构。

用二叉查找树实现字典

使用二叉查找树实现词典时， 要先将数据对（的列表） 按照单词词典顺序排列。

数据对 = [单词 + 该单词的倒排列表的引用（地址）]

若用内存上的二叉查找树实现之前例子中的词典， 就会得到如下图所示的树形结构。 树中的各个结点是通过地址引用（指针） 连接起来的

img

一般倒排列表都会很长，字典很大。因此会考虑将倒排列表存储到二级存储的连续区域中。

在二级存储上实现词典时，也要先将数据对按照单词的词典顺序排列， 然后一个接一个地存储到存储器上。 但是， 如果只是单纯地一个接一个地存储， 就无法知道各数据对应该在哪里结束了， 因此在此之上还要维护一个列表， 用于存储从开头算起每个数据对的偏移量。 对应的数据结构如图所示。 在进行检索时， 可以对该偏移量的列表进行二分查找。

img

如果词典能够完整地加载到内存， 那么所形成的二叉树的搜索效率将会非常高。 特别是当二叉树处于平衡状态时， 平均进行log2Nlog2N 次查找就能找到单词。
但是， 如果词典无法完整地加载到内存， 而必须存储到二级存储器上时， 二叉树就未必是高效的数据结构了。 HDD 或 SSD 等二级存储器一般被称作“块设备”， 由于它们是以块为单位进行输入输出的 ， 所以即使只是读取块中 1 个字节的数据， 也不得不对整个块进行输入输出操作。 例如， 假设我们用二叉查找树实现了含有 100 万个单词的词典， 那么进行二分查找的话， 平均需要 20 次查找， 因此在最坏的情况下就需要加载 20 个块。 也就是说， 假设二级存储的加载性能为 5ms/ 块， 那么在 1 次检索中， 仅花费在二级存储输入输出上的时间就高达100ms。
因此， 当要存储大型词典时， 往往要使用适合块设备的 B+ 树等树形数据结构。

用B+树实现字典

B+ 树是一种平衡的多叉树， 属于从 B 树派生出来的树形结构。 在 B+ 树中， 所有的记录都存储在树中的叶结点（Leaf Node） 上， 内部结点（Internal Node） 上只以关键字的顺序存储关键字

img

B+树通常以文件系统中页尺寸的常数倍为单位管理各节点。这样有助于减少检索时对二级存储的输入输出次数。

5.2 倒排索引构建/更新角度

简单的文档列表直接存储在内存中。比如我们的项目搜索引擎的倒排索引就是放在内存中的，但是大多数情况倒排索引都是非常稀疏的表，因此用链表实现倒排索引非常好。

而文档链表一般都很大，因此很多都存储在二级存储中。这样就有两种构建方法：基于排序的构建方法和基于合并的构建方法。

基于排序的索引构建法

  1. 对各文档中构成该文档的每个单词都建立一条【单词、文档编号、TF】的记录。然后将该记录写入二级存储上的文件末尾
  2. 将文件各条记录按照字典顺序排列；单词字段相同的再按照文档编号顺序排列
  3. 逐行读取排序后的文件，取出每个单词的文档编号列表；并用这些列表构建每个单词的倒排索引（这一步可以压缩倒排列表，此处省略）

基于合并的索引构建法

基于合并的索引构建法是一种先在内存上构建出倒排索引的片段，然后将这些片段导出到二级存储，最后将导出的多个倒排索引合并在一起。

  1. 在内存上构建【单词-倒排】的kv映射表Map。
  2. 如果某单词不在Map里，就要将该单词加入到Map中
  3. 当Map过大，就将Map导入文件里
  4. 重复1-3步骤，直到处理完所有文档。最后利用多路归并将将导出的各文件合并在一起。（这一步也可以压缩倒排，此处省略）

动态索引构建

之前说的索引构建方法都是只有构建完成后才可用于检索。这叫静态构建方法（Offline Index Construction）。

还有一种动态构建方法（Online Index Construction / Dynamic Indexing）。这种方法可以一边更新索引，一边检索。其基本策略如下所示：

  • 将索引分成内存上的索引和磁盘上的索引分别管理
  • 添加文档后，优先更新内存上的索引
  • 当内存索引满时，将其整合到磁盘上的索引中

5.3 倒排索引压缩

为什么要进行压缩？

如果数据量很大，倒排索引庞大，在使用倒排索引进行检索的过程中，总检索时间中的大部分时间往往花费在了从二级存储读取倒排索引上。于是，就经常可以看到在存储倒排索引前，对其进行压缩以减少从二级存储读取的时间，进而使检索处理得以高速运转的对策。

也就是说，我们可以根据如下原理，通过压缩倒排索引来加快检索处理的速度。

从二级存储中读取（部分）经过压缩的倒排索引的时间＋还原倒排索引的时间
＜从二级存储中读取（部分）尚未经过压缩的倒排索引的时间

倒排索引的压缩分为针对词典的压缩和针对倒排文件的压缩两种。
我们可以通过使用更少的信息量表示单词的集合来实现词典的压缩。例如，对于按照词典顺序排列的单词列表而言，通过避免重复存储相同的前缀，就可以减少存储词典时所需的必要存储空间。但是，在大多数情况下，由于词典的大小远远小于倒排文件的大小，所以一般认为压缩词典对于加快检索处理的速度并没有太大的贡献。

而倒排文件的压缩，可以通过使用更少的信息量表示其构成要素来实现。构成要素就是指文档编号、单词在文档内的出现次数（TF，Term Frequency，词频）以及由单词在文档内的偏移量构成的整数数组。

使用可变长度的编码确实可以带来大幅度的压缩。

待填坑==

6. 参考文献

  1. 自制搜索引擎
  2. B树与B+树
  3. TF-IDF与余弦相似性的应用（一）：自动提取关键词
  4. 机器学习排序之Learning to Rank简单介绍
  5. 搜索引擎的检索模型-查询与文档的相关度计算