浅谈搜索引擎基础（下）

链接分析

我们在最开始说过，搜索引擎在查找能够满足用户需求的网页时，主要会考虑两方面的因素，一方面是用户发出的查询与网页内容的相关性得分，另一点就是通过链接分析方法计算获得的得分，也即网页的重要性。

PageRank算法

PageRank算法是Google创始人于1997年构建早期搜索系统原型时提出的链接分析算法，目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。

对于某个网页A来说，该网页的PageRank计算基于以下两个基本假设：

• 数量假设：在Web图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。
• 质量假设：指向页面A的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是高质量的页面指向页面A，页面A越重要。

PageRank计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关系的。也即如果有一个搜索引擎完全基于PageRank，那用户不论输入什么查询语句，返回的结果都是相同的，都是PageRank值最高的页面。

PageRank计算

初始阶段，每个页面设置相同的PageRank值，通过若干轮的计算，每个页面会收敛到最终的PageRank值。

在一轮PageRank得分的更新计算中，每个页面将其当前的PageRank值平均分配到本页包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和，即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值，就完成了一轮PageRank计算。

链接陷阱与远程跳转

如果仔细思考一下就会发现上面的PageRank算法存在问题。一个典型的例子就是链接陷阱，比如三个网页，相互链接指向，形成了一个环结构，这种结构在计算PageRank的时候，该结构将导致系统只会吸收传入的分支，而不能将获得的分值传播出去，随着PageRank一轮轮地连续计算，链接陷阱内的页面PageRank值将会越来越高。

远程跳转是解决链接陷阱的通用方式，所谓远程跳转，即在网页向外传递分值的时候，不限于向出链所指网页传递，也可以以一定的概率向任意其他网页跳转。权值通过这种虚拟边向外传递，以此来避免链接陷阱导致的问题。

HITS算法（Hypertext Induced Topic Selection）

Hub页面与Authority页面

Hub页面与Authority页面是HITS算法最基本的两个定义，所谓Authority页面是指与某个领域或某个话题相关的高质量网页；所谓Hub页面，指的是包含了很多指向高质量Authority页面链接的网页。

相互增强关系

HITS算法隐含并利用了两个基本假设：

• 一个好的Authority页面会被很多好的Hub页面指向
• 一个好的Hub页面会指向很多好的Authority页面

通过这种相互增强关系不断迭代计算，即可找出哪些页面是高质量的Hub页面和Authority页面。

HITS算法流程

HITS算法与PageRank一个显著的区别就是HITS算法与用户输入的查询请求密切相关，而PageRank算法是与查询无关的全局算法。

HITS算法接收到了用户查询之后，会将查询提交给某个现有的搜索引擎或是自己构建的检索模型，并在返回的搜索结果中，提取排名靠前的网页，得到一组与用户查询高度相关的初始网页集合，这个集合被称为根集。

在根集的基础上，凡是与根集网页有直接链接指向关系（指向根集内页面/根集页面有链接指向）的网页都被扩充进扩展网页集合。HITS算法在这个扩展网页集合内寻找好的Hub页面与Authority页面。

对于扩展网页集合，我们对每个页面都设置两个初始权值，一般将Hub权值和Authrity权值都初始化为1

之后可以根据前面的两条基本假设不断进行迭代，直到权值收敛。

HITS算法存在主题漂移问题，如果在扩展网页集合里包含部分与查询主题无关的页面，而且这些页面之间有较多的相互链接指向，那么HITS算法很可能给给予这些无关网页很高的排名，这种现象被称为紧密链接社区现象。

HITS算法计算效率较低，且较容易被作弊者操纵结果，而PageRank因为增加了远程跳转，机制上优于HITS算法。

SALSA算法

SALSA算法融合了PageRank与HITS算法的基本思想，是目前效果最好的链接分析算法之一。

SALSA算法有两个阶段，首先是确定计算对象集合的阶段，这一阶段与HITS算法基本相同；第二阶段是链接关系传播过程，这一阶段采纳了PageRank的随机游走模型。

首先SALSA算法像HITS算法一样算出扩展网页集合。

之后，SALSA算法根据网页链接关系，将扩展网页集合转换为一个二分图，一个子集合是Hub集合，另一个是Authroity集合，规则如下：

• 如果一个网页网页包含出链指向扩展网页集合内其他节点，则这个网页可以被归入Hub集合
• 如果一个网页网页包含扩展网页集合内其他节点指向的入链，则这个网页可以被归入Authority集合

