专业搜索引擎的排序算法研究

1、南京师范大学硕士学位论文专业搜索引擎的排序算法研究姓名：徐金雷申请学位级别：硕士专业：教育技术学指导教师：杨晓江20070508摘要搜索引擎是一项崭新而深奥的技术，包括分词、文档分类、特征提取、索引、存储、检索和排序等一系列技术环节。在这些环节中，排序是和用户最相关的一个关键环节，当用户输入关键词检索时，如果搜索引擎已经将用户希望的网页检索出来了，但是却将这些网页捧在若干页后，则用户几乎不可能浏览到该网页，这样大大降低了用户的满意度。本文主要研究了搜索引擎的排序问题。本文首先通过文献调研，研究通用搜索引擎排序的一般方法，如词频和位置加权算法、DirectHit算法、Alexa的网站排名算法、G

2、oogle的排序算法等，从这些方法中借鉴出通用搜索引擎排序的重要因素，分析了这些因素的求解方法，通过实验对可能的因素进行了求解。此外，鉴于基础教育搜索引擎是一个专业的搜索引擎，笔者研究发现：使用专业搜索引擎的用户有特定的专业背景，对排序的期望值更高，希望检索山的页面都是很相关的。通搜索引擎对某个关键词检索出的页面是分布于多个主题的，不符合用户的需求。笔者提出了主题相关度因素，对每个页面计算和主题相关韵程度，再与通用搜索引擎排序的若干因素合理整合，使专业搜索引擎的排序更加符合用户的需要。本文在基础教育搜索引擎上进行了排序实验，实验证明，这种排序策略是合理可行的。本文在研究排序的同时，对搜索引擎的

3、用户评价进行了大量的调研，对几大搜索引擎的性能、检索方式、检索结果和用户负担等方面进行了比较研究。以期对我们的项目研究有所借鉴。关键词：专业搜索引擎，排序算法，主题相关度，基础教育，用户评价IllAbstractSearchengineitselfisanewandesoterictechnique，includingsometechnical aspects like segmentation，document classify， feature extraction，indexing，storage，retrieval and rankingIn these areas， ranking

4、is most relevant to usersWhen users input a keyword，if search engine locates the web pages users wanted to bottom pages，it is almost impossible for the user to browse through the website，thus greatly reducing the users sati8factionThis paper is mainly on the search engine ranking problemWe first stu

5、dy the literature，and research on the common ranking algorithms of universal search engines， such as the word frequency and location algorithm,Direct Hit algorithm，Alexa website ranking algorithm，Googles ranking algorithmWe research on the important factors of the ranking of search engineThrough exp

6、eriments we work out some possible factorsMoreover，basic education search engine is a specific searchengineThe users of specific search engines have specific backgrounds， hoping the retrieved pages are relatedIn universal search enginea keyword search on the web page is located in a variety of topic

7、sWe put topic relativity factor and calculate itWe combine this factor with universal search engineIt can help the ranking of professional search engine meet usersneedThe experiments show that this ranking strategy is reasonable and feasibleBased on the research of ranking at the same time，we do lot

8、s of research on the usersevaluation of search engineAnd comparative study on several major search engines such as the performance，retrieving means，and search results，hoping to promote our research proj ectsKeywords：Specific Search Engine，Ranking Algorithm，Topic Relativity， Basic Education，Users Eva

9、lua七ion学位论文独创性声明本人郑重声明：1、坚持以“求实、创新”的科学精神从事研究工作。2、本论文是我个人在导师指导下进行的研究工作和取得的研究成果。3、本论文中除引文外，所有实验、数据和有关材料均是真实的。4、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经发表或撰写过的研究成果。5、其他同志对木研究所做的贡献均已在论文中作了声明并表示了谢意。作者签名：日期：至臣i!：墨学位论文使用授权声明本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆

10、被查阅；有权将学位论文的内容编入有关数据库进行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。作者签名：日期：芝1歪2：!业：第1章前言11专业搜索引擎排序算法的研究背景111搜索引擎的发展1、搜索引擎的诞生与发展搜索引擎1作为网络信息搜寻的工具，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理。并为用户提供检索服务。所有搜索引擎的祖先2，是1990年由Montreal的McGillulliveBity学生AlEmtage、PeterDeutsch、BillWheelan发明的Archie(ArchieFAQ)。当时WoddWideWeb还朱

