内网搜索引擎算法的分析与研究

刘兴强　杨桃　范云琳　陈婷婷　闫自金　宋绍云

摘要：近年来，Intranet不断飞速发展，导致信息量趋于庞大。于是如何让用户查找到自己想要的信息成为Intranet搜索引擎的一个难题。关于这个问题，它将对几种经典的Intranet搜索排序算法进行分析、比较。希望在以后的开发中可以以它为参照，进行相关算法的改进，尽可能的让算法更接近完美，使搜索结果更能符合用户的需求。

关键词：搜索引擎；算法；原理；特点；PageRank；HITS

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2014）01-0120-03

1 概述

随着社会的发展，各种信息的飞速增长，搜索引擎成为了人们查找信息的首选工具。搜索引擎的研究，国外比中国要早近10年，但国内还是陆续涌现出优秀的搜索引擎，如：百度、中搜。伴随着搜索技术的成熟，Intranet搜索引擎将成为获取信息、掌握知识的利器。而面对云信息时代的到来，传统的搜索引擎提供的服务已不能满足人们日益增长的对个性化服务的需要。因此，搜索引擎还将有较大的发展和进步空间，检索功能将更趋向于集成化和更具亲和力、更显人性化。

算法是搜索引擎的灵魂，要改善搜索服务实质上就是改进算法。要想在现有的算法基础上进一步改进，就要先了解它。该文的先对两种经典算法PageRank和HITS进行了分析和比较，并指出它们各自的优缺点。还对这两种算法的延伸算法Hilltop、SALSA进行了介绍，他们融合了HITS和PageRank两个算法的基本思想。最后指出了当前算法仍有的问题和改进方向。

2 两种经典的算法

PageRank算法和HITS算法都是比较经典的搜索引擎算法。许多算法都是在它们的基础上进行改进的，是搜索引擎算法分析的两个最基础且最重要的算法。

2.1 PageRank算法

PageRank算法是在1998年由Sergey Brin和Lawrence Page提出的[1]。该算法是从“被许多好的网页引用的网页一定是好网页”的关系出发，来确定一个网页的质量。当一个网页被很多其他网页包含，那么该网页很可能是一个高质量网页；然而假如有一个网页它的链接没有被许多网页页所包含，而它却拥有一个优质网页的链接指向，则它或许也是高质量网页； 一个网页的重要性值被平均分配并传递到它所引用的所有网页中。当用户随机的浏览当前网页集以外的某网页时，将要访问的网页的可能性值等于被访问网页的PageRank值。

PageRank算法原理：首先根据网页之间链接的引用关系建立关系图，并给最底层的每个页面赋予同样的PageRank初始值；再根据网页间的引用关系把它的值平均分配给它引用了的所有页面；最后，将各个页面自己所拥有的所有通过引用传过来的值求和就是它的PageRank值。通过这样层层计算，所有页面最终求得它的PageRank值。根据每一遍的计算跟进，各个网页不断更新自己的PageRank值。如图1是一个简单的计算实例。

圖1 PageRank计算实例

由图可得：PageRank（14） = PageRank（12）/2 + PageRank（24）/3 = 6 + 8 = 14

PageRank算法特点：它是一个与查询主题不相关的离线求值算法，全部PageRank值在查询前就预先计算获得；极大的减少了有搜索到达时才来查询的计算量，使得搜索更迅速。但是这种方法忽略了结果和用户查询相关与否，采用了平均分配权值反而对一些新的网页存在不公平现象。这导致旧网页权值高、查询到无关结果等。

2.2 HITS算法

HITS（Hyperlink-Induced Topic Search）算法是由康奈尔大学（Cornell University）的Jon Kleinberg博士于1997年首次提出的。该算法将网页分为两种类型：Authority页面和Hub页面。Authority页面是指某个方面或主题非常相关的优质网页；Hub 页面是指引用了许多优质页面的网页，例如：hao123等。HITS算法认为好的Hub页面会指向很多好的Authority页面；当然好的Authority页面也会有许多Hub页面所指向[3]。

HITS算法只计算与主题比较接近的页面，它由一个页面的入链数量来计算它的Authority权值，再根据该页面的出链数量计算它的Hub权值。通过迭代计算和定义的收敛闭值不断的对Authority权值和Hub权值进行更新，直至结果收敛[2]。最后找出一定数量Authority权值和Hub权值都比较高的页面作为最佳页面集。

算法原理：

1） 获取根集：用传统的搜索引擎对用户搜索的关键词进行搜索，获得与主题相关的网页，从这些网页中拿出一些权威性比较高的网页作为根集，且根集要比较小；2） 对根集进行扩展：在根集中加入它的集合内页面的入链页面和出链页面，形成一个更大的集合。

3） 获取最佳页面集合：以扩展集合中的Hub 网页看成一个顶点集Vl ， 权威网页看成顶点集V2， Vl 中的网页到V2中的网页的引用关系为边集E， 形成一个二分有向图SG= （V1， V2， E）。如图2所示：