根据以上规则，如果某个网页同时包含入链和出链，则可以同时归入两个集合。Hub集合内网页的出链组成了二分图的边。

与HITS算法不同，这里SALSA在形成二分图之后，原来的有向边不再保留方向，转换为无向边：

二分图

接下来是链接关系传播阶段，SALSA算法舍弃了HITS的相互增强假设，转而采用PageRank随机游走模型的思想。

SALSA算法假设存在某个浏览者，从子集合中随机选择一个节点出发，如果节点包含多条边，则以相等概率随机选择一条边，从Hub（Authority）子集合跳到Authority（Hub）集合内节点，如此不断在两个子集之间转移，形成了SALSA自身的链接关系传播模式。

这个随机游走模型看起来与PageRank不同，但实际上『以相等概率随机选择一条边』与『每个页面将其当前的PageRank值平均分配到本页包含的出链上』是等价的。而HITS算法属于权值广播模式，即将节点本身的权值完全传播给有链接指向的节点，并不根据链接多少进行分配。

之后我们要将二分图转化为Authority节点关系图。

得到Authority节点关系图要去掉原二分图中的Hub节点，只保留Authority节点，并新建Authority节点之间的链接关系，Authority节点之间的链接关系继承自二分图中原有的链接关系。简单举个例子，Authority节点A到B的链接概率为原二分图中所有A到B的间接路径的概率和，而每条间接路径的概率通过这条路径上所有子路径的概率乘积计算得出，每条子路径的概率根据所属节点出链的个数平均分配。最后得到的Authority节点关系图如下：

可以发现节点1是独立的，是因为在原二分图中并不存在由节点1到节点3/5/6的任何间接路径。（其实Authority节点关系图在后面起到的作用只是判断哪些节点之间是连通的，转移概率并没有用到）

建好Authority节点关系图之后，即可根据随机游走模型来计算每个节点的Authority权值。在实际计算过程中，SALSA将搜索结果排序问题进一步转换为求Authority节点矩阵的主秩问题，矩阵的主秩即为每个节点的相应Authority权值得分，按照Authority得分由高到低排列，即可得到最终的搜索排序结果。

简单说一下，我们根据Authority节点关系图得知节点3、5、6是连通的，1是独立的，然后我们根据如下公式计算每个Authority节点的Authority权值得分：

这个式子很好理解，第一部分就是当前节点所在的子连通图的节点个数占总节点个数的百分比，也即当前节点所在子连通图对于整个Authority节点关系图的重要程度；第二部分是当前节点的入链个数占当前节点所在子连通图入链个数的百分比，也即当前节点在当前节点所在子连通图的重要程度。从式子中也可以看出，所有Authority节点的权值之和为1。

举个例子，节点3的权重最后计算结果为0.25，3/4乘2/6。

另外，如果整个Authority节点关系图是连通的，那么SALSA算法退化为根据节点入链个数决定排序顺序的算法。

SALSA算法不需要像HITS算法一样进行不断的迭代，所以计算效率要快于HITS算法，也同时解决了HITS算法的主题漂移问题（一是因为去掉了Hub页面，二是倾向于取Authority中重要连通图中重要的子Authority节点）。SALSA算法是目前效果最好的链接分析算法之一。

主题敏感 PageRank（Topic Sensitive PageRank）

PageRank算法与查询无关，只能作为相似度计算的一个因子体现作用，无法独立使用。而主题敏感PageRank是查询相关的，可单独作为相似度计算公式使用。

主题敏感 PageRank 主要有两个计算步骤，第一个是离线的分类主题PageRank数值计算；第二步是在线利用算好的主题PageRank分值，来评估网页和用户查询的相似度。

第一步是参考ODP网站，ODP网站定义了16个大的主题类别，每个主题类别下有人工收集的精选高质量网页地址。然后以这16类主题类型的网页为基础，计算PageRank分值，即每个网页会被赋予16个主题相关的PageRank分值。不像普通的PageRank算法，所有的权值都被初始化为1，人工收集的精选高质量网页地址会被赋予较高的权值，然后由它们根据链接关系向其它网页传递权值。

第二步是在线相似度计算，首先要根据用户查询分类器对查询进行分类，计算用户属于定义好的各个类别的概率分别是多少，然后再相应的乘以待计算相似度的网站每个类别的PageRank值，最终得到相似度。

主题敏感PageRank的机制非常适合作为个性化搜索的技术方案，比如在计算用户查询的类别时，不仅考虑用户当前输入的查询词，也考虑用户过去的搜索记录等个性化信息，就能更精准的提供搜索服务。

网页反作弊