11、出现。Archie是第一个自动索引互联网上匿名FrP网站文件的程序，但它还不是真正的搜索引擎。Archie是一个可搜索的FTP文件名列表，用户必须输入精确的文件名搜索，然后Arehie会a告诉_|IJ户哪一个FTP地址可以下载该文件由于专门用于检索信息的Robot程序像蜘蛛(spider)-样在网络间爬来爬去，因此，搜索引擎的Robot程序被称为spider(Spider FAQ)程序。tH=界上第一个Spider样序，是MIT Matthew Gray的World砸de Web Wanderer，川丁追踪互联网发展规模。刚开始它只用来统计互联网上的服务器数量，后来则发展为也能够捕获网址(UR

12、L)。1993年2月，6个Stanford(斯坦福)大学生的想法是分析字词关系，以对互联网上的大量信息作更有效的检索。这就是Excite。后来曾以概念搜索闻名，2002年5月，被Infospace收购的Exdte停止自己的搜索引擎，改用元搜索引擎Dogpile。1994年4月，Stanford两名博士生，美籍华AJenyYang(杨致远)llDavid Filo共同创办了Yahoo。随着访问量和收录链接数的增长，YahooI|录开始支持简单的数据库搜索。因为Yahoo的数据是手工输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。搜索效率明显提高。(Yahoo以后陆续使用Altav

13、ista、lnktomi、G009le提供搜索引擎服务)Info-ek(SteveKitschAnnounFreeDemosOfthelnfoseekSearchEngine)是另一个重要的搜索引擎，虽然公司声称1994年1月已创立，但直到年底它的搜索引擎才与公众见面。起初，Infoseek只是一个不起眼的搜索引擎，它沿袭Yahoo,释lLycos的概念，并没有什么独特的革新。但是它的发展史和后来受到的众口称赞证明，起初第一个登台并不总是很重要Infoseek友善的片j户界面、大量附加服务(such asUPStracking，News，adirectory,andthelike)使它声望日隆

14、。而1995年12月与Netscape的战略性协议，使它成为个强势搜索引擎：当用户点i蕾Netscape浏览器上的搜索按钮时，弹出lnfoseek的搜索服务，而此前由Yahoo提供该服务31995年，一种新的搜索引擎形式出现了元搜索引擎(AMeta SearchEngineRoundup)。用户只需提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查洵结果，集中起来处理后再返同给用户。DEC的AlmVism(2001年夏季起部分网友需通过p_xy访问，无p-roxy可tLJqbseach单选altavista搜索，只能显示第一页搜索结果

15、)是一个迟到者，1995年12月才登场亮相(AltaVistaPublic Beta Press Release)。但是，大量的创新功能使它迅速剑达当时搜索引擎的顶峰。林瑞宜陈榕虎搜索引擎新研究情报探索2005年5月2http：www,foshanwcomscoseose07htm3 Infoseek后来曾以相关性闻名，2001年2月，Infoseek停止了自己的搜索引辇，开始改用Overture的搜索结果AJtavista最突出的优势是它的速度。而A】tavism的另一些新功能，则永远改变了搜索引擎的定义AltaVmta是第一个支持自然语言搜索的搜索引擎，AltaVista是第一个实现高级搜

16、索语法的搜索引擎(如AND，OR,NOT等)用户可以用Al蝴sta搜索Newsgroups(新闻组)的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索Titles、搜索Java applets，搜索ActiveXobjects。AltaVmta也声称是第一个支持用户自己向网页索引库提交或删除URL的搜索引擎。并能在244,时内上线AltaVista最有趣的新功能之一，是搜索有链接指向某个URL的所有网站。1998年lO月之前，Google只是Smfd大学的一个小项目BackRub。1995年博士生LarryPage开始学习搜索引擎设计，于1997年9月15日注册Tgooglee,on

17、l的域名，1997年底，在SemeyBrin币lSeott Hassan、Alan Sterberg的共同参与下，BachRub开始提供Demo。1999年2月，Google完成了从Alpha版到Beta舨的蜕变。ch酒e公司则把1998年9上J27EI认作自己的生日。Google在Pagerank、动态摘要、网页快照、DailyRcfiesh、多文档格式支持、地图股票词典寻人等集成搜索、多语言支持、用户界面等功能上的革新，像Altavista-样，再一次永远改变了搜索引擎的定义。2、中文搜索引擎的发展七人天网是国家“九五”重点科技攻关项目“中文编码和分布式中英文信息发现”的研究成果，由北人计