图2 V1和V2的关系图

对于集合V1中的任意一个网页来说，如果它指向的高质量（权威性高的）页面越多，那么它的中心性值越大；而对V2中的页面来说，如果它被好的Hub页面引用的越多，则它的权威性值也越大。然后根据一个页面的权威性权值等于所有指向它的页面的中心性权值之和，中心性权值等于它指向的所有页面的权威性权值之和。通过迭代计算和不断的对权威性值和中心性值进行更新，直至结果收敛。最后，根据各页面最终的权威性值和中心性值进行综合分析，并从扩展集合中得到最佳页面。

HITS算法特点：

HITS算法能很好地对网络结构进行描述，它只是对网页的一个小集合进行权值计算，所以需要的时间很少。但该算法必须在接收到用户查询后才能根据相关主题进行计算，而且需要进行很多次迭代计算才能获得最终结果，使得计算效率较低。当“扩充网页集合”内有网页增减或者链接关系改变时，HITS算法的排名结果就会有非常大的改变，易受“垃圾链接”的影响使得评分异常，出现主题漂移、网页作弊。

2.3 HITS算法与PageRank算法比较

根据以上对HITS算法和PageRank算法的思想、原理进行分析，对这两种算法一些特点的比较如表1。

3 改进算法

3.1 Hilltop算法

1） 算法基本思想

Hilltop算法是由Krishna Baharat 在2000年左右研究的，于2001年申请专利，后来他加入了Google并授权给Google使用的。Hilltop算法不仅采纳了PageRank算法使用某个页面入链的数量以及质量来计算该页面的权值的方法，而且还吸收了HITS算法中根据与用户查询主题的相关性来获得高质量页面子集的思想。此算法认为只有与用户搜索主题相同的页面，才是用户真正需要的。因此，与主题相关的页面之间的链接比和主题不相关的页面之间的链接拥有更大的贡献值。

2） Hilltop 算法的过程

通过计算得到一个与用户搜索的主题最为紧密关联的专家页面列表（专家页面：它的全部出链数大于s且指向s个不是同一组织或其所有者之间没有关系的网站页面）；

由列表中专家页面的出链找到结果页面；

根据引用结果页面的不是同一组织或其所有者之间没有关系的网站页面的数量和主题相关度情况来计算它的重要性权值，并将结果页面按重要性值的高低情况进行排序。

3） 算法特点

HillTop算法是一种客观衡量网页质量的排序方法，查询与语言、内容无关。在Hilltop算法中应用专家页面，该页面的搜索和确定对算法起关键作用，较好的提高了搜索结果的质量。然而专家页面的质量和公平性在一定程度上难以保证，该算法降低了人性操作的排序影响，并忽略了大多数非专家页面对它的影响。并且HillTop算法没有考虑搜索结果中存在的问题，当计算中没有找到足够多的专家页面，则它没有结果返回。

3.2 SALSA算法

SALSA算法由以色列学者R.Lempel和S.Moran于2000年在第9届国际互联网大会上提出，其英文全称为Stochastic Approach for Link-Structure Analysis[3]。

1） 算法基本思想

SALSA算法保留了PageRank 的随机访问和HITS 中与查询主题相关的特点，它同样把网页分为Authority和Hub的网页集合，但取消了Authority与Hub之间的相互贡献评分的关系。SALSA算法不仅考虑了一般的用户随机向前浏览的习惯，而且也加入了用户有时候会回退浏览网页的事实，让算法更具健壮性。该算法在应用中可以大致划分为与HITS算法基本相同確定计算对象集合和像PageRank算法那样采用随机访问的链接关系传播过程两个阶段。

2） 算法特点

SALSA 算法摈弃了HITS 中相互加强的迭代过程，节省了资源、减小了计算量，并且它在扩展根集时忽略了一些无效的链接（如：广告和赞助商链接等），在一定程度上解决了主题漂移问题使查找更为精确。但SALSA算法在求网页的Authority值时，没有考虑直接相邻网页集以外的其它网页对它的影响。

4 结论

基于对以上几种搜索引擎算法的分析，不管多么经典的算法目前都还是不尽完美，它始终处在一个长期发展的过程中。当然，我们可以从多种算法中取长补短以获得更好的搜索效果，也有很多人这样做了。但是，要想在这方面得到突破性的改进，开发

者应该多关注一下用户或者从用户的角度出发去发现一些存在的问题并想办法解决。期待在不久的将来内网搜索引擎算法方面会有更大的改善，以应对云时代的到来，达到更高标准的用户需求。

参考文献：

[1] 韩金华.搜索引擎算法综述[J].中国学术期刊电子出版社，2011.

[2] 陈凯.搜索引擎有关排序算法研究[D].武汉理工大学，2011.5.

[3] 张俊林.这就是搜索引擎：核心技术详解[M].电子工业出版社，2012.1.

[4] 邓仲华，李志芳，赵又霖.基于链接的网页排序算法研究分析[J].中国学术期刊电子出版社，2010.