"第 25卷第 7期 2005年 7月
文章编号 : 1001 - 9081 (2005) 07 - 1711 - 02
计算机应用 Computer App lications
Vol 25 No. 7 . July 2005
基于 PageRank算法的搜索引擎优化策略
张 ,李志蜀 巍 (四川大学 计算机学院 ,四川 成都 610065 ) ( zhangwei_scu@ hotm ail com ) . 摘 :在介绍 Google等搜索引擎最常用的 PageRank搜索结果排名算法的基础上 ,详细阐述了 要 各种网页链接结构对基于 PageRank算法的网站搜索引擎排名结果可能产生的影响 ,并分析了实际应 用中网站针对 PageRank算法的各种优化策略 ,讨论了各自的优点 。 关键词 : PageRank; Google;链接 中图分类号 : TP391. 3 文献标识码 : A
O pti iz in g stra teg ies for search eng in es ba sed on PageRank a lgor ithm m
ZHANG W ei, L I Zhi2shu
(School of Com pu ter S cience, S ichuan U n iversity, Chengdu S ichuan 610065, Ch ina) Abstract: PageRank algorithm used by Google and many other search engines was introduced. The possible influence that various kinds of W eb linking structures exerted on the ranking results of search engines based on PageRank were analysed. The advantages of various op tim izing strategies of PageRank were discussed. Key words: PageRank; Google; link
最近几年来 , Google已经成为世界范围内使用最为广泛 的搜索引擎之一 。 Google的优点不仅仅在于去除无用的 (广 告 )标语构成单一页面的功能 、 独自的 Cache 系统 、 动态制成 (数千台规模 摘要信息 、 为实现高速检索而设置的分散系统 的 L inux群集器 )等 [ 1 ] ,而最大的优点正是其检索结果的正确 性 ,与其他搜索引擎相比更优的搜索结果排名 ,有利于用户尽 可能快地找到所需的信息 。而研究目前国内互联网网站 ,可 以发现我们在处理网页间的链接结构时 ,往往存在很大的随 意性 。殊不知网页间的链接结构正是决定网站在搜索结果中 排名的重要因素之一 。这种搜索结果排名技术建立在一种针 对 W eb文档的复杂算法上 ,称之为 PageRank算法 。 本文的目的是在对 PageRank算法分析的基础上 ,分析各 类网络链接结构对搜索结果 ( PageRank值 ) 的影响 ,以及由此 产生的搜索引擎优化策略 。
1 PageRank算法
简单的说 , PageRank是代表互联网上某个页面重要性的 一个数值 。 一般搜索引擎将 PageRank值与网页搜索结果相似度共 同作为搜索结果的排序依据 。就像后边即将阐述的一样 ,检 索语句不会呈现在 PageRank 自己的计算式上 。不管得到多 少检索语句 , PageRank 也是一定的 、 文件固有的评分量 ,该值 仅仅依赖于网络的链接结构 。 PageRank算法的具体思路是 ,将某个页面的 PageRank除 以存在于这个页面的正向链接 ,由此得到的值分别和正向链 接所指向的页面的 PageRank相加 ,即得到了被链接的页面的 PageRank。 算法基于“ 从许多优质的网页链接过来的网页 ,必定还 是优质网页 ” 的回归关系 ,来判定所有网页的重要性 。一个 网页的得票越多 ,则认为它的重要性也就越高 。进一步说 ,投
收稿日期 : 2004 - 12 - 28;修订日期 : 2005 - 03 - 16 作者简介 :张巍 ( 1979 - ) ,男 ,天津人 ,硕士研究生 ,主要研究方向 :计算机网络 、 信息系统 ; 李志蜀 ( 1946 - ) ,男 ,重庆人 ,博士生导师 ,主 要研究方向 :计算机网络 、 智能控制.
票网页的重要性也决定着票本身的重要程度 。 计算某个网页 PageRank值时所有的入链接都要考虑在 内 ,页面 A 的 PageRank值计算公式如下 : PR (A ) = ( 1 - d) + d ( PR ( t1) /C ( t1) + … + PR ( tn) /C ( tn) ) 公式中的 PR 代表页面的 PageR ank数值 , t1 ～ tn 代表有 链接指向页面 A 的网页 , C是网页出链接的数量 , d是阻尼系 数 (常数 , Google通常取值 0. 85) 。 由于用户在互联网浏览时 可能不按当前页面中的链接前进 , 而随机跳跃到完全无关页 面 ,所以 d实际上代表的是用户跟随网页链接浏览 ,而不产生 随机跳跃的概率值 。 ( 1 )式是在计算网页 PageRank值的最初公式 。由于至今 Google都没有对外公布它所采用的算法 ,所以可能 Google在使 用时采取了该公式的一些变形 。但这也几乎不影响下面的分 析。 由 ( 1 )式可知 ,计算某个网页的 PageRank值总是依赖于 其他的相关页面 ,所以计算 PageRank值实际上是一个迭代的 过程 ,计算结果的精确程度依赖于初值的选取和迭代的次数 。 对于初值一般取 1,而为了保证实际应用中这个结果总是收 敛的 ,则加入了阻尼系数 d [ 2 ] 。 另外需要说明的是 PR 值与 PageRank值的区别 。安装了 Google工具栏的用户也许看到工具栏上的 PageRank显示条 , 这个工具可以即时地反映出浏览器当前访问的网页在 Google 中的 PageRank值的标记 ,该值在 0至 10范围内变化 。之所以 称之为“ 标记 ” 是因为它并非网页的真实 PageRank值 ,而是真 实值的一个对数指标 ,对数基应该是 5～6范围内的某个数值 。 网页对它的所有出链接的页面进行 PageRank 投票 ” “ 。 由于随机跳转的可能性 ,投出的 PageRank总值比网页本身的 PageRank值稍小 (本身值 3 d ) 。这个值在所有出链接中平 均分配 。因而指向你的网页的页面的 PageRank值固然重要 ,
1712
计算机应用
2005年
但该页面的出链接数量也同样不可忽略 :出链接越多 ,你的网 页得到的 PageRank值就越少 。另外由于 PR 值是 PageRank 真实值的对数指标 ,这意味着一个网页从某个较高的 PR 值 得到提升要比从较低的 PR值上升过来需要更多的 PageRank 值 。在这种情况下 ,一个较多出度的 PR8网页和另一个只有 较少出链接的 PR4页面相比 ,哪个更有效些 ? 这可能依赖于 PR值的对数基和具体的链接情况了 。 需要注意的是当一个网页以“ 投票“ 方式影响其他页面 的 PageRank值 时 , 不 会 减 少 自 身 的 PageRank 值 。这 并 非 PageRank的转移过程 。
可见链接的不好 ,完全可能浪费潜在的 PageRank值 。根 据试验的规律 ,得出针对内部链接结构的第一个优化策略 :一 般来说 ,环形链接或者任意两个页面都有相互链接时能达到 网站 PageRank大值 。
图 2 索引页的 PageRank
2 基于 PageRank的优化策略
假设我们有一个网站 ,很显然将网站的 PageRank平均分 配到各个网页 (如果可能的话 ) 是非常不明智的 ,因为我们不 可能 、 也没有必要使网站的所有网页搜索排名都做到很高 。 如果能将网站的大部分 PageRank值以某种方式导向其中的 一个或少数网页 ,使得它 (们 )的排名大大提高 ,其效果当然 要好于平均分配的结果 。所以下边讨论的重点不在单个网页 的权值 , 而 是 考 虑 整 个 网 站 或 者 说 网 站 中 的 重 要 页 面 的 PageRank值 ,这些页面可能是索引页 、 中心页或是专门为某 些搜索术语优化的页面 。 2. 1 考虑内部链接的影响 网站 PageRank值即为网站内部所有页面 PageRank值的 和 。一个网站的 PageRank最大值等于它的页面数量 。入站 链接可以增加这个最大值 ,而出站链接则能减少之 。网站内 部链接组织不好 ,网站可能会达不到最大的 PageRank值 ,但 是却不可能超过该值 。需要注意 ,虽然增加页面可以增加网 站的 PageRank值 ,但不是随便增加什么页面都能达到效果 。 那些完全相同或几乎相同的页面称为 cookie2cutter, Google认 为是垃圾信息并会引发相应的警报机制使得页面甚至是整个 网站受到处罚 。所以从根本上来说网页要有一定的质量 。 下面分析一下网站内部链接如何影响 PageRank值 。在 这里我们考虑的是一个相对独立的网站 ,入站链接和出站链 接的影响暂不考虑在内 。
图 1 内部链接对 PageRank的影响
假设一个包含三个网页的网站 ,没有外部链接 (图 1 ) 。 ( a ) , ( b ) , ( c )的情况下 ,我们为每个网页分配初值 1,阻尼 在 系数保持与 Google一致 ( 0. 85 ) ,经过迭代收敛后 ,得到三种 情况的 PageRank值如下 : ( a ) : PageRank A = 0. 15, PageRank B = 0. 15, PageRank C = 0. 15; ( b ) : PageRank A = 0. 15, PageRank B = 0. 277 5, PageRank C = 0. 15; ( c) : PageRank A = 1, PageRank B = 1, PageRank C = 1; 网站 ( a ) 的 PageRank 值 为 0. 45, 严 重 浪 费 了 潜 在 的 PageRank值 。 ( b)的情况稍好一些 ,总值 0. 577 5比上一个例 子有所增加 ,但仍然只是最大值的一小部分 (对于该结构存在 的摇摆页情况 ,在这里不作讨论 ) 。在 ( c )的链接结构下 ,网站 达到了 PageRank最大值 ,也可以通过环形结果获得 : A 到 B , B 到 C, C再到 A。同样的情况也可以将页面增加到 3个以上 。
假设把 A 作为索引页 ,有 ( a) , ( b)两种链接结构 ,省略计 算过程后迭代结果如下 : ( a ) : Page A = 1. 459 459, Page B = 0. 770 270 3, Page C = 0. 770 270 3; ( b ) : Page A = 1. 298 245, Page B = 0. 999 999 9, Page C = 0. 701 754 3; 两种结构的总值仍然是 3 (最大值 ) ,所以没有浪费 。但 ( b )的情况下 , A 明显损失了 PageRank,页面 C也损失了一部 分 PageRank,因为 A、 B分享方式替代了 A 独享 , A 通过 A →C 链接反馈回 C的值也就减小 。 所以得 出 第 二 条 优 化 策 略 : 为 了 获 得 索 引 页 的 最 大 PageRank值 ,其他页面应该尽可能减少相互链接 。如果某个 页面链接到的页面有回路链接 ,那么在这个页面上增加一个 新的出链接会导致间接损失一部分的 PageRank值 。如果没 有这样的回路 ,则不会减少 PageRank值 。这在内部链接中并 不十分重要 ,但对发生到网站外的链接时就不一样了 。 可见 ,通过组织内部链接 ,可以将网站的 PageRank值导 向某个选定的页面 。内部链接可以根据网站的 PageRank需 要来组织 ,但必须是 Google认可的页面 。 2. 2 入站链接和出站链接 入站链 接 (由 网 站 外 部 进 入 的 链 接 ) 是 增 加 网 站 PageRank值 的 方 式 之 一 。入 站 链 接 来 自 何 处 并 不 重 要 , Google认为只要网站管理员没有对链入网站的其他网站产生 控制 ,就不会因为这种链接做出处罚 。 链接页的 PageRank值很重要 ,但同时出链接的数量也相 当关键 。例如 :如果是一个 PageRank值为 2的网页的唯一出 链接 ,将得到 0. 15 + 0. 85 ( 2 /1 ) = 1. 85的值 ;而一个 100个出 链接的 PageRank 8 网页 ,得到的是 0. 15 + 0. 85 ( 7 /100 ) = 0. 209 5。 很明显 , PR2 链接更有效 。一旦有 PageRank值注入 到网站中 ,计算将需要重新进行 。某些页面的值增加 ,某些保 持不变 ,这依赖于内部链接结构 ,但肯定不会有页面会损失 PageRank值 。 入站链接指向你试图导向的重要页面更有好处 , 如果 PageRank注入到其他页 ,则会因为内部链接分散到网站中 。 索引页也会得到提升 ,但不如直接链接提升得多 。直接得到 入站链接的页面得到的值最大 。 第三条优化策略 :将网站索引页作为引入入站链接的最 佳目标 。 出站链接会导致网站 PageRank值的消耗 。为了抵消这 种消耗 ,需要确保链接是互给的 。互惠链接可能得到也可能 损失 PageRank值 ,所以交换链接时需要特别小心 。 当 PageRank值随着指向另一个网站的链接而引出时 ,内 部链接的所有页面都将受到影响 。虽然具体的 PageRank值 变化情况依赖于链接结构 ,但一般来说给出链接的网页往往 是损失 PageRank值最大的 ,因此得出第四条优化策略 :出站 (下转第 1718页 )
1718
计算机应用
2005年
均仅有两个字段 ,即 HZ和 SY 字段 ,字段 HZ存放单个汉 M 字 ,字段 SY 存放对应汉字的首音码 。在表 GBKSY M M1. DB 中 ,字段 SY 宽度为 1个字符即可 ,在表 GBKSY M M2. DB 中 , 该字段宽度为 3个字符 。表 GBKSY M2. DB 的存储记录如表
4所示 ,字段 SY 中两首音码中间带“3 ” M ,表示对应汉字的
使用上述分析生成的首音码表 ,并应用如图 1所示的转换 算法就可以方便地将输入的姓名自动转换成其对应的首音码 。 图 1 中 的 码 表 1 和 码 表 2 分 别 指 表 GBKSY M1. DB 和 表 GBKSY M2. DB。由于表 GBKSY M2. DB 中汉字很少 ,为了提高 查询速度 ,先查询该表 ,若找不到再查询表 GBKSY M1. DB。
首音码不能自动确定 ,需要人工选择 。 由于 G BK中 G B汉字使用频度较高 ,为了提高查询速度 ,在 表G BKSY DB中 G M1. B汉字排序在前 ,扩充汉字排序在后。
5 结语
通过对 64 000多个无重复姓名进行测试 ,直接使用 GBK 拼音表首音重码选择率为 20% ,去掉首音相同汉字后首音重 码选择率降为 14. 4% ,而采用本文设计的码表及转换算法首 音重码选择率降至 3. 7%。可见 ,使用本码表及转换算法可 以大幅度降低首音重码选择率 ,显著提高转换效率 。该码表 及算法已经在温州职业技术学院分院图书馆 、 温州菜篮子集 团蔬菜种子批发公司中得到应用 ,效果很好 。若对偶尔遇到 的重码选择感到不便 ,也可以去掉图 1 中的“ 人工选择首音 重码 ” 功能 ,由系统自动组合各首音重码 ,就可以实现全自动 转换 。但这将增加一定的数据冗余 ,若想要去掉冗余数据 ,可 以在转换后再进行人工编辑 。当然 ,该码表可能忽略了一些 汉字的首音重码 ,在使用时只要按上述规则添加即可 。虽然 本文仅对用作姓名的汉字的音码重码进行分析 ,但其分析方 法也可以为解决汉字的其他方面 (如药名 、 书名 、 歌曲名等 ) 的首音重码问题提供参考 。 参考文献 :
[1 ] 李琦. 基于汉字拼音首字母的信息查询法的分析与实现 [J ]. 四
4 汉字型姓名智能转换为首音码的实现
川轻化工学院学报 , 2003, 4 (3) : 71 - 74.
[2 ] 张春生 ,廉洁 ,包图雅. 拼音缩写码在医药行业管理中的应用 [J ]. 内蒙古民族大学学报 , 2003, 18 (2) : 121 - 122. [3 ] GBK,汉字内码扩展规范 [ S ], 1995. [4 ] (宋 )佚名 ,王应麟 , [梁 ]周兴嗣 , (清 )李毓秀 ,木子. 百家姓 三
字经 千字文 弟子规 [M ]. 乌鲁木齐 :新疆青少年出版社 , 1996. 图 1 汉字型姓名智能转换为首音码的算法流程
[5 ] 金山词霸 2005专业版 [CP /DK ]. 金山公司 , 2004.
(上接第 1712页 )
链接放在 PageRank较低的页面 ,造成的 PageRank损失较小 。 任何一个网站都几乎不可能没有出站链接 ,但不巧的是 ,所有 的 正常 ” “ 链接都会泄漏 PageRank值。但还有些“ 特别 ” 的链接方 式不用泄漏。PageRank泄漏与否依赖于 Google能否识别出链接 , 这样可以使用 Google不能识别或是不考虑的链接 ,包括表单处理 (for action)和包含 JavaScrip t代码的链接 [3 ] 。 m 表单的 action属性不一定是处理表单脚本的 url,它可以指向 任何网站的任何一个页面。 例子 :
< form name = "myfor " action = m " http: / / cs scu. edu. cn / somepage. htm l" > . < a href = " javascrip t: document myfor subm it () " > . m. 四川大学计算机学院 < / a >
此外 , action 属 性 甚 至 可 以 不 必 位 于 form 表 单 而 在 JavaScrip t代码中 ,而 JavaScrip t代码可以位于存储路径的 js 目录下 ,而该目录一般 Google的 sp ider程序都不访问 。
同时 ,由于 PageRank算法的检索无关性 ,也可能导致一 些不利的结果 ,例如对一些词汇在特定的上下文中有特定的 含义 ,或是一些专业词汇 ,仅仅依靠 PageRank排名的结果可 能不太令人满意 ,比如同样是查找“ 结构 ” 这个词 ,在建筑学 的上下文中 ,和芯片制造的上下文中 ,用户希望得到的检索结 果必然不尽相同 。但由于 PageRank是网页的固定属性 ,可能 就达不到期望的效果了 。如果将整个互联网看成一个维度 , 那么 PageRank则是该维度上的一个矢量 ,针对以上的缺陷 , 可以考虑建立这类矢量的一个矢量集 。换句话说 ,可以针对 某些指定的主题词计算出多个 PageRank值 ,然后根据检索内 容匹配相应主题词的网页 PageRank值 [ 4 ] 。当然 ,在结果排序 时用到的 PageRank值仍然是唯一的 。这种改进在检索期间 的消耗上有所增加 ,但在结果排序上却有大大提高 。 参考文献 :
[1 ] BR I S, PAGE L. The anatomy of a large2scale hypertextual web N search engine[A ]. Proceedings of the Seventh International World W ide W eb Conference[C ], 1998. [2 ] BABA H , 馬場肇. Google の秘密 - PageRank
3 总结及 PageRank改进
PageRank值由网络链接结构决定 ,与具体的检索内容无 关 ,因而检索期间消耗很小 ,优于早期的 H ITS算法 。在不考 虑网页内容具体需要的情况下 ,提出的优化策略有利于提高 网站在基于 PageRank算法排名的搜索引擎搜索结果中的排 名 。这种效应也许短时间内尚不明显 ,但随着页面的增加和 网站间链接的逐渐增多 ,最终的效果还是可观的 。
底解説 [ EB /
OL ].
http: / /www. kusastro. kyoto2u. ac. jp / ～ baba /wais/pager2
ank. htm l, 2003. [3 ] JEH G, W I OM J. Scaling personalized web search [R ]. Stanford D University, 2002. [4 ] HAVEL I ALA TH. Top ic2Sensitive PageRank[A ]. Proceedings of W the Eleventh International World W ide W eb Conference[C ], 2002.
..."
|
You need to upgrade your Flash Player , or try to enable javascript in order see this document properly.
|
|
Comments