18、算机系网络与分布式系统研究室开发，于1997年lO月29E1正式在CERNET上提供服务。2000年初成立天网搜索引擎新课题组，由国家973重点基础研究发展规划项目基金资助开发，收录网页约6000万，利埘教育网优势，有强人的FTP搜索功能。2000年1月，超链分析专利发明人、前hfoscek资深工程师李彦宏与好友徐勇(加州伯克利分校博士)在北京中关村创立了百度(Baidu)公司。2001年8月发布BaiduCorn搜索引擎Beta版(此前Baidu只为其它门户网站如搜狐新浪Tom等提供搜索引擎)，2001年10月22日正式发布Baidu搜索引擎。Baidu虽然只提供中文搜索，但目前收录中文网页

19、超过9000万，可能是最大的的中文数据库。Baidu搜索引擎的其它特色包括：网页快照、网页预览预览全部网页、相关搜索词、错别字纠正提示、新闻搜索，Hash搜索、信息快递搜索。2002年3月闪电计划(Blitzen Project)开始后，技术升级明显加快112搜索引擎的技术架构搜索引擎的原理，可以看做三步：从互联网上抓取网页一建立索引数据库一在索引数据库中搜索排序。从互联网上抓取网页国l则能够从互联网上自动收集网页的Spider系统程序，自动访问互联网，并沿着任何网页中的所有URL爬剑其它网页，重复这过程，并把爬过的所有网页收集回来。建立索引数据库由分折索引系统程序对收集回来的网页进行分析，提

20、取相关网页信息(包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其它网页的链接关系等)，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度(或重要性)，然后用这些相关信息建立网页索引数据库。在索引数据库中搜索排序一当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相关网页针对该关键词的相关度早己算好，所以只需按照现成的相关度数值排序。相关度越高，排名越靠前。最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。113基础教育搜索引擎的应运而生及系

21、统架构自从面向2l世纪教育振兴行动计划首次明确将“教育信息化”确定为教育发展的2重要主题并将教育资源建设定为重点，各企业、学校、部门纷纷投入大量的人力、物力建设教育资源。到今天分布在全国各地服务器的基础教育资源是无法统计的，而且它每天都像滚雪球一样在不断的增长2001年6月教育部颁布基础教育课程改革纲要(试行)，提出了基础教育课程改革的具体目标，其中之一是培养学生搜集和处理信息的能力、获取新知识的能力、分析和解决问题的能力以及交流与合作的能力。基础教育专业搜索引擎(以下简称BERSE)作为基础教育领域的专业搜索引擎的诞生也就不足为怪了，它的诞生是基础教育资源建设和基础教育改革发展的必然结果，也

22、是广大从事基础教育研究工作、教学工作人员离不开的工具，对学生来说也是培养他们rr技能的平台之一。图卜1基础教育搜索引擎的系统架构图BERSE系统的结构如图1-1所示，本系统主要包括控制器、网络蜘蛛、资源分类器、索引器，商业服务、检索器和相关数据库等主要模块。这些模块是互相联系的，它fJ的功能划分并不是完全独立的，相互间存在着内在联系。它们的主要功能描述如下：控制器：控制系统良好运行的各项参数，如服务器分配、数据调度、负载平衡等。网络蜘蛛：它是一个Web Crawler，它负责不问断地从互联网上搜集、更新基础教育资源并存储剑文档下载库中。分类器、索引器：对网络蜘蛛搜集剑的资源进行处理分类，并建立

23、索引存储到索引数据库中商业服务；为基础教育资源开发商提供产品推介平台，同时也是本系统实现其商业利润的一个模块。检索器：为本系统的用户提供基础教育资源搜索、导航服务。114捧序在搜索引擎中的作用和地位当前互联网已经达到数十亿网页的规模，并且正在以海量的速度增氏，由于其规模如此3之庞大，用户在查询资料的时候，经常面对搜索引擎返回的成千上万的网页链接，而用户点击这些链接后发现如下问题：1)某些网页的确包含用户输入的搜索词，可是内容却并非是相关的；2)某些网页早已更新，用户查询的主题甚至已不存在；3)某些网页的信息已十分陈旧失去意义；4)某些网页确有用户所需要的资料，但是质量不高，或朱达到用户所期望的