出于商业利益驱使，很多人会通过特殊手段将网页的搜索排名提高到与其网页质量不相称的位置，这样会严重影响搜索引擎用户的搜索体验。

常见的作弊方法包括：内容作弊、链接作弊、隐藏作弊等，这里均简单介绍一下。

内容作弊比如在网页中重复关键词、放置无关查询词、在图片alt标签以及网页标题等重要标签放置关键词等，或者用一些低质量的内容搞内容农场。

链接作弊有链接农场，就是大量互相紧密链接的网页集合，还有利用链接描述性文字的谷歌轰炸等等。

页面隐藏作弊有IP地址作弊、HTTP请求作弊来欺骗爬虫。

反作弊的方法比如信任传播模型，筛选出一些肯定不会作弊的白名单页面，给予一定信任分值，然后白名单内节点通过链接关系将信任度分值向外扩散传播，然后确定一个信任度阈值；或者反过来用黑名单做不信任传播模型；还有异常发现模型，倾向于去发现作弊网页不同于正常网页的特征。

用户查询意图分析

用户之所以会产生搜索行为，往往是在解决任务时遇到自己不熟悉的概念或问题，由此产生了对特定信息的需求，之后用户会在头脑中逐步形成描述需求的查询词，将查询词交给搜索引擎，然后对搜索结果进行浏览，找到满足自身需求的信息或者根据搜索结果的启发，修正自己的查询关键词重新搜索。

上面的问题在于，从用户产生信息需求到最终形成用户查询，中间有很大的不确定性，用户用的查询语句与用户的信息需求很难一开始就是完全等价的。因此用户会改写自己的需求，比如抽象化改写、具体化改写及同义重构改写。

用户搜索意图分类

有人将用户的意图分为三个大类：导航型、信息型、事务型。

这让我想到了有篇文章，阿里小蜜将用户的意图分为三种：问答型、任务型、语聊型。

• 问答与信息型相同，都是希望获取某种信息，知道某种知识。
• 任务型与事务型相同，都是希望完成一个目标明确的任务。
• 导航型搜索引擎独有，用户希望查找某个网页，但又不知道URL，所以借助搜索引擎。
• 语聊型chatbot独有，毕竟没人会和一个搜索引擎闲聊吧。

意图识别可以采取一些通用的分类器，比如SVM、决策树等完成。

搜索日志挖掘

搜索引擎是搜索引擎对用户行为的记录，一般记载了查询、发出查询的用户ID，发出查询的时间、点击网页的网址及这条网址在搜索记录中的排名情况。

查询会话

比如在搜索日志中，我们可以找出用户在较短时间段内发出的连续多个查询，这样的一段日志被称作一个查询会话，一个查询会话中的用户查询语句往往会有语义上的相关性。比如我们可以依此来构建查询图，用来表示查询之间的这种相互关系。

点击图

点击图是非常有价值的信息，我们可以认为搜索结果里被点击过的网页与用户查询更相关。

相关搜索

相关搜索也常被称作查询推荐，就是百度搜索页面拉到底的那些推荐查询词。

搜索引擎计算相关查询的方法基本有两种，基于查询会话的方法和基于点击图的方法。

基于查询会话，就是将其他用户包含当前查询语句的查询会话中的其他查询语句推荐给用户。基于点击图的方法是，如果两个查询各自对应的点击网址中，有很大比例是相同的，那么说明这两个查询在语义上紧密相关，可以作为相互推荐的相关查询。

查询纠错

说查询纠错之前我想先说一下查询预测，《浅谈机器学习基础》中的Apriori算法就是用来发现频繁项集并在用户输入查询词时推荐给用户的。

查询纠错其实分为两步，一是错误识别，而是错误纠正。

大多数错误识别机制是基于词典的，即将用户输入的查询分词后查找词典，如果在词典里没有找到，那么这很可能是一个错误输入。

至于错误纠正，主要的方法有两种，一个是编辑距离，另一个是噪声信道模型。

编辑距离其实在《浅谈自然语言处理基础》中自动机那部分应该提到的，但是省略了，这里简单说一下。编辑距离通常使用有限状态自动机来实现，编辑距离的意义是衡量两个字符串的拼写差异有多大，也即对于某个字符串来说，可以通过进行几次操作，来逐步将其转换成另一个字符串，这些操作可以是删除字符、添加字符、更改字符以及交换字符顺序。与原错误串编辑距离较小的正确串很有可能就是用户所想要输入的字符串。

