（教育技术学专业论文）专业搜索引擎的排序算法研究.pdf

摘要 搜索引擎是一项崭新而深奥的技术，包括分词、文档分类、特征提取、索引、存储、检 索和排序等一系列技术环节。在这些环节中，排序是和用户最相关的一个关键环节，当用户 输入关键词检索时，如果搜索引擎已经将用户希望的网页检索出来了，但是却将这些网页捧 在若干页后，则用户几乎不可能浏览到该网页，这样大大降低了用户的满意度。本文主要研 究了搜索引擎的排序问题。 本文首先通过文献调研，研究通用搜索引擎排序的一般方法，如词频和位置加权算法、 d i r e c th i t 算法、a l e x a 的网站排名算法、g o o g l e 的排序算法等，从这些方法中借鉴出通用 搜索引擎排序的重要因素，分析了这些因素的求解方法，通过实验对可能的因素进行了求解。 此外，鉴于基础教育搜索引擎是一个专业的搜索引擎，笔者研究发现：使用专业搜索引擎的 用户有特定的专业背景，对排序的期望值更高，希望检索山的页面都是很相关的。通搜索 引擎对某个关键词检索出的页面是分布于多个主题的，不符合用户的需求。笔者提出了主题 相关度因素，对每个页面计算和主题相关韵程度，再与通用搜索引擎排序的若干因素合理整 合，使专业搜索引擎的排序更加符合用户的需要。本文在基础教育搜索引擎上进行了排序实 验，实验证明，这种排序策略是合理可行的。 本文在研究排序的同时，对搜索引擎的用户评价进行了大量的调研，对几大搜索引擎的 性能、检索方式、检索结果和用户负担等方面进行了比较研究。以期对我们的项目研究有所 借鉴。 关键词：专业搜索引擎，排序算法，主题相关度，基础教育，用户评价 i l l a b s t r a c t s e a r c he n g i n ei t s e l fi san e wa n de s o t e r i ct e c h n i q u e ，i n c l u d i n gs o m e t e c h n i c a l a s p e c t s l i k e s e g m e n t a t i o n ，d o c u m e n tc l a s s i f y ，f e a t u r e e x t r a c t i o n ，i n d e x i n g ，s t o r a g e ，r e t r i e v a la n dr a n k i n g i nt h e s ea r e a s ， r a n k i n gi sm o s tr e l e v a n tt ou s e r s w h e nu s e r si n p u tak e y w o r d ，i fs e a r c h e n g i n el o c a t e st h ew e bp a g e su s e r sw a n t e dt ob o t t o mp a g e s ，i ti sa l m o s t i m p o s s i b l ef o rt h eu s e rt ob r o w s et h r o u g ht h ew e b s i t e ，t h u sg r e a t l y r e d u c i n gt h eu s e r ss a t i 8 f a c t i o n t h i sp a p e ri sm a i n l yo nt h es e a r c he n g i n er a n k i n gp r o b l e m w ef i r s t s t u d yt h el i t e r a t u r e ，a n dr e s e a r c ho nt h ec o m m o nr a n k i n ga l g o r i t h m so f u n i v e r s a ls e a r c h e n g i n e s ， s u c ha st h e w o r d f r e q u e n c ya n dl o c a t i o n a l g o r i t h m , d i r e c th i ta l g o r i t h m ，a l e x aw e b s i t e r a n k i n ga l g o r i t h m ， g o o g l e sr a n k i n ga l g o r i t h m w er e s e a r c ho nt h ei m p o r t a n tf a c t o r so ft h e r a n k i n go fs e a r c he n g i n e t h r o u g he x p e r i m e n t sw ew o r ko u ts o m ep o s s i b l e f a c t o r s m o r e o v e r ，b a s i ce d u c a t i o ns e a r c he n g i n ei sas p e c i f i cs e a r c h e n g i n e t h eu s e r so fs p e c i f i cs e a r c he n g i n e sh a v es p e c i f i c b a c k g r o u n d s ， h o p i n gt h er e t r i e v e dp a g e sa r er e l a t e d i nu n i v e r s a l s e a r c he n g i n e a k e y w o r ds e a r c ho nt h ew e bp a g ei sl o c a t e di nav a r i e t yo ft o p i c s w ep u t t o p i cr e l a t i v i t yf a c t o ra n dc a l c u l a t ei t w ec o m b i n et h i sf a c t o rw i t h u n i v e r s a ls e a r c he n g i n e i tc a nh e l pt h er a n k i n go fp r o f e s s i o n a ls e a r c h e n g i n em e e tu s e r s n e e d t h ee x p e r i m e n t ss h o wt h a tt h i sr a n k i n gs t r a t e g y i sr e a s o n a b l ea n df e a s i b l e b a s e do nt h er e s e a r c ho fr a n k i n ga tt h es a m et i m e ，w ed ol o t so fr e s e a r c h o nt h eu s e r s e v a l u a t i o no fs e a r c he n g i n e a n dc o m p a r a t i v es t u d y o ns e v e r a l m a j o rs e a r c he n g i n e ss u c ha st h ep e r f o r m a n c e ，r e t r i e v i n gm e a n s ，a n ds e a r c h r e s u l t s ，h o p i n gt op r o m o t eo u rr e s e a r c hp r o je c t s k e y w o r d s ：s p e c i f i cs e a r c he n g i n e ，r a n k i n ga l g o r i t h m ，t o p i cr e l a t i v i t y ， b a s i ce d u c a t i o n ，u s e r s e v a l u a 七i o n 学位论文独创性声明 本人郑重声明： 1 、坚持以“求实、创新”的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究成 果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已 经发表或撰写过的研究成果。 5 、其他同志对木研究所做的贡献均已在论文中作了声明并表示了 谢意。 作者签名： 日期： 学位论文使用授权声明 至臣i ! ：墨 本人完全了解南京师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版：有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅；有权将学位论文的内容编入有关数据库进 行检索；有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 作者签名： 日期：芝歪! 业芝12 ：! ： 第1 章前言 1 1 专业搜索引擎排序算法的研究背景 1 1 1 搜索引擎的发展 1 、搜索引擎的诞生与发展 搜索引擎1 作为网络信息搜寻的工具，它以一定的策略在互联网中搜集、发现信息，对 信息进行理解、提取、组织和处理。并为用户提供检索服务。所有搜索引擎的祖先2 ，是1 9 9 0 年由m o n t r e a l 的m c g i l l u l l i v e b i t y 学生a l e m t a g e 、p e t e r d e u t s c h 、b i l l w h e e l a n 发明的 a r c h i e ( a r c h i e f a q ) 。当时w o d d w i d e w e b 还朱出现。a r c h i e 是第一个自动索引互联网上匿名 f r p 网站文件的程序，但它还不是真正的搜索引擎。a r c h i e 是一个可搜索的f t p 文件名列表， 用户必须输入精确的文件名搜索，然后a r e h i e 会a 告诉_ | i j 户哪一个f t p 地址可以下载该文件 由于专门用于检索信息的r o b o t 程序像蜘蛛( s p i d e r ) - - 样在网络间爬来爬去，因此，搜索 引擎的r o b o t 程序被称为s p i d e r ( s p i d e rf a q ) 程序。t h = 界上第一个s p i d e r 样序，是m i tm a t t h e w g r a y 的w o r l d 砸d ew e bw a n d e r e r ，川丁追踪互联网发展规模。刚开始它只用来统计互联网上 的服务器数量，后来则发展为也能够捕获网址( u r l ) 。 1 9 9 3 年2 月，6 个s t a n f o r d ( 斯坦福) 大学生的想法是分析字词关系，以对互联网上的大 量信息作更有效的检索。这就是e x c i t e 。后来曾以概念搜索闻名，2 0 0 2 年5 月，被i n f o s p a c e 收购的e x d t e 停止自己的搜索引擎，改用元搜索引擎d o g p i l e 。 1 9 9 4 年4 月，s t a n f o r d 两名博士生，美籍华a j e n y y a n g ( 杨致远) l l d a v i df i l o 共同创办 了y a h o o 。随着访问量和收录链接数的增长，y a h o o i | 录开始支持简单的数据库搜索。因为 y a h o o 的数据是手工输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。 搜索效率明显提高。( y a h o o 以后陆续使用a l t a v i s t a 、l n k t o m i 、g 0 0 9 l e 提供搜索引擎服务) i n f o - e k ( s t e v e k i t s c h a n n o u n f r e e d e m o s o f t h e l n f o s e e k s e a r c h e n g i n e ) 是另一个重 要的搜索引擎，虽然公司声称1 9 9 4 年1 月已创立，但直到年底它的搜索引擎才与公众见面。 起初，i n f o s e e k 只是一个不起眼的搜索引擎，它沿袭y a h o o , 释l l y c o s 的概念，并没有什么独特 的革新。但是它的发展史和后来受到的众口称赞证明，起初第一个登台并不总是很重要 i n f o s e e k 友善的片j 户界面、大量附加服务( s u c ha s u p s t r a c k i n g ，n e w s ，a d i r e c t o r y , a n d t h e l i k e ) 使它声望日隆。而1 9 9 5 年1 2 月与n e t s c a p e 的战略性协议，使它成为个强势搜索引擎：当用 户点i 蕾n e t s c a p e 浏览器上的搜索按钮时，弹出l n f o s e e k 的搜索服务，而此前由y a h o o 提供该服 务3 1 9 9 5 年，一种新的搜索引擎形式出现了元搜索引擎( a m e t as e a r c h e n g i n e r o u n d u p ) 。用户只需提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选 定的独立搜索引擎，并将从各独立搜索引擎返回的所有查洵结果，集中起来处理后再返同给 用户。 d e c 的a l m v i s m ( 2 0 0 1 年夏季起部分网友需通过p _ x y 访问，无p - r o x y 可t l j q b s e a c h 单选 a l t a v i s t a 搜索，只能显示第一页搜索结果) 是一个迟到者，1 9 9 5 年1 2 月才登场亮相( a l t a v i s t a p u b l i cb e t ap r e s sr e l e a s e ) 。但是，大量的创新功能使它迅速剑达当时搜索引擎的顶峰。 林瑞宜陈榕虎搜索引擎新研究情报探索2 0 0 5 年5 月 2 h t t p ：w w w , f o s h a n w c o m s c o s e o s e 0 7 h t m 3 i n f o s e e k 后来曾以相关性闻名，2 0 0 1 年2 月，i n f o s e e k 停止了自己的搜索引辇，开始改用o v e r t u r e 的搜索 结果 a j t a v i s t a 最突出的优势是它的速度。而a 】t a v i s m 的另一些新功能，则永远改变了搜索引 擎的定义a l t a v m t a 是第一个支持自然语言搜索的搜索引擎，a l t a v i s t a 是第一个实现高级搜 索语法的搜索引擎( 如a n d ，o r , n o t 等) 用户可以用a l 蝴s t a 搜索n e w s g r o u p s ( 新闻组) 的内容并从互联网上获得文章，还可以搜索图片名称中的文字、搜索t i t l e s 、搜索j a v aa p p l e t s ， 搜索a c t i v e x o b j e c t s 。a l t a v m t a 也声称是第一个支持用户自己向网页索引库提交或删除u r l 的搜索引擎。并能在2 4 4 , 时内上线a l t a v i s t a 最有趣的新功能之一，是搜索有链接指向某个 u r l 的所有网站。 1 9 9 8 年l o 月之前，g o o g l e 只是s m f d 大学的一个小项目b a c k r u b 。1 9 9 5 年博士生l a r r y p a g e 开始学习搜索引擎设计，于1 9 9 7 年9 月1 5 日注册t g o o g l e e , o n l 的域名，1 9 9 7 年底，在s e m e y b r i n 币l s e o t th a s s a n 、a l a ns t e r b e r g 的共同参与下，b a c h r u b 开始提供d e m o 。1 9 9 9 年2 月， g o o g l e 完成了从a l p h a 版到b e t a 舨的蜕变。c h 酒e 公司则把1 9 9 8 年9 上j 2 7 e i 认作自己的生日。 g o o g l e 在p a g e r a n k 、动态摘要、网页快照、d a i l y r c f i e s h 、多文档格式支持、地图股票词典寻 人等集成搜索、多语言支持、用户界面等功能上的革新，像a l t a v i s t a - - 样，再一次永远改变 了搜索引擎的定义。 2 、中文搜索引擎的发展 七人天网是国家“九五”重点科技攻关项目“中文编码和分布式中英文信息发现”的研 究成果，由北人计算机系网络与分布式系统研究室开发，于1 9 9 7 年l o 月2 9 e 1 正式在c e r n e t 上提供服务。2 0 0 0 年初成立天网搜索引擎新课题组，由国家9 7 3 重点基础研究发展规划项目 基金资助开发，收录网页约6 0 0 0 万，利埘教育网优势，有强人的f t p 搜索功能。 2 0 0 0 年1 月，超链分析专利发明人、前h f o s c e k 资深工程师李彦宏与好友徐勇( 加州伯克 利分校博士) 在北京中关村创立了百度( b a i d u ) 公司。2 0 0 1 年8 月发布b a i d u c o r n 搜索引擎 b e t a 版( 此前b a i d u 只为其它门户网站如搜狐新浪t o m 等提供搜索引擎) ，2 0 0 1 年1 0 月2 2 日正 式发布b a i d u 搜索引擎。b a i d u 虽然只提供中文搜索，但目前收录中文网页超过9 0 0 0 万，可能 是最大的的中文数据库。b a i d u 搜索引擎的其它特色包括：网页快照、网页预览预览全部网 页、相关搜索词、错别字纠正提示、新闻搜索，h a s h 搜索、信息快递搜索。2 0 0 2 年3 月闪电 计划( b l i t z e np r o j e c t ) 开始后，技术升级明显加快 1 1 2 搜索引擎的技术架构 搜索引擎的原理，可以看做三步：从互联网上抓取网页一建立索引数据库一在索引数据 库中搜索排序。从互联网上抓取网页国l 则能够从互联网上自动收集网页的s p i d e r 系统 程序，自动访问互联网，并沿着任何网页中的所有u r l 爬剑其它网页，重复这过程，并把 爬过的所有网页收集回来。建立索引数据库由分折索引系统程序对收集回来的网页进行 分析，提取相关网页信息( 包括网页所在u r l 、编码类型、页面内容包含的关键词、关键 词位置、生成时间、大小、与其它网页的链接关系等) ，根据一定的相关度算法进行大量复 杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度( 或重要性) ，然 后用这些相关信息建立网页索引数据库。在索引数据库中搜索排序一当用户输入关键词搜 索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相 关网页针对该关键词的相关度早己算好，所以只需按照现成的相关度数值排序。相关度越高， 排名越靠前。最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来 返回给用户。 1 1 3 基础教育搜索引擎的应运而生及系统架构 自从面向2 l 世纪教育振兴行动计划首次明确将“教育信息化”确定为教育发展的 2 重要主题并将教育资源建设定为重点，各企业、学校、部门纷纷投入大量的人力、物力建设 教育资源。到今天分布在全国各地服务器的基础教育资源是无法统计的，而且它每天都像滚 雪球一样在不断的增长2 0 0 1 年6 月教育部颁布基础教育课程改革纲要( 试行) ，提出 了基础教育课程改革的具体目标，其中之一是培养学生搜集和处理信息的能力、获取新知识 的能力、分析和解决问题的能力以及交流与合作的能力。 基础教育专业搜索引擎( 以下简称b e r s e ) 作为基础教育领域的专业搜索引擎的诞生 也就不足为怪了，它的诞生是基础教育资源建设和基础教育改革发展的必然结果，也是广大 从事基础教育研究工作、教学工作人员离不开的工具，对学生来说也是培养他们r r 技能的 平台之一。 图卜1 基础教育搜索引擎的系统架构图 b e r s e 系统的结构如图1 - 1 所示，本系统主要包括控制器、网络蜘蛛、资源分类器、索 引器，商业服务、检索器和相关数据库等主要模块。这些模块是互相联系的，它 f j 的功能划 分并不是完全独立的，相互间存在着内在联系。它们的主要功能描述如下： 控制器：控制系统良好运行的各项参数，如服务器分配、数据调度、负载平衡等。 网络蜘蛛：它是一个w e bc r a w l e r ，它负责不问断地从互联网上搜集、更新基础教育资 源并存储剑文档下载库中。 分类器、索引器：对网络蜘蛛搜集剑的资源进行处理分类，并建立索引存储到索引数据 库中 商业服务；为基础教育资源开发商提供产品推介平台，同时也是本系统实现其商业利润 的一个模块。 检索器：为本系统的用户提供基础教育资源搜索、导航服务。 1 1 4 捧序在搜索引擎中的作用和地位 当前互联网已经达到数十亿网页的规模，并且正在以海量的速度增氏，由于其规模如此 3 之庞大，用户在查询资料的时候，经常面对搜索引擎返回的成千上万的网页链接，而用户点 击这些链接后发现如下问题： 1 ) 某些网页的确包含用户输入的搜索词，可是内容却并非是相关的； 2 ) 某些网页早已更新，用户查询的主题甚至已不存在； 3 ) 某些网页的信息已十分陈旧失去意义； 4 ) 某些网页确有用户所需要的资料，但是质量不高，或朱达到用户所期望的层次。 为使所点击的最初若干链接能满足需要，因此搜索引擎应尽可能在不遗漏相关网页的基 础上，将最恰当的最可信的网页链接放在返回结果的最前面。因此，搜索引擎的排序算法， 成为搜索引擎最核心和关键的技术之一，也是现今网络服务研究的热点之一 从用户角度来说，如果搜索引擎的排序结果不合理，那么他也不愿意使用该搜索引擎。 一个搜索引擎的排序直接决定用户使用的满意度。 襄1 1 中国搜索引擎用户不满意因素及比倒 不满意因素所占比饲 搜索结果重复 5 0 * 搜索结果排序欠佳 4 3 搜索结果太杂乱 3 7 搜索结果不合时宜 3 6 广告太多 3 5 根据某搜索引擎2 0 0 0 年4 月的近5 0 万的_ h j 户点击情况的查询日忐所作的一项统计 表12 用户在前5 页的翻页统计 页号l2345 百分比 4 7 薯1 2 1 l 冀7 1 4 5 1 0 3 1 7 可见，用户绝大部分的浏览集中在前几页，往后的页面被用户浏览到的几率越米越小， 有的页面几乎不被用户浏览到。 1 1 5 专业搜索引擎捧序的研究现状 国内该方面的研究比较少，主要集中在对某些著名搜索引擎的研究上，如对g o o g l e 的 研究。发表的论文数量并不多，并且大部分是介智 性的，实刖性不强。但是近几年国内搜索 引擎的发展速度加快，有代表性的是百度和天网，其中百度关于排序的研究成果没有公开发 表，天网的最新专著搜索引擎一技术、原理与系统公开了其捧序的部分信息 国外这方面的研究成果相对要多，具有代表性的是对g o o g l e 捧序算法的研究，其中尤 以对p a g e r a n k 及其h i t s 相关研究居多。比较成熟的算法有： 1 ) 词频和位置加权排序算法 2 ) d i r e c th i t 算法 3 ) a l e x a 的网站排名算法 4 ) g o o g l e 的排序算法 5 ) 开源搜索引擎如l u c e n e 的排序思想 搜索引擎排序算法作为商业机密不作公开，因为一旦公开，则必有一些网站会针对其中 的一些因素，在自己的网站上进行加强，从而获得较高的捧名，打乱互联网的公平竞争原则 所以，一般的研究主要是基于某些搜索引擎搜索现状的推理和猜测。 近些年，一个新兴的高级技术行业s e o ( 搜索引擎优化) 发展很快，s e o 主要为企业 4 网站提供服务，目的是通过一些网络技术手段使企业网站提高在a l e x a 或g o o g l e 等搜索引 擎中的捧名，提升用户点击的几率，获得更多的商机。通过s e o 手段提高排名要缴纳一定 的费用。一般捧名越前缴费越多 然而s e o 获得捧名的手段有时候是不合法不公平的，所以一些大的搜索引擎如a l e x a 和g o o g l e 等，对这类通过不正当手段获得高排名的网站会不定期进行检查，采取严厉的惩 罚措施甚至封杀。s e o 和搜索引擎之间一直不问断地进行斗争 1 1 6 专业搜索引擎捧序的面临的主要问题 1 、从用户角度 在通用搜索引擎中，为了使用户能比较快捷地得到想要的资源，排序环节起到了很重要 的作用。g o o g l e 之所以能成为全球搜索第一品牌，其优秀的排序结果是决定性因素之一 在中国搜索引擎明户所不满意的因素调查如下： 1 ) 搜索结果的重复5 0 2 ) 排序结果欠佳4 3 3 ) 搜索结果太杂乱3 7 4 ) 搜索结果不合时宜3 6 5 ) 广告过多3 5 用户对排序的结果不满意占了很大的比重。刚户认为，排序在前的网站往往不是最新的； 前面的网页内容不是自己最需要的，很多是对白己没有刚的信息；有时候为了找到一个有用 的网页需要往后翻好几页等。 2 、从w e b 资源本身 就我们的项目基础教育资源搜索引擎来说，在开放的网络教育资源环境中，利刚搜索引 擎查找所需的w e b 资源，往往不能很容易的得到所需的资源，这是因为：1 ) 教育资源的文 档生存周期比较长，更新比较慢；2 ) 教育领域学科较多，很多学科之间存在交义现象；3 ) 数据量大，即便最符合用户意图的页面已经被检索出来了，但是很难捧到最前面。 在基础教育资源搜索引擎系统的背景下，对排序有特定的要求： 基础教育资源搜索引擎是一个专业搜索引擎，通用搜索引擎的排序策略在一定程度上 不能满足其需要。通用搜索引擎的排序主要考虑词频和网页权威性等。而b e r s e 不能仅仅 沿用通用搜索引擎的排序思想，必须设计符合自身专业搜索引擎的排序策略。 这是在文本分类基础之上的又一次资源提炼。现有待检索的文档资源都是经过文档分 类程序处理的，绝大部分资源是符合基础教育特性的。但是总有少数和基础教育的联系不紧 密，排序程序在呈现排序结果时尽量将这些文档排后。 1 1 7 专业搜索引擎捧序研究的意义 笔者参与开发的基础教育资源搜索引擎是一个典型的专业搜索引擎，组织索引了大量的 网络教育资源，是基础教育领域的信息查询工具之一。面向的用户是从事基础教育的老师、 教研工作者、家长和中小学学生，这些用户使用该搜索引擎的目的性很强。如果该搜索引擎 不能将非常重要的资源检索出来并排到前面，将极大地影响该搜索引擎的用户满意度。因此， 如何设计基础资源的搜索引擎的排序就显得尤为重要。 在通用搜索引擎中键入检索词，得到的输出结果是多方面的，包含多个主题和领域。虽 然众多网络用户的需求是多方面的，但是对某个具体身份的_ h 户而言，他很可能需要特定的 输出结果，通用搜索引擎的排序结果往往不能满足特定用户对特定专题的需求。以下分别从 5 三个例子来看： 饲一：一个中学语文老师想查找一些鲁迅的文章，输入关键词“鲁迅”进行检索，他想 要的是关于鲁迅的一些生平或者作品，但是检索结果如图1 - 2 图1 2 。鲁迅”在百度中的检索结果首页 从检索结果可以看出，用户在首页就很难直接找到跟鲁迅相关的作品，如“鲁迅美术学 院”，该页最下端还有“鲁迅教育集团”等不相关的信息。 例二：物理老师检索“杠杆”，希望能找剑和物理教学相关的辅助材料。百度中的检索 结果如图l - 3 。 6 图1 - 3 “杠杆”在百度中的检索结果首页 百度首页上的前几项中仅有两项和物理教学有相关，大部分是无关的。如果这个物理老 师想要更多的资源，他则需往后翻页去浏览寻找。 例三：一个语文老师想介绍一些和泰山相关的知识，但是检索结果如图1 4 。 图1 - 4 “泰山”在百度中的检索结果首页 7 对这个语文老师来说，其中只有两个网址是有用的，而其他的网址则没有什么参考价值， 要想获得更多的资源，还得往后翻页。 总之，有的搜索引擎能满足相当一部分用户的搜索需求，但是如果用户是特定的某个领 域的，有专一主题的需求时，排序的结果就不能满足这些用户了。所以，本文就专业搜索引 擎的排序作研究，有很大的现实意义。 1 2 1 研究思路 1 2 本文的主要工作 本文研究的思路首先是研究现今各大成功的通_ f l 搜索引擎的排序策略，从中分析影响搜 索引擎排序的因素。然后对专业搜索引擎的特殊性作分析，得出专业搜索引擎不同于通_ l j 搜 索引擎的总体原则，最后在通用搜索引擎排序研究的基础之上，创造适合专业搜索引擎排序 的因素，并整合成合理的算法。通过实验不断的调整算法使摊序更加有效。 1 2 2 研究主要内容 本文着重研究对排序影响重要的若干因素并适当求解，设计排序算法，就基础教育搜索 引擎项目实例进行排序实验，在实验的过程中对算法进行调整。提炼算法使之符合一般意义 的专业搜索引擎。 1 2 3 研究的成果和创新 本文对各大搜索引擎的排序算法作了研究，在此基础上，分析和归纳了适合通用搜索引 擎排序的重要因素，并对其中的若干因素作出求解。 本文详细分析了专业搜索引擎捧序的特殊要求，提出了专业搜索引擎排序的原则。设计 了适合基础教育搜索引擎捧序的算法，并通过一系列实验证明算法的合理和可行。同时不断 地改进。由基础教育搜索引擎的排序算法提炼升华，本文提出了适合一般专业搜索引擎的捧 序算法，具有推广的意义。 8 第2 章信息检索中的排序 2 1 传统信息检索的相关捧序技术 给定幕个文档集合d ，大小为m ；设两篇文档“、“2 d ，一个查询q ，用什么标准 来衡量“1 与“2 相比，谁和q 更相关呢? ”这方面最经典的、最有影响力的工作是g e r a l d s a h o n 等在3 0 多年前提出的“向量空间模型”( v e c t o rs p a c em o d e l ，v s m ) 。该模型做了如下 假设：文档d 和查询q 的相关性可以由它们所包含的共有词汇情况来描述。 这样，文档d 和查询q 就都被简化成词汇的集合( 多重集) 。不失一般性，令为一个词 典，1 为词项，n 为它的规模，则 d = ( 矿，毋，咿) q = ( f p ，哆，彬) 4 其中，m t 、珥o = l ，2 ，) 表示相应词项山现的次数，即词频t f 如果次数为0 ，则 表示该词项在文档或查询中没有出现。在通常的应_ h j 系统中，人们直接用佩、珥来表示d 采lq 。 d 和q 的相关度评价就以这两个向量的某种“相近程度”为基础。 1 ) 词项在文档和查询中出现的次数( 词频) 是一个基本量，我们称为“词频”，规格 化表示： d = ( ，驯姚2 轰 查询q 也有同样的表示，这里w t 也称为词频，这种方式用词频来表示该词项在 文档和查询中的权重。 2 ) 若一个词项在很多文档中出现，尽管它可能在某个文档内部出现的频率较高，但 是对于不同文档的区分能力就不会很强，因此它的权重应该相对小些，这就引出了 该词的文档频率d f 的概念用岛表示词项在文档集合d 中涉及的文档个数，m 表示集合d 的大小，则文档频率为d f ( ) = 鲁 我们需要一个和d f 成反比的量，称之为倒置文档频率i d f ，常用的一种定义 是f ：l g ( | r m - - ) 。这样结合词频，就有了经典的7 f f 权重的设计： 1 2 弼嘲2 瓦m ix l g ( 争 给定某种权重的定量设计，求文档和查询的相关性就变成了求d 和q 向量的某 种距离，最常用的是余弦( c o s ) 距离： 毗护鬻 这些理论，源于传统信息检索领域，针对的是普通的文本。 搜索引擎一原理、技术与实现 李晓明p 1 7 6 表1 0 - - 3 补偿因子定义表 9 2 2 通用搜索引擎的排序算法和策略 本文通过大量的中外文献调研，归纳了现今通用搜索引擎的排序算法，主要有以下几种： 2 2 1 词频和位置加权捧序算法 词频位置加权排序算法是一种只从关键词出现的相对密度进行排序的方法。在计算关键 词的相对密度时应该考虑：关键词出现的位置、出现的次数、文档的跃度。其中关键词出现 的位置应该考虑这样几个位置：标题( t i t l e ) 、元标记( m e t a ) 、关键词( k e y w o r d ) 、链接 文本( a n c h o r t e x t ) 。在本算法中，词对文档的相关性与词在该文档中的权值成正比下表 是不同关键字在不同位置的权重值分布。 表2 关键词和词频位置关系的权值裹 关键词位置权值关键词位置权值 外部链接文字1 0每句开头1 5 标题1 0加粗或斜体1 域名 7 文本用法 l h 1 ，h 2 号字体 5 t i t l e 属性l 每段句首 5 a 1 t 属性 0 5 路径或文件名4m e t a 描述0 ，5 m c t a 关键词 关键词堆积 40 0 5 ( k e y w o r d s ) 该算法的优点在于简单、易实现，它的不足之处在于：该算法比较适j 【l = i 于结构化文档数 据，如期刊数据等，对自由的互联网来说，很难保证文档的结构和文档的质量。 2 2 2d i r e c th i t 算法 d i r e c th i t 是a s kj e e v e s 公司的一种注重信息质量和用户行为反馈的排序算法，它的基 本思想是：用户输入检索词条t 后，如果用户在浏览搜索引擎提供的n 条结果记录中第i 条记 录( r u l ) 时，停留了较长时问，则说明记录i 与关键词t 具有较高的相关度；如果用户停留 时间较短，用户很快返回结果记录浏览第j 条记录，说明记录i 与关键词t 相关度较小由此 可见，同一个词在不同的时间进行检索，得到的结果集排序可能不同，b p d i r e c th i t 捧序是 一种依赖用户搜索行为的动态排序。在该排序算法中，网页排序结果由两部分决定；u r l 被 点击次数和被浏览的时间长度。 该算法的优点是：首先它利用了用户的反馈信息进行排序，在一定程度上满足了“j 【f = l 户 保障原则”；其次，该算法在排序时考虑了信息的质量。而该算法的不足之处在于：一是用 户行为比较随意，很难保证捧序结果的准确性；二是在多页的检索结果中，大部分用户只浏 览前几页的结果，因此对于一些排名较示或者新登录的网站很难有机会获得点击，从而一直 无法提高自己的排名。 3 2 3a l e x a 的网站捧名算法 a l e x a 是以发布世界网站排名而引人注目的一个网站。在u r l 数量上，a l e x a 位居世界四 大名搜索引擎第一位，已经超过了3 5 0 亿。 1 0 1 ，a l e x a 的世界网站排名 1 ) 综合排名，也可以叫做绝对排名，即特定的一个网站在所有3 5 0 多亿网站中的名次 a l e x a 每三个月公布一次新的网站综合排名此排名的依据是用户链接数( u s e r sr e a c h ) 和 页面浏览数( p a g ev i e w s ) 三个月累积的几何平均值。 2 ) 分类捧名，一是按主题分类，比如新闻，娱乐，购物等，m e x a 给出某个特定网站在 同一类网站中的名次。a l e x a 将其收集到的网站共分了1 6 个大类，每个类下又分为多个主题。 二是按语言分类，比如英文网站、中文网站、法文网站、德文网站等，给出特定站点在所有 此类语言网站中的名次。m e x a 提供了2 1 种不同语言网站的分类排名。其中中文网站还细分 成简体中文和繁体中文两种。对于中文网站的排名只发布捧在前1 0 0 名的网站名单。 2 、a l e x a 对网站排名的前提条件 1 ) m e x a 的网站排名是按照每个特定网站的被访问量进行排名的。访问量越大，排名越 靠前。 2 ) 访问量是针对定义在域上的网站进行统计的如：s i n a c c n ， n e w s s i n a t o m a n 和t e c h s i n a t o m c n 将被视作同一网站进行计数，因为它们同属于 s i n sc o i l c n 这个域。 3 ) 提供同样内容的网站将被视为同一网站计算。比如说，传播研究网使用 w tm e d i a r e s e a r c h c 0 9 1 c l l $ 1 h t t p ：v n w m e d i a r e s e a r c h c a 两个域名发布同样的内容，那 么将被作为同一个网站来计算。 4 ) 纳入统计的访问量仅来自使用a l e x a i 具栏( a l e x at o o l b a r ) 的用户。也就是说， 只有用户下载了a l e x a 工具栏，并将其嵌入自己的浏览器。这样，该用户访问某个网站的话， 访问的记录才能算作被访问网站的访问量。据a l e x a 统计，现在使用该工具栏的用户达数百 万。 5 ) a l e x a i 具栏仅在w i n d o w s 操作系统下，i n t e r n e te x p l o e r 浏览器中管用，使用其它 操作系统或者浏览器的访问将不能被计数。 6 ) 遇到有安全保护或加密的站点( 如使用h t t p s 协议) ，a l e x a 工具栏将自动关闭，因此 那些安全系数高的网站，a l e x a 将不能对其进行搜索和统计捧名 3 、a l e x a 对网站访问量算法 1 ) 某个特定网站被捧名时，依据的访问量数据是基于该网站3 个月访问量记录的累积。 也就是说a l e x a 每三个月发布一次排名结果，即通常说的名次。它的计算主要取决于用户链 接数( u s e r sr e a c h ) 和页面浏览数( p a g ev i e w s ) a l e x a 系统每天对每个网站的用户链接 数和页面浏览数进行统计，通过这两个量的三个月累积值的几何平均得出当前名次变动是 指与前三个月的比较 2 ) 用户链接数( u s e r sr e a c h ) 指通过i n t e r n e t 访问某个特定网站的人数。用访问某个 特定网站的人数占所有i n t e r n e t 埘户数的比例来表示。即： 用户链接数= ( 访问人数全部a l e x a 用户数) 1 0 0 9 6 a l e x a 以每百万人作为计数单位。以雅虎( y a h o o ) 为例，如果它的用户链接数为2 8 的 话，就是说，随意抽取一百万的i a t e r n e t 用户，其中有2 8 0 ，0 0 0 人访问y a h o o 3 ) 页面浏览数( p a g ev i e w s ) 是指用户访问了某个特定网站的多少个页面。是所有访 问该网站的朋户浏览的页面数之和。每个用户浏览的页面数取平均值，是所有访问该网站的 用户每天每人浏览的独立页面数的平均。同一人、同一天、对同一页面的多次浏览只记一次。 4 、影响a l e x a 网站排名的其它因素 1 ) 受使用a l e x a 工具栏用户的语言、地域、文化等各方面的影响。因此英文网站相对于 其它语言的网站，访问量数据更容易被充分地统计。 2 ) 由于某种需要，用户可能过多的访问a l e x a c o m ，a m a z o i lc o a r c h i v e o r g y - - 个 网站，所以这几个网站的访问量可能被过高的统计。 3 ) 很容易受网站对自己宣传的程度、打广告的多少、别的网站为其建立链接的多少的 影响 2 2 4g o o g l e 的捧序算法 g o o g l e 是全世界被使用的最多的通用搜索引擎。与其它搜索引擎比较，除高性能和易用 以外，一个决定性的因素是其优秀的搜索结果。g o o g l e 搜索结果的质量在很大程度上受益于 p a g e r a n l 【_ 个精密的排序网页文件等级的方式。p a g e r a n k 的思想源于学术引文机制： 当从网页a 链接到网页b 时，就认为网页a 投了网页b 一票，增加了网页b 的重要性，最后根据 网页b 的得票数评定其重要性计算公式为： 卫 p r ( a ) = 0 一d ) + d 芝：p r ( p , ) c ( b ) f t l 其中： p r ( a ) ：页面a 的网页级别 p r ( p i ) ：页面n 的网页级别 c ( b ) ：页面b 链出的链接数量 d ：阻尼系数，取值在0 - i 之间，一般取0 8 5 n ：互联网上所有网页的数量 g o o g l e 采用一种近似的迭代的方法计算网页的网页级别，即给每个网页一个初始值，然 后利用上面的公式，进行有限次迭代运算得到网页的级别值。在迭代的过程中，每个网页的 网页级别和收敛于整个网络的页面数。每个页面的平均网页级别是l ，实际上的值在( 1 - - d ) 和( 心j + ( 1 - d ) ) 之间。p a g e r a n k 只是g o o g l e 用来排序的一个重要因素，g o o g l e 还运用了很多其 他因素来排序，这里就不展开了 p a g e r a n k 是由g o o g l e 的创始人l a r r yp a g e 希l s e r g e yb r i n 在斯坦福大学开发出的一套用 于网页评级的系统组织管理工具，p a g e r a n k 利用了互联网独特的民主特性及其巨大的链接结 构，在浩翰的链接资源中，g o o g l e 提取出上亿个超级链接进行分析，制作出一个巨人的网络 地图( m a p ) 。依据此地图，p a g e r a n 技术能够快速地计算出网页的级别( r a n k ) ，从而进行捧 序输出。它的基本思想主要是来自传统文献计量学中的文献引文分析，即一篇文献的质量和 重要性可以