24、层次。为使所点击的最初若干链接能满足需要，因此搜索引擎应尽可能在不遗漏相关网页的基础上，将最恰当的最可信的网页链接放在返回结果的最前面。因此，搜索引擎的排序算法，成为搜索引擎最核心和关键的技术之一，也是现今网络服务研究的热点之一从用户角度来说，如果搜索引擎的排序结果不合理，那么他也不愿意使用该搜索引擎。一个搜索引擎的排序直接决定用户使用的满意度。襄11中国搜索引擎用户不满意因素及比倒不满意因素所占比饲搜索结果重复50*搜索结果排序欠佳43搜索结果太杂乱37搜索结果不合时宜36广告太多35根据某搜索引擎2000年4月的近50万的_Hj户点击情况的查询日忐所作的一项统计表12用户在前5页的翻页统计

25、页号l2345百分比47薯121l冀714510317可见，用户绝大部分的浏览集中在前几页，往后的页面被用户浏览到的几率越米越小，有的页面几乎不被用户浏览到。115专业搜索引擎捧序的研究现状国内该方面的研究比较少，主要集中在对某些著名搜索引擎的研究上，如对Google的研究。发表的论文数量并不多，并且大部分是介智性的，实刖性不强。但是近几年国内搜索引擎的发展速度加快，有代表性的是百度和天网，其中百度关于排序的研究成果没有公开发表，天网的最新专著搜索引擎一技术、原理与系统公开了其捧序的部分信息国外这方面的研究成果相对要多，具有代表性的是对Google捧序算法的研究，其中尤以对PageRank及其

26、HITS相关研究居多。比较成熟的算法有：1)词频和位置加权排序算法2)Direct Hit算法3)Alexa的网站排名算法4)Google的排序算法5)开源搜索引擎如lucene的排序思想搜索引擎排序算法作为商业机密不作公开，因为一旦公开，则必有一些网站会针对其中的一些因素，在自己的网站上进行加强，从而获得较高的捧名，打乱互联网的公平竞争原则所以，一般的研究主要是基于某些搜索引擎搜索现状的推理和猜测。近些年，一个新兴的高级技术行业SEO(搜索引擎优化)发展很快，SEO主要为企业4网站提供服务，目的是通过一些网络技术手段使企业网站提高在Alexa或Google等搜索引擎中的捧名，提升用户点击的几

27、率，获得更多的商机。通过SEO手段提高排名要缴纳一定的费用。一般捧名越前缴费越多然而SEO获得捧名的手段有时候是不合法不公平的，所以一些大的搜索引擎如Alexa和Google等，对这类通过不正当手段获得高排名的网站会不定期进行检查，采取严厉的惩罚措施甚至封杀。SEO和搜索引擎之间一直不问断地进行斗争116专业搜索引擎捧序的面临的主要问题1、从用户角度在通用搜索引擎中，为了使用户能比较快捷地得到想要的资源，排序环节起到了很重要的作用。Google之所以能成为全球搜索第一品牌，其优秀的排序结果是决定性因素之一在中国搜索引擎明户所不满意的因素调查如下：1)搜索结果的重复502)排序结果欠佳433)搜

28、索结果太杂乱374)搜索结果不合时宜365)广告过多35用户对排序的结果不满意占了很大的比重。刚户认为，排序在前的网站往往不是最新的；前面的网页内容不是自己最需要的，很多是对白己没有刚的信息；有时候为了找到一个有用的网页需要往后翻好几页等。2、从Web资源本身就我们的项目基础教育资源搜索引擎来说，在开放的网络教育资源环境中，利刚搜索引擎查找所需的Web资源，往往不能很容易的得到所需的资源，这是因为：1)教育资源的文档生存周期比较长，更新比较慢；2)教育领域学科较多，很多学科之间存在交义现象；3)数据量大，即便最符合用户意图的页面已经被检索出来了，但是很难捧到最前面。在基础教育资源搜索引擎系统的

29、背景下，对排序有特定的要求：基础教育资源搜索引擎是一个专业搜索引擎，通用搜索引擎的排序策略在一定程度上不能满足其需要。通用搜索引擎的排序主要考虑词频和网页权威性等。而BERSE不能仅仅沿用通用搜索引擎的排序思想，必须设计符合自身专业搜索引擎的排序策略。这是在文本分类基础之上的又一次资源提炼。现有待检索的文档资源都是经过文档分类程序处理的，绝大部分资源是符合基础教育特性的。但是总有少数和基础教育的联系不紧密，排序程序在呈现排序结果时尽量将这些文档排后。117专业搜索引擎捧序研究的意义笔者参与开发的基础教育资源搜索引擎是一个典型的专业搜索引擎，组织索引了大量的网络教育资源，是基础教育领域的信息查询