噪声信道模型在《浅谈自然语言处理基础》的汉语自动分词的N-最短路径方法那里提到过，当时讲的是，假设一串有分词符号的字符串经过噪声信道，丢失了分词符号，我们要根据其输出反推，找出概率最大的输入，也即完成了分词过程。

这里也是类似，我们假设正确串W是输入，错误串V是输出，那么对于多个候选正确答案，我们就要找到概率最大的作为错误串V对应的正确查询串。具体的计算要用贝叶斯公式，需要找出最大的P(W|V)所对应的那个W，根据贝叶斯公式，P(W|V)=P(V|W)*P(W)/P(V)，P(V)都是相同的就不考虑了，关键还是求P(V|W)*P(W)，P(V|W)是正确串W被误写为V的概率，P(W)是正确串W的出现概率，这两个概率都需要通过训练语料统计出来。

网页去重

最开始也提到过，互联网页面中有相当大比例的内容是完全相同或者大体相同的，内容重复可以归结为以下4种类型：

• 内容、布局均相同
• 内容相同、布局不同
• 部分重要的内容相同，布局相同
• 部分重要的内容相同，布局不同

如果我们能够找出这些重复网页，那首先我们能够节省一部分存储空间，其次能够提高网页的收集速度。而且镜像多的网页，往往比较重要。另外，如果用户点击了一个死链接，可以将用户引导到一个内容相同的页面。

通用去重算法框架

通用去重算法框架

对于给定的文档，首先通过一定的特征抽取手段，从文档中抽取出一系列能够表征文档主题内容的特征集合。这一步往往有其内在要求，即尽可能保留文档重要信息，抛弃无关信息，以加快计算速度。

在文档转换成特征集合后，为了进一步加快计算速度，很多高效实用的算法会在特征集合的基础上，对信息进一步压缩，采用信息指纹相关算法，将特征集合压缩为新的数据集合，其包含的元素数量远小于特征集合数量，有时甚至只有唯一的一个文档指纹。

把文档压缩为文档指纹之后，即可开始通过相似性计算来判断哪些网页是近似重复页面。这里常用的方法有Jaccard相似度，Jaccard相似度在《浅谈推荐系统基础》中提到过，就是交集比上并集。

Shingling算法

与上面说的通用去重算法框架相同，Shingling算法由两个大步骤组成，第一步是从文档中抽取能够代表文档内容的特征，第二步则是根据两个文档对应特征集合的重叠程度来判断文章是否近似重复。

第一步用一张图就能说清楚：

文本文档转化为特征集合

把文档按照上述方法拆分为若干个单词片段，并对每个片段进行哈希，即得到文档内容的特征集合，这样的一个特征就叫做一个shingle，进一步，如果单词片段长度为k，就叫做k-shingle。

另外，还有另一种基于词的shingle，这样的形式被证明在新闻报道近似重复检测中非常有效。对于新闻报道的重复检测，将shingle定义为一个停用词（the/for/a等）加上后续的两个词。

然后通过Jaccard相似度就可以计算两篇文章之间的相似度，这是原始的Shingling算法，k的选择依赖于文档的典型长度以及典型的字符表大小，如果k太小，很有可能会导致所有网页之间都有较高的Jaccard相似度。总之，k应该选择的足够大，以保证任意给定的shingle出现在任意文档中的概率较低。

有人提出了针对原始Shingling算法的优化算法，因为原始Shingling算法对于不同的网页，特征集合的长度也不同，而且往往长度都较大。优化后的Shingling算法不再采用一个哈希函数对所有的单词片段进行哈希，而是随机选择m种哈希函数，对所有的原始单词片段进行哈希，但是我们只保留每种哈希函数所有的结果里面，最小的那个，这样文档就能被转换为固定大小m的最小哈希签名。之后，我们就可以根据Jaccard相似度计算方法，计算最小哈希签名的相似度了。

I-Match算法

I-Match算法是先根据大规模语料进行统计，记录语料中的所有单词，然后去除掉一定比例IDF得分过高以及过低的单词，剩下的作为特征词典。

对于需要去重的网页，采用特征词典过滤，保留在特征词典中出现过的单词，然后对所有单词进行一次哈希，得到一个唯一的数值，通过比较该数值是否相同，来判定两个网页是否近似重复。

我们还可以进一步优化，就是不再只使用一个特征词典，而是使用多个大致相同而又有微小差异的词典，来避免I-Match算法对于增删单词过于敏感的问题。

SimHash算法

SimHash算法可能是目前最优秀的去重算法之一，是局部敏感哈希的一种。

