文档介绍：... ... 几种搜索引擎算法研究 WWW ( World Wide Web )是一个巨大的,分布全球的信息服务中心,正在以飞快的速度扩展。 1998 年 亿个文档[14] ,每天增加约 1百万的文档[6] ,不到 9个月的时间文档总数就会翻一番[14] 。 WEB 上的文档和传统的文档比较,有很多新的特点,它们是分布的,异构的,无结构或者半结构的,这就对传统信息检索技术提出了新的挑战。传统的 WEB 搜索引擎大多数是基于关键字匹配的,返回的结果是包含查询项的文档,也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性,破坏搜索引擎结果的客观性和准确性。另外,有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面,并且目录大多靠人工维护,主观性强,费用高,更新速度慢[2] 。最近几年,许多研究者发现, 用的话, 可以极大的提高检索结果的质量。基于这种超链分析的思想, Sergey Brin 和 Lawrence Page 在 1998 年提出了 PageRank 算法[1] ,同年 J. Kleinberg 提出了 HITS 算法[5] ,其它一些学者也相继提出了另外的链接分析算法,如 SALSA , PHITS , Bayesian 等算法。这些算法有的已经在实际的系统中实现和使用,并且取得了良好的效果。文章的第 2部分按照时间顺序详细剖析了各种链接分析算法,对不同的算法进行了比较。第 3部分对这些算法做了评价和总结,指出了存在的问题和改进方向。 2. WEB 超链分析算法 Google 和 PageRank 算法搜索引擎 Google 最初是斯坦福大学的博士研究生 Sergey Brin 和 Lawrence Page 实现的一个原型系统[2] , 现在已经发展成为 。 Google 的体系结构类似于传统的搜索引擎,它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理,使最重要的网页出现在结果的最前面。 Google 通过 PageRank 元算法计算出网页的 PageRank 值,从而决定网页在结果集中的出现位置, PageRan k 值越高的网页,在结果中出现的位置越前。 PageRank 算法 PageRank 算法基于下面 2个前提: 前提 1:一个网页被多次引用,则它可能是很重要的;一个网页虽然没有被多次引用,但是被重要的网页引用,则它也可能是很重要的;一个网页的重要性被平均的传递到它所引用的网页。这种重要的网页称为权威( Authoritive )网页。前提 2:假定用户一开始随机的访问网页集合中的一个网页,以后跟随网页的向外链接向前浏览网页, 不回退浏览,浏览下一个网页的概率就是被浏览网页的 PageRank 值。简单 PageRank 算法描述如下: u是一个网页, 是u指向的网页集合, 是指向 u的网页集合, 是u指向外的链接数,显然=||,c是一个用于规范化的因子( Google 通常取 ),(这种表示法也适用于以后介绍的算法)则 u的 Rank 值计算如下: ... ... 这就是算法的形式化描述,也可以用矩阵来描述此算法,设 A为一个方阵,行和列对应网页集的网页。如果网页