30、工具之一。面向的用户是从事基础教育的老师、教研工作者、家长和中小学学生，这些用户使用该搜索引擎的目的性很强。如果该搜索引擎不能将非常重要的资源检索出来并排到前面，将极大地影响该搜索引擎的用户满意度。因此，如何设计基础资源的搜索引擎的排序就显得尤为重要。在通用搜索引擎中键入检索词，得到的输出结果是多方面的，包含多个主题和领域。虽然众多网络用户的需求是多方面的，但是对某个具体身份的_H户而言，他很可能需要特定的输出结果，通用搜索引擎的排序结果往往不能满足特定用户对特定专题的需求。以下分别从5三个例子来看：饲一：一个中学语文老师想查找一些鲁迅的文章，输入关键词“鲁迅”进行检索，他想要的是关于鲁迅的一

31、些生平或者作品，但是检索结果如图1-2图12。鲁迅”在百度中的检索结果首页从检索结果可以看出，用户在首页就很难直接找到跟鲁迅相关的作品，如“鲁迅美术学院”，该页最下端还有“鲁迅教育集团”等不相关的信息。例二：物理老师检索“杠杆”，希望能找剑和物理教学相关的辅助材料。百度中的检索结果如图l-3。6图1-3“杠杆”在百度中的检索结果首页百度首页上的前几项中仅有两项和物理教学有相关，大部分是无关的。如果这个物理老师想要更多的资源，他则需往后翻页去浏览寻找。例三：一个语文老师想介绍一些和泰山相关的知识，但是检索结果如图14。图1-4“泰山”在百度中的检索结果首页7对这个语文老师来说，其中只有两个网址是

32、有用的，而其他的网址则没有什么参考价值，要想获得更多的资源，还得往后翻页。总之，有的搜索引擎能满足相当一部分用户的搜索需求，但是如果用户是特定的某个领域的，有专一主题的需求时，排序的结果就不能满足这些用户了。所以，本文就专业搜索引擎的排序作研究，有很大的现实意义。12本文的主要工作121研究思路本文研究的思路首先是研究现今各大成功的通_fl搜索引擎的排序策略，从中分析影响搜索引擎排序的因素。然后对专业搜索引擎的特殊性作分析，得出专业搜索引擎不同于通_lJ搜索引擎的总体原则，最后在通用搜索引擎排序研究的基础之上，创造适合专业搜索引擎排序的因素，并整合成合理的算法。通过实验不断的调整算法使摊序更加

33、有效。122研究主要内容本文着重研究对排序影响重要的若干因素并适当求解，设计排序算法，就基础教育搜索引擎项目实例进行排序实验，在实验的过程中对算法进行调整。提炼算法使之符合一般意义的专业搜索引擎。123研究的成果和创新本文对各大搜索引擎的排序算法作了研究，在此基础上，分析和归纳了适合通用搜索引擎排序的重要因素，并对其中的若干因素作出求解。本文详细分析了专业搜索引擎捧序的特殊要求，提出了专业搜索引擎排序的原则。设计了适合基础教育搜索引擎捧序的算法，并通过一系列实验证明算法的合理和可行。同时不断地改进。由基础教育搜索引擎的排序算法提炼升华，本文提出了适合一般专业搜索引擎的捧序算法，具有推广的意义。

34、8第2章信息检索中的排序21传统信息检索的相关捧序技术给定幕个文档集合D，大小为M；设两篇文档“、“2D，一个查询q，用什么标准来衡量“1与“2相比，谁和q更相关呢?”这方面最经典的、最有影响力的工作是Gerald Sahon等在30多年前提出的“向量空间模型”(vector space model，VSM)。该模型做了如下假设：文档d和查询q的相关性可以由它们所包含的共有词汇情况来描述。这样，文档d和查询q就都被简化成词汇的集合(多重集)。不失一般性，令为一个词典，1为词项，N为它的规模，则d=(矿，毋，咿)q=(fP，哆，彬)4其中，mt、珥O=l，2，)表示相应词项山现的次数，即词频TF