第一步是文档指纹计算，首先从文档内容中抽取一批能表征文档的特征，然后将这些特征映射为固定长度的二进制表示，再利用权值改写特征的二进制向量，形成一个实数向量，之后将所有特征对应的实数向量相加，最后再将实数向量转换为二进制向量，方式为，如果对应位置数字大于0，则设置为1，小于等于0，则设置为0：

比如举个例子（本例不涉及权重）：

• 选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位
• 将simhash的各位初始化为0
• 提取原始文本中的特征，一般采用各种分词的方式。比如对于"the cat sat on the mat"，采用两两分词的方式得到如下结果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
• 使用传统的32位hash函数计算各个word的hashcode，比如："th".hash = -502157718
  ，"he".hash = -369049682，……
• 对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加1；否则减1
• 对最后得到的32位的simhash，如果该位大于1，则设为1；否则设为0

第二步是相似文档查找，SimHash的基本思想是这样的：将索引网页根据文档指纹进行分类，新网页只在部分分组内进行匹配，以减少新文档和索引网页的比较次数。

基本思路如上图所示。先通过分组匹配找到与新网页A/B/C/D块对应位置范围内完全相同的网页，再一一匹配查找是否存在完全相同的文档指纹，当然我们也可以不以完全相同为标准，比如海明距离3以内即可。

搜索引擎缓存机制

搜索引擎通常通过缓存，也即在高速内存硬件设备内开辟一块数据存储区，用来容纳常见的用户查询及搜索结果（或者索引数据及搜索的中间结果），同时采取一定的管理策略来维护存储区内的数据。

搜索引擎缓存系统架构

缓存系统包含两个部分，即缓存存储区及缓存管理策略。缓存存储区是高速内存中的一种数据结构，可以存放某个查询对应的搜索结果，也可以存放搜索中间结果，比如一个查询单词的倒排列表。缓存管理策略又包含两个子系统，即缓存淘汰策略和缓存更新策略。

对于一个优秀的缓存系统来说，应该最大化缓存命中率以及保持缓存内容与索引内容一致。

常见的缓存对象可以是搜索结果，或者查询词汇对应的倒排列表。对于搜索结果型缓存来说，用户查询的响应速度非常快；而倒排列表型缓存的命中率高。有时候我们还可以保存两个经常搭配出现单词的倒排列表的交集，以这种中间结果形式作为缓存内容。

搜索引擎缓存的结构设计可以有多种选择，最常见的是单级缓存，也可以设计为二级甚至是三级缓存结构，比如二级缓存，就可以第一级缓存是搜索结果型缓存，第二级是倒排列表型缓存，这就兼有了响应速度快和命中率高这两个优点。

缓存淘汰策略

缓存淘汰策略和操作系统中的内存管理策略有相似的地方。

动态策略

动态策略的缓存数据完全来自于在线用户查询请求，这种缓存策略的基本思路是：对缓存项保留一个权重值，这个权重值根据查询命中情况动态调整，当缓存已满的情况出现时，优先淘汰权重值最低的那个缓存项。

比如LRU策略，就是最近最少使用策略，淘汰掉最近最少使用的缓存内容。Landlord策略是一种加权缓存策略，计算出缓存项目的性价比，然后如果缓存已满，淘汰掉性价比低的缓存内容。还有SLRU策略，这是对LRU策略的改进，缓存被分为了保护区和非保护区，每个区域的缓存都按使用频度由高到低排序，如果缓存未命中，则放入非保护区高频端（MRU），如果命中了，则放入保护区高频端，这样保护区的记录最少要被访问两次。

混合策略

混合策略是指其缓存数据一方面来自于用户查询，另一方面来自于搜索日志等历史数据。

比如SDC策略：静态动态混合缓存策略（Static and Dynamic Caching），静态缓存就事先根据搜索日志统计出最高频的那部分查询请求，动态就结合LRU或者SLRU这些动态策略来搞。SDC策略是目前效果最好的缓存策略之一。还有AC策略，这里就不详细说了。

缓存更新策略

目前的缓存更新策略可以分为两种：缓存--索引密切耦合策略和缓存--索引非耦合策略。

缓存--索引密切耦合策略就是在索引和缓存之间增加一种直接的变换通知机制，一旦索引内容发生变化则通知系统缓存，然后系统缓存将改变的内容进行更新。

缓存--索引非耦合策略就是给每个缓存项设置一个过期值，随着时间流逝，缓存项会逐渐过期。

当然如果内容更新不频繁，也可以简单的，等到夜深人静的时候统一更新缓存就是了。