35、如果次数为0，则表示该词项在文档或查询中没有出现。在通常的应_HJ系统中，人们直接用佩、珥来表示d采l q。d和q的相关度评价就以这两个向量的某种“相近程度”为基础。1)词项在文档和查询中出现的次数(词频)是一个基本量，我们称为“词频”，规格化表示：d=(，驯姚2轰查询q也有同样的表示，这里wt也称为词频，这种方式用词频来表示该词项在文档和查询中的权重。2)若一个词项在很多文档中出现，尽管它可能在某个文档内部出现的频率较高，但是对于不同文档的区分能力就不会很强，因此它的权重应该相对小些，这就引出了该词的文档频率DF的概念用岛表示词项在文档集合D中涉及的文档个数，M表示集合D的大小，则文档频率为

36、DF()=鲁我们需要一个和DF成反比的量，称之为倒置文档频率IDF，常用的一种定义是F：lg(|rM-)。这样结合词频，就有了经典的7FF权重的设计：12弼嘲2瓦mI xlg(争给定某种权重的定量设计，求文档和查询的相关性就变成了求d和q向量的某种距离，最常用的是余弦(cos)距离：毗护鬻这些理论，源于传统信息检索领域，针对的是普通的文本。搜索引擎一原理、技术与实现李晓明p176表10-3补偿因子定义表922通用搜索引擎的排序算法和策略本文通过大量的中外文献调研，归纳了现今通用搜索引擎的排序算法，主要有以下几种：221词频和位置加权捧序算法词频位置加权排序算法是一种只从关键词出现的相对密度进行

37、排序的方法。在计算关键词的相对密度时应该考虑：关键词出现的位置、出现的次数、文档的跃度。其中关键词出现的位置应该考虑这样几个位置：标题(Title)、元标记(META)、关键词(Keyword)、链接文本(AnchorText)。在本算法中，词对文档的相关性与词在该文档中的权值成正比下表是不同关键字在不同位置的权重值分布。表2关键词和词频位置关系的权值裹关键词位置权值关键词位置权值外部链接文字10每句开头15标题10加粗或斜体1域名7文本用法lH1，H2号字体5Title属性l每段句首5A1t属性05路径或文件名4Meta描述0，5关键词堆积Mcta关键词0054(keywords)该算法的优

38、点在于简单、易实现，它的不足之处在于：该算法比较适J【l=I于结构化文档数据，如期刊数据等，对自由的互联网来说，很难保证文档的结构和文档的质量。222DirectHit算法Direct Hit是Ask Jeeves公司的一种注重信息质量和用户行为反馈的排序算法，它的基本思想是：用户输入检索词条t后，如果用户在浏览搜索引擎提供的n条结果记录中第i条记录(RUL)时，停留了较长时问，则说明记录i与关键词t具有较高的相关度；如果用户停留时间较短，用户很快返回结果记录浏览第j条记录，说明记录i与关键词t相关度较小由此可见，同一个词在不同的时间进行检索，得到的结果集排序可能不同，BPDirect Hit

39、捧序是一种依赖用户搜索行为的动态排序。在该排序算法中，网页排序结果由两部分决定；URL被点击次数和被浏览的时间长度。该算法的优点是：首先它利用了用户的反馈信息进行排序，在一定程度上满足了“J【f=l户保障原则”；其次，该算法在排序时考虑了信息的质量。而该算法的不足之处在于：一是用户行为比较随意，很难保证捧序结果的准确性；二是在多页的检索结果中，大部分用户只浏览前几页的结果，因此对于一些排名较示或者新登录的网站很难有机会获得点击，从而一直无法提高自己的排名。323Alexa的网站捧名算法Alexa是以发布世界网站排名而引人注目的一个网站。在URL数量上，Alexa位居世界四大名搜索引擎第一位，已

40、经超过了350亿。101，Alexa的世界网站排名1)综合排名，也可以叫做绝对排名，即特定的一个网站在所有350多亿网站中的名次Alexa每三个月公布一次新的网站综合排名此排名的依据是用户链接数(Users Reach)和页面浏览数(Page Views)三个月累积的几何平均值。2)分类捧名，一是按主题分类，比如新闻，娱乐，购物等，Mexa给出某个特定网站在同一类网站中的名次。Alexa将其收集到的网站共分了16个大类，每个类下又分为多个主题。二是按语言分类，比如英文网站、中文网站、法文网站、德文网站等，给出特定站点在所有此类语言网站中的名次。Mexa提供了21种不同语言网站的分类排名。其中中

41、文网站还细分成简体中文和繁体中文两种。对于中文网站的排名只发布捧在前100名的网站名单。2、Alexa对网站排名的前提条件1)Mexa的网站排名是按照每个特定网站的被访问量进行排名的。访问量越大，排名越靠前。2)访问量是针对定义在域上的网站进行统计的如：sinaccn，newssinatoman和techsinatOmcn将被视作同一网站进行计数，因为它们同属于sins COilcn这个域。3)提供同样内容的网站将被视为同一网站计算。比如说，传播研究网使用wt mediaresearchc091Cll$1http：vnwmediaresearchca两个域名发布同样的内容，那么将被作为同一个网

42、站来计算。4)纳入统计的访问量仅来自使用AlexaI具栏(AlexaToolbar)的用户。也就是说，只有用户下载了Alexa工具栏，并将其嵌入自己的浏览器。这样，该用户访问某个网站的话，访问的记录才能算作被访问网站的访问量。据Alexa统计，现在使用该工具栏的用户达数百万。5)AlexaI具栏仅在windows操作系统下，Internet Exploer浏览器中管用，使用其它操作系统或者浏览器的访问将不能被计数。6)遇到有安全保护或加密的站点(如使用https协议)，Alexa工具栏将自动关闭，因此那些安全系数高的网站，Alexa将不能对其进行搜索和统计捧名3、Alexa对网站访问量算法1)

43、某个特定网站被捧名时，依据的访问量数据是基于该网站3个月访问量记录的累积。也就是说Alexa每三个月发布一次排名结果，即通常说的名次。它的计算主要取决于用户链接数(Users Reach)和页面浏览数(Page Views)Alexa系统每天对每个网站的用户链接数和页面浏览数进行统计，通过这两个量的三个月累积值的几何平均得出当前名次变动是指与前三个月的比较2)用户链接数(Users Reach)指通过Internet访问某个特定网站的人数。用访问某个特定网站的人数占所有Internet埘户数的比例来表示。即：用户链接数=(访问人数全部Alexa用户数)10096 Alexa以每百万人作为计数单

44、位。以雅虎(Yahoo)为例，如果它的用户链接数为28的话，就是说，随意抽取一百万的Iaternet用户，其中有280，000人访问Yahoo3)页面浏览数(PageViews)是指用户访问了某个特定网站的多少个页面。是所有访问该网站的朋户浏览的页面数之和。每个用户浏览的页面数取平均值，是所有访问该网站的用户每天每人浏览的独立页面数的平均。同一人、同一天、对同一页面的多次浏览只记一次。4、影响Alexa网站排名的其它因素1)受使用Alexa工具栏用户的语言、地域、文化等各方面的影响。因此英文网站相对于其它语言的网站，访问量数据更容易被充分地统计。2)由于某种需要，用户可能过多的访问alexaC

45、Om，amazoIL coarchiveorgY-个网站，所以这几个网站的访问量可能被过高的统计。3)很容易受网站对自己宣传的程度、打广告的多少、别的网站为其建立链接的多少的影响224Google的捧序算法Google是全世界被使用的最多的通用搜索引擎。与其它搜索引擎比较，除高性能和易用以外，一个决定性的因素是其优秀的搜索结果。Google搜索结果的质量在很大程度上受益于PageRanl【_个精密的排序网页文件等级的方式。PageRank的思想源于学术引文机制：当从网页A链接到网页B时，就认为网页A投了网页B一票，增加了网页B的重要性，最后根据网页B的得票数评定其重要性计算公式为：卫PR(A)

46、=0一d)+d芝：PR(p,)c(B)ftl其中：PR(A)：页面A的网页级别PR(pI)：页面n的网页级别C(B)：页面B链出的链接数量d：阻尼系数，取值在0-I之间，一般取085N：互联网上所有网页的数量Google采用一种近似的迭代的方法计算网页的网页级别，即给每个网页一个初始值，然后利用上面的公式，进行有限次迭代运算得到网页的级别值。在迭代的过程中，每个网页的网页级别和收敛于整个网络的页面数。每个页面的平均网页级别是l，实际上的值在(1-d)和(心J+(1-d)之间。PageRank只是Google用来排序的一个重要因素，Google还运用了很多其他因素来排序，这里就不展开了PageR

47、ank是由Google的创始人Larry Page希lSergey Brin在斯坦福大学开发出的一套用于网页评级的系统组织管理工具，PageRank利用了互联网独特的民主特性及其巨大的链接结构，在浩翰的链接资源中，Google提取出上亿个超级链接进行分析，制作出一个巨人的网络地图(Map)。依据此地图，PageRan技术能够快速地计算出网页的级别(Rank)，从而进行捧序输出。它的基本思想主要是来自传统文献计量学中的文献引文分析，即一篇文献的质量和重要性可以通过其它文献对其引川的数量来衡量，也就是说，一篇文献被其它文献引心越多，则文献质量就越高。在这样一个假设基础之上，一个网页的质量和重要性也

48、可以通过其它网页对其超文本链接的数量来衡量。具体来说，假如网页A有一个指向网页B的链接，Google就认为“网页A投了网页B一票”。Google根据网页被链接的数量来评定其重要性。如果说，最后指向A的网页数为100，而指向B的网页数只有lO，则说明网页A比网页B更加重要。另外，在实际计算网页的PageRank值时，除了考虑网页得票数(即链接)的纯数量之外，Google还考虑到网页A的所有链入网页(链接到某网页的其它网页称为该网页的链入网页)对它的推荐能力(即由于它们对网页A的链接，使人们认为网页A的重要程度)希I推荐程度(即它们认为网页A的重要程度)。一个网页本身的PageRank值越高，则它

49、对其链出网页(从某个网页链出的网页称为该网页的链出网页)的推荐能力就越大；一个网页的链出网页越少，那么它对其中一个链出网页的推荐程度就越高。据此，Google计算出每个网页的重要性综合指标，即网页级别。重要的、高质量的网页可获得较高的网页级别，从而在搜索结果中可获较高的排位。(当然，如果与查询项目不匹配，再重要的网页也毫无意义。Google采用完善的超文12本匹配分析技术，实现为用户查找既重要又准确的网页)假设网页A有网页T1，T2，Tn的链接指向它，我们可以用以下公式来简要表达Google关于网页PageRank值的计算：PR(A)=(1一d)十d(PR(T1)C(T1)十十PR(Tn)c(

50、Tn)其中，PR(A)是指网页A的PageRank值；T1，T2，Tn是网页A的链入网页：PIc(Ti)是指网页Ti的PageRank值(i=1。2n)；C(Ti)是指网页Ti的链出网页的数量(i=l，2，n)，即指向其它网页的数量；d是权重因子，取0d1，通常取085，本文实验取的值就是085；PR(Tn)c(Tn)为链接指向网页的网页Tn投与网页的网页级别值，亦称MiniPageRank。可以看出，某一网页A的PageRank为其它网页Tn(链接指向网页A的网页)的PageRank除去Tn网页外向链接的数量后的总和，其主要取决于三个因素：(1)该网页的链入数量；(2)该网页的链入网页本身的

51、PageRank值；(3)该网页的链入网页本身的链出数量。根据以上公式，一个网页的链入数量越多、这些链入网页的PageRank值越高，这些链入网页本身的链山数量越少，则该网页的PageRank值越高。假定有如下一个较简单的网络结构图(如下图所示)，则幽中每个页面的PageRank值计算如下：围2-；四个页面的链接关系初始时每个网页都设置其Page Rank为1PR(A)=0115(base)+011275(from C)=012775PR(B)=0115(base)+010425(from A)=011925PR(O=0115(base)+010425(from A)+011275(from

52、B)+011275(from D)=014475PR(D)=0115(base)+010425(from Page A)=011925 经过143次递归计算后得到如下值：PR(A)=114131522515PR(B)=015503931379PR(C)=114860614724PR(D)=015503931379在网页的PageRank值计算过程中，Google首先给每一个网页赋一个初始PageRank值，然后根据PageRank算法进行递归计算，直至相邻两次计算的差值相差小于某一个值(1010)就可以收敛了。PageRank技术根据网页之间的链接结构对网页的重要性进行客观的评价，并将网页的PageRank值应用于检索结果的排序，网页Rank值越高，表明其越重要，排序也越前。这样，在很大程度上避免和减少了人为因素，做到客观地将最恰当的检索结果展现给州户。消除了网站等级、论资排辈等观念，使真正有信息资源价值的任何小网站的网页，在被检索时，和13名网站的网页占有同等的地位，使搜索用户不会被虚假捧名靠前的网站所阻隔，保证了网民们有价值的信息畅通无阻。225SALSA算法在保留PageRank随机漫游和HITS中HUB值和SALSA权威值思想的同时，SALSA算法考虑了用户后退浏览网页的情况，取消了BUB值和权威值的互相加强关系。226HILTS算法(