用户googlepr值
googlepr值 时间:2021-04-18 阅读:()
学校代码10699分类号TP311密级学号046100607题目Web信息搜索技术的研究作者杨彬学科、专业计算机科学与技术指导教师康慕宁申请学位日期2007年3月西北工业大学硕士学位论文(学位研究生)题目:Web信息搜索技术的研究作者:杨彬学科专业:计算机科学与技术指导教师:康慕宁二〇〇七年三月I摘要随着万维网的发展,Web上的信息资源正在以前所未有的速度增长.
面对海量的数据,用户常常无法从中找到自己所需要的数据.
如何使用户能够在网络中快速,准确的找到所需要的数据是Web信息检索面临的挑战.
搜索引擎技术的出现,为用户提供了一种在Web中检索信息的简单的方法,使用户能够通过关键字进行相关资源的搜索.
但是用户所需的资源种类不同,通用搜索引擎难以提供给用户足够的资源,因此出现了针对特定领域的搜索服务.
RSS新闻搜索就是这类应用,它仅仅搜索RSS新闻资源.
同时,越来越多的网络应用采用了B/S模式,因此出现了许多集成在浏览器上的搜索服务,并提供其他方便用户的附加功能.
本文首先介绍了信息检索技术的基本概念和模型,介绍了搜索引擎和元搜索引擎的基本结构;对基于链接分析的搜索引擎排序算法PageRank和HITS进行了分析和对比,在此基础上提出了基于概念的权重PageRank改进算法以及为页面标记概念的两种方法;提出了基于用户反馈的结果融合排名算法;详细介绍了RSS新闻搜索平台的结构,数据库模式设计,搜索操作的性能优化方法,主客观结合的新闻排名机制;最后介绍了一种浏览器插件,它主要提供一种为页面进行概念标记的方法,同时提供元搜索接口等其他服务.
关键词:Web检信息索,PageRank,RSS闻浏览新搜索,排名,器插件IIABSTRACTWiththedevelopmentofWorldWideWeb,theamountofdataonwebexpandsdramatically.
Facingsomanydataonweb,theusersalwayslosetheirwaytofindthespecificdata.
Itisachallengeinwebinformationretrievaltomaketheuserfindthedataaccuratelyandquickly.
SearchEngineprovidesasimplemethodtofindwebpage.
UserscanfindthewebpagebytellingtheSearchEnginethekeyword.
Usersalwaysdemanddifferenttypesofresources,butgeneralSearchEnginecannotprovidesufficientresourceforusers.
Somespecificsearchserviceemerges.
Forexample,RSSsearchservice'saimistoonlysearchtheRSSnewsresourcesspecifically.
MoreandmorewebapplicationsuseBrowser/Serverarchitecture,sothatmanytoolsembeddedinbrowsershasbeenimplemented.
Thesetoolsalwaysprovideanintegratedsearchserviceandotherfunctionconvenientforusers.
ThepapergivesanoverviewofbasicconceptsandmodulesofInformationRetrieval,andthearchitectureofSearchEngineandMetaSearchEngine.
ComparesthePageRankandHITSalgorithm,andthenproposesaweightedPageRankalgorithmbasedonconcepts,andtwomethodsoftaggingconceptsforwebpage.
Proposesaresultmergerankingmethodbasedonusers'feedback.
ThepaperdescribesthearchitectureoftheRSSsearchplatformindetail,includingtheschemasofthedatabase,theoptimizationofsearchoperation,andtherankingmechanismofRSSnews.
Atlast,describesatoolbarembeddedinabrowser,whichprovidesamethodoftaggingconceptsandmetaserachservices.
Keywords:WebInformationRetrieval,PageRank,RSSNewsSearch,Ranking,ToolsembeddedinBrowser西北工业大学硕士学位论文目录III目录摘要IABSTRACT.
II目录III第一章绪论11.
1研究的背景和意义.
11.
2国内外的研究现状.
11.
3研究工作概述.
21.
4本文组织结构.
2第二章Web信息检索技术概述42.
1传统信息检索方法.
42.
1.
1信息检索的形式定义.
42.
1.
2特别检索和过滤.
42.
1.
3经典信息检索模型.
52.
1.
4检索的评价.
62.
1.
5检索过程.
72.
2Web信息检索技术72.
2.
1Web数据的特点72.
2.
2搜索引擎概述.
82.
2.
3元搜索引擎概述.
92.
2.
4Web挖掘技术92.
3小结10第三章搜索排序算法研究.
113.
1基于链接分析的排序算法分析.
113.
1.
1PageRank算法113.
1.
2HITS算法.
123.
1.
3PageRank算法和HITS算法的比较分析.
133.
2基于概念的权重PageRank改进算法143.
2.
1基于网页内容的概念选取方法.
143.
2.
2基于Folksonomy的概念选取方法.
153.
2.
3基于概念的权重PageRank改进算法设计.
173.
3基于用户反馈的结果归并算法.
193.
4小结21第四章RSS新闻搜索平台的设计与实现.
224.
1RSS新闻搜索平台基本框架.
224.
2数据管理结构设计与实现.
234.
2.
1关系数据库模式设计原则.
244.
2.
2RSS种子文档的结构分析.
24西北工业大学硕士学位论文目录IV4.
2.
3设计实体关系模式.
264.
2.
4表的模式设计.
274.
2.
5存储过程接口设计.
294.
3搜索操作的性能优化.
314.
3.
1针对查询建立索引.
314.
3.
2拆分大表.
334.
3.
3解除规范化设计.
364.
3.
4事务隔离级别设定.
374.
3.
5分布式数据库的部署.
394.
4新闻排名规则的设计与实现.
424.
4.
1客观排名因子.
424.
4.
2主观排名因子.
454.
4.
3综合排名的设计与实现.
464.
5小结48第五章嵌入浏览器的搜索集成工具的设计与实现.
495.
1浏览器插件开发原理.
495.
2添加深标签方法的设计.
505.
3搜索引擎集成功能的实现.
515.
4用户搜索历史记录.
525.
5高亮关键字的实现.
525.
6小结54第六章结束语556.
1工作总结556.
2后续工作展望.
55参考文献56发表论文和参加科研情况说明.
58致谢59西北工业大学硕士学位论文第一章绪论1第一章绪论1.
1研究的背景和意义万维网从诞生到现在不过二十余年,但它给人们的生活带来了巨大的影响.
随着网络应用的快速发展,WWW(WorldWideWeb)已经成为许多行业信息发布、交流的主要平台.
Web上可以利用的文本数据总量就有千兆字节,另外还存在着大量的图像、音频、视频等多媒体资源.
一方面WWW包含了从技术资料,商业信息到新闻快讯,体育娱乐咨询等多种类别和形式的信息;而另一方面,由于网络的动态性,资源分布分散,没有统一的数据管理形式,使用户很难在WWW上找到自己所需要的信息.
这一矛盾从Web诞生就存在,但是直到现在也没有得到根本的解决.
Web信息检索技术能够高效、准确的从Web数据中查找用户需要的信息、并以有效的形式呈现给用户.
Web信息检索技术不仅有很强的实用性,有很大的现实意义,而且作为Web数据管理的一部分,在学术界也受到广泛关注[6,7].
1.
2国内外的研究现状传统的信息检索技术源于图书馆,它对信息项进行表示、存储、组织和存取.
信息检索技术首先要对系统进行建模,常用的模型包括布尔模型,向量模型和概率模型.
在模型基础上进行文档的标引,查询和文档的定义,并给出针对查询的相似度计算公式,最后通过用户界面返回给用户.
搜索引擎是早期出现的Web信息检索方法.
它的出现在一定程度上缓解了从巨大的WWW的资源中查找信息的难度.
搜索引擎已经成为普通用户在网络上获取信息的主要方法,用户输入关键字,通过搜索引擎获取一组包含该搜索关键字的相关页面.
搜索引擎本身通过网页采集程序收集大量网页并且建立索引,当用户查询到来时通过查找索引并返回相关页面.
搜索引擎一般分为集中式和分布式两种.
当前最成功的搜索引擎代表是Google.
网络目录也是常用的一种Web信息检索工具.
目录是各种知识的等级分类.
用户可以通过逐层的目录浏览,查找自己感兴趣的页面.
Web目录通常包括政治,经济,教育等大的类别,一级分类在12到26个之间,每个目录下还有更细的分类.
网络目录的代表是Yahoo!
.
大多数搜索引擎现在也提供主题目录,如AOL,Excite西北工业大学硕士学位论文第一章绪论2等,但是这些都是针对某些特定领域的,如有的站点关注于商业,新闻或政治.
网络目录和搜索引擎是最早出现的两种通用的Web信息检索方法.
元搜索引擎是建立在独立搜索引擎之上的搜索引擎.
这类搜索引擎自身不维护数据,而是将用户请求发送到若干独立搜索引擎,取回这些独立搜索引擎的搜索结果并进行结果融合并显示给用户.
这类搜索引擎的代表有MetaCrawler,SavvySearch和Inquirus.
由于网络资源包括的资源过于丰富,出现了针对特定领域的搜索平台.
比如针对学术论文的CiteSeer;针对网络上大量的RSS新闻,Blog页面,越来越多的网络应用提供了RSS新闻搜索,比如Digg.
这些网络应用和通用的搜索引擎、网络目录的最大区别是只关注一类Web资源,而不是广泛的搜取网络上的所有资源,例如RSS新闻搜索只关注RSS新闻种子资源,百度MP3搜索只关注文件格式为mp3,wmv等的音频资源.
1.
3研究工作概述Web信息检索技术包含的研究方向较多,本身面临着许多挑战,目前没有一个高效统一的模型用于Web信息检索.
作为成功的第一代Web信息检索模型的代表搜索引擎技术也正融入越来越多新思想与新技术.
数据挖掘,人工智能,机器学习,自然语言分析,社会学等学科的技术都融入到Web信息检索领域.
笔者于2005年参加中美合作"下一代智能搜索平台"项目的研发,先后参加了"DIGGOL个人信息挖掘助手"和"WizAg智能RSS新闻聚合搜索平台"的研发.
主要完成了搜索平台的总体结构设计,数据库模式设计,搜索排名算法设计与实现,搜索性能优化以及嵌入浏览器的用户界面开发等工作.
结合项目经验,提出了基于概念的权重PageRank改进算法,基于用户反馈的元搜索引擎模型及结果归并方法.
1.
4本文组织结构本论文是按照作者承担的主要研究和开发工作来安排的,共分为六章,每一章的主要内容如下所示:第一章绪论.
本章简要介绍了本文的研究背景和意义、研究工作内容以及论文内容的安排.
第二章Web信息检索技术概述.
本章介绍了传统信息检索方法,经典信息检索模型,信息检索的评价标准;介绍了Web信息检索技术的基本概念,分析了西北工业大学硕士学位论文第一章绪论3Web数据的特点,对搜索引擎和元搜索引擎进行了简要介绍.
第三章搜索排序算法研究.
首先研究了基于链接分析的搜索引擎排序算法PageRank和HITS(Hypertext-InducedTopicSearch);然后提出了两种提取概念的方法,并在此基础上设计了基于概念的权值PageRank改进算法;最后提出基于用户反馈的元搜索模型,在此模型基础上设计了结果归并算法.
第四章RSS新闻搜索平台的设计与实现.
详细介绍了RSS新闻搜索平台的构架,数据库设计,搜索性能优化方法和分布式数据库部署策略.
介绍了新闻文章的主客观因子结合的综合排名算法的设计与实现.
第五章嵌入浏览器的搜索集成工具的设计与实现.
介绍了一种嵌入浏览器的用户界面设计与实现方法.
第六章结束语.
本章总结了全文的主要工作,并展望了后续的研究工作,指出了进一步的研究内容.
西北工业大学硕士学位论文第二章Web信息检索技术概述4第二章Web信息检索技术概述2.
1传统信息检索方法信息检索(InformationRetrieval)是对信息项进行表示,存储,组织和存取[1].
信息检索的主要目标就是检索出所有与用户查询相关的文献.
在传统的信息检索系统中,通常采用标引词来编制索引和检索文献.
标引词就是关键词或一组相关词,其自身有一定的意义.
标引词更为一般的形式是一篇文献中出现的任何词,这样构成全文检索系统.
信息检索的核心问题就是预测哪些文献相关,哪些文献不相关.
通常取决与采用的排序算法,处在排列最顶端的文献被认为是最可能相关.
本节首先形式化的定义信息检索模型,然后介绍两种常见的检索方式和三种经典信息检索模型,最后介绍了信息检索的过程.
2.
1.
1信息检索的形式定义信息检索模型是一个四元组,其中(1)D是文献集中的一组文献逻辑视图,称为文献的表示;(2)Q是一组用户信息需求的逻辑视图,称为查询;(3)F是一种机制,由于构建文献表示、查询及他们之间关系的模型;(4)R(qi,dj)是排序函数,该函数输出一个与查询qi∈Q和文献表示dj∈D有关的实数,这样就在文献之间根据查询qi定义了一个顺序.
2.
1.
2特别检索和过滤特别检索和过滤是传统信息检索中的主要两种应用方式[1].
特别检索类似于图书馆里的图书检索,图书馆的书库中的藏书一般情况下是固定的(一般仅在新学期会购入新书),不同学生到图书馆中查找自己所需要的书籍.
由此可见,特别检索的特点在于集合中的文献保持相对静止的状态,而用户的查询则是变化的.
搜索引擎也属于这种类型的检索.
过滤又称为路由选择,其特点和特别检索相反,它的特点在于用户的查询规则相对稳定,而文献集合是经常变化的.
例如一些股票市场和新闻服务,用户定西北工业大学硕士学位论文第二章Web信息检索技术概述制一些查询,在不同时间返回不同的数据.
过滤的难处在于构建一个真正反映用户优先选择的用户需求档.
例如在第四章中详细介绍的RSS新闻搜索平台中,提供按种子类别进行过滤的功能,而用户需求档就是种子的名字.
2.
1.
3经典信息检索模型信息检索的三个经典模型分别为:布尔模型,向量模型和概率模型.
布尔模型:布尔模型是基于集合理论和布尔代数的一种简单的检索模型.
在布尔模型中,文献和查询用标引词集合来表示,又被称为集合论模型.
布尔模型假定标引词在文献中要么出现、要么不出现,因此标引词权值变量都是二值的,即wi,j∈{0,1}.
查询被表示成有确切语义的布尔表达式,通常是由若干个标引词通过联结词not,and,or连接起来的.
查询本质上是一个常规的布尔表达式,它可以表示为多个合取向量的析取,即析取范式DNF(DisjunctiveNormalForm),记为qdnf;qcc表示的任意合取分量.
文献dj和查询q的相似度定义为:{))()(,()|(10),(ccijiidngccccqgdgkqqqjqdsim=∧∈=如果其它如果sim(dj,q)=1,则布尔模型表示文献dj与查询q相关,否则文献与查询不相关.
但是,布尔模型只能判断文献是否相关,而无法判断部分匹配的情况.
向量模型:在向量模型[2]中,文献和查询用t维空间的向量来表示,称该模型为代数模型.
通过给查询和文献中的标引词分配非二值权值,实现部分匹配.
这些权值被用于计算文献和用户查询之间的相似度.
向量模型通过对检出文献相似度降序排列的方式来实现文献与查询的部分匹配.
在向量模型中,元组(ki,dj)的权值wi,j是一个正的非二值数.
此外,查询中的标引词也要加权.
用wi,q表示二元组[ki,q]的权值,wi,q>=0,查询向量q表示为q=(w1,q,w2,q,…,wt,q),其中t是系统中标引词的数目.
文献dj的向量可以表示为dj=(w1,j,w2,j,…,wt,j).
矢量模型通过矢量dj和q之间的形似性来评价文献dj和查询q的相似度.
一般使用两个向量的余弦值来计算相似度,即∑∑∑===**=*=tiqitijitiqijijjjwwwwqdqdqdsim1,21,21,,||||),(概率模型:概率模型[3]试图通过概率方法处理信息检索问题.
给定一个用户查5西北工业大学硕士学位论文第二章Web信息检索技术概述询q和文档集中的一个文档dj,概率模型试图估计用户找到其感兴趣的文档dj的概率,模型假设这个相关概率只是依赖于查询和文档的表示.
概率模型假设在文档集中存在一个子集,它是查询q的结果集.
理想结果集记为R,它使得总体的相关概率最大.
集合R中的文档被认为是于查询相关的,不在集合R中的文档则被认为是不相关的.
在概率模型中,标引词的权值是二值的,即wi,j{0,1},wi,q{0,1}.
查询q是标引词的一个子集.
设R是已知的相关文档集,设R是R的补集,P(R|Wj)是文档dj与查询q相关的概率,p(R|Wj)是文档dj与查询q不相关的概率.
文档dj与查询q的相似度可以定义为:)|()|(),(jjjWRPWRPqdsim=在这些基本信息检索模型基础上,研究人员又提出了许多改进模型,例如在基于集合论的模型上,提出了模糊集合论模型和扩展布尔模型;在代数模型基础上,衍生了广义向量模型,潜语义标引模型和神经网络模型;在概率模型基础上,区分出了推理网络模型和信任度网络模型.
2.
1.
4检索的评价常用的系统性能指标是时间和空间指标.
在一个信息检索系统中,人们最关注的指标是相应时间和所需空间.
在这些基本的指标基础上,针对信息检索系统的特点,还有两个重要的衡量标准就是查全率和查准率[1].
设信息查询实例为I,I对应的相关文献集合为R,用|R|表示该集合中的文献数目.
假定用给定的检索策略对信息查询I进行处理,并生成一个文献结果集合A,用|A|表示该集合中的文献数目.
用|Ra|表示R和A的交集中的文献数量:查全率是指检出的相关文献与相关文献(集合R)总数的比值,即查全率为:||||RRRa=查准率是指检出的相关文献与检出文献(集合A)总数的比值,即查准率为:||||ARPa=6西北工业大学硕士学位论文第二章Web信息检索技术概述72.
1.
5检索过程在检索过程开始之前,必须定义一个文本数据库.
这通常由数据库管理器来完成,它将要使用的文献,将要在该文本上执行的操作转换为文献的逻辑视图.
数据库管理器还要为数据库中的文本进行标引,对文本建立索引.
在检索过程中会用到不同的索引结构,最常见的一种索引就是倒排文档.
用户首先详细说明用户需求,随后对用户需求进行分析和转换,为用户需求提供一个系统表达式,接着通过查询获得检出文献.
在把文献发送给用户之前,要根据相关度,对检出文献进行排序.
随后用户检查经过排序后返回的文献集合,查找有用的信息.
在这过程中,用户可能会将反馈信息发送给系统,系统可以利用用户所选择的文献改进查询的表达.
而在这些过程中,一般都需要一个用户界面,例如在Web浏览器中显示的一个Web搜索引擎页面.
2.
2Web信息检索技术Web应用的迅速发展和它的指数增长已广为人知,仅可利用的文本数据总量就有千兆字节.
Web可以看成一个非常大的,非结构化且无处不在的数据库.
这就需要有效的工具来管理,检索和从数据库中筛选信息.
Web信息检索的基本形式有三种,第一种是搜索引擎,它标引一部分网络文献作为一个全文数据库,例如AltaVista;第二种是Web目录,它按主题来对所选择的Web文献进行分类,例如Yahoo!
;第三种是利用超链接结构来检索网络[1].
本节首先介绍Web数据的特点,然后分别对搜索引擎和元搜索引擎技术进行了简单介绍.
2.
2.
1Web数据的特点网络带来的Web数据有非常鲜明的特点,这些特点都加大了Web信息检索的难度.
数据的分布性:由于网络的本质特性,Web数据经常分布在许多计算机平台上;不稳定数据的高比例,由于Web的动态性,新的计算机和数据容易添加或删除.
当域名或文件名发生改变或不存在时,还要处理悬空链接和重新定位的问题;网络数据量的指数增长带来了大规模的数据;非结构化和冗余的数据,每个HTML页面都没有很好的结构,许多网络数据是重复的镜像,或者非常相似,据统计约有30%的网页是重复的.
如果考虑语义上的冗余则重复数据更多;数据的质量不高,网络可以看出是一个新的出版媒体,然而在大多数情况下,许多内容西北工业大学硕士学位论文第二章Web信息检索技术概述并没有经过编辑处理,甚至任何一个用户都可以在网络上添加内容(比如现在流行的个人网络日志Blog,电子布告板BBS),因此网络上的数据可能是错误的,无效的;异构数据大量出现在网络中,除了有多种媒体和由此产生的多种格式外,还需要处理不同的语言,不同的字母表,而这其中可能非常庞大,例如中文,日文等亚洲字母表.
2.
2.
2搜索引擎概述大多数搜索引擎采用了集中式的收集器-索引器结构[4],其体系结构如图2-1所示.
收集器(又常被称作蜘蛛Spider,爬虫Worm,机器人Robots)是一个程序,它按某种策略(如广度优先或深度优先)遍历网络,发回新的或更新过的网页,然后将这些发送回的数据存储在文档库中.
实际上收集器并不是实际运行在异地的机器上,而是在本地系统中运行,向异地的Web服务器发送请求并获取网页.
索引器分析收集器收集到的网页,将文档表示成便于检索的形式,并在文档上建立索引,最后将生成的索引库保存在主服务器上.
索引一般采用某种形式的倒排索引,倒排索引的每一项包含一组指针,这些指针指向和这个索引项相关的网页.
当用户输入某个关键词进行搜索时,需要通过用户接口将查询发送到检索器,检索器通过索引快速找到相关的文档,然后按某种算法排序计算这些文档的排序值,最后将排序后的结果返回给用户.
WWW收集器索引器检索器主服务器,索引数据库用户接口文档库图2-1搜索引擎体系结构图大多数搜索引擎使用布尔模型或向量模型及这些模型的扩展进行排序.
除了经典的词频-逆文献率方法外,经常使用的还有布尔扩展、向量扩展和最大引用等方法.
新的排序算法使用到了超链接信息,这是Web和传统IR数据库之间的最根本区别之一.
指向一个网页的超链接的数量能够用来测量该网页的流行程度和质量.
此外,被相同页面所引用的网页与网页之间的公共链接表明了这些页面之间的关系.
常见的例子有WebQuery,HITS和PageRank.
将在第三章详细讨论HITS8西北工业大学硕士学位论文第二章Web信息检索技术概述9和PageRank.
当前有许多成功运行的搜索引擎,例如AltaVista,Excite,Infoseek,Lycos,Google,百度和天网搜索.
2.
2.
3元搜索引擎概述元搜索引擎是把一个给定的查询发送到几个搜索引擎、Web目录及其他数据库,并收集和统一结果的一种网络服务器[1].
可以认为元搜索引擎是建立在独立搜索引擎之上的搜索引擎.
它利用下层的若干个独立搜索引擎提供的服务向上提供统一的检索服务,本身不采集文档、维护索引.
元搜索引擎首先按某种策略把用户的查询发送给特定的几个独立搜索引擎,再将各独立搜索引擎所得结果按照某种结果归并策略进行融合,排序,最终给出统一的查询结果.
元搜索引擎综合多个搜索引擎的结果,可以增加网络资源的覆盖率,提高搜索的查全率;同时,元搜索引擎在进行结果归并时,依据某种归并策略,可以对独立搜索引擎的一次查询结果进行二次集成和排序,提高搜索的查准率.
经典的元搜索引擎主要由三部分组成:请求提交代理、检索接口代理、结果显示代理[5].
请求提交代理负责选择调用哪些独立搜索引擎,检索时间限制,检索返回结果数量限制等;检索接口代理将用户的检索请求按不同的格式发送到各个独立搜索引擎;结果显示代理负责各个独立搜索引擎检索结果的去重,合并,显示.
当前也有许多成功运行的元搜索引擎,例如:MetaCrawler,vivisimo,bbmao,SavvySearch,Search.
2.
2.
4Web挖掘技术Web挖掘是从与WWW相关的资源和行为中抽取感兴趣的、有用的模型和隐含信息.
一般地,Web挖掘可分为三类:Web内容挖掘,Web结构挖掘和Web使用记录挖掘[6].
Web挖掘技术能改善Web信息检索的质量,提供更多的应用类型,而且Web挖掘技术也是当前数据管理领域的一个热点研究方向[7].
Web内容挖掘:从文档内容或其描述中抽取知识的过程.
其主要内容是对Web页面文档内容及搜索引擎的查询结果进行总结,聚类,分类等.
Web内容挖掘有两种策略:直接挖掘文档的内容或在其他工具搜索的基础上进行改进.
Web结构挖掘:从WWW的组织结构和链接关系中推导知识.
由于文档之间的互连,WWW能够提供除文档内容之外的有用信息,利用这些信息,可以对页面进行排序,发现重要的页面.
第三章介绍的PageRank和HITS算法就是这一类型Web挖掘的代表.
西北工业大学硕士学位论文第二章Web信息检索技术概述10Web使用记录挖掘:主要目标是从Web的访问记录中抽取感兴趣的模式.
WWW中每个服务器都保留了访问日志,记录了关于用户访问和交互的信息,分析这些数据可以帮助理解用户行为,从而改进站点的结构;或为用户提供个性化的服务.
在第四章中介绍的RSS新闻搜索平台中采用的主观排名因子,就是这一类型的应用.
2.
3小结本章首先介绍了信息检索的形式化定义,对特别检索和过滤这两种不同的检索方式进行了对比;介绍了布尔模型、向量模型和概率模型三种经典信息检索模型;指出信息检索系统的基本评价标准是查全率和查准率;描述了一般的信息检索系统中的信息检索过程;接着分析了Web数据的特点,介绍了搜索引擎和元搜索引擎的体系结构和基本工作原理,最后介绍了Web挖掘技术.
西北工业大学硕士学位论文第三章搜索排序算法研究11第三章搜索排序算法研究3.
1基于链接分析的排序算法分析一个超文本文档(即网页)内可能存在大量的超链接,每个超链接指向互联网上的其他文档.
因此,互联网上的文档间存在一个有规则的网络拓扑结构.
对互联网的组织结构和链接关系进行推导,可以得到互联网上某个文档的重要程度,进而可以对这些文档进行排序.
因此,当前主流的搜索引擎(如Google,百度)都采用了基于链接分析的排序算法.
目前基于链接结构分析的搜索引擎排序算法主要都来源于两种经典算法:一种是斯坦福大学SergeyBrin和LawrencePage提出的PageRank算法[8],为了验证该算法的性能,他们建立了Google搜索引擎的原型,现在Google已经发展成全世界最知名,最强大的搜索引擎.
另一种算法是康奈尔大学JonKleinberg提出的HITS算法[9].
本章首先简要描述这两种算法的基本思想,对各自的特点进行了分析比较,然后针对PageRank算法采用的平分页面自身PageRank值的策略,提出了一种按概念权重分配PageRank值的改进算法.
概念可以采用多种方法进行选取,文中给出两种方法.
3.
1.
1PageRank算法PageRank算法是最经典的搜索引擎排序算法,它的基础是网络用户的随机访问模型[10].
Brin和Page在其论文中提出一种用户行为的模型:假设有一个随机的网络冲浪者,任意给定一个网页,持续点击链接,最终厌倦并开始访问另一个随机页面,这一模型被称为随机冲浪模型.
这样,在随机冲浪模型中,一个随机的网络冲浪者访问一个页面的可能性就是该网页的PageRank值.
PageRank算法的基本思想其实来源于传统的学术文献的引文分析方法,而Brin和Page把这一思想应用到了Web页面中.
传统的文献分析方法为,一篇文献的重要性可以通过其他文献对其引用的数量来衡量.
如果文献A被同学科的许多文献所引用,则文献A在该学科内应该是一篇有影响力的著作.
同样,在Web环境下,如果页面A通过超级链接指向了页面B,相当于页面A引用了页面B,即页西北工业大学硕士学位论文第三章搜索排序算法研究面A给页面B投了一票,页面A需要把自己的一部分PageRank值分给页面B,图3-1是一种网络拓朴结构下的PageRank值分配示意图.
最后,根据每个页面的PageRank值来判断页面的重要性,重要的页面会在搜索引擎的搜索结果中位于前列.
如果一个网页有许多网页都指向它,那么它可能获得很高的PageRank值;如果一个网页被一个本身PageRank值很高的页面所指向,那么它同样可能具有很高的PageRank值.
页面PageRank值的计算公式为:PR(A)=(1-d)+d*(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))假设页面T1…Tn都有超链接指向页面A.
其中PR(A)表示页面A的PageRank值;参数d是一个衰减因子,根据不同情况可以设定d在0到1之间,通常设定为0.
85.
C(T)表示页面T指向其他页面的链接个数.
在通常情况下,设定每个网页的初始PageRank值为1,通过以上公式,递归计算各网页的PageRank值,直到网页的PageRank值趋于稳定.
由于其用户行为模型假设用户访问网络是完全随机的,因此一个页面的PageRank值被平分给了其所指向的页面,由上述公式中的项PR(T1)/C(T1)可以明显的看出其平分策略.
959560607080408040C160C2155C395B1120B2190A180A2160A370图3-1PageRank值分配示意图3.
1.
2HITS算法Kleinberg在其论文中提出了HITS算法,用来评定网页内容的重要性.
HITS的重要性评价是针对用户查询的.
该算法将网页分为两个类别,即权威页(authorities)和中心页(hubs).
权威页是表达某一主题的页面,对这一主题12西北工业大学硕士学位论文第三章搜索排序算法研究它的价值很高,依赖于指向它的页面.
中心页是指向多个权威页的页面,它把这些权威页链接在一起,依赖于它所指向的页面.
HITS算法为每个页面引入两个权值,即authority权值和hub权值,通过一定的计算可得到针对某个检索提问的最具价值的网页,即排名最高的权威页.
HITS算法首先通过传统的搜索引擎(如AltaVista)选取一定数量的页面作为根集,然后在根集的基础上进行扩展,把引用根集的页面和被根集引用的页面都加入进来,生成基本集,再针对基本集中的超链接建立所要处理的子图.
在这个子图上,建立页面的authorities和hubs的计算公式.
设A(p)表示页面p的authorities值,H(p)表示页面p的hubs值,指向页面p的集合为B(p)={q1,q2,…,qn},页面p指向的页面的集合为I(p)={q1',q2',…,qn'}.
则A(p)=H(q1)+…+H(qn);H(p)=A(q1'A(qn');通过迭代计算,最终得到页面p的authorities值.
HITS算法中的authorities和hubs值是互相加强的.
图3-2是一种网络拓朴结构下的HITS值分配示意图.
q1q2q3pr1r2r3ap=hq1+hq2+hq3hp=ar1+ar2+ar3图3-2HITS值分配示意图3.
1.
3PageRank算法和HITS算法的比较分析虽然PageRank算法和HITS算法都是基于超链接拓扑结构分析的搜索引擎排序算法,但是两者还是有区别的:13西北工业大学硕士学位论文第三章搜索排序算法研究14(1)PageRank完全忽略网页内容,仅根据网络超链接的拓扑结构计算得到网页的PageRank值,是一种独立查询(query-independent)的算法.
而HITS的authorities值是相对于某个检索主题的,是一种依赖查询(query-dependent)的算法.
(2)PageRank是基于对Web的整体分析,而HITS算法则是通过传统搜索引擎查选结果构建的基本集上进行分析的,是Web的局部分析,容易造成"主题漂移"现象.
(3)虽然PageRank处理的数据比HITS多,但是HITS首先需要抽取根集,并扩充基本集,从客户端等待的时间上看,PageRank需要的时间比HITS短.
(4)从权重的传播上看,PageRank基于随机冲浪模型,可以认为网页的重要性从一个authorities传到另一个authorities.
而在HITS的模型中,则是从hub页传到authorities页.
从目前的应用来看,PageRank算法相对于HITS算法有一定的优势,Google成功的商业运作,就是很好的例证.
虽然PageRank算法已成功应用到Google当中,但是它并不考虑网页的具体内容,平分PageRank值,不考虑各个链接重要性,这是值得改进的.
在下一节中,我们讨论一种权重PageRank改进算法.
3.
2基于概念的权重PageRank改进算法由于PageRank采用的随机冲浪模型认为每个链接的重要程度是相同的,所以采用了平分策略.
实际上,不同的超链接的价值是不同的.
假设A页面有指向B页面的超链接,则B页面可能是和A页面高度相关的一个页面,比如都是讨论同一主题的页面;然而也可能B页面和A页面根本不相关,B页面可能只是一个广告页.
这一点和传统的文献引文分析不同,文献引文经过严格的审查,可以保证引文间的高度相关性,而在Web环境下,超链接的质量无法保证.
针对PageRank所存在的上述问题,结合HITS算法的思想,提出了一种改进算法,即根据网页间概念的关联比重及用户搜索的概念,按权重分配页面的PageRank值.
3.
2.
1基于网页内容的概念选取方法在该改进算法的实现中,首先要为每个网页确定若干个概念.
概念的选取可以有多种方法,如UdoKruschwitz在其论文[11]中总结了一种方法:选择在以下标签上下文中出现多于一次的关键字作为概念.
这些标签包括:meta信息,文档的西北工业大学硕士学位论文第三章搜索排序算法研究15题目,文档的标题,超链接的文本,以及重点强调的部分(如字体为粗体或斜体的部分).
这种方法主要的特点是基于页面源码分析,可以认为是一种客观的概念.
这种对Web页面源码分析提取概念的方法可以认为是传统的文本分析的一个拓展,已经有许多种成熟的算法,特别是针对英文.
这种算法的基本过程可以概括为以下几个关键步骤:(1)对文本进行切词.
针对英文,空格是自然的分割符,由空格隔开的就是独立的单词.
仅仅依靠空格的分词是最基础的,通常情况下还需要有一个停用词表,用来过滤那些对检索来说作用不大的单词,或没有实际意义的单词.
最后,需要进行词干提取,因为英文中不但有比较级的变化,例如比较级,最高级;还有时态、单复数的变化,例如:working,works,worked对应同一个词干work,目前最常用的词干提取算法是PorterStem[12].
针对中文,切词本身就是一项复杂的问题,因为中文没有天然的分割符,容易出现切词的二义性及歧义,中文切词具体方法可以参考相关文献.
(2)构造一个语义字典.
语义字典对于文本切词来说是有指导意义的,它规定了每个词的不同重要级别.
比如,名词,实意动词表达的概念要比虚词,冠词,语气词表达一个文档的实际内容多.
同时,通过语义词典,还可以进行层次概念抽取,同义近义词的合并与提取.
当前已经有较多的成熟语义词典,针对英文有Princeton大学研发的WordNet,针对中文有北京大学研发的现代汉语语料库和语义信息词典.
借助这些语义字典,可以更好的完成文本的切词以及概念的提取.
(3)超文本文档的分析.
超文本文档中不同标记内的文本提供给更多的附加信息,比如在标题标签内的文本,粗体、黑体标签内的文本,超链接中的文本的权重要加大.
3.
2.
2基于Folksonomy的概念选取方法上一小节中提到的概念选取方法是一种客观的选取算法.
Web环境下的文本标记的一个特点就是用户的参与,可以让用户对文档添加概念进行标记,即社会性.
Folksonomy分类法就是民间社会分类法.
这个概念起源于社会性书签服务中最具特色的自定义标签功能.
Folksonomy分类标引可以由三类角色完成,分别为专家,信息发布者,以及普通用户[20].
专家对一个文档的概念标引常常出现在传统的信息检索领域.
比如一个图书馆管理员按照图书馆的分类体系,对一本书进行标引,分类,标记概念.
这要求图书馆管理员熟悉分类体系,需要经过严格的专业知识学习与训练.
如果在Web西北工业大学硕士学位论文第三章搜索排序算法研究16环境下应用,则需要类似图书馆管理员的角色对Web文档进行分类和概念标记.
早期的Yahoo!
网络目录采用的目录式检索就是采用这种方法,它通过人力把Web页面归为若干大类,每一类低下又有若干子类.
但是随着Web文档的海量增长,仅靠专家人力地标记Web文档的可行性不大.
因此,这种方法在Web环境下显然是不适用的.
信息发布者对一个文档的标引在学术论文中很常见,通常作者会从论文中选出规范的、用以表示全文主题内容信息的单词或术语作为这篇论文的关键字列在论文中.
比如,文献[8]的关键字为:"WorldWideWeb","SearchEngine","InformationRetrieval","PageRank","Google".
这些关键字就可以作为文献[8]的概念.
在Web环境下,作者同样可以把关键字发表在文档中,一种可行的方法就是写在Meta标签中,例如concept1,concept2.
但是并不是每个页面的作者都原意完成这种操作,因为它还没有像在学术论文中标记关键字一样成为规范,即使一个页面的作者不编辑Meta标签,也并不影响页面的显示和页面中的各种应用功能.
而且这一方法可能带来垃圾页面,比如作者出于其他目的,在Meta标签中添加和页面实际内容无关的概念,造成垃圾信息.
在Meta标签中堆砌关键字是垃圾页面经常采用的一种方法.
因此这种标记概念的方法虽然比由专家标记的可行性大,但是也并不完全适用于Web环境.
普通用户对Web文档进行添加标签是最适用于Web环境的一种应用模式.
这一模式起源于美味标签(del.
icio.
us)和Flickr(www.
flickr.
com).
美味标签提供了用户对一个网页添加标签的功能.
比如用户A对网站tomcat.
apache.
org添加了三个标签,"Java","Software","WebServer";用户B对这个网站加的标签是"Apache","WebServer","Java";最后经过统计,出现频率最高的标签"Java","WebServer","Apache"就作为这个文档的Folksonomy的概念.
通过统计用户添加的标签,是获取Folksonomy概念的最简单和有效的途径.
采用统计出现频率高的标签,可以有效的抑制一些非法用户添加的恶意概念.
在我们设计开发的WizAg智能RSS新闻聚合搜索平台(www.
wizag.
com)中,提供用户对每个RSS新闻文档添加标签的功能,通过统计这些标签出现的频率,可以作为一篇新闻文档的Folksonomy概念;在第四章中,将详细介绍这种用户添加的Folksonomy概念对RSS新闻文档排名的影响.
在我们开发的浏览器插件中,通过浏览器的支持,可以为用户提供对任何网页添加标签的功能.
在第五章中,将详细介绍这种添加标签的方法.
西北工业大学硕士学位论文第三章搜索排序算法研究3.
2.
3基于概念的权重PageRank改进算法设计在改进算法中,考虑一个页面与它所指向的所有页面之间的相似程度,按权重分配这个页面的PageRank值,并且考虑用户当前正在搜索的关键字,在这里认为用户正在搜索的关键字为一个概念.
改进后的算法描述如下:假设有一个页面A,它通过超链接指向若干个页面,再设Concept(A)为页面A的概念的集合,Out(A)为页面A通过自身页面内的超链接所指向的其他页面的集合,设Out(A)={p1,p2,…,pn};C(A)表示页面A指向其他页面的链接个数,在这里C(A)=n;可以定义一个平分因子d',用于给那些概念和页面A完全不相关的页面分配一定比例的PageRank值.
可以定义页面pi从页面A获取的PageRank值为:PR'(pi)=PR(A)*d'*(1/C(A))+PR(A)*(1–d')*wi其中wi就是页面A和页面pi基于概念的权重.
则一个页面的PageRank值的计算公式可以改进为:PR(A)=(1-d)+d(PR'(T1)+…+PR'(Tn))分别定义用户搜索关键字(假设为K)K∈Concept(A)和KConcept(A)情况下的wi:当K∈Concept(A)时,wi的定义:初始时令count=0;对于每一个Out(A)中的元素pi,如果K∈Concept(pi),则count++;上述操作结束后,如果K∈Concept(pi),wi=1/count;如果KConcept(pi),wi=0.
当KConcept(A),wi的定义:设Ni=|Concept(A)∩Concept(pi)|(i=1,2,…,n),即页面A的概念集合和页面pi的概念集合的交集的元素个数;令wi为页面pi和页面A的权重值,则可定义),.
.
.
,2,1(1niNNwniiii==∑=.
例如,对图3-3所示的网络拓朴结构可分别计算页面p1,p2,p3从页面A处获得的PageRank值.
假设PR(A)=1,d=0.
85,d'=0.
2.
(1)根据经典PageRank计算公式,可算出:PR(p1)=PR(p2)=PR(p3)=(1-0.
85)+0.
85*1*(1/3)=0.
43333333(2)根据基于概念的权重PageRank公式,计算过程如下:假设用户搜索的概念为C1:PR(p1)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*(1/2))=17西北工业大学硕士学位论文第三章搜索排序算法研究0.
54666667PR(p2)=PR(p1)=0.
54666667PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*0)=0.
20666667可以看出,由于p1,p2页面含有搜索的概念C1,因此从页面A获得了更多的PageRank值.
而p3只获得了平分的PageRank值.
假设用户搜索的概念为C4:PR(p1)=PR(p2)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*0)=0.
20666667PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*1)=0.
88666667可以看出,由于只有p3页面含有搜索的概念C4,因此p3从页面A获得了更多的PageRank值.
p1,p2只获得了平分的PageRank值.
图3-3基于概念的权值PageRank分配示意图假设用户搜索的概念为C5,即用户搜索概念不在页面A的概念集合中:PR(p1)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(2/7))=0.
40095238PR(p2)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(3/7))=0.
49809524PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(2/7))=0.
40095238由于用户搜索的概念没有出现在页面A中,因此页面A按照和其指向的各个页面的概念相似程度,按权重分配了自己的PageRank值.
18西北工业大学硕士学位论文第三章搜索排序算法研究3.
3基于用户反馈的结果归并算法在2.
2.
3节中已经介绍了元搜索引擎的基本概念.
其中提到元搜索引擎的一个重要组成部分是进行结果收集后的统一显示.
常见的元搜索引擎结果融合策略有:直接将各独立搜索引擎的结果合并显示,按各独立搜索引擎响应时间的先后顺序返回,摘要排序法,位置排序法,摘要/位置排序法,星级体系排序法等[5,13].
以上排序方法都是按照客观因素进行排名的,比如响应时间,文档词频,链接在各个独立搜索引擎的排名位置,独立搜索引擎搜索到相同链接的次数等.
这些排名方法都没有考虑用户的搜索行为,即用户对搜索结果的评价.
为了提高元搜索引擎的查准率,本节提出一种结合用户反馈的元搜索结果归并方法.
该方法的特点在于记录用户反馈,结合用户兴趣爱好和客观因素进行综合排名,在第四章中将介绍一种类似的新闻综合排名算法.
基于用户反馈的元搜索引擎模型在原有元搜索引擎模型的三个组成部分上,增加了数据库,知识库,WordNet语义字典模块,如图3-4所示.
结果显示代理将查询结果返回给用户,同时把用户的行为信息记录到数据库中.
通过统计分析数据库上的这些用户行为,结合WordNet语义字典和知识库对搜索关键字进行聚类,计算搜索引擎质量分值,形成搜索引擎选择策略,指导请求提交代理选择调用独立的搜索引擎.
在进行结果归并时,通过记录的用户行为信息,可以计算用户评价分值,作为结果归并时的主观影响因子.
如图3-4基于用户反馈的元搜索引擎体系结构图首先取回各个独立搜索引擎返回的查询结果,去除重复的链接,设链接集合19西北工业大学硕士学位论文第三章搜索排序算法研究为RUrl={Url1,Url2,…,Urlm}.
搜索结果链接Urlj(针对搜索关键字Ki)的用户评价分值:RUrl)(Url)Url,ect(KValueInDir*d+)Url,t(KValueDirec*d=)Url,Value(Kjji2jiiji∈)RUrl),(KClickCountMin()Url,(KClickCount*d*EXP((-1)-1)Url,t(KValueDirecijiji=))Url,'t(KValueDirec*)'K,Sim(K(*e*EXP((-1)-1)Url,ect(KValueInDir'jiiiji∑∈=KiSimSetKi用户评价分值(Value(Ki,Urlj))是用户直接评价分值(ValueDirect(Ki,Urlj))与用户间接评价分值(ValueInDirect(Ki,Urlj))之和.
用户直接评价分值考虑用户点击Ki的搜索结果链接的情况.
设ClickCount(Ki,Urlj)为用户点击搜索关键字Ki的结果集中链接Urlj的次数之和;Min(ClickCount(Ki,RUrl))表示用户点击搜索关键字Ki的结果集中任一链接的最小的次数.
d为可调节系数,根据不同情况可以设定不同的值,一般可以取0.
1~0.
5;选择指数函数归一化.
用户间接评价分值考虑用户点击与搜索关键字Ki相似的关键字集合Ki'的点击情况.
集合KiSimSet={Ki'|Sim(Ki,Ki')>M},即与Ki的相似度大于阈值M的关键字集合.
Sim(Ki,Ki')是Ki与Ki'之间的相似度计算函数,可以借助基于WordNet语义词典的词语相似度计算软件,比如WordNet::Similarity,计算出搜索关键字之间的相似度数值;e为可调节系数,根据不同情况可以设定不同的值,一般可以取0.
1~0.
5;选择指数函数归一化.
]14[为了达到较高的综合查准率,元搜索引擎的结果归并策略应该结合客观和主观两方面因素,因此对元搜索的结果归并排序公式可以做如下统一的定义:搜索结果链接Urlj(针对搜索关键字Ki)的归并排名值:RankValue(Ki,Urlj)=a*Object(Ki,Urlj)+b*Subject(Ki,Urlj)Object(Ki,Urlj)代表归一化后的客观排名影响因子,可以包括上述提到的摘要排序值,位置排序值,星级体系排序值等等;Subject(Ki,Urlj)代表用户对结果链接Urlj的主观排名影响因子,即用户评价分值Value(Ki,Urlj).
a,b为可调节系数,元搜索引擎可以根据不同的查询关键字,不同的查询领域,控制主客观排名影响因子所占的比例.
例如,在专业搜索领域,元搜索引擎调用专业搜索引擎搜索,由于进行专业搜索的用户大部分具有该领域的专业知识,因此,用户对搜索结果的评价意义较大,可以加大主观影响因子;而在一般的通用搜索领域,用户对搜索结果的评价意义可能不如前者大,而且可能存在噪音的影响,因此可以加20西北工业大学硕士学位论文第三章搜索排序算法研究21大客观影响因子.
元搜索的结果显示代理通过计算每个链接的归并排名值,按从高到低的顺序把结果集返回给用户,完成结果归并.
在第四章的RSS新闻搜索平台的新闻排名规则中的主观排名因子设计,就借鉴了这一基于用户反馈的排序算法.
3.
4小结本章首先介绍传统了经典搜索引擎算法PageRank和HITS,并对其优缺点进行了对比.
针对原有PageRank算法采用的平分页面自身PageRank值的策略,提出了一种按权值分配的改进算法.
权值由页面间的概念关联比重和用户的搜索概念确定.
结合参加的项目经验,分别提出了主观和客观两种选择概念的策略.
最后,提出一种基于用户反馈的元搜索模型,并在此模型基础上提出一种元搜索引擎结果归并算法.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现第四章RSS新闻搜索平台的设计与实现RSS新闻是当前Web实时信息的一种主要发布形式.
它是站点用来和其他站点之间共享内容的一种简易方式,通常被用于新闻网站.
当前,各大新闻网站,门户网站,甚至一些个人Blog都提供了RSS服务,该服务已经成为网络中最热门的服务之一.
一些主流新闻网站的RSS更新周期非常的小,几乎每时每刻都有新的RSS种子诞生.
为了提供强有力的RSS新闻浏览,聚合,搜索功能,我们设计开发了智能RSS新闻聚合搜索平台.
本章详细介绍平台的体系结构,存储结构设计,搜索排名机制和性能优化方法.
4.
1RSS新闻搜索平台基本框架平台采用浏览器/服务器构架.
平台的体系结构如图4.
1所示.
服务器1:RSS新闻搜索下载,概念抽取,排序服务程序.
服务器3:数据库服务器,运行数据库B(只读)服务器2:数据库服务器运行数据库A(可读,可写)服务器4:Web服务器浏览器浏览器浏览器浏览器互联网(提供RSS服务的网站)图4.
1RSS新闻搜索平台体系结构图服务器1:运行一系列RSS新闻搜集下载综合服务程序.
RSS新闻搜索下载22西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现23服务程序按照一定的搜索规则,在互联网上找到RSS种子,定时自动更新下载其包含的新闻信息,并保存到服务器2上的数据库A中;RSS新闻概念抽取服务程序对下载的新闻主体进行概念抽取,抽取的规则基本按照3.
2.
1节中提到的基于网页内容的概念抽取方法进行;RSS新闻排序服务程序对下载下来的新的RSS新闻,结合其相应的概念,按照特定的排序规则进行排名,并将排序值更新到数据库A中.
服务器2:一台数据库服务器,运行着数据库管理系统,维护一个可读可写的数据库A.
它保存着所有的RSS新闻信息,数据备份,相关参数.
服务器3:一台数据库服务器,但它运行的是一个只读数据库.
主要用来为Web服务器提供数据.
这台数据库的更新是由数据库服务器A控制的,当数据库服务器A中有的数据有变化,按照一定的规则,数据库A把新的内容复制到数据库B中,并把数据库B中过时的数据清除.
服务器4:一台Web服务器,运行着整个网络应用程序.
它从服务器3中的只读数据库B中读取数据,动态生成Web页面显示给用户.
用户的反馈信息通过浏览器传到Web服务器,再由Web服务器写入服务器2的可写数据库A.
服务器1,服务器2,服务器3,服务器4在同一个局域网内.
浏览器:用户通过浏览器访问Web服务器,获取Web页面进行浏览.
用户的反馈操作通过浏览器返回给Web服务器.
4.
2数据管理结构设计与实现由于平台设计的关系繁多,数据类型规范,数据存储量增长较快,因此选用关系型数据库作为平台数据的数据管理模型.
由于平台涉及两个数据库服务器,在局域网内构成分布式数据库结构.
为了降低分布式数据库的复杂性,服务器2,3上的数据库选用同一种数据库管理系统,构成同构同质型分布式数据库.
在实现中,数据库管理系统选用的是MicrosoftSQLServer2000.
RSS新闻搜索平台的搜索对象是新闻文章,相对与传统搜索引擎系统中的网页.
本节首先分析介绍关系数据库设计的基本原则,然后分析新闻搜集下载服务程序下载到的RSS种子(feeds)的XML文档;然后建立一个泛关系模型,包含一篇文章的所有属性,分析该模式包含的函数依赖,并对泛关系进行模式分解;最后建立实体关系模型.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现244.
2.
1关系数据库模式设计原则在关系数据库中占据核心地位的是关系,在实现中以表的形式表现出来.
衡量关系模式好坏的标准是模式的范式.
范式的种类于数据依赖有着直接的联系.
基于函数依赖的范式有1NF,2NF,3NF,BCNF等.
1NF要求每个属性值都是不可再分的原子值;2NF要求每个非主属性完全函数依赖于候选键;3NF要求每个非主属性都不传递依赖于候选键;BCNF要求每个属性都不传递依赖于候选键.
对于更复杂的数据模型,还有针对多值函数依赖的4NF,针对连接依赖的5NF等.
关系模式设计可能在一开始设计的是包含所有属性的泛关系,或者由于用户需求的变更导致关系模式的修改,这些情况下都无法到到必要的范式要求,这时就需要对关系进行模式分解.
在关系模式分解过程中要保证数据等价和语义等价.
数据等价需要通过保证无损连接分解实现,而语义等价需要通过保持函数依赖实现.
范式的提出是为了在函数依赖保持的前提下尽可能的避免数据冗余.
然而随着硬件价格的下跌,海量存储技术的出现,使得在一些应用场合允许出现一定的数据冗余.
比如,通过一定的数据冗余来提高速度和性能,因此可以适当的使用非规范化的模式提高特定操作的性能,以支持对响应时间要求苛求的操作.
4.
2.
2RSS种子文档的结构分析一个RSS新闻信息常常包含一个标题和一个主体信息,通常还包含指向这个完整信息的超链接.
用户可以首先浏览新闻标题和简要的主体信息,如果发现该文章有趣,可以点击该新闻的超链接查看新闻全文.
当前主流网站提供的RSS种子通常是一个XML文档.
发布新闻的网站定时更新XML文档的内容,发布最新的新闻信息,就好像通讯社每天都发布新的通信稿.
通过分析每个种子的XML文档,可以获取新闻文章的全部属性.
每个RSS种子通常有一个名字,它所指向的XML通常由一个超链接定位.
例如种子SlateMagazine,它的XML位置为http://www.
slate.
com/rss/,图4-2是该种子在2006年12月30日的快照.
如图4-2所示,每个XML文档通常包含若种子的描述信息和若干篇新闻;每篇新闻通常是由item标签标记的,每个item内又包括标题,简要的描述,新闻发布时间,和指向这篇新闻完整内容的超链接,同时还可能包括一些扩展信息,例如类别信息,文章的作者等.
当RSS新闻搜索下载程序将种子的XML文档下载西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现完成后,需要对XML文档进行分析,把每个item的详细信息提取出来,构成一篇篇新闻文章.
图4-2RSS种子文档示意图(SlateMagzine2006-12-30)新闻文章下载完成后,经过RSS新闻概念抽取服务程序对每篇新闻文章的描述进行了概念抽取过程,每篇文章还有对应的若干个概念.
因此一篇文章的全部属性可以表示为:ArtitlesR(Title,Description,PubDate,Link,RssFeedsName,RssFeedsLink,Concepts)但是如果以这样的模式把新闻文章存储到数据库中,会导致大量的数据冗余,容易导致不一致性的发生.
如图4-3所示,如果一篇文章的描述抽取出了若干个概念,则这篇文章的基本信息(Title,Description,PubDate,LinkRssFeedsName,RssFeedsLink)都会冗余存储,例如图4-3中1至7行记录的是同一篇文章,但是由于这篇文章的描述信息抽出了七个概念,因此导致数据冗余;同时,如果两篇不同的新闻对应的描述相同,那么这两篇新闻的描述和概念(Title,Descripton,Concepts)也发生了数据冗余,比如第1至7行的一篇文章和第22至28行的一篇文章就发生了此类冗余.
25西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现图4-3ArticlesR的关系图模式ArticlesR包含了一个新闻文章应该包含的所有属性,可以认为该关系是一个泛关系,可以用关系数据库的规范化原则对这个泛关系进行模式分解,得到规范化的模式.
在下一节中,我们使用实体关系模型对新闻文章建模.
4.
2.
3设计实体关系模式经过对RSS种子文档的分析,我们可以确定在搜索平台中最常用到的四个实体.
实体的定义分别为RSS种子(RssFeeds),新闻文章(Articles),描述信息(Descriptions),概念(Concepts).
这四个实体是平台应用的核心,其他所有的应用都是围绕着这四个实体展开的.
实体Rss种子的属性包括:种子的名字(RssFeedsName),指向该种子XML文档的超链接(RssFeedsLink).
实体新闻文章的属性包括:新闻发布时间(PubDate),和指向这篇新闻完整内容的超链接(Link),包含文章标题和描述的描述信息.
实体描述信息的属性包括:标题(Title),简要的描述(Description).
实体概念的属性包括:概念的内容(Concepts),出现这个概念的文章数(Count).
关系的定义为:种子包含文章关系(R_RssArticles),包括实体Rss种子和实体新闻文章.
一个种子可以包含若干篇新闻文章,一篇新闻文章也可能来源于多个种子,是一个多对多的关系.
文章包含描述关系(R_ArticlesDescriptions),包括实体新闻文章和实体描述信息.
一篇新闻文章只对应一个描述信息,但是一个描述信息可能对应多篇新闻文章,即多篇新闻文章的内容可能是重复的,是一个多对26西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现一的关系.
描述信息对应概念关系(R_DescriptionConcepts),包括实体描述信息和实体概念.
一个描述信息按照概念抽取算法可能抽取若干个概念,而一个概念可能由多个描述中都抽取出来,是一个多对多的关系.
最后建立实体关系模型图,如图4-4所示.
MM1NNNRssFeedsR_RssArticlesArticlesR_ArticlesDescriptionsDescriptionsR_DescriptionConceptsConcepts图4-4新闻文章的实体关系模型图4.
2.
4表的模式设计在实体关系模型的基础上进行关系的模式设计,首先针对实体进行模式设计:RssFeeds(RssFeedsLink,RssFeedsName)Articles(Link,PubDate,Title,Description)Descriptions(Title,Descritpion)Concepts(Concepts,Count)在这些模式上的函数依赖分别为:RssFeeds:RssFeedsLink->RssFeedsNameArticles:Link->PubDate,Title,Description该模式设计的每个属性已经是原子的,符合1NF规范.
同时,不存在属性传递依赖于主属性,符合BCNF规范.
虽然每个实体中已经可以选取适当的属性作为主键,但是这些属性的数据类型都是字符类型.
当实体通过关系表连接时,可能用到大量的连接操作,连接操作如果在字符类型的属性上进行,需要进行大量的字符串匹配算法,必将严重影响连接的效率,因此在这里对每个实体都加入一个整型的自动编号属性作为主键.
由于R_ArticlesDescriptions关系是多对一的关27西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现28系,因此在模式设计时,可以不单独把这个关系设计为一个表,而把"多"的那个实体表的主键作为外键加入到"一"的实体属性里,因此,经过修改的实体表模式设计为:RssFeeds(RssFeedsId,RssFeedsLink,RssFeedsName)Articles(AritlcesId,Link,PubDate,DescriptionId)Descriptions(DescriptionId,Title,Descritpion)Concepts(ConceptsId,Concepts,Count)在这里,每个实体表都必须满足实体完整性约束,即每个表的主键都不能为空.
由于我们对每个实体都选用了自动编号的属性作为主键,因此主键都不会为空.
为了更好的从语义上保证实体完整性,要求RssFeeds的属性RssFeedsLink不能为空;Articles的属性Link不能为空;Descriptions的属性Title和Description不能同时为空;Concepts的属性Concepts不能为空.
同时,Articles表还要保证参照完整性,即Articles的属性DescriptionId是参照Descriptions的外码.
在实体表的基础上,对实体关系模型中的多对多的关系进行模式设计.
R_DescriptionConcepts(DescriptionId,ConceptsId)R_RssArticles(RssFeedsId,ArticlesId)这两个关系表的属性必须满足参照完整性.
即R_DescriptionConcepts的属性DescriptionId是参照Descriptions的外码,属性ConceptsId是参照Concepts的外码;R_RssArticles的属性RssFeedsId是参照RssFeeds的外码,属性ArticlesId是参照Articles的外码.
在4.
2.
2节中我们看到,一篇新闻文章包含的全部信息应该是模式ArticlesR包含的属性.
在本节设计的模式基础上,需要进行连接查询得到新闻文章的所有属性.
得到新闻文章的基本信息的操作如下:PrpjectArticlesId,Title,Description,PubDate,Link(ArticlesNATURALJOINDescriptions)得到新闻文章对应的种子信息的操作如下:PrpjectArticlesId,RssFeedsId,RssFeedsName(ArticlesNATURALJOINR_RssArticlesNATURALJOINRssFeeds)得到新闻文章对应的概念的操作如下:PrpjectArticlesId,ConceptsId,Concepts(ArticlesNATURALJOINDescriptionsNATURALJOINConcepts)以上三个查询可以分别查询得到文章的基本信息,文章对应的种子信息,文章对应的概念.
下一节将介绍使用存储过程将每一个查询封装起来,提供给Web服务器上的Web应用程序调用的方法.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现4.
2.
5存储过程接口设计在关系数据库的实现中,上一节提到的三个关系代数查询可以方便的转化成说明性查询语言SQL的查询语句集.
Web应用程序可以通过将拼接好的SQL查询串发送给数据库管理系统,获取相应的数据.
同时也可以调用存储过程获取相应的数据.
存储过程是一组为了完成特定功能的SQL语句集,经编译后存储在数据库中.
存储过程是数据库中的一个重要对象,任何一个设计良好的数据库应用程序都应该用到存储过程.
存储过程具有以下优点:存储过程允许标准组件式编程;能够实现较快的执行速度;能够减少网络流量;可被作为一种安全机制来充分利用.
如图4-5所示,存储过程ShowArticlesInfos的功能是提供给Web应用所需要的全图4-5存储过程实例程序代码部信息.
Web应用可能会按照用户的要求,选择查看不同的新闻文章.
比如用户要求查看最近两天的文章,存储过程中的参数@Date就可以传递一个时间参数到存储过程内.
通过参数的设置,可以使Web应用的数据库调用不受影响,和数据库之间的交互变得更加透明.
作为数据库开发人员,只要更改存储过程体内的SQL29西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现语句段,提供给Web应用程序就可以了.
在平台的设计中,Web应用程序读取数据库的相关内容显示在页面,用户通过Web应用程序做的反馈信息,RSS新闻搜索下载,概念抽取,排序服务程序对数据库的数据更新,排序,删除等操作都通过存储过程完成.
根据需求分析的结果,Web应用中显示的页面需要通过数据库获取的数据有如下几种:(1)显示最近n天的新闻文章,并且按每页m条新闻,分页显示.
(2)显示种子i的最近n天的新闻文章.
(3)显示包含某个概念i的最近n天的新闻文章.
(4)显示包含某一指定字符串string的所有新闻文章.
在Web应用中,提供了很多用户反馈的方式.
比如添加Tag,加评论,还有投票标注等.
用户反馈的信息需要返回到数据库记录,这些信息用于再现用户的反馈,并且这些反馈信息对排序也有贡献,详细内容将在4.
3节中介绍.
用户的反馈也通过存储过程的方法与数据库交互.
(5)用户a对新闻文章i添加Tag,Tag的内容为'tagcontent'(6)用户a对新闻文章i添加评论信息,评论信息的内容为'commentcontent'(7)用户a对新闻文章i投票标注.
30西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现RSS新闻搜索下载,概念抽取,排序服务程序的数据库接口设计:(8)下载新的新闻文章,保存到数据库.
(9)对新下载的文章抽取概念,保存到数据库.
(10)对文章计算排名.
4.
3搜索操作的性能优化RSS新闻搜索下载服务程序每天都在下载大量的新闻文章,并存储到数据库中.
由于新闻文章的增多,相应的概念也会大量增加,这都导致了数据库的数据量增长迅速.
随着数据量的增长,使数据库的性能也有所下降.
在RSS新闻搜索平台中的一些需要与用户实时交互的搜索操作,速度快甚至比结果准确更重要.
如果让用户等待的时间过长,会使用户产生厌烦心理.
因此,本节主要研究如何提高数据库的性能,特别是提高特定查询的性能.
4.
3.
1针对查询建立索引在RSS新闻搜索平台中,用户最常使用的是进行多种方式的查询.
为了提高查询速度,针对特定查询建立索引是必要的.
最常用的查询就是显示文章的所有基本信息,这个操作用到若干表的连接操作.
因此需要在每个表的连接属性上建立聚集索引.
针对连接ArticlesNATURALJOINR_RssArticlesNATURALJOINRssFeeds和连接ArticlesNATURALJOINDescriptionsNATURALJOINConcepts,需要对Articles表,R_RssArticles表,RssFeeds表,Descriptions表,Concepts表连接所需的属性建立索引.
而这些连接所需的属性恰好是这些表的主键,因此在这些表的主键上建立聚集索引,可以提高查询速度.
另一类常用的查询涉及到概念.
一种查询操作是通过文章查找这个文章包含31西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现的所有概念,用于Web页面的显示.
另一种是由概念查找包含这个概念的所有新闻文章,即查看同一主题的相关文章.
针对这两类查询,需要建立两个索引,Descriptions->Concepts的DCI索引和Concepts->Descriptions的CDI的索引.
假设有四篇新闻,其包含的概念分别为:News1(MiddleEast,BushAdministration)News2(SaddamHussein,MiddleEast,BushAdministration)News3(NorthKorea,NuclearTest)News4(DiplomaticEffort,BushAdministration,NuclearTest)DCI索引较为常见,可以通过在R_DescriptionConcepts表上的DescriptionId属性上建立聚集索引就可以实现,图4-6是一个简单的DCI示意图.
而CDI索引可以认为是一种倒排索引,每个索引项包含一个概念和一组指针,指针指向包含该概念的所有新闻文章,如图4-7所示,当用户想查看和"nucleartest"相关新闻时,可以快速的通过CDI查找到新闻文档New3和News4.
CDI索引类似搜索引擎中索引器建立的索引,但是索引器建立倒排索引的索引项是针对页面中的每一个词,而CDI的索引项针对的是概念.
这一索引的实现是通过建立一个新的表R_ConceptsDescription(ConceptsId,DescriptionsId),并在ConceptsId上建立聚集索引.
News1News2News3News4MiddleEastSaddamHusseinNorthKoreaDiplomaticEffortBushAdministrationNuclearTestMiddleEastBushAdministrationBushAdministrationNuclearTest图4-6DCI索引示意图32西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现BushAdministration334.
3.
2拆分大表经过服务器上的统计,服务器1上的RSS新闻下载服务程序每天下载的文章数在新近下载的新闻文章信息,即按时间比较方便,当新的一个月开始时,就可以执行与如图4-9所示图4-7CDI索引示意图2~3万之间,最多一天的文章下载数量是近5万篇.
这样存储新闻文章基本信息的表就会迅速增长,例如文章基本信息Articles表,描述的基本信息Descriptions表.
而几乎所有的查询都要涉及到这两个表,而且大部分查询都要用到连接操作.
每次操作数据库都需要把表从磁盘读到缓冲区,随着表的增大,访问磁盘的次数增多,必将导致性能严重下降.
根据需求,Web应用程序访问最多的数据是顺序进行查询.
因此,可以按照时间,把数据量大的表拆分成小表.
拆分的规则为把现有的大表,按时间间隔(比如一个月时间)拆分成若干小表,如图4-8所示.
Articles表按时间的拆分可以通过SQL语句实现,比如生成Articles_2表的实现如图4-9所示.
按时间拆分的控制类似的SQL语句完成.
执行的时机可以借助触发器完成,但是由于触发器会带给数据库额外的负担,因此在实现中选择使用的方法是通过外部程序调用,即通过RSS新闻下载程序在每个月开始时,调用相应SQL语句完成对大表的拆分.
MiddleEastNuclearTestSaddamHusseinNorthKoreaDiplomaticEffortNews1News2News4News1News2News3News4News2News3News4西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现.
.
.
Articles表.
包含了一年的所有新闻文章基本信息数据.
Articles_1表.
包含1月份的数据Articles_2表.
包含2月份的数据Articles_12表.
包含12月份的数据图4-8对Articles表按时间的拆分示意图图4-9按时间拆分Articles表的SQL实现按时间拆分是拆分的一种规则,还可以按其他规则进行拆分.
按照服务器上的统计信息,按种子查询的概率仅次于按时间查询,例如在Web应用中,用户经常选择查看某一特定种子的新闻.
因此可以通过文章来自的种子进行拆分,如图4-10所示.
Articles表按种子的拆分可以通过SQL语句实现,比如生成Articles_TechCrunch表的实现如图4-11所示.
按种子拆分的规则不仅可以达到按时间拆分规则的效果,还可以作为一种数据分片的原则应用在分布式数据库中.
比如可以把所有中文种子的小表分配到中国的数据库服务器中,把所有日文种子的小表分配到日本的数据库服务器中,这样减少物理网络传送时间,达到提高速度的目的.
对Articles表的拆分结束后,需要把和Articles关联密切,查询经常使用的的表也进行拆分.
例如经常有查询用到ArticlesNATURALJOINR_RssArticles和34西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现ArticlesNATURALJOINDescriptions这两个连接操作.
如果仅仅保证Articles用小表,而和它连接的表依然是大表,大表的频繁磁盘读写使连接速度依然较慢.
因此,需要对R_RssArticles和Descriptions表进行拆分,拆分策略依赖于Articles表的拆分策略.
如果Articles表按时间拆分,则R_RssArticle和Descriptions表也按时间拆分,例如R_RssArticles_2,Descriptions_2表对应Articles_2表,仅包含Articles_2表对应的文章;如果Articles表按种子拆分,则R_RssArticle和Descriptions表也按种子拆分,例如R_RssArticles_TechCrunch,Descriptions_TechCrunch表对应Articles_TechCrunch表,仅包含Articles_TechCrunch表对应的文章.
R_RssArticles表和Descriptions表的拆分SQL实现方法类似于Articles表,这里不在赘述.
.
.
.
Articles表.
包含了所有种子的新闻文章基本信息数据.
Articles_Digg表.
包含种子Digg的数据Articles_BoingBoing表.
包含种子BoingBoing的数据Articles_TechCrunch表.
包含种子TechCrunch的数据图4-10对Articles表按来源种子的拆分示意图图4-11按来源种子拆分Articles表的SQL实现35西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现36拆分时需要考虑的一点是使大部分的查询在某一个拆分后的小表上可以实现,这样可以明显减少磁盘定位和缓冲区换入换出的代价,因此这样拆分大表对性能提高有明显帮助.
如果拆分的表过于小,使得大部分查询都要涉及多个小表,反而会影响查询的性能.
同时,表拆分的过多会使表本身变多,增大数据库管理系统的系统表和系统负担.
拆分的规则可以视具体情况而定,如果一个月的数据量仍然很大,可以考虑按周拆分;如果按每个种子拆分,有的种子对应的文章太少的话,可以按多个种子进行合并拆分.
4.
3.
3解除规范化设计把一个规范化的模式变化为非规范化的过程被称为解除规范化.
在硬件存储设备的价格急剧下降的情况下,允许一定量的数据冗余来提高响应速度是可取的,是一种空间换取时间的策略.
考虑Web应用最常使用的新闻文章数据.
当用户通过URL(www.
wizag.
com)访问站点,首先呈现给用户的就是网站的首页.
首页显示速度的快慢,直接影响用户对该网站的信心.
如果每次首页显示的数据都要通过若干连接才能找到,首页显示的速度无疑会很慢,因为即时使用了索引,在数据量相当大的情况下,连接操作比选择操作还是要慢很多.
在这种情况下,可以考虑使用在4.
2.
2节中涉及的ArticlesR关系模式.
因为在这个关系模式上,直接进行选择就可以提供给Web应用需要的所有数据,而不需要再进行连接操作.
这就需要对原有模式进行解除规范化.
在实现中,建立一个ArticlesR关系模式的表ArticlesCache.
命名为Cache的原因是因为这个表不代表一个实体,仅仅是因为性能的需要,提供的一个中间结果表.
不需要把所有的Articles表的数据全部存在ArticlesCache表中,这样就失去了使用规范化设计的Articles表的意义.
结合4.
3.
2的按时间拆分的思想,可以把最近若干天(例如七天)的新闻文章信息保存在ArticlesCache表中.
ArticlesCache表的最方便的实现是使用物化视图,随着新的新闻数据的到来,物化视图可以自动更新,不需要其它介入.
另一种方法就是定时更新,删除旧的ArticlesCache表,在新数据的基础上,生成新的ArticlesCache表.
由于SQLServer2000对物化视图的支持不完善,在该平台的实现中采取的是后一种策略.
实现依然采用SQL代码,如图4-12所示.
这样查询本身的耗时就是在一个表上的选择操作,和连接操作相比,耗时已经非常小了.
如果服务器的内存足够大,可以把ArticlesCache表一直加载在内存中,西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现设立较高的优先级,使得数据库管理系统的缓冲区交换策略不能将此块内容换出.
这样这一查询操作不涉及磁盘的读操作,速度会更快.
如果内存不够大,可以适当调小ArticlesCache表的大小,比如可以把近三天,近一天的内容一直加载在内存中.
在内存极端紧张的情况下,可以把首页需要显示的若干新闻文章的信息加载到内存,使得首页所需数据的快速显示.
在SQLServer2000中,通过DBCC命令,可以完成强制加载一个表在内存而不换出的功能.
图4-12生成ArticlesCache表的SQL实现解除规范化设计可能带来的缺点就是数据的不一致性.
在搜索平台中,新闻文章下载完成后,没有操作去修改文章的内容.
因此,只要保证生成ArticlesCache表时数据一致,在以后的正常操作中,不会发生不一致现象的出现.
即时由于非法操作导致了数据不一致,在下一次生成ArticlesCache后就可以恢复,短暂时间的数据不一致性不会对平台带来致命的影响,因为毕竟RSS新闻搜索平台对数据一致性的要求没有银行系统那么严格.
关于数据一致性的问题其他问题,在下一节通过设定事务的隔离级别来详细讨论.
4.
3.
4事务隔离级别设定37在关系数据库中,在没有指定事务的情况下,认为每条SQL语句的执行都是一个事务.
事务具有ACID性质,即原子性,一致性,隔离性和持久性.
原子性要求西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现事务内的操作要么全部执行,要么什么都不做,由数据库管理系统的事务管理子系统实现;一致性要求事务的执行不能带来不一致的数据;隔离性要求并发执行的多个事务的正确性,由数据库管理系统的并发控制子系统实现;持久性要求事务一旦完成,所有更新永久的反映在数据库中,由数据库管理系统的恢复管理子系统完成[15].
SQL2提供事务的四种隔离级别,由高到低分别为:SERIALIZABLE:保证并发的事务是可串行化的.
是系统默认的级别.
REPEATABLEREAD:只允许事务读已提交的数据,并且要求共享锁一直保留到事务结束.
READCOMMITTED:允许事务读已提交的数据.
READUNCOMMITTED:允许事务读未提交的数据.
在SQL中可以设置一次数据库连接的事务级别,如图4-13所示.
图4-13设定事务隔离级别的SQL语句示例为了保证事务的隔离性,数据库采用封锁机制,对一个资源的读操作,DBMS加共享锁;对一个资源的写操作,DBMS加排它锁.
共享锁之间是相容的,而共享锁与排它锁之间,排它锁和排它锁之间都是相斥的.
当多个事务争用一个资源时,可能导致某个事务的长时间等待,饿死,甚至带来死锁.
考虑平台的如下情况:当RSS新闻下载服务程序下载了新的文章后,要进行INSERT操作插入到数据库中,这时需要对Articles表加排他锁.
而如果这时来了查询操作,需要进行对表Articles的查询,查询操作必须等待下载服务程序对数据库的插入操作全部结束.
平均每次下载文章是1000篇左右,插入到数据库的时间可能需要5~10秒中.
这样,查询操作就可能需要等待5~10秒中后进行.
同样,当RSS新闻排序服务程序在运行排序计算时,需要对Articles表进行UPDATE操作,同样要进行加排他锁操作,而排序的计算时间更长,每次执行需要在30分钟左右,如果在30分钟内无法响应用户的查询,则这对整个Web应用来说是明显不合理的.
因此,为了保证查询的速度,可以选择适当的降低事务隔离级别.
把所有查询相关事务的隔离级别都设置成READUNCOMMITTED.
虽然这样可能导致查询结果有不一致的数据,但是和等待较长时间相比,对RSS搜索平台来说是一个合适的选择.
在图4-5所示的显示Web应用所需文章信息的存储过程实例程序代码中,就通过SQL语句降低了隔离级别.
通过降低隔离级别可以降低等待时间,提高响应速度.
但是对死锁的避免来38西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现说,则需要更多方面的考虑.
在用户增多,数据量增大,写操作和更新操作频繁的环境下,死锁发生的概率加大了.
考虑搜索平台一种状态,如图4-14所示.
假Transaction1:T1:ShareLock(A)T3:ExclusiveLock(Articles)T5:Release(A),Release(Articles)Transaction2:T2:ShareLock(Articles)T4:ExclusiveLock(A)T6:Release(Articles)Release(A)图4-14两个事务并行执行导致的死锁示意图设Transaction1是Rss新闻排名服务程序执行的事务,它准备更新Articles的排名,首先读取用户的反馈信息,对反馈表A加共享锁,然后再更新文章的排名信息,对Articles加排他锁,执行结束分别释放两个锁.
Transaction2是一个用户在浏览器中的反馈操作,用户首先查询相关新闻文章,对Articles表加了共享锁,然后对文章进行反馈,写入到反馈表A中,执行结束分别释放两个锁.
如果两个事务分别执行,不会发生死锁,但是当两个事务并行执行,T3时刻Transaction1无法对表Articles加排他锁,因为其正被Transaction2占用,Transaction1陷入等待;而T4时刻Transaction2无法对表A加排它锁,因为其正被Transaction1占用,Transaction2也陷入等待,系统进入死锁状态.
4.
3.
2节中的拆分大表策略在一定程度上降低了死锁发生的概率,因为如果一个表越大,访问到该表的事务的可能性就越大,发生冲突导致死锁的概率也就越大.
为了最大限度的避免死锁的发生,最终选用了分布式数据库策略.
在下一节中,详细介绍分布式数据库的部署.
4.
3.
5分布式数据库的部署由于用户在Web应用中的操作可以分为两类,一类是浏览新闻文章信息,即对数据库的读操作;另一类操作是用户的反馈行为,这些反馈信息需要记录到数据库,即对数据库的写操作,写操作还包括RSS新闻排序程序的更新排名操作.
当数据库对一个资源进行读操作时,数据库管理系统只对该资源加共享锁,而共39西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现享锁之间是互容的,即读和读操作不会产生死锁.
只有当读和写操作同时进行,或写和写操作同时进行时才可能出现死锁.
为了降低搜索平台争用同一资源造成的死锁现象,一个好的解决方案就是构造一个只读数据库,让Web应用的所有读操作都在只读数据库上进行,而写操作写到可写数据库中.
在图4-1的RSS新闻搜索平台体系结构图中,服务器3上运行的数据库B就是只读数据库,Web应用需要的所有新闻文章信息来自于该只读数据库,而写操作则直接写到可写数据库A中.
首先考虑分布式数据库的结构,如图4-15所示.
反馈浏览用户反馈的写操作发布发布服务器2:数据库A(可读,可写)服务器3:数据库B1(只读)服务器3:数据库B2(只读)数据库连接控制程序服务器4:Web服务器图4-15分布式数据库的结构图RSS新闻下载程序下载的数据保存到数据库A中,数据库A的数据是实时更新的.
新的一批新闻文章数据下载后,经过概念抽取,排序计算后,就可以被用户浏览了,这时需要将这批新闻文章发布到服务器3的只读数据库中,例如发布到B1,这时B1就是最新的只读数据库,数据库连接控制程序就会引导服务器4的Web服务器从B1中读取数据;这时,新的新闻的下载,概念抽取,排序操作依然在继续,当新的一批数据处理完毕后,数据库A的新数据又需要发布到只读数据库了,因为这时B1被数据库连接控制程序所占用,而B2是空闲的,因此新的数据被发布到B2.
发布成功后,B2上的数据是最新的,这时数据库连接控制程序会引导Web服务器从B2上读取数据.
而下次的发布将发送至空闲的B1.
依此40西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现类推,每次发布操作会选择一个空闲的只读数据库进行.
发布成功后由数据库连接控制程序引导Web服务器读取有最新数据的只读数据库.
而用户的反馈行为由用户在浏览器中发出,Web服务器接收到后发给数据库连接控制程序,该程序会将这些反馈直接写入到服务器2的数据库A中.
究竟发布哪些表到只读数据库是可以选择的,最简单的方法就是仅仅选择发送解除规范化设计的表ArticlesCache,这样大部分查询操作在这个表上就可以完成.
但是当用户访问不在ArticlesCache的新闻时,如果仍在只读数据库上查找,可能返回得结果就是空.
为了解决这个问题,一个方法是改动数据库连接控制程序,当用户要求读取的数据在只读数据库中不存在时,就要引导Web服务器去数据库A中读取数据,但是这一方法违背了建立分布式数据库的初衷,因此需要采用另一个方法,即选择发布多个表到只读数据库.
通过这些发布的表可以获取所有新闻的信息.
可以发现,要获得所有新闻的信息,Articles表,Descriptions表,RssArticles表,R_RssArticles表,R_DescriptionConcepts表需要定时发布到只读数据库中.
在实现中使用了SQLServer2000的分发,发布,订阅功能.
图4-15中的数据库A做发布和分发数据库,数据库B1,B2做订阅数据库.
具体配置方法这里不再赘述.
在4.
3.
2中提到,按种子的语言对Articles表进行分表,可以把数据分到不同物理位置的数据库服务器中,此分布式系统构架如图4-16所示.
.
.
.
.
.
.
数据库B数据库B3中文种子数据数据库B4日文种子数据数据库B5德文种子数据Web服务器C3(位于中国)Web服务器C4(位于日本)Web服务器C5(位于德国)图4-16按语言的分布式系统结构图位于中国的用户访问中国的Web服务器,如果用户要求浏览的新闻来自于中41西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现文种子,则可以就近选择数据库B3进行读取;如果用户要求浏览的新闻来自于德文数据库,则需要到全局数据库B中查找,或者到数据库B5中查找.
这一类型的分布式数据库仅仅是设计,在系统中没有实现,因为现阶段搜索平台只针对英文,主要面向美国用户,数据库服务器和Web服务器也都设在美国.
4.
4新闻排名规则的设计与实现在RSS新闻搜索平台中,每个新闻文章都有一个排名值,就像每个页面在Google搜索引擎中都有其对应的PageRank值.
本节介绍RSS新闻搜索平台的排名规则和实现.
4.
4.
1客观排名因子文章来源于RSS种子,而RSS种子来源于发布种子的站点.
可以认为,一个高质量的站点发布的种子是高质量的,而一篇来自于高质量种子的新闻文章是高质量的.
在Web环境下,一个站点被链接的次数可以作为衡量一个网站质量好坏的标准.
在3.
1节中已经介绍了PageRank算法,可以认为PageRank值是对一个页面流行程度,重要程度的客观评价.
借用PageRank的思想,可以获取指向种子的来源站点的链接数作为文章的客观排名因子.
链接数的获取需要借助Google提供的API,把"link:theURLoftheRSSsite"发送给Google,会返回指向该站点的链接数.
注意,这里发送的URL一般是站点的一级域名.
如图4-17所示,指向www.
slate.
com的链接数是45,3000.
这样就获得了种子SlateMagzine(http://www.
slate.
com/rss/)的客观排名因子.
图4-17借助Google获取站点链接数的示例上述过程可以方便的使用一个源码分析程序完成,源码分析程序在元搜索引擎中是非常常见的.
其工作流程一般为:(1)将URL参数http://www.
google.
com/searchq=link%3Awww.
slate.
com发送给源码获取程序,获取相应网页的源代码,如图4-18所示.
(2)利用正则匹配或字符串查找函数,找到源代码中出现链接数目的位置,获取该链接数.
42西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现43图4-18含有查询站点链接数的Google页面源代码在计算排名值时常常需要对参与的数据进行归一化操作.
先来介绍最大值归一的一种设计:设Rank_O(Articles)代表一篇文章的客观排名值;FeedsLinkCount(Feeds)代表指向种子Feeds的链接数;FeedsFrom(Articles)代表文章的来源种子,max(FeedsLinkCount)当前数据库中保存的所有种子站点的链接数的最大值.
则:Rank_O(Articles)=FeedsLinkCount(FeedsFrom(Articles))/max(FeedsLinkCount)如果一篇文章文章来源于多个种子,说明这篇文章也很重要,设一篇文章的来源种子数为FeedsCount(Articles),这一参数可以通过R_RssArticles表中获取.
Max(FeedsCount)代表系统中,一篇文章对应种子数的最大值.
则一篇文章的客观排名值为:Rank_O(Articles)=o1*FeedsLinkCount(FeedsFrom(Articles))/max(FeedsLinkCount)+o2*FeedsCount(Articles)/Max(FeedsCount)o1,o2为可调节因子,可以根据需要调整两个因子所占的比重.
选择最大值归一的一个缺点就是必须选择相应数据的最大值,而最大值只有在所有相关数据出现后才能得到,这就可能延缓归一化的计算.
比如要得到max(FeedsLinkCount),必须在获取了每个feeds对应的链接数后才能得到.
在SQL的实现中可以选择聚集函数MAX进行实现.
另外,最大值归一化适用于分布比较均匀的场合,考虑如下两组情况:A(45300,49400,50000,47200,38400,23200)B(45300,49400,5000000,47200,38400,23200)分别采用最大值归一化的结果为:A'(0.
906,0.
988,1,0.
944,0.
768,0.
464)B'(0.
00906,0.
00988,1,0.
00944,0.
00768,0.
00464)可以看出,A组比B组更适用于最大值归一.
由于B组数据出现一个数量级明显大于其它成员数据的数据,因此导致大部分数据归一化的结果很小,不能起到很好的辨别作用,而且存储这样一个数据需要变量的精度很高.
这种情况下,可以选择使用指数归一化方法.
指数归一可以动态调整因子,使归一尽量平滑,消除归一化后数据的波动.
由于网站间的链接数的差别可能很大,不能保证不出现类似B组数据的产生.
而一篇文章的来源种子数最多不过十余个,不会出现数量级差别过大的情况.
因西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现此,在RSS搜索平台的最后实现中,o1因子选择使用了指数归一化方法(设a为动态调整因子,平台中设置为-0.
1),o2因子选择使用了最大值归一化方法.
这样,最终一篇文章的客观排名值为:Rank_O(Articles)=o1*(1-EXP(a*FeedsLinkCountFeedsFrom(Articles)))+o2*FeedsCount(Articles)/Max(FeedsCount)在实现过程中,需要对模式RssFeeds进行扩充,需要保存种子对应的来源站点域名(RssFeedsSiteLink)和当前的链接数(FeedsLinkCount),修改后的RssFeeds模式为:RssFeeds(RssFeedsId,RssFeedsLink,RssFeedsName,RssFeedsSiteLink,FeedsLinkCount)这样,对每篇文章的客观排名值,就可以通过函数实现,如图4-19所示.
图4-19文章客观排名值的SQL实现44西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现4.
4.
2主观排名因子对于新下载的文章,其排名值仅仅来源于客观排名因子,但是RSS新闻搜索平台提供了多种形式的反馈给用户使用.
如果用户对一篇文章进行了反馈,可以认为是用户对一篇文章感兴趣,是用户主观的承认一篇文章的重要程度.
基于反馈的排名算法在3.
3节中已经详细讨论,这里针对搜索平台的具体情况进行新闻文章的主观排名因子设计.
首先考虑RSS搜索平台提供给用户的几种反馈形式,图4-20是Web应用中对一篇文章提供的用户界面.
如果一个用户对某篇新闻文章添加了Tag(图中Tagit按钮),或添加了评注(图中addcomments链接),或把该文章通过Email发送给了其它用户(图中emailthis链接),则说明他对这篇感兴趣,或者说他认为这篇文章重要,因此,可以认为一个文章被用户此类反馈越多,这篇文章越重要,因此应该可以提升文章的排名.
同时,如果用户点击了新闻的标题阅读了该新闻,也可以认为是此类反馈.
另一种形式的反馈是投票,如图votes所示,上箭头表示投赞成票,即用户认为该文章重要,应该提升文章的排名;下箭头表示投反对票,即用户认为该文章不重要,应该降低文章的排名.
图4-20Web应用中的用户界面截屏图设Rank_S(Articles)代表文章的主观排名值,ReadNums(Articles)代表读该文章的用户数,TagNums(Articles)代表标记该文章的用户数,CommentNums(Articles)表示评注该文章的用户数,EmailNums(Articles)表示发送Email该文章的用户数,VoteNums(Articles)表示对该文章投赞成票的用户数,OpposeNums(Articles)表示对该文章投反对票的用户数,则:Rank_S(Articles)=s1*(1–EXP(b*ReadNums(Articles)))+s2*(1–EXP(c*TagNums(Articles)))+s3*(1–EXP(d*CommentNums(Articles)))+s4*(1–EXP(e*EmailNums(Articles)))+s5*(1–EXP(f*VoteNums(Articles)))-s6*(1–EXP(g*OpposeNums(Articles)))45西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现46为了记录这些反馈信息,需要在数据库中把这些信息保存在表中,这里需要设计几个表来保存这些信息,这些表的模式为:ReadArticles(ArticlesId,UserId)TagArticles(ArticlesId,UserId,TagContent)CommentArticles(ArticlesId,UserId,Comments)EmailArticles(ArticlesId,UserId)VoteArticles(ArticlesId,UserId,VoteOrOppose)这些表都在服务器2的数据库A中,不用发布到分布式数据库的只读数据库中.
用户的反馈信息通过Web服务器和数据库链接管理程序直接写入服务器2的数据库A.
文章的主观排名因子的SQL实现依然使用函数,类似于上一节中的客观排名因子的SQL实现.
4.
4.
3综合排名的设计与实现一篇文章的综合排名值由主观排名因子和客观排名因子相加得到,设Rank(Articles)代表一篇文章的综合排名值,则:Rank(Articles)=o*Rank_O(Articles)+s*Rank_S(Articles)文章的综合排名值包含了两部分,针对不同的用户和不同的时间,可以通过调整可调节系数o和s来改变权重.
例如,当一篇文章刚刚下载时,第一次计算的排名值只有客观部分,但随着时间的增长,对该文章的反馈越来越多,主观排名值越来越多,因此可以适当的调大主观调节因子s,这里s可以被设置为一个计算次数的函数,随着计算次数的增加,自动增大主观系数.
通过计算综合排名,每篇新闻文章都有了一个最终的排名值.
为了保存每篇文章的排名值,需要修改Articles的模式,添加保存排名值的字段Rank,修改后的模式为:Articles(AritlcesId,Link,PubDate,DescriptionId,Rank)综合排名的计算通常是一个耗时的过程,在实现中使用存储过程调用函数的方式来进行排名值的计算与更新,如图4-21所示.
在实际运行中发现,如果每次直接使用Update进行更新排名值,会导致Articles表的长时间锁定,而计算的结果却发现若干天前的文章排名基本是不会变化的,因此耗时的排名计算被浪费了.
因此,计算排名的存储过程只更新最近若干天的文章的排名.
在实现中,只更新最近两天的新闻排名,两天之前的新闻排名值保持最后的排名值不再变化.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现图4-21文章综合排名值的SQL实现这种方法虽然实现简单,但是由于计算排名时用到指数计算等耗时的操作,造成对一个资源的长时间锁定,这种锁定会增大系统的负担,增大锁等待的时间,甚至引起死锁.
在实现中,采用两种方法来避免长时间的锁定.
一种方法是采用局部计算的方法,即每次只计算一部分文章的排名值,然后再计算另一部分文章的排名值,这样不会造成对一个资源的长时间锁定,避免锁超时的发生,如图4-22所示.
另一种方法是把由排名计算外部程序计算排名值,而该程序计算排名的这部分时间不对资源加锁,直到全部计算完毕后,再更新排名值,这样大大减少锁的持续时间,如图4-23所示.
对Articles加排它锁,计算1000篇文章的排名值,释放锁.
其他应用可以对Articles加锁对Articles加排它锁,再计算1000篇文章的排名值,释放锁.
其他应用可以对Articles加锁.
.
.
全部计算结束.
数据库内:T1:对Articles加共享锁,获取需要计算排名的所有文章号.
T3:然后释放锁.
T5:对Articles加排他锁,更新已计算好的排名值.
释放锁.
排名计算外部程序(例如C#程序):T2:获取需要计算的文章号.
T4:计算排名值.
图4-22局部计算法示意图图4-23外部程序调用示意图用户的查询往往会返回很多符合条件的结果,在这个结果集中就可以按照排名值的大小按顺序返回给用户.
当排名值相同时,按发布时间的先后返回给用户.
当然,用户也可以选择直接按照发布时间查看新闻,因为人们总是对新的文章敢兴趣.
在实际系统的实现中,一篇文章的排名值还受到个人用户兴趣的影响,当前新闻热点趋势的影响.
而这些信息都需要用到由文章描述信息抽取出的概念.
利47西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现48用概念可以实现文本聚类,热点发现和新闻实时推荐等功能.
由于涉及过多技术细节,这里略去.
排名是信息检索的一个重要问题,而且对排名的评价总是涉及到人的主观因素,因此没有一个公认的排名算法能适应在各种环境.
现在的一个趋势是对一组特定的用户,采用特定的排名算法,或对一个通用的算法设定不同的调节系数.
4.
5小结本章详细介绍了RSS新闻搜索平台的设计实现过程.
首先描述了系统的整体构架.
并且详细介绍了数据库的模式设计,数据库性能优化方法,分布式数据库的部署策略等.
最后对新闻排序规则作了总结,分别从主观排名因子和客观排名因子两方面进行了分析,并设计了综合排名算法.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现49第五章嵌入浏览器的搜索集成工具的设计与实现随着IE,Firefox等优秀浏览器的发展,用户上网浏览网页,通过搜索引擎查询都会使用到浏览器.
随着网络应用B/S模式的流行,浏览器更是在网络应用中占据了重要的地位.
因此,通过浏览器为用户提供良好的用户界面是十分必要的.
当前主流的搜索引擎网站,门户网站都开发了自己的浏览器插件,比如GoogleToolbar,YahooToolbar,新浪点点通工具条等.
当前的主流浏览器都提供对工具条,浏览器栏的接口支持.
针对IE5.
0以上版本,设计开发了提供元搜索功能的集成搜索工具条,同时提供IE浏览动作监听和用户对可搜索深标签的添加.
5.
1浏览器插件开发原理IE5.
0以上版本提供了面板对象来支持浏览器插件.
实现IE面板对象组件的是一个ATL(ActiveTemplateLibrary)控件,它是一个轻量级的COM(ComponentObjectModel)组件.
面板对象分为三种类型,浏览器栏面板、工具栏面板和桌面工具栏面板.
而浏览器栏面板又有两种表现形式:垂直和水平的.
在实现中,选择工具栏面板实现工具条.
实现工具条面板组件需要实现基本的COM接口IUnknown和IClassFactory外,还需要实现IDeskBand、IObjectWithSite、IPersistStream三个接口.
由于嵌入浏览器的搜索引擎的集成工具栏需要和用户交互,接受用户的输入搜索查询串,所以还要实现IInputObject接口.
接口都有一个由IDL语言定义的GUID.
通过使用MSVC6.
0的ATLCOM工程向导,设计实现一个上述接口的工具条面板组件后,把该组件的GUID注册到注册表和IE浏览器中之后就可以在浏览器中使用了.
为了实现对浏览器的控制,需要注册一个浏览器帮助对象BHO(BrowserHelperObject)到注册表.
BHO通常是一个DLL,在IE每次启动时和IE一起加载启动.
在BHO中可以实现IObjectWithSite接口,获取当前浏览器对象接口(IWebBrowser2)的指针,就可以控制浏览器的行为了.
在我们设计的DIGGOLSearchToolBar中,主要提供了如下功能:(1)添加嵌入网页的可搜索深标签的功能.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现50该功能支持用户在任意网页上添加深标签.
深标签的特点在于,用户可以对网页的特定段落,特定位置,特定资源添加多个标签,进行注释.
它不同于针对网页的标签,对一个网页只能加一个标签.
这种深标签依然可以返回给服务器,作为网页的Folksonomy概念.
(2)搜索引擎集成功能,提供元搜索的搜索入口.
该功能是一个简单的元搜索引擎.
它支持用户在搜索栏内写入搜索关键字后,选择点击不同的按钮进行不同搜索引擎进行搜索.
实际上,该功能只实现了元搜索引擎的请求提交代理和检索接口代理的主要功能,但并没有提供结果融合的策略,即没有实现结果显示代理.
(3)用户搜索历史的记录.
该功能记录用户所有的浏览器访问Web行为,将访问URL信息记录到数据库中,便于进行对用户反馈的分析及用户兴趣的发现.
(4)高亮网页关键字功能.
该功能使用户可以选择网页上的任意关键字进行高亮显示,作为方便用户浏览网页的一种辅助功能.
5.
2添加深标签方法的设计这里提供按网页内容添加(Tag)和按位置添加标签两种方式,其基本流程为:(1)通过浏览器插件获取用户在网页中选取的内容或位置.
(2)通过浏览器插件在该内容或位置处插入标签图标和承载标签编辑框的窗体,以及用于操作的脚本.
(3)插入的脚本在承载标签的窗体上生成用于接受用户输入的编辑框等控件,用于接受用户输入.
(4)用户输入自定义信息后,点击关闭按钮,脚本发出连接,浏览器插件监听该连接,并获取编辑框内容,保存该内容,按用户选择把相关信息保存在本地或上传到服务器.
(5)用户再次登陆添加过标签的网页时,根据保存的相关信息在原先添加的位置自动添加标签.
用户可以利用鼠标右击菜单中的选项,删除该标签.
(6)用户可以通过本地页面查找保存在本机数据库中的标签的相关信息.
也可以通过在相应的服务器上查找用户自己的标签的相关信息,或查找其他用户共享的标签的相关信息.
(7)如果加过标签的网页是一个搜索引擎的搜索结果页,则自动把相应的搜索西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现51所用的搜索关键字和搜索引擎的搜索结果的一或多页保存在用户本机上或一个服务器上,并提供一个让用户查找本用户或其他共向用户的标签的相关信息或相应的搜索结果页的功能和用户界面.
如果加标签的网页是框架模式(Frameset)则通过浏览器插件逐层获取框架模式的对应的标码语言文档,对每个Frameset元素分别判断、操作,进行添加元素的操作,标签操作.
该过程需要浏览器插件技术和脚本技术相结合完成.
浏览器插件主要完成监听超链接,获取添加标签的位置,添加标签载体,保存标签内容等功能.
而脚本主要用于控制生成的标签,获取用户的输入标签内容,并将标签内容发送给浏览器插件以便存储.
5.
3搜索引擎集成功能的实现在5.
1节中已经提到工具条面板插件要实现接口IObjectWithSite.
该接口是IE用来对插件进行管理和通讯用的一个接口.
必须要实现这个接口的两个函数:SetSite()和GetSite().
在SetSite()函数中,获得指向当前浏览器对象接口(IWebBrowser2)的指针,有了这个指针就可以通过它来对IE进行监听和控制.
IWebBrowser2接口的函数Navigate2()可以控制浏览器浏览的页面.
这样,只要构造出每个成员搜索引擎的搜索URL规则,就可以简单的构造一个元搜索的请求提交代理.
在实现中按照客户针对美国用户的喜好,选择了最常用的三个搜索引擎作为成员搜索引擎,分别是Google,Yahoo,MSN.
检索接口代理完成的一个基本工作就是将用户的检索请求按不同的格式发送到各个独立搜索引擎,因此需要分析每个搜索引擎的搜索请求提交URL的具体形式.
假设用户的搜索关键字为"searchkeyword@",则这三个搜索引擎的搜索URL分别为:Google:http://www.
google.
com/search&q=search+keyword+%40Yahoo:http://search.
yahoo.
com/searchp=search+keyword+%40MSN:http://search.
msn.
com/results.
aspxq=search+keyword+%40可以看出,每个搜索引擎的URL构成的形式基本相同,都是基本搜索URL+搜索关键字.
由于URL中的一些特殊字符有固定的含义,因此需要将搜索关键字中的特殊字符进行转换.
比如示例搜索关键字"searchkeyword@"中的@在URL中都转换为了%40.
特殊字符的转换规则是:%+该字符的ASCII码值,而搜索串中的空格一般转化为字符'+'.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现52这样可以设计一个结构体和一个函数,结构体用于保存成员搜索引擎的基本信息,而函数用于将用户输入的搜索查询串转换为适合搜索引擎查询规范的字符串形式.
structsearchengine{Char*SEName;//搜索引擎的名字Char*SEURL;//搜索引擎的URL}Char*TransferCode(char*);//把查询串转化为适合搜索引擎查询的查询串结构体searchengine的初始内容为:{{"Google","http://www.
google.
com/search&q="},{"Yahoo","http://search.
yahoo.
com/searchp="},{"MSN","http://search.
msn.
com/results.
aspxq="}}使用结构体的原因是可以方便的增加、删除成员搜索引擎.
根据上述分析结果,只要在工具条中获取用户输入的搜索查询串,经过函数TransferCode的转换,和对应搜索引擎的*SEURL拼接成相应的搜索引擎查询URL,通过Navigate2()直接控制浏览器访问该URL,就能在浏览器中得到相应搜索引擎的搜索结果页面.
这样,就完成了各个搜索引擎的参数转换,实现了元搜索的检索接口代理.
5.
4用户搜索历史记录对用户搜索历史的记录主要利用浏览器插件对IE动作的监听功能,同样用到浏览器对象接口IWebBrowser2.
每个COM工程都必须实现IDispatch接口,通过IDispatch的Invoke()方法就能监听IE的动作了.
不过为了识别每个动作的类型,需要在工程中加入头文件ExDispID.
h,它定义了所有DWebBrowserEvents2的事件.
这些事件包括:浏览器正在浏览一个页面(DISPID_BEFORENAVIGATE2),浏览器打开了一个新的窗口(DISPID_NEWWINDOW2),浏览器正在浏览的页面已经全部显示完毕(DISPID_DOCUMENTCOMPLETE).
在每个动作完成的时刻,可以通过浏览器插件把这一动作记录下来,主要是获取用户通过浏览器访问的URL信息.
通过记录用户访问的URL信息,可以进行用户的兴趣发现.
5.
5高亮关键字的实现高亮关键字的实现是通过动态改变浏览器中显示的内容实现的.
浏览器工作西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现53的原理是将每个HTML标签转化成一个元素显示在浏览器中.
动态改变浏览器显示的内容就是在不改变页面本身HTML源码的情况下,直接修改浏览器显示的元素.
这一过程首先通过浏览器对象接口IWebBrowser2获得MarkupServices接口.
这个接口可以改变HTMLDocument的内容.
高亮关键字的流程如下:(1)通过当前网页的Document,获得相应的IMarkupService接口指针.
IMarkupServices*pMS;hr=m_pHtmlDoc2->QueryInterface(IID_IMarkupServices,(void**)&pMS);(2)通过IMarkupService指针获得IMarkupPointer指针.
IMarkupPointer*pPtr1;hr=pMS->CreateMarkupPointer(&pPtr1);(3)给定要查找的文字,通过IMarkupPointer在网页中找到对应文字出现的位置.
hr=pPtr1->FindText(poSearchStr,0,pPtr2,NULL);(4)创建一个字体的Element,由于高亮关键字.
unsignedshort*mSetFind=L"ID=IEfindSTYLE=\"background-color:#ffff33\"";IHTMLElement*pFontEl;hr=pMS->CreateElement(TAGID_FONT,mSetFind,&pFontEl);(5)把新生成的FONTElement插入到要高亮的关键字两边hr=pMS->InsertElement(pFontEl,pPtr1,pPtr2);(6)创建用于定位网页的Script脚本Element.
unsignedshort*mSetFind=src=\"find.
js\"";hr=pMS->CreateElement(TAGID_SCRIPT,mSetScript,&pScript);在本地的find.
js文件中,可以通过插入的FontElement的ID(IEfind),获得该对象的位置,进而通过脚本实现网页滚动到当前关键字位置.
(7)把新生成的ScriptElement插入到前一步生成的FontElement后.
定位pPtr1到FontElement后.
pPtr1->MoveAdjacentToElement(pFontEl,ELEMENT_ADJACENCY_AfterEnd);hr=pMS->InsertElement(pScript,pPtr1,pPtr1);通过IMarkupService接口,可以动态改变Element,这样就可以在页面上添加新的Element,修改,删除已有的Element.
通过添加脚本Element,几乎可以使网页进行各种操作.
图5-1是高亮关键字的实际效果图.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现图5-1高亮关键字的效果图5.
6小结本节介绍了嵌入浏览器的搜索集成工具的设计和实现过程.
嵌入浏览器的搜索集成工具已经被各大搜索网站所采用,但是其主要功能无非是高亮搜索关键字和元搜索请求提交.
我们设计开发的搜索集成工具在此基础上还提供了添加深标签的方法,提供了一种新的浏览器插件的功能.
完成这一功能使用了浏览器插件和脚本结合的方法,这一方法已经申请专利.
54西北工业大学硕士学位论文第六章结束语55第六章结束语6.
1工作总结课题项目来源于中美合作"下一代智能搜索平台"项目.
由于项目采用极限编程模式,用户需求变化快,采用的工作模式特殊,需要多人合作开发和积极沟通.
笔者主要完成了浏览器插件的开发,RSS新闻搜索平台的数据库设计,并负责与客户沟通,用户需求说明确认和需求分析工作.
主要完成的工作如下:(1)完成了浏览器插件的设计与开发,开发了DIGGOL智能搜索助手的工具条和浏览器栏插件.
提供浏览器动作监听,客户端-服务器构架的支持,以及添加可搜索深标签的方法.
(2)完成RSS新闻搜索平台的数据库设计.
完成新闻排名模块的开发.
完成按照不同要求进行的搜索模块的开发.
完成用户反馈模块的开发.
完成基于概念的新闻热点发现,新闻热点关联的开发.
(3)完成基于组(Group)功能的RSS新闻搜索平台的数据库设计及相关应用开发.
(4)为了提高网站相应速度,采用多种策略进行了数据库性能优化,并完成分布式数据库的部署.
(5)及时和客户沟通,理解用户需求,完成需求分析.
针对客户在开发过程中提出的需求变更,快速开发出原型提供给用户进行确认.
6.
2后续工作展望传统的基于关键字的搜索引擎已经有了基本的框架,而第三代智能搜索还处于起步状态.
智能搜索在传统的信息检索基础上融合了数据挖掘,人工智能等许多学科.
需要研究的内容主要有如下几个方面:(1)广泛收集用户反馈信息,针对不同用户提供更加准确的查询结果.
提高查询的针对性.
(2)提供给具有相同兴趣爱好的一组人的信息搜索和共享平台.
新闻主题社区的自动发现.
(3)随着语义网络的发展,在语义网络下的搜索服务是面临的一项新的挑战.
西北工业大学硕士学位论文参考文献56参考文献[1]RicardoBaeza-Yates,BerthierRibeiro著.
现代信息检索ModernInformationRetrieval(王知津等译).
北京:机械工业出版社,2005.
[2]G.
Salton.
TheSMARTRetrievalSystem–ExperimentsinAutomaticDocumentProcessing.
PrentiveHallInc.
,EnglewoodCliffs,NJ,1971.
[3]S.
E.
RobertsonandK.
SparkJones.
Relevanceweightingofsearchterms.
JournaloftheAmericanSocirtyforInformationScience,27(30):129-146,1976.
[4]李晓明,闫宏飞,王继民.
搜索引擎――原理、技术与系统.
北京:科学出版社,2005.
[5]徐宝文,张卫丰.
搜索引擎与信息获取技术.
北京:清华大学出版社,2003.
[6]韩家炜,孟小峰,王静等.
Web挖掘研究.
计算机研究与发展.
2001年4月第38卷第4期.
[7]JimGray.
Therevolutionindatabasearchitecture.
In:WeikumG,KnigAC,DelochS,eds.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData.
ACMPress,2004,1~4.
[8]SergeyBrin,LawrencePage.
TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine.
Proceedingsofthe7thInternationalWorldWideWebConference,1998.
[9]JonM.
Kleinberg.
AuthoritativeSourcesinaHyperlinkedEnvironment.
JournaloftheACM.
1999.
[10]LawrencePage,SergeyBrin.
ThePageRankCitationRanking-BringingOrdertotheWeb.
http://dbpubs.
stanford.
edu:8090/cgi-bin/makehtml.
cgidocument=1999/66[11]UdoKruschwitz.
WorldKnowledgeforthedomainofyourchoice.
IEEEInternationalConferenceonSystems,Man,andCybernetics.
2001.
[12]ThePorterStemmingAlgorithmhttp://www.
tartarus.
org/~martin/PorterStemmer/[13]张强弓,喻国宝,廖湖声等.
一种元搜索引擎的查询结果处理模型.
华南理工大学学报(自然科学版),2004年11月32卷增刊:47-51.
[14]T.
Pedersen,S.
Patwardhan,andJ.
Michelizzi.
Wordnet::similarity-measuringtherelatednessofconcepts[C].
In:ProceedingsoftheNineteenthNationalConferenceonArtificialIntelligence(AAAI-04),2004.
[15]A.
Silberschatz,H.
F.
Korth,S.
Sudarshan著;数据库系统概念DatabaseSystemConcepts(杨冬青,唐世渭译);北京:机械工业出版社,2004.
[16]施伯乐,丁宝康,汪卫.
数据库系统教程.
北京:高等教育出版社,2003.
[17]胡百敬.
MicrosoftSQLServer性能调教.
北京:电子工业出版社,2005.
[18]韩近强,陈华.
嵌入IE的搜索引擎集成工具的设计与实现.
全国搜索引擎和网上信息挖掘学西北工业大学硕士学位论文参考文献57术研讨会2003SEWM,北京大学,2003.
[19]董志勇.
Web信息检索中基于超链接的网页评估算法研究.
硕士学位论文.
河海大学.
2004.
[20]AdamMaths.
Folksonomies-CooperativeClassificationandCommunicationThroughSharedMetadata.
ComputerMediatedCommunication,2004.
[21]徐科,黄国景,崔志明.
元搜索引擎中基于用户兴趣的个性化调度模型.
清华大学学报(自然科学版),2005年第45卷第S1期:1915-1919.
西北工业大学硕士学位论文发表论文和参加科研情况说明58发表论文和参加科研情况说明[1]杨彬,康慕宁.
基于概念的权重PageRank改进算法.
情报杂志.
2006年第11期,已出版.
[2]杨彬,康慕宁.
基于用户反馈的搜索引擎选择及结果归并方法.
计算机工程.
2008年第4期,已录用.
[3]郭晨娟,杨彬,梁平.
网页加入可搜索的深标签及浏览器插件与脚本结合的方法.
申请专利号200610041811.
1,已公开.
西北工业大学硕士学位论文致谢59致谢首先感谢我的导师康慕宁教授,他在两年多的时间里一直悉心教导我,在学业上、生活上以及思想上都给予我巨大的帮助.
在整个研究生学习期间给予我了耐心指导,严格要求和热情鼓励.
他实事求是的精神,积极乐观的态度,将使我受益终生.
在此我要向康慕宁老师无私的教诲表示衷心的感谢.
感谢李战怀教授在工作和学习中给我的巨大的帮助.
他严谨的治学态度,渊博的知识使我受益匪浅.
感谢他为我提供了良好的工作环境,使我有幸能参加与美国DIGGOL公司的合作项目.
特别感谢他对我学术研究上的指导和帮助.
感谢项目组组长张文波,作为项目负责人,他积极忘我的工作态度让人钦佩.
特别感谢他对我的信任和对我日常生活上的关心与照顾.
感谢美国DIGGOL公司的梁平教授,西安迪戈科技公司的李联宁经理.
他们为我们带来了许多先进的思想和工作模式.
感谢张延园教授,蒋立源教授和李建良老师.
感谢同课题组的郭晨娟硕士、韩宇彬硕士、雷万宝硕士、彭丽硕士,刘璐硕士.
在整个项目的研发过程中,他们表现出了深厚的专业基础,良好的团队精神以及乐于助人的品格,不仅保证了项目的顺利进展,更让工作充满了乐趣,在此表示由衷的敬佩与谢意.
最后,特别感谢我的父亲杨勤耕,母亲刘璟及所有亲人,他们在我的成长过程中给予我无私的爱和全力的支持.
对所有关心,帮助我的人表示感谢!
西北工业大学学位论文知识产权声明书本人完全了解学校有关保护知识产权的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属于西北工业大学.
学校有权保留并向国家有关部门或机构送交论文的复印件和电子版.
本人允许论文被查阅和借阅.
学校可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文.
同时本人保证,毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学.
保密论文待解密后适用本声明.
学位论文作者签名:指导教师签名:年月日年月日西北工业大学学位论文原创性声明秉承学校严谨的学风和优良的科学道德,本人郑重声明:所呈交的学位论文,是本人在导师的指导下进行研究工作所取得的成果.
尽我所知,除文中已经注明引用的内容和致谢的地方外,本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果,不包含本人或他人已申请学位或其它用途使用过的成果.
对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明.
本人学位论文与资料若有不实,愿意承担一切相关的法律责任.
学位论文作者签名:年月日
面对海量的数据,用户常常无法从中找到自己所需要的数据.
如何使用户能够在网络中快速,准确的找到所需要的数据是Web信息检索面临的挑战.
搜索引擎技术的出现,为用户提供了一种在Web中检索信息的简单的方法,使用户能够通过关键字进行相关资源的搜索.
但是用户所需的资源种类不同,通用搜索引擎难以提供给用户足够的资源,因此出现了针对特定领域的搜索服务.
RSS新闻搜索就是这类应用,它仅仅搜索RSS新闻资源.
同时,越来越多的网络应用采用了B/S模式,因此出现了许多集成在浏览器上的搜索服务,并提供其他方便用户的附加功能.
本文首先介绍了信息检索技术的基本概念和模型,介绍了搜索引擎和元搜索引擎的基本结构;对基于链接分析的搜索引擎排序算法PageRank和HITS进行了分析和对比,在此基础上提出了基于概念的权重PageRank改进算法以及为页面标记概念的两种方法;提出了基于用户反馈的结果融合排名算法;详细介绍了RSS新闻搜索平台的结构,数据库模式设计,搜索操作的性能优化方法,主客观结合的新闻排名机制;最后介绍了一种浏览器插件,它主要提供一种为页面进行概念标记的方法,同时提供元搜索接口等其他服务.
关键词:Web检信息索,PageRank,RSS闻浏览新搜索,排名,器插件IIABSTRACTWiththedevelopmentofWorldWideWeb,theamountofdataonwebexpandsdramatically.
Facingsomanydataonweb,theusersalwayslosetheirwaytofindthespecificdata.
Itisachallengeinwebinformationretrievaltomaketheuserfindthedataaccuratelyandquickly.
SearchEngineprovidesasimplemethodtofindwebpage.
UserscanfindthewebpagebytellingtheSearchEnginethekeyword.
Usersalwaysdemanddifferenttypesofresources,butgeneralSearchEnginecannotprovidesufficientresourceforusers.
Somespecificsearchserviceemerges.
Forexample,RSSsearchservice'saimistoonlysearchtheRSSnewsresourcesspecifically.
MoreandmorewebapplicationsuseBrowser/Serverarchitecture,sothatmanytoolsembeddedinbrowsershasbeenimplemented.
Thesetoolsalwaysprovideanintegratedsearchserviceandotherfunctionconvenientforusers.
ThepapergivesanoverviewofbasicconceptsandmodulesofInformationRetrieval,andthearchitectureofSearchEngineandMetaSearchEngine.
ComparesthePageRankandHITSalgorithm,andthenproposesaweightedPageRankalgorithmbasedonconcepts,andtwomethodsoftaggingconceptsforwebpage.
Proposesaresultmergerankingmethodbasedonusers'feedback.
ThepaperdescribesthearchitectureoftheRSSsearchplatformindetail,includingtheschemasofthedatabase,theoptimizationofsearchoperation,andtherankingmechanismofRSSnews.
Atlast,describesatoolbarembeddedinabrowser,whichprovidesamethodoftaggingconceptsandmetaserachservices.
Keywords:WebInformationRetrieval,PageRank,RSSNewsSearch,Ranking,ToolsembeddedinBrowser西北工业大学硕士学位论文目录III目录摘要IABSTRACT.
II目录III第一章绪论11.
1研究的背景和意义.
11.
2国内外的研究现状.
11.
3研究工作概述.
21.
4本文组织结构.
2第二章Web信息检索技术概述42.
1传统信息检索方法.
42.
1.
1信息检索的形式定义.
42.
1.
2特别检索和过滤.
42.
1.
3经典信息检索模型.
52.
1.
4检索的评价.
62.
1.
5检索过程.
72.
2Web信息检索技术72.
2.
1Web数据的特点72.
2.
2搜索引擎概述.
82.
2.
3元搜索引擎概述.
92.
2.
4Web挖掘技术92.
3小结10第三章搜索排序算法研究.
113.
1基于链接分析的排序算法分析.
113.
1.
1PageRank算法113.
1.
2HITS算法.
123.
1.
3PageRank算法和HITS算法的比较分析.
133.
2基于概念的权重PageRank改进算法143.
2.
1基于网页内容的概念选取方法.
143.
2.
2基于Folksonomy的概念选取方法.
153.
2.
3基于概念的权重PageRank改进算法设计.
173.
3基于用户反馈的结果归并算法.
193.
4小结21第四章RSS新闻搜索平台的设计与实现.
224.
1RSS新闻搜索平台基本框架.
224.
2数据管理结构设计与实现.
234.
2.
1关系数据库模式设计原则.
244.
2.
2RSS种子文档的结构分析.
24西北工业大学硕士学位论文目录IV4.
2.
3设计实体关系模式.
264.
2.
4表的模式设计.
274.
2.
5存储过程接口设计.
294.
3搜索操作的性能优化.
314.
3.
1针对查询建立索引.
314.
3.
2拆分大表.
334.
3.
3解除规范化设计.
364.
3.
4事务隔离级别设定.
374.
3.
5分布式数据库的部署.
394.
4新闻排名规则的设计与实现.
424.
4.
1客观排名因子.
424.
4.
2主观排名因子.
454.
4.
3综合排名的设计与实现.
464.
5小结48第五章嵌入浏览器的搜索集成工具的设计与实现.
495.
1浏览器插件开发原理.
495.
2添加深标签方法的设计.
505.
3搜索引擎集成功能的实现.
515.
4用户搜索历史记录.
525.
5高亮关键字的实现.
525.
6小结54第六章结束语556.
1工作总结556.
2后续工作展望.
55参考文献56发表论文和参加科研情况说明.
58致谢59西北工业大学硕士学位论文第一章绪论1第一章绪论1.
1研究的背景和意义万维网从诞生到现在不过二十余年,但它给人们的生活带来了巨大的影响.
随着网络应用的快速发展,WWW(WorldWideWeb)已经成为许多行业信息发布、交流的主要平台.
Web上可以利用的文本数据总量就有千兆字节,另外还存在着大量的图像、音频、视频等多媒体资源.
一方面WWW包含了从技术资料,商业信息到新闻快讯,体育娱乐咨询等多种类别和形式的信息;而另一方面,由于网络的动态性,资源分布分散,没有统一的数据管理形式,使用户很难在WWW上找到自己所需要的信息.
这一矛盾从Web诞生就存在,但是直到现在也没有得到根本的解决.
Web信息检索技术能够高效、准确的从Web数据中查找用户需要的信息、并以有效的形式呈现给用户.
Web信息检索技术不仅有很强的实用性,有很大的现实意义,而且作为Web数据管理的一部分,在学术界也受到广泛关注[6,7].
1.
2国内外的研究现状传统的信息检索技术源于图书馆,它对信息项进行表示、存储、组织和存取.
信息检索技术首先要对系统进行建模,常用的模型包括布尔模型,向量模型和概率模型.
在模型基础上进行文档的标引,查询和文档的定义,并给出针对查询的相似度计算公式,最后通过用户界面返回给用户.
搜索引擎是早期出现的Web信息检索方法.
它的出现在一定程度上缓解了从巨大的WWW的资源中查找信息的难度.
搜索引擎已经成为普通用户在网络上获取信息的主要方法,用户输入关键字,通过搜索引擎获取一组包含该搜索关键字的相关页面.
搜索引擎本身通过网页采集程序收集大量网页并且建立索引,当用户查询到来时通过查找索引并返回相关页面.
搜索引擎一般分为集中式和分布式两种.
当前最成功的搜索引擎代表是Google.
网络目录也是常用的一种Web信息检索工具.
目录是各种知识的等级分类.
用户可以通过逐层的目录浏览,查找自己感兴趣的页面.
Web目录通常包括政治,经济,教育等大的类别,一级分类在12到26个之间,每个目录下还有更细的分类.
网络目录的代表是Yahoo!
.
大多数搜索引擎现在也提供主题目录,如AOL,Excite西北工业大学硕士学位论文第一章绪论2等,但是这些都是针对某些特定领域的,如有的站点关注于商业,新闻或政治.
网络目录和搜索引擎是最早出现的两种通用的Web信息检索方法.
元搜索引擎是建立在独立搜索引擎之上的搜索引擎.
这类搜索引擎自身不维护数据,而是将用户请求发送到若干独立搜索引擎,取回这些独立搜索引擎的搜索结果并进行结果融合并显示给用户.
这类搜索引擎的代表有MetaCrawler,SavvySearch和Inquirus.
由于网络资源包括的资源过于丰富,出现了针对特定领域的搜索平台.
比如针对学术论文的CiteSeer;针对网络上大量的RSS新闻,Blog页面,越来越多的网络应用提供了RSS新闻搜索,比如Digg.
这些网络应用和通用的搜索引擎、网络目录的最大区别是只关注一类Web资源,而不是广泛的搜取网络上的所有资源,例如RSS新闻搜索只关注RSS新闻种子资源,百度MP3搜索只关注文件格式为mp3,wmv等的音频资源.
1.
3研究工作概述Web信息检索技术包含的研究方向较多,本身面临着许多挑战,目前没有一个高效统一的模型用于Web信息检索.
作为成功的第一代Web信息检索模型的代表搜索引擎技术也正融入越来越多新思想与新技术.
数据挖掘,人工智能,机器学习,自然语言分析,社会学等学科的技术都融入到Web信息检索领域.
笔者于2005年参加中美合作"下一代智能搜索平台"项目的研发,先后参加了"DIGGOL个人信息挖掘助手"和"WizAg智能RSS新闻聚合搜索平台"的研发.
主要完成了搜索平台的总体结构设计,数据库模式设计,搜索排名算法设计与实现,搜索性能优化以及嵌入浏览器的用户界面开发等工作.
结合项目经验,提出了基于概念的权重PageRank改进算法,基于用户反馈的元搜索引擎模型及结果归并方法.
1.
4本文组织结构本论文是按照作者承担的主要研究和开发工作来安排的,共分为六章,每一章的主要内容如下所示:第一章绪论.
本章简要介绍了本文的研究背景和意义、研究工作内容以及论文内容的安排.
第二章Web信息检索技术概述.
本章介绍了传统信息检索方法,经典信息检索模型,信息检索的评价标准;介绍了Web信息检索技术的基本概念,分析了西北工业大学硕士学位论文第一章绪论3Web数据的特点,对搜索引擎和元搜索引擎进行了简要介绍.
第三章搜索排序算法研究.
首先研究了基于链接分析的搜索引擎排序算法PageRank和HITS(Hypertext-InducedTopicSearch);然后提出了两种提取概念的方法,并在此基础上设计了基于概念的权值PageRank改进算法;最后提出基于用户反馈的元搜索模型,在此模型基础上设计了结果归并算法.
第四章RSS新闻搜索平台的设计与实现.
详细介绍了RSS新闻搜索平台的构架,数据库设计,搜索性能优化方法和分布式数据库部署策略.
介绍了新闻文章的主客观因子结合的综合排名算法的设计与实现.
第五章嵌入浏览器的搜索集成工具的设计与实现.
介绍了一种嵌入浏览器的用户界面设计与实现方法.
第六章结束语.
本章总结了全文的主要工作,并展望了后续的研究工作,指出了进一步的研究内容.
西北工业大学硕士学位论文第二章Web信息检索技术概述4第二章Web信息检索技术概述2.
1传统信息检索方法信息检索(InformationRetrieval)是对信息项进行表示,存储,组织和存取[1].
信息检索的主要目标就是检索出所有与用户查询相关的文献.
在传统的信息检索系统中,通常采用标引词来编制索引和检索文献.
标引词就是关键词或一组相关词,其自身有一定的意义.
标引词更为一般的形式是一篇文献中出现的任何词,这样构成全文检索系统.
信息检索的核心问题就是预测哪些文献相关,哪些文献不相关.
通常取决与采用的排序算法,处在排列最顶端的文献被认为是最可能相关.
本节首先形式化的定义信息检索模型,然后介绍两种常见的检索方式和三种经典信息检索模型,最后介绍了信息检索的过程.
2.
1.
1信息检索的形式定义信息检索模型是一个四元组,其中(1)D是文献集中的一组文献逻辑视图,称为文献的表示;(2)Q是一组用户信息需求的逻辑视图,称为查询;(3)F是一种机制,由于构建文献表示、查询及他们之间关系的模型;(4)R(qi,dj)是排序函数,该函数输出一个与查询qi∈Q和文献表示dj∈D有关的实数,这样就在文献之间根据查询qi定义了一个顺序.
2.
1.
2特别检索和过滤特别检索和过滤是传统信息检索中的主要两种应用方式[1].
特别检索类似于图书馆里的图书检索,图书馆的书库中的藏书一般情况下是固定的(一般仅在新学期会购入新书),不同学生到图书馆中查找自己所需要的书籍.
由此可见,特别检索的特点在于集合中的文献保持相对静止的状态,而用户的查询则是变化的.
搜索引擎也属于这种类型的检索.
过滤又称为路由选择,其特点和特别检索相反,它的特点在于用户的查询规则相对稳定,而文献集合是经常变化的.
例如一些股票市场和新闻服务,用户定西北工业大学硕士学位论文第二章Web信息检索技术概述制一些查询,在不同时间返回不同的数据.
过滤的难处在于构建一个真正反映用户优先选择的用户需求档.
例如在第四章中详细介绍的RSS新闻搜索平台中,提供按种子类别进行过滤的功能,而用户需求档就是种子的名字.
2.
1.
3经典信息检索模型信息检索的三个经典模型分别为:布尔模型,向量模型和概率模型.
布尔模型:布尔模型是基于集合理论和布尔代数的一种简单的检索模型.
在布尔模型中,文献和查询用标引词集合来表示,又被称为集合论模型.
布尔模型假定标引词在文献中要么出现、要么不出现,因此标引词权值变量都是二值的,即wi,j∈{0,1}.
查询被表示成有确切语义的布尔表达式,通常是由若干个标引词通过联结词not,and,or连接起来的.
查询本质上是一个常规的布尔表达式,它可以表示为多个合取向量的析取,即析取范式DNF(DisjunctiveNormalForm),记为qdnf;qcc表示的任意合取分量.
文献dj和查询q的相似度定义为:{))()(,()|(10),(ccijiidngccccqgdgkqqqjqdsim=∧∈=如果其它如果sim(dj,q)=1,则布尔模型表示文献dj与查询q相关,否则文献与查询不相关.
但是,布尔模型只能判断文献是否相关,而无法判断部分匹配的情况.
向量模型:在向量模型[2]中,文献和查询用t维空间的向量来表示,称该模型为代数模型.
通过给查询和文献中的标引词分配非二值权值,实现部分匹配.
这些权值被用于计算文献和用户查询之间的相似度.
向量模型通过对检出文献相似度降序排列的方式来实现文献与查询的部分匹配.
在向量模型中,元组(ki,dj)的权值wi,j是一个正的非二值数.
此外,查询中的标引词也要加权.
用wi,q表示二元组[ki,q]的权值,wi,q>=0,查询向量q表示为q=(w1,q,w2,q,…,wt,q),其中t是系统中标引词的数目.
文献dj的向量可以表示为dj=(w1,j,w2,j,…,wt,j).
矢量模型通过矢量dj和q之间的形似性来评价文献dj和查询q的相似度.
一般使用两个向量的余弦值来计算相似度,即∑∑∑===**=*=tiqitijitiqijijjjwwwwqdqdqdsim1,21,21,,||||),(概率模型:概率模型[3]试图通过概率方法处理信息检索问题.
给定一个用户查5西北工业大学硕士学位论文第二章Web信息检索技术概述询q和文档集中的一个文档dj,概率模型试图估计用户找到其感兴趣的文档dj的概率,模型假设这个相关概率只是依赖于查询和文档的表示.
概率模型假设在文档集中存在一个子集,它是查询q的结果集.
理想结果集记为R,它使得总体的相关概率最大.
集合R中的文档被认为是于查询相关的,不在集合R中的文档则被认为是不相关的.
在概率模型中,标引词的权值是二值的,即wi,j{0,1},wi,q{0,1}.
查询q是标引词的一个子集.
设R是已知的相关文档集,设R是R的补集,P(R|Wj)是文档dj与查询q相关的概率,p(R|Wj)是文档dj与查询q不相关的概率.
文档dj与查询q的相似度可以定义为:)|()|(),(jjjWRPWRPqdsim=在这些基本信息检索模型基础上,研究人员又提出了许多改进模型,例如在基于集合论的模型上,提出了模糊集合论模型和扩展布尔模型;在代数模型基础上,衍生了广义向量模型,潜语义标引模型和神经网络模型;在概率模型基础上,区分出了推理网络模型和信任度网络模型.
2.
1.
4检索的评价常用的系统性能指标是时间和空间指标.
在一个信息检索系统中,人们最关注的指标是相应时间和所需空间.
在这些基本的指标基础上,针对信息检索系统的特点,还有两个重要的衡量标准就是查全率和查准率[1].
设信息查询实例为I,I对应的相关文献集合为R,用|R|表示该集合中的文献数目.
假定用给定的检索策略对信息查询I进行处理,并生成一个文献结果集合A,用|A|表示该集合中的文献数目.
用|Ra|表示R和A的交集中的文献数量:查全率是指检出的相关文献与相关文献(集合R)总数的比值,即查全率为:||||RRRa=查准率是指检出的相关文献与检出文献(集合A)总数的比值,即查准率为:||||ARPa=6西北工业大学硕士学位论文第二章Web信息检索技术概述72.
1.
5检索过程在检索过程开始之前,必须定义一个文本数据库.
这通常由数据库管理器来完成,它将要使用的文献,将要在该文本上执行的操作转换为文献的逻辑视图.
数据库管理器还要为数据库中的文本进行标引,对文本建立索引.
在检索过程中会用到不同的索引结构,最常见的一种索引就是倒排文档.
用户首先详细说明用户需求,随后对用户需求进行分析和转换,为用户需求提供一个系统表达式,接着通过查询获得检出文献.
在把文献发送给用户之前,要根据相关度,对检出文献进行排序.
随后用户检查经过排序后返回的文献集合,查找有用的信息.
在这过程中,用户可能会将反馈信息发送给系统,系统可以利用用户所选择的文献改进查询的表达.
而在这些过程中,一般都需要一个用户界面,例如在Web浏览器中显示的一个Web搜索引擎页面.
2.
2Web信息检索技术Web应用的迅速发展和它的指数增长已广为人知,仅可利用的文本数据总量就有千兆字节.
Web可以看成一个非常大的,非结构化且无处不在的数据库.
这就需要有效的工具来管理,检索和从数据库中筛选信息.
Web信息检索的基本形式有三种,第一种是搜索引擎,它标引一部分网络文献作为一个全文数据库,例如AltaVista;第二种是Web目录,它按主题来对所选择的Web文献进行分类,例如Yahoo!
;第三种是利用超链接结构来检索网络[1].
本节首先介绍Web数据的特点,然后分别对搜索引擎和元搜索引擎技术进行了简单介绍.
2.
2.
1Web数据的特点网络带来的Web数据有非常鲜明的特点,这些特点都加大了Web信息检索的难度.
数据的分布性:由于网络的本质特性,Web数据经常分布在许多计算机平台上;不稳定数据的高比例,由于Web的动态性,新的计算机和数据容易添加或删除.
当域名或文件名发生改变或不存在时,还要处理悬空链接和重新定位的问题;网络数据量的指数增长带来了大规模的数据;非结构化和冗余的数据,每个HTML页面都没有很好的结构,许多网络数据是重复的镜像,或者非常相似,据统计约有30%的网页是重复的.
如果考虑语义上的冗余则重复数据更多;数据的质量不高,网络可以看出是一个新的出版媒体,然而在大多数情况下,许多内容西北工业大学硕士学位论文第二章Web信息检索技术概述并没有经过编辑处理,甚至任何一个用户都可以在网络上添加内容(比如现在流行的个人网络日志Blog,电子布告板BBS),因此网络上的数据可能是错误的,无效的;异构数据大量出现在网络中,除了有多种媒体和由此产生的多种格式外,还需要处理不同的语言,不同的字母表,而这其中可能非常庞大,例如中文,日文等亚洲字母表.
2.
2.
2搜索引擎概述大多数搜索引擎采用了集中式的收集器-索引器结构[4],其体系结构如图2-1所示.
收集器(又常被称作蜘蛛Spider,爬虫Worm,机器人Robots)是一个程序,它按某种策略(如广度优先或深度优先)遍历网络,发回新的或更新过的网页,然后将这些发送回的数据存储在文档库中.
实际上收集器并不是实际运行在异地的机器上,而是在本地系统中运行,向异地的Web服务器发送请求并获取网页.
索引器分析收集器收集到的网页,将文档表示成便于检索的形式,并在文档上建立索引,最后将生成的索引库保存在主服务器上.
索引一般采用某种形式的倒排索引,倒排索引的每一项包含一组指针,这些指针指向和这个索引项相关的网页.
当用户输入某个关键词进行搜索时,需要通过用户接口将查询发送到检索器,检索器通过索引快速找到相关的文档,然后按某种算法排序计算这些文档的排序值,最后将排序后的结果返回给用户.
WWW收集器索引器检索器主服务器,索引数据库用户接口文档库图2-1搜索引擎体系结构图大多数搜索引擎使用布尔模型或向量模型及这些模型的扩展进行排序.
除了经典的词频-逆文献率方法外,经常使用的还有布尔扩展、向量扩展和最大引用等方法.
新的排序算法使用到了超链接信息,这是Web和传统IR数据库之间的最根本区别之一.
指向一个网页的超链接的数量能够用来测量该网页的流行程度和质量.
此外,被相同页面所引用的网页与网页之间的公共链接表明了这些页面之间的关系.
常见的例子有WebQuery,HITS和PageRank.
将在第三章详细讨论HITS8西北工业大学硕士学位论文第二章Web信息检索技术概述9和PageRank.
当前有许多成功运行的搜索引擎,例如AltaVista,Excite,Infoseek,Lycos,Google,百度和天网搜索.
2.
2.
3元搜索引擎概述元搜索引擎是把一个给定的查询发送到几个搜索引擎、Web目录及其他数据库,并收集和统一结果的一种网络服务器[1].
可以认为元搜索引擎是建立在独立搜索引擎之上的搜索引擎.
它利用下层的若干个独立搜索引擎提供的服务向上提供统一的检索服务,本身不采集文档、维护索引.
元搜索引擎首先按某种策略把用户的查询发送给特定的几个独立搜索引擎,再将各独立搜索引擎所得结果按照某种结果归并策略进行融合,排序,最终给出统一的查询结果.
元搜索引擎综合多个搜索引擎的结果,可以增加网络资源的覆盖率,提高搜索的查全率;同时,元搜索引擎在进行结果归并时,依据某种归并策略,可以对独立搜索引擎的一次查询结果进行二次集成和排序,提高搜索的查准率.
经典的元搜索引擎主要由三部分组成:请求提交代理、检索接口代理、结果显示代理[5].
请求提交代理负责选择调用哪些独立搜索引擎,检索时间限制,检索返回结果数量限制等;检索接口代理将用户的检索请求按不同的格式发送到各个独立搜索引擎;结果显示代理负责各个独立搜索引擎检索结果的去重,合并,显示.
当前也有许多成功运行的元搜索引擎,例如:MetaCrawler,vivisimo,bbmao,SavvySearch,Search.
2.
2.
4Web挖掘技术Web挖掘是从与WWW相关的资源和行为中抽取感兴趣的、有用的模型和隐含信息.
一般地,Web挖掘可分为三类:Web内容挖掘,Web结构挖掘和Web使用记录挖掘[6].
Web挖掘技术能改善Web信息检索的质量,提供更多的应用类型,而且Web挖掘技术也是当前数据管理领域的一个热点研究方向[7].
Web内容挖掘:从文档内容或其描述中抽取知识的过程.
其主要内容是对Web页面文档内容及搜索引擎的查询结果进行总结,聚类,分类等.
Web内容挖掘有两种策略:直接挖掘文档的内容或在其他工具搜索的基础上进行改进.
Web结构挖掘:从WWW的组织结构和链接关系中推导知识.
由于文档之间的互连,WWW能够提供除文档内容之外的有用信息,利用这些信息,可以对页面进行排序,发现重要的页面.
第三章介绍的PageRank和HITS算法就是这一类型Web挖掘的代表.
西北工业大学硕士学位论文第二章Web信息检索技术概述10Web使用记录挖掘:主要目标是从Web的访问记录中抽取感兴趣的模式.
WWW中每个服务器都保留了访问日志,记录了关于用户访问和交互的信息,分析这些数据可以帮助理解用户行为,从而改进站点的结构;或为用户提供个性化的服务.
在第四章中介绍的RSS新闻搜索平台中采用的主观排名因子,就是这一类型的应用.
2.
3小结本章首先介绍了信息检索的形式化定义,对特别检索和过滤这两种不同的检索方式进行了对比;介绍了布尔模型、向量模型和概率模型三种经典信息检索模型;指出信息检索系统的基本评价标准是查全率和查准率;描述了一般的信息检索系统中的信息检索过程;接着分析了Web数据的特点,介绍了搜索引擎和元搜索引擎的体系结构和基本工作原理,最后介绍了Web挖掘技术.
西北工业大学硕士学位论文第三章搜索排序算法研究11第三章搜索排序算法研究3.
1基于链接分析的排序算法分析一个超文本文档(即网页)内可能存在大量的超链接,每个超链接指向互联网上的其他文档.
因此,互联网上的文档间存在一个有规则的网络拓扑结构.
对互联网的组织结构和链接关系进行推导,可以得到互联网上某个文档的重要程度,进而可以对这些文档进行排序.
因此,当前主流的搜索引擎(如Google,百度)都采用了基于链接分析的排序算法.
目前基于链接结构分析的搜索引擎排序算法主要都来源于两种经典算法:一种是斯坦福大学SergeyBrin和LawrencePage提出的PageRank算法[8],为了验证该算法的性能,他们建立了Google搜索引擎的原型,现在Google已经发展成全世界最知名,最强大的搜索引擎.
另一种算法是康奈尔大学JonKleinberg提出的HITS算法[9].
本章首先简要描述这两种算法的基本思想,对各自的特点进行了分析比较,然后针对PageRank算法采用的平分页面自身PageRank值的策略,提出了一种按概念权重分配PageRank值的改进算法.
概念可以采用多种方法进行选取,文中给出两种方法.
3.
1.
1PageRank算法PageRank算法是最经典的搜索引擎排序算法,它的基础是网络用户的随机访问模型[10].
Brin和Page在其论文中提出一种用户行为的模型:假设有一个随机的网络冲浪者,任意给定一个网页,持续点击链接,最终厌倦并开始访问另一个随机页面,这一模型被称为随机冲浪模型.
这样,在随机冲浪模型中,一个随机的网络冲浪者访问一个页面的可能性就是该网页的PageRank值.
PageRank算法的基本思想其实来源于传统的学术文献的引文分析方法,而Brin和Page把这一思想应用到了Web页面中.
传统的文献分析方法为,一篇文献的重要性可以通过其他文献对其引用的数量来衡量.
如果文献A被同学科的许多文献所引用,则文献A在该学科内应该是一篇有影响力的著作.
同样,在Web环境下,如果页面A通过超级链接指向了页面B,相当于页面A引用了页面B,即页西北工业大学硕士学位论文第三章搜索排序算法研究面A给页面B投了一票,页面A需要把自己的一部分PageRank值分给页面B,图3-1是一种网络拓朴结构下的PageRank值分配示意图.
最后,根据每个页面的PageRank值来判断页面的重要性,重要的页面会在搜索引擎的搜索结果中位于前列.
如果一个网页有许多网页都指向它,那么它可能获得很高的PageRank值;如果一个网页被一个本身PageRank值很高的页面所指向,那么它同样可能具有很高的PageRank值.
页面PageRank值的计算公式为:PR(A)=(1-d)+d*(PR(T1)/C(T1)+…+PR(Tn)/C(Tn))假设页面T1…Tn都有超链接指向页面A.
其中PR(A)表示页面A的PageRank值;参数d是一个衰减因子,根据不同情况可以设定d在0到1之间,通常设定为0.
85.
C(T)表示页面T指向其他页面的链接个数.
在通常情况下,设定每个网页的初始PageRank值为1,通过以上公式,递归计算各网页的PageRank值,直到网页的PageRank值趋于稳定.
由于其用户行为模型假设用户访问网络是完全随机的,因此一个页面的PageRank值被平分给了其所指向的页面,由上述公式中的项PR(T1)/C(T1)可以明显的看出其平分策略.
959560607080408040C160C2155C395B1120B2190A180A2160A370图3-1PageRank值分配示意图3.
1.
2HITS算法Kleinberg在其论文中提出了HITS算法,用来评定网页内容的重要性.
HITS的重要性评价是针对用户查询的.
该算法将网页分为两个类别,即权威页(authorities)和中心页(hubs).
权威页是表达某一主题的页面,对这一主题12西北工业大学硕士学位论文第三章搜索排序算法研究它的价值很高,依赖于指向它的页面.
中心页是指向多个权威页的页面,它把这些权威页链接在一起,依赖于它所指向的页面.
HITS算法为每个页面引入两个权值,即authority权值和hub权值,通过一定的计算可得到针对某个检索提问的最具价值的网页,即排名最高的权威页.
HITS算法首先通过传统的搜索引擎(如AltaVista)选取一定数量的页面作为根集,然后在根集的基础上进行扩展,把引用根集的页面和被根集引用的页面都加入进来,生成基本集,再针对基本集中的超链接建立所要处理的子图.
在这个子图上,建立页面的authorities和hubs的计算公式.
设A(p)表示页面p的authorities值,H(p)表示页面p的hubs值,指向页面p的集合为B(p)={q1,q2,…,qn},页面p指向的页面的集合为I(p)={q1',q2',…,qn'}.
则A(p)=H(q1)+…+H(qn);H(p)=A(q1'A(qn');通过迭代计算,最终得到页面p的authorities值.
HITS算法中的authorities和hubs值是互相加强的.
图3-2是一种网络拓朴结构下的HITS值分配示意图.
q1q2q3pr1r2r3ap=hq1+hq2+hq3hp=ar1+ar2+ar3图3-2HITS值分配示意图3.
1.
3PageRank算法和HITS算法的比较分析虽然PageRank算法和HITS算法都是基于超链接拓扑结构分析的搜索引擎排序算法,但是两者还是有区别的:13西北工业大学硕士学位论文第三章搜索排序算法研究14(1)PageRank完全忽略网页内容,仅根据网络超链接的拓扑结构计算得到网页的PageRank值,是一种独立查询(query-independent)的算法.
而HITS的authorities值是相对于某个检索主题的,是一种依赖查询(query-dependent)的算法.
(2)PageRank是基于对Web的整体分析,而HITS算法则是通过传统搜索引擎查选结果构建的基本集上进行分析的,是Web的局部分析,容易造成"主题漂移"现象.
(3)虽然PageRank处理的数据比HITS多,但是HITS首先需要抽取根集,并扩充基本集,从客户端等待的时间上看,PageRank需要的时间比HITS短.
(4)从权重的传播上看,PageRank基于随机冲浪模型,可以认为网页的重要性从一个authorities传到另一个authorities.
而在HITS的模型中,则是从hub页传到authorities页.
从目前的应用来看,PageRank算法相对于HITS算法有一定的优势,Google成功的商业运作,就是很好的例证.
虽然PageRank算法已成功应用到Google当中,但是它并不考虑网页的具体内容,平分PageRank值,不考虑各个链接重要性,这是值得改进的.
在下一节中,我们讨论一种权重PageRank改进算法.
3.
2基于概念的权重PageRank改进算法由于PageRank采用的随机冲浪模型认为每个链接的重要程度是相同的,所以采用了平分策略.
实际上,不同的超链接的价值是不同的.
假设A页面有指向B页面的超链接,则B页面可能是和A页面高度相关的一个页面,比如都是讨论同一主题的页面;然而也可能B页面和A页面根本不相关,B页面可能只是一个广告页.
这一点和传统的文献引文分析不同,文献引文经过严格的审查,可以保证引文间的高度相关性,而在Web环境下,超链接的质量无法保证.
针对PageRank所存在的上述问题,结合HITS算法的思想,提出了一种改进算法,即根据网页间概念的关联比重及用户搜索的概念,按权重分配页面的PageRank值.
3.
2.
1基于网页内容的概念选取方法在该改进算法的实现中,首先要为每个网页确定若干个概念.
概念的选取可以有多种方法,如UdoKruschwitz在其论文[11]中总结了一种方法:选择在以下标签上下文中出现多于一次的关键字作为概念.
这些标签包括:meta信息,文档的西北工业大学硕士学位论文第三章搜索排序算法研究15题目,文档的标题,超链接的文本,以及重点强调的部分(如字体为粗体或斜体的部分).
这种方法主要的特点是基于页面源码分析,可以认为是一种客观的概念.
这种对Web页面源码分析提取概念的方法可以认为是传统的文本分析的一个拓展,已经有许多种成熟的算法,特别是针对英文.
这种算法的基本过程可以概括为以下几个关键步骤:(1)对文本进行切词.
针对英文,空格是自然的分割符,由空格隔开的就是独立的单词.
仅仅依靠空格的分词是最基础的,通常情况下还需要有一个停用词表,用来过滤那些对检索来说作用不大的单词,或没有实际意义的单词.
最后,需要进行词干提取,因为英文中不但有比较级的变化,例如比较级,最高级;还有时态、单复数的变化,例如:working,works,worked对应同一个词干work,目前最常用的词干提取算法是PorterStem[12].
针对中文,切词本身就是一项复杂的问题,因为中文没有天然的分割符,容易出现切词的二义性及歧义,中文切词具体方法可以参考相关文献.
(2)构造一个语义字典.
语义字典对于文本切词来说是有指导意义的,它规定了每个词的不同重要级别.
比如,名词,实意动词表达的概念要比虚词,冠词,语气词表达一个文档的实际内容多.
同时,通过语义词典,还可以进行层次概念抽取,同义近义词的合并与提取.
当前已经有较多的成熟语义词典,针对英文有Princeton大学研发的WordNet,针对中文有北京大学研发的现代汉语语料库和语义信息词典.
借助这些语义字典,可以更好的完成文本的切词以及概念的提取.
(3)超文本文档的分析.
超文本文档中不同标记内的文本提供给更多的附加信息,比如在标题标签内的文本,粗体、黑体标签内的文本,超链接中的文本的权重要加大.
3.
2.
2基于Folksonomy的概念选取方法上一小节中提到的概念选取方法是一种客观的选取算法.
Web环境下的文本标记的一个特点就是用户的参与,可以让用户对文档添加概念进行标记,即社会性.
Folksonomy分类法就是民间社会分类法.
这个概念起源于社会性书签服务中最具特色的自定义标签功能.
Folksonomy分类标引可以由三类角色完成,分别为专家,信息发布者,以及普通用户[20].
专家对一个文档的概念标引常常出现在传统的信息检索领域.
比如一个图书馆管理员按照图书馆的分类体系,对一本书进行标引,分类,标记概念.
这要求图书馆管理员熟悉分类体系,需要经过严格的专业知识学习与训练.
如果在Web西北工业大学硕士学位论文第三章搜索排序算法研究16环境下应用,则需要类似图书馆管理员的角色对Web文档进行分类和概念标记.
早期的Yahoo!
网络目录采用的目录式检索就是采用这种方法,它通过人力把Web页面归为若干大类,每一类低下又有若干子类.
但是随着Web文档的海量增长,仅靠专家人力地标记Web文档的可行性不大.
因此,这种方法在Web环境下显然是不适用的.
信息发布者对一个文档的标引在学术论文中很常见,通常作者会从论文中选出规范的、用以表示全文主题内容信息的单词或术语作为这篇论文的关键字列在论文中.
比如,文献[8]的关键字为:"WorldWideWeb","SearchEngine","InformationRetrieval","PageRank","Google".
这些关键字就可以作为文献[8]的概念.
在Web环境下,作者同样可以把关键字发表在文档中,一种可行的方法就是写在Meta标签中,例如concept1,concept2.
但是并不是每个页面的作者都原意完成这种操作,因为它还没有像在学术论文中标记关键字一样成为规范,即使一个页面的作者不编辑Meta标签,也并不影响页面的显示和页面中的各种应用功能.
而且这一方法可能带来垃圾页面,比如作者出于其他目的,在Meta标签中添加和页面实际内容无关的概念,造成垃圾信息.
在Meta标签中堆砌关键字是垃圾页面经常采用的一种方法.
因此这种标记概念的方法虽然比由专家标记的可行性大,但是也并不完全适用于Web环境.
普通用户对Web文档进行添加标签是最适用于Web环境的一种应用模式.
这一模式起源于美味标签(del.
icio.
us)和Flickr(www.
flickr.
com).
美味标签提供了用户对一个网页添加标签的功能.
比如用户A对网站tomcat.
apache.
org添加了三个标签,"Java","Software","WebServer";用户B对这个网站加的标签是"Apache","WebServer","Java";最后经过统计,出现频率最高的标签"Java","WebServer","Apache"就作为这个文档的Folksonomy的概念.
通过统计用户添加的标签,是获取Folksonomy概念的最简单和有效的途径.
采用统计出现频率高的标签,可以有效的抑制一些非法用户添加的恶意概念.
在我们设计开发的WizAg智能RSS新闻聚合搜索平台(www.
wizag.
com)中,提供用户对每个RSS新闻文档添加标签的功能,通过统计这些标签出现的频率,可以作为一篇新闻文档的Folksonomy概念;在第四章中,将详细介绍这种用户添加的Folksonomy概念对RSS新闻文档排名的影响.
在我们开发的浏览器插件中,通过浏览器的支持,可以为用户提供对任何网页添加标签的功能.
在第五章中,将详细介绍这种添加标签的方法.
西北工业大学硕士学位论文第三章搜索排序算法研究3.
2.
3基于概念的权重PageRank改进算法设计在改进算法中,考虑一个页面与它所指向的所有页面之间的相似程度,按权重分配这个页面的PageRank值,并且考虑用户当前正在搜索的关键字,在这里认为用户正在搜索的关键字为一个概念.
改进后的算法描述如下:假设有一个页面A,它通过超链接指向若干个页面,再设Concept(A)为页面A的概念的集合,Out(A)为页面A通过自身页面内的超链接所指向的其他页面的集合,设Out(A)={p1,p2,…,pn};C(A)表示页面A指向其他页面的链接个数,在这里C(A)=n;可以定义一个平分因子d',用于给那些概念和页面A完全不相关的页面分配一定比例的PageRank值.
可以定义页面pi从页面A获取的PageRank值为:PR'(pi)=PR(A)*d'*(1/C(A))+PR(A)*(1–d')*wi其中wi就是页面A和页面pi基于概念的权重.
则一个页面的PageRank值的计算公式可以改进为:PR(A)=(1-d)+d(PR'(T1)+…+PR'(Tn))分别定义用户搜索关键字(假设为K)K∈Concept(A)和KConcept(A)情况下的wi:当K∈Concept(A)时,wi的定义:初始时令count=0;对于每一个Out(A)中的元素pi,如果K∈Concept(pi),则count++;上述操作结束后,如果K∈Concept(pi),wi=1/count;如果KConcept(pi),wi=0.
当KConcept(A),wi的定义:设Ni=|Concept(A)∩Concept(pi)|(i=1,2,…,n),即页面A的概念集合和页面pi的概念集合的交集的元素个数;令wi为页面pi和页面A的权重值,则可定义),.
.
.
,2,1(1niNNwniiii==∑=.
例如,对图3-3所示的网络拓朴结构可分别计算页面p1,p2,p3从页面A处获得的PageRank值.
假设PR(A)=1,d=0.
85,d'=0.
2.
(1)根据经典PageRank计算公式,可算出:PR(p1)=PR(p2)=PR(p3)=(1-0.
85)+0.
85*1*(1/3)=0.
43333333(2)根据基于概念的权重PageRank公式,计算过程如下:假设用户搜索的概念为C1:PR(p1)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*(1/2))=17西北工业大学硕士学位论文第三章搜索排序算法研究0.
54666667PR(p2)=PR(p1)=0.
54666667PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*0)=0.
20666667可以看出,由于p1,p2页面含有搜索的概念C1,因此从页面A获得了更多的PageRank值.
而p3只获得了平分的PageRank值.
假设用户搜索的概念为C4:PR(p1)=PR(p2)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*0)=0.
20666667PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1–0.
2)*1)=0.
88666667可以看出,由于只有p3页面含有搜索的概念C4,因此p3从页面A获得了更多的PageRank值.
p1,p2只获得了平分的PageRank值.
图3-3基于概念的权值PageRank分配示意图假设用户搜索的概念为C5,即用户搜索概念不在页面A的概念集合中:PR(p1)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(2/7))=0.
40095238PR(p2)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(3/7))=0.
49809524PR(p3)=(1-0.
85)+0.
85*(1*0.
2*(1/3)+1*(1-0.
2)*(2/7))=0.
40095238由于用户搜索的概念没有出现在页面A中,因此页面A按照和其指向的各个页面的概念相似程度,按权重分配了自己的PageRank值.
18西北工业大学硕士学位论文第三章搜索排序算法研究3.
3基于用户反馈的结果归并算法在2.
2.
3节中已经介绍了元搜索引擎的基本概念.
其中提到元搜索引擎的一个重要组成部分是进行结果收集后的统一显示.
常见的元搜索引擎结果融合策略有:直接将各独立搜索引擎的结果合并显示,按各独立搜索引擎响应时间的先后顺序返回,摘要排序法,位置排序法,摘要/位置排序法,星级体系排序法等[5,13].
以上排序方法都是按照客观因素进行排名的,比如响应时间,文档词频,链接在各个独立搜索引擎的排名位置,独立搜索引擎搜索到相同链接的次数等.
这些排名方法都没有考虑用户的搜索行为,即用户对搜索结果的评价.
为了提高元搜索引擎的查准率,本节提出一种结合用户反馈的元搜索结果归并方法.
该方法的特点在于记录用户反馈,结合用户兴趣爱好和客观因素进行综合排名,在第四章中将介绍一种类似的新闻综合排名算法.
基于用户反馈的元搜索引擎模型在原有元搜索引擎模型的三个组成部分上,增加了数据库,知识库,WordNet语义字典模块,如图3-4所示.
结果显示代理将查询结果返回给用户,同时把用户的行为信息记录到数据库中.
通过统计分析数据库上的这些用户行为,结合WordNet语义字典和知识库对搜索关键字进行聚类,计算搜索引擎质量分值,形成搜索引擎选择策略,指导请求提交代理选择调用独立的搜索引擎.
在进行结果归并时,通过记录的用户行为信息,可以计算用户评价分值,作为结果归并时的主观影响因子.
如图3-4基于用户反馈的元搜索引擎体系结构图首先取回各个独立搜索引擎返回的查询结果,去除重复的链接,设链接集合19西北工业大学硕士学位论文第三章搜索排序算法研究为RUrl={Url1,Url2,…,Urlm}.
搜索结果链接Urlj(针对搜索关键字Ki)的用户评价分值:RUrl)(Url)Url,ect(KValueInDir*d+)Url,t(KValueDirec*d=)Url,Value(Kjji2jiiji∈)RUrl),(KClickCountMin()Url,(KClickCount*d*EXP((-1)-1)Url,t(KValueDirecijiji=))Url,'t(KValueDirec*)'K,Sim(K(*e*EXP((-1)-1)Url,ect(KValueInDir'jiiiji∑∈=KiSimSetKi用户评价分值(Value(Ki,Urlj))是用户直接评价分值(ValueDirect(Ki,Urlj))与用户间接评价分值(ValueInDirect(Ki,Urlj))之和.
用户直接评价分值考虑用户点击Ki的搜索结果链接的情况.
设ClickCount(Ki,Urlj)为用户点击搜索关键字Ki的结果集中链接Urlj的次数之和;Min(ClickCount(Ki,RUrl))表示用户点击搜索关键字Ki的结果集中任一链接的最小的次数.
d为可调节系数,根据不同情况可以设定不同的值,一般可以取0.
1~0.
5;选择指数函数归一化.
用户间接评价分值考虑用户点击与搜索关键字Ki相似的关键字集合Ki'的点击情况.
集合KiSimSet={Ki'|Sim(Ki,Ki')>M},即与Ki的相似度大于阈值M的关键字集合.
Sim(Ki,Ki')是Ki与Ki'之间的相似度计算函数,可以借助基于WordNet语义词典的词语相似度计算软件,比如WordNet::Similarity,计算出搜索关键字之间的相似度数值;e为可调节系数,根据不同情况可以设定不同的值,一般可以取0.
1~0.
5;选择指数函数归一化.
]14[为了达到较高的综合查准率,元搜索引擎的结果归并策略应该结合客观和主观两方面因素,因此对元搜索的结果归并排序公式可以做如下统一的定义:搜索结果链接Urlj(针对搜索关键字Ki)的归并排名值:RankValue(Ki,Urlj)=a*Object(Ki,Urlj)+b*Subject(Ki,Urlj)Object(Ki,Urlj)代表归一化后的客观排名影响因子,可以包括上述提到的摘要排序值,位置排序值,星级体系排序值等等;Subject(Ki,Urlj)代表用户对结果链接Urlj的主观排名影响因子,即用户评价分值Value(Ki,Urlj).
a,b为可调节系数,元搜索引擎可以根据不同的查询关键字,不同的查询领域,控制主客观排名影响因子所占的比例.
例如,在专业搜索领域,元搜索引擎调用专业搜索引擎搜索,由于进行专业搜索的用户大部分具有该领域的专业知识,因此,用户对搜索结果的评价意义较大,可以加大主观影响因子;而在一般的通用搜索领域,用户对搜索结果的评价意义可能不如前者大,而且可能存在噪音的影响,因此可以加20西北工业大学硕士学位论文第三章搜索排序算法研究21大客观影响因子.
元搜索的结果显示代理通过计算每个链接的归并排名值,按从高到低的顺序把结果集返回给用户,完成结果归并.
在第四章的RSS新闻搜索平台的新闻排名规则中的主观排名因子设计,就借鉴了这一基于用户反馈的排序算法.
3.
4小结本章首先介绍传统了经典搜索引擎算法PageRank和HITS,并对其优缺点进行了对比.
针对原有PageRank算法采用的平分页面自身PageRank值的策略,提出了一种按权值分配的改进算法.
权值由页面间的概念关联比重和用户的搜索概念确定.
结合参加的项目经验,分别提出了主观和客观两种选择概念的策略.
最后,提出一种基于用户反馈的元搜索模型,并在此模型基础上提出一种元搜索引擎结果归并算法.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现第四章RSS新闻搜索平台的设计与实现RSS新闻是当前Web实时信息的一种主要发布形式.
它是站点用来和其他站点之间共享内容的一种简易方式,通常被用于新闻网站.
当前,各大新闻网站,门户网站,甚至一些个人Blog都提供了RSS服务,该服务已经成为网络中最热门的服务之一.
一些主流新闻网站的RSS更新周期非常的小,几乎每时每刻都有新的RSS种子诞生.
为了提供强有力的RSS新闻浏览,聚合,搜索功能,我们设计开发了智能RSS新闻聚合搜索平台.
本章详细介绍平台的体系结构,存储结构设计,搜索排名机制和性能优化方法.
4.
1RSS新闻搜索平台基本框架平台采用浏览器/服务器构架.
平台的体系结构如图4.
1所示.
服务器1:RSS新闻搜索下载,概念抽取,排序服务程序.
服务器3:数据库服务器,运行数据库B(只读)服务器2:数据库服务器运行数据库A(可读,可写)服务器4:Web服务器浏览器浏览器浏览器浏览器互联网(提供RSS服务的网站)图4.
1RSS新闻搜索平台体系结构图服务器1:运行一系列RSS新闻搜集下载综合服务程序.
RSS新闻搜索下载22西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现23服务程序按照一定的搜索规则,在互联网上找到RSS种子,定时自动更新下载其包含的新闻信息,并保存到服务器2上的数据库A中;RSS新闻概念抽取服务程序对下载的新闻主体进行概念抽取,抽取的规则基本按照3.
2.
1节中提到的基于网页内容的概念抽取方法进行;RSS新闻排序服务程序对下载下来的新的RSS新闻,结合其相应的概念,按照特定的排序规则进行排名,并将排序值更新到数据库A中.
服务器2:一台数据库服务器,运行着数据库管理系统,维护一个可读可写的数据库A.
它保存着所有的RSS新闻信息,数据备份,相关参数.
服务器3:一台数据库服务器,但它运行的是一个只读数据库.
主要用来为Web服务器提供数据.
这台数据库的更新是由数据库服务器A控制的,当数据库服务器A中有的数据有变化,按照一定的规则,数据库A把新的内容复制到数据库B中,并把数据库B中过时的数据清除.
服务器4:一台Web服务器,运行着整个网络应用程序.
它从服务器3中的只读数据库B中读取数据,动态生成Web页面显示给用户.
用户的反馈信息通过浏览器传到Web服务器,再由Web服务器写入服务器2的可写数据库A.
服务器1,服务器2,服务器3,服务器4在同一个局域网内.
浏览器:用户通过浏览器访问Web服务器,获取Web页面进行浏览.
用户的反馈操作通过浏览器返回给Web服务器.
4.
2数据管理结构设计与实现由于平台设计的关系繁多,数据类型规范,数据存储量增长较快,因此选用关系型数据库作为平台数据的数据管理模型.
由于平台涉及两个数据库服务器,在局域网内构成分布式数据库结构.
为了降低分布式数据库的复杂性,服务器2,3上的数据库选用同一种数据库管理系统,构成同构同质型分布式数据库.
在实现中,数据库管理系统选用的是MicrosoftSQLServer2000.
RSS新闻搜索平台的搜索对象是新闻文章,相对与传统搜索引擎系统中的网页.
本节首先分析介绍关系数据库设计的基本原则,然后分析新闻搜集下载服务程序下载到的RSS种子(feeds)的XML文档;然后建立一个泛关系模型,包含一篇文章的所有属性,分析该模式包含的函数依赖,并对泛关系进行模式分解;最后建立实体关系模型.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现244.
2.
1关系数据库模式设计原则在关系数据库中占据核心地位的是关系,在实现中以表的形式表现出来.
衡量关系模式好坏的标准是模式的范式.
范式的种类于数据依赖有着直接的联系.
基于函数依赖的范式有1NF,2NF,3NF,BCNF等.
1NF要求每个属性值都是不可再分的原子值;2NF要求每个非主属性完全函数依赖于候选键;3NF要求每个非主属性都不传递依赖于候选键;BCNF要求每个属性都不传递依赖于候选键.
对于更复杂的数据模型,还有针对多值函数依赖的4NF,针对连接依赖的5NF等.
关系模式设计可能在一开始设计的是包含所有属性的泛关系,或者由于用户需求的变更导致关系模式的修改,这些情况下都无法到到必要的范式要求,这时就需要对关系进行模式分解.
在关系模式分解过程中要保证数据等价和语义等价.
数据等价需要通过保证无损连接分解实现,而语义等价需要通过保持函数依赖实现.
范式的提出是为了在函数依赖保持的前提下尽可能的避免数据冗余.
然而随着硬件价格的下跌,海量存储技术的出现,使得在一些应用场合允许出现一定的数据冗余.
比如,通过一定的数据冗余来提高速度和性能,因此可以适当的使用非规范化的模式提高特定操作的性能,以支持对响应时间要求苛求的操作.
4.
2.
2RSS种子文档的结构分析一个RSS新闻信息常常包含一个标题和一个主体信息,通常还包含指向这个完整信息的超链接.
用户可以首先浏览新闻标题和简要的主体信息,如果发现该文章有趣,可以点击该新闻的超链接查看新闻全文.
当前主流网站提供的RSS种子通常是一个XML文档.
发布新闻的网站定时更新XML文档的内容,发布最新的新闻信息,就好像通讯社每天都发布新的通信稿.
通过分析每个种子的XML文档,可以获取新闻文章的全部属性.
每个RSS种子通常有一个名字,它所指向的XML通常由一个超链接定位.
例如种子SlateMagazine,它的XML位置为http://www.
slate.
com/rss/,图4-2是该种子在2006年12月30日的快照.
如图4-2所示,每个XML文档通常包含若种子的描述信息和若干篇新闻;每篇新闻通常是由item标签标记的,每个item内又包括标题,简要的描述,新闻发布时间,和指向这篇新闻完整内容的超链接,同时还可能包括一些扩展信息,例如类别信息,文章的作者等.
当RSS新闻搜索下载程序将种子的XML文档下载西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现完成后,需要对XML文档进行分析,把每个item的详细信息提取出来,构成一篇篇新闻文章.
图4-2RSS种子文档示意图(SlateMagzine2006-12-30)新闻文章下载完成后,经过RSS新闻概念抽取服务程序对每篇新闻文章的描述进行了概念抽取过程,每篇文章还有对应的若干个概念.
因此一篇文章的全部属性可以表示为:ArtitlesR(Title,Description,PubDate,Link,RssFeedsName,RssFeedsLink,Concepts)但是如果以这样的模式把新闻文章存储到数据库中,会导致大量的数据冗余,容易导致不一致性的发生.
如图4-3所示,如果一篇文章的描述抽取出了若干个概念,则这篇文章的基本信息(Title,Description,PubDate,LinkRssFeedsName,RssFeedsLink)都会冗余存储,例如图4-3中1至7行记录的是同一篇文章,但是由于这篇文章的描述信息抽出了七个概念,因此导致数据冗余;同时,如果两篇不同的新闻对应的描述相同,那么这两篇新闻的描述和概念(Title,Descripton,Concepts)也发生了数据冗余,比如第1至7行的一篇文章和第22至28行的一篇文章就发生了此类冗余.
25西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现图4-3ArticlesR的关系图模式ArticlesR包含了一个新闻文章应该包含的所有属性,可以认为该关系是一个泛关系,可以用关系数据库的规范化原则对这个泛关系进行模式分解,得到规范化的模式.
在下一节中,我们使用实体关系模型对新闻文章建模.
4.
2.
3设计实体关系模式经过对RSS种子文档的分析,我们可以确定在搜索平台中最常用到的四个实体.
实体的定义分别为RSS种子(RssFeeds),新闻文章(Articles),描述信息(Descriptions),概念(Concepts).
这四个实体是平台应用的核心,其他所有的应用都是围绕着这四个实体展开的.
实体Rss种子的属性包括:种子的名字(RssFeedsName),指向该种子XML文档的超链接(RssFeedsLink).
实体新闻文章的属性包括:新闻发布时间(PubDate),和指向这篇新闻完整内容的超链接(Link),包含文章标题和描述的描述信息.
实体描述信息的属性包括:标题(Title),简要的描述(Description).
实体概念的属性包括:概念的内容(Concepts),出现这个概念的文章数(Count).
关系的定义为:种子包含文章关系(R_RssArticles),包括实体Rss种子和实体新闻文章.
一个种子可以包含若干篇新闻文章,一篇新闻文章也可能来源于多个种子,是一个多对多的关系.
文章包含描述关系(R_ArticlesDescriptions),包括实体新闻文章和实体描述信息.
一篇新闻文章只对应一个描述信息,但是一个描述信息可能对应多篇新闻文章,即多篇新闻文章的内容可能是重复的,是一个多对26西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现一的关系.
描述信息对应概念关系(R_DescriptionConcepts),包括实体描述信息和实体概念.
一个描述信息按照概念抽取算法可能抽取若干个概念,而一个概念可能由多个描述中都抽取出来,是一个多对多的关系.
最后建立实体关系模型图,如图4-4所示.
MM1NNNRssFeedsR_RssArticlesArticlesR_ArticlesDescriptionsDescriptionsR_DescriptionConceptsConcepts图4-4新闻文章的实体关系模型图4.
2.
4表的模式设计在实体关系模型的基础上进行关系的模式设计,首先针对实体进行模式设计:RssFeeds(RssFeedsLink,RssFeedsName)Articles(Link,PubDate,Title,Description)Descriptions(Title,Descritpion)Concepts(Concepts,Count)在这些模式上的函数依赖分别为:RssFeeds:RssFeedsLink->RssFeedsNameArticles:Link->PubDate,Title,Description该模式设计的每个属性已经是原子的,符合1NF规范.
同时,不存在属性传递依赖于主属性,符合BCNF规范.
虽然每个实体中已经可以选取适当的属性作为主键,但是这些属性的数据类型都是字符类型.
当实体通过关系表连接时,可能用到大量的连接操作,连接操作如果在字符类型的属性上进行,需要进行大量的字符串匹配算法,必将严重影响连接的效率,因此在这里对每个实体都加入一个整型的自动编号属性作为主键.
由于R_ArticlesDescriptions关系是多对一的关27西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现28系,因此在模式设计时,可以不单独把这个关系设计为一个表,而把"多"的那个实体表的主键作为外键加入到"一"的实体属性里,因此,经过修改的实体表模式设计为:RssFeeds(RssFeedsId,RssFeedsLink,RssFeedsName)Articles(AritlcesId,Link,PubDate,DescriptionId)Descriptions(DescriptionId,Title,Descritpion)Concepts(ConceptsId,Concepts,Count)在这里,每个实体表都必须满足实体完整性约束,即每个表的主键都不能为空.
由于我们对每个实体都选用了自动编号的属性作为主键,因此主键都不会为空.
为了更好的从语义上保证实体完整性,要求RssFeeds的属性RssFeedsLink不能为空;Articles的属性Link不能为空;Descriptions的属性Title和Description不能同时为空;Concepts的属性Concepts不能为空.
同时,Articles表还要保证参照完整性,即Articles的属性DescriptionId是参照Descriptions的外码.
在实体表的基础上,对实体关系模型中的多对多的关系进行模式设计.
R_DescriptionConcepts(DescriptionId,ConceptsId)R_RssArticles(RssFeedsId,ArticlesId)这两个关系表的属性必须满足参照完整性.
即R_DescriptionConcepts的属性DescriptionId是参照Descriptions的外码,属性ConceptsId是参照Concepts的外码;R_RssArticles的属性RssFeedsId是参照RssFeeds的外码,属性ArticlesId是参照Articles的外码.
在4.
2.
2节中我们看到,一篇新闻文章包含的全部信息应该是模式ArticlesR包含的属性.
在本节设计的模式基础上,需要进行连接查询得到新闻文章的所有属性.
得到新闻文章的基本信息的操作如下:PrpjectArticlesId,Title,Description,PubDate,Link(ArticlesNATURALJOINDescriptions)得到新闻文章对应的种子信息的操作如下:PrpjectArticlesId,RssFeedsId,RssFeedsName(ArticlesNATURALJOINR_RssArticlesNATURALJOINRssFeeds)得到新闻文章对应的概念的操作如下:PrpjectArticlesId,ConceptsId,Concepts(ArticlesNATURALJOINDescriptionsNATURALJOINConcepts)以上三个查询可以分别查询得到文章的基本信息,文章对应的种子信息,文章对应的概念.
下一节将介绍使用存储过程将每一个查询封装起来,提供给Web服务器上的Web应用程序调用的方法.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现4.
2.
5存储过程接口设计在关系数据库的实现中,上一节提到的三个关系代数查询可以方便的转化成说明性查询语言SQL的查询语句集.
Web应用程序可以通过将拼接好的SQL查询串发送给数据库管理系统,获取相应的数据.
同时也可以调用存储过程获取相应的数据.
存储过程是一组为了完成特定功能的SQL语句集,经编译后存储在数据库中.
存储过程是数据库中的一个重要对象,任何一个设计良好的数据库应用程序都应该用到存储过程.
存储过程具有以下优点:存储过程允许标准组件式编程;能够实现较快的执行速度;能够减少网络流量;可被作为一种安全机制来充分利用.
如图4-5所示,存储过程ShowArticlesInfos的功能是提供给Web应用所需要的全图4-5存储过程实例程序代码部信息.
Web应用可能会按照用户的要求,选择查看不同的新闻文章.
比如用户要求查看最近两天的文章,存储过程中的参数@Date就可以传递一个时间参数到存储过程内.
通过参数的设置,可以使Web应用的数据库调用不受影响,和数据库之间的交互变得更加透明.
作为数据库开发人员,只要更改存储过程体内的SQL29西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现语句段,提供给Web应用程序就可以了.
在平台的设计中,Web应用程序读取数据库的相关内容显示在页面,用户通过Web应用程序做的反馈信息,RSS新闻搜索下载,概念抽取,排序服务程序对数据库的数据更新,排序,删除等操作都通过存储过程完成.
根据需求分析的结果,Web应用中显示的页面需要通过数据库获取的数据有如下几种:(1)显示最近n天的新闻文章,并且按每页m条新闻,分页显示.
(2)显示种子i的最近n天的新闻文章.
(3)显示包含某个概念i的最近n天的新闻文章.
(4)显示包含某一指定字符串string的所有新闻文章.
在Web应用中,提供了很多用户反馈的方式.
比如添加Tag,加评论,还有投票标注等.
用户反馈的信息需要返回到数据库记录,这些信息用于再现用户的反馈,并且这些反馈信息对排序也有贡献,详细内容将在4.
3节中介绍.
用户的反馈也通过存储过程的方法与数据库交互.
(5)用户a对新闻文章i添加Tag,Tag的内容为'tagcontent'(6)用户a对新闻文章i添加评论信息,评论信息的内容为'commentcontent'(7)用户a对新闻文章i投票标注.
30西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现RSS新闻搜索下载,概念抽取,排序服务程序的数据库接口设计:(8)下载新的新闻文章,保存到数据库.
(9)对新下载的文章抽取概念,保存到数据库.
(10)对文章计算排名.
4.
3搜索操作的性能优化RSS新闻搜索下载服务程序每天都在下载大量的新闻文章,并存储到数据库中.
由于新闻文章的增多,相应的概念也会大量增加,这都导致了数据库的数据量增长迅速.
随着数据量的增长,使数据库的性能也有所下降.
在RSS新闻搜索平台中的一些需要与用户实时交互的搜索操作,速度快甚至比结果准确更重要.
如果让用户等待的时间过长,会使用户产生厌烦心理.
因此,本节主要研究如何提高数据库的性能,特别是提高特定查询的性能.
4.
3.
1针对查询建立索引在RSS新闻搜索平台中,用户最常使用的是进行多种方式的查询.
为了提高查询速度,针对特定查询建立索引是必要的.
最常用的查询就是显示文章的所有基本信息,这个操作用到若干表的连接操作.
因此需要在每个表的连接属性上建立聚集索引.
针对连接ArticlesNATURALJOINR_RssArticlesNATURALJOINRssFeeds和连接ArticlesNATURALJOINDescriptionsNATURALJOINConcepts,需要对Articles表,R_RssArticles表,RssFeeds表,Descriptions表,Concepts表连接所需的属性建立索引.
而这些连接所需的属性恰好是这些表的主键,因此在这些表的主键上建立聚集索引,可以提高查询速度.
另一类常用的查询涉及到概念.
一种查询操作是通过文章查找这个文章包含31西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现的所有概念,用于Web页面的显示.
另一种是由概念查找包含这个概念的所有新闻文章,即查看同一主题的相关文章.
针对这两类查询,需要建立两个索引,Descriptions->Concepts的DCI索引和Concepts->Descriptions的CDI的索引.
假设有四篇新闻,其包含的概念分别为:News1(MiddleEast,BushAdministration)News2(SaddamHussein,MiddleEast,BushAdministration)News3(NorthKorea,NuclearTest)News4(DiplomaticEffort,BushAdministration,NuclearTest)DCI索引较为常见,可以通过在R_DescriptionConcepts表上的DescriptionId属性上建立聚集索引就可以实现,图4-6是一个简单的DCI示意图.
而CDI索引可以认为是一种倒排索引,每个索引项包含一个概念和一组指针,指针指向包含该概念的所有新闻文章,如图4-7所示,当用户想查看和"nucleartest"相关新闻时,可以快速的通过CDI查找到新闻文档New3和News4.
CDI索引类似搜索引擎中索引器建立的索引,但是索引器建立倒排索引的索引项是针对页面中的每一个词,而CDI的索引项针对的是概念.
这一索引的实现是通过建立一个新的表R_ConceptsDescription(ConceptsId,DescriptionsId),并在ConceptsId上建立聚集索引.
News1News2News3News4MiddleEastSaddamHusseinNorthKoreaDiplomaticEffortBushAdministrationNuclearTestMiddleEastBushAdministrationBushAdministrationNuclearTest图4-6DCI索引示意图32西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现BushAdministration334.
3.
2拆分大表经过服务器上的统计,服务器1上的RSS新闻下载服务程序每天下载的文章数在新近下载的新闻文章信息,即按时间比较方便,当新的一个月开始时,就可以执行与如图4-9所示图4-7CDI索引示意图2~3万之间,最多一天的文章下载数量是近5万篇.
这样存储新闻文章基本信息的表就会迅速增长,例如文章基本信息Articles表,描述的基本信息Descriptions表.
而几乎所有的查询都要涉及到这两个表,而且大部分查询都要用到连接操作.
每次操作数据库都需要把表从磁盘读到缓冲区,随着表的增大,访问磁盘的次数增多,必将导致性能严重下降.
根据需求,Web应用程序访问最多的数据是顺序进行查询.
因此,可以按照时间,把数据量大的表拆分成小表.
拆分的规则为把现有的大表,按时间间隔(比如一个月时间)拆分成若干小表,如图4-8所示.
Articles表按时间的拆分可以通过SQL语句实现,比如生成Articles_2表的实现如图4-9所示.
按时间拆分的控制类似的SQL语句完成.
执行的时机可以借助触发器完成,但是由于触发器会带给数据库额外的负担,因此在实现中选择使用的方法是通过外部程序调用,即通过RSS新闻下载程序在每个月开始时,调用相应SQL语句完成对大表的拆分.
MiddleEastNuclearTestSaddamHusseinNorthKoreaDiplomaticEffortNews1News2News4News1News2News3News4News2News3News4西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现.
.
.
Articles表.
包含了一年的所有新闻文章基本信息数据.
Articles_1表.
包含1月份的数据Articles_2表.
包含2月份的数据Articles_12表.
包含12月份的数据图4-8对Articles表按时间的拆分示意图图4-9按时间拆分Articles表的SQL实现按时间拆分是拆分的一种规则,还可以按其他规则进行拆分.
按照服务器上的统计信息,按种子查询的概率仅次于按时间查询,例如在Web应用中,用户经常选择查看某一特定种子的新闻.
因此可以通过文章来自的种子进行拆分,如图4-10所示.
Articles表按种子的拆分可以通过SQL语句实现,比如生成Articles_TechCrunch表的实现如图4-11所示.
按种子拆分的规则不仅可以达到按时间拆分规则的效果,还可以作为一种数据分片的原则应用在分布式数据库中.
比如可以把所有中文种子的小表分配到中国的数据库服务器中,把所有日文种子的小表分配到日本的数据库服务器中,这样减少物理网络传送时间,达到提高速度的目的.
对Articles表的拆分结束后,需要把和Articles关联密切,查询经常使用的的表也进行拆分.
例如经常有查询用到ArticlesNATURALJOINR_RssArticles和34西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现ArticlesNATURALJOINDescriptions这两个连接操作.
如果仅仅保证Articles用小表,而和它连接的表依然是大表,大表的频繁磁盘读写使连接速度依然较慢.
因此,需要对R_RssArticles和Descriptions表进行拆分,拆分策略依赖于Articles表的拆分策略.
如果Articles表按时间拆分,则R_RssArticle和Descriptions表也按时间拆分,例如R_RssArticles_2,Descriptions_2表对应Articles_2表,仅包含Articles_2表对应的文章;如果Articles表按种子拆分,则R_RssArticle和Descriptions表也按种子拆分,例如R_RssArticles_TechCrunch,Descriptions_TechCrunch表对应Articles_TechCrunch表,仅包含Articles_TechCrunch表对应的文章.
R_RssArticles表和Descriptions表的拆分SQL实现方法类似于Articles表,这里不在赘述.
.
.
.
Articles表.
包含了所有种子的新闻文章基本信息数据.
Articles_Digg表.
包含种子Digg的数据Articles_BoingBoing表.
包含种子BoingBoing的数据Articles_TechCrunch表.
包含种子TechCrunch的数据图4-10对Articles表按来源种子的拆分示意图图4-11按来源种子拆分Articles表的SQL实现35西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现36拆分时需要考虑的一点是使大部分的查询在某一个拆分后的小表上可以实现,这样可以明显减少磁盘定位和缓冲区换入换出的代价,因此这样拆分大表对性能提高有明显帮助.
如果拆分的表过于小,使得大部分查询都要涉及多个小表,反而会影响查询的性能.
同时,表拆分的过多会使表本身变多,增大数据库管理系统的系统表和系统负担.
拆分的规则可以视具体情况而定,如果一个月的数据量仍然很大,可以考虑按周拆分;如果按每个种子拆分,有的种子对应的文章太少的话,可以按多个种子进行合并拆分.
4.
3.
3解除规范化设计把一个规范化的模式变化为非规范化的过程被称为解除规范化.
在硬件存储设备的价格急剧下降的情况下,允许一定量的数据冗余来提高响应速度是可取的,是一种空间换取时间的策略.
考虑Web应用最常使用的新闻文章数据.
当用户通过URL(www.
wizag.
com)访问站点,首先呈现给用户的就是网站的首页.
首页显示速度的快慢,直接影响用户对该网站的信心.
如果每次首页显示的数据都要通过若干连接才能找到,首页显示的速度无疑会很慢,因为即时使用了索引,在数据量相当大的情况下,连接操作比选择操作还是要慢很多.
在这种情况下,可以考虑使用在4.
2.
2节中涉及的ArticlesR关系模式.
因为在这个关系模式上,直接进行选择就可以提供给Web应用需要的所有数据,而不需要再进行连接操作.
这就需要对原有模式进行解除规范化.
在实现中,建立一个ArticlesR关系模式的表ArticlesCache.
命名为Cache的原因是因为这个表不代表一个实体,仅仅是因为性能的需要,提供的一个中间结果表.
不需要把所有的Articles表的数据全部存在ArticlesCache表中,这样就失去了使用规范化设计的Articles表的意义.
结合4.
3.
2的按时间拆分的思想,可以把最近若干天(例如七天)的新闻文章信息保存在ArticlesCache表中.
ArticlesCache表的最方便的实现是使用物化视图,随着新的新闻数据的到来,物化视图可以自动更新,不需要其它介入.
另一种方法就是定时更新,删除旧的ArticlesCache表,在新数据的基础上,生成新的ArticlesCache表.
由于SQLServer2000对物化视图的支持不完善,在该平台的实现中采取的是后一种策略.
实现依然采用SQL代码,如图4-12所示.
这样查询本身的耗时就是在一个表上的选择操作,和连接操作相比,耗时已经非常小了.
如果服务器的内存足够大,可以把ArticlesCache表一直加载在内存中,西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现设立较高的优先级,使得数据库管理系统的缓冲区交换策略不能将此块内容换出.
这样这一查询操作不涉及磁盘的读操作,速度会更快.
如果内存不够大,可以适当调小ArticlesCache表的大小,比如可以把近三天,近一天的内容一直加载在内存中.
在内存极端紧张的情况下,可以把首页需要显示的若干新闻文章的信息加载到内存,使得首页所需数据的快速显示.
在SQLServer2000中,通过DBCC命令,可以完成强制加载一个表在内存而不换出的功能.
图4-12生成ArticlesCache表的SQL实现解除规范化设计可能带来的缺点就是数据的不一致性.
在搜索平台中,新闻文章下载完成后,没有操作去修改文章的内容.
因此,只要保证生成ArticlesCache表时数据一致,在以后的正常操作中,不会发生不一致现象的出现.
即时由于非法操作导致了数据不一致,在下一次生成ArticlesCache后就可以恢复,短暂时间的数据不一致性不会对平台带来致命的影响,因为毕竟RSS新闻搜索平台对数据一致性的要求没有银行系统那么严格.
关于数据一致性的问题其他问题,在下一节通过设定事务的隔离级别来详细讨论.
4.
3.
4事务隔离级别设定37在关系数据库中,在没有指定事务的情况下,认为每条SQL语句的执行都是一个事务.
事务具有ACID性质,即原子性,一致性,隔离性和持久性.
原子性要求西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现事务内的操作要么全部执行,要么什么都不做,由数据库管理系统的事务管理子系统实现;一致性要求事务的执行不能带来不一致的数据;隔离性要求并发执行的多个事务的正确性,由数据库管理系统的并发控制子系统实现;持久性要求事务一旦完成,所有更新永久的反映在数据库中,由数据库管理系统的恢复管理子系统完成[15].
SQL2提供事务的四种隔离级别,由高到低分别为:SERIALIZABLE:保证并发的事务是可串行化的.
是系统默认的级别.
REPEATABLEREAD:只允许事务读已提交的数据,并且要求共享锁一直保留到事务结束.
READCOMMITTED:允许事务读已提交的数据.
READUNCOMMITTED:允许事务读未提交的数据.
在SQL中可以设置一次数据库连接的事务级别,如图4-13所示.
图4-13设定事务隔离级别的SQL语句示例为了保证事务的隔离性,数据库采用封锁机制,对一个资源的读操作,DBMS加共享锁;对一个资源的写操作,DBMS加排它锁.
共享锁之间是相容的,而共享锁与排它锁之间,排它锁和排它锁之间都是相斥的.
当多个事务争用一个资源时,可能导致某个事务的长时间等待,饿死,甚至带来死锁.
考虑平台的如下情况:当RSS新闻下载服务程序下载了新的文章后,要进行INSERT操作插入到数据库中,这时需要对Articles表加排他锁.
而如果这时来了查询操作,需要进行对表Articles的查询,查询操作必须等待下载服务程序对数据库的插入操作全部结束.
平均每次下载文章是1000篇左右,插入到数据库的时间可能需要5~10秒中.
这样,查询操作就可能需要等待5~10秒中后进行.
同样,当RSS新闻排序服务程序在运行排序计算时,需要对Articles表进行UPDATE操作,同样要进行加排他锁操作,而排序的计算时间更长,每次执行需要在30分钟左右,如果在30分钟内无法响应用户的查询,则这对整个Web应用来说是明显不合理的.
因此,为了保证查询的速度,可以选择适当的降低事务隔离级别.
把所有查询相关事务的隔离级别都设置成READUNCOMMITTED.
虽然这样可能导致查询结果有不一致的数据,但是和等待较长时间相比,对RSS搜索平台来说是一个合适的选择.
在图4-5所示的显示Web应用所需文章信息的存储过程实例程序代码中,就通过SQL语句降低了隔离级别.
通过降低隔离级别可以降低等待时间,提高响应速度.
但是对死锁的避免来38西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现说,则需要更多方面的考虑.
在用户增多,数据量增大,写操作和更新操作频繁的环境下,死锁发生的概率加大了.
考虑搜索平台一种状态,如图4-14所示.
假Transaction1:T1:ShareLock(A)T3:ExclusiveLock(Articles)T5:Release(A),Release(Articles)Transaction2:T2:ShareLock(Articles)T4:ExclusiveLock(A)T6:Release(Articles)Release(A)图4-14两个事务并行执行导致的死锁示意图设Transaction1是Rss新闻排名服务程序执行的事务,它准备更新Articles的排名,首先读取用户的反馈信息,对反馈表A加共享锁,然后再更新文章的排名信息,对Articles加排他锁,执行结束分别释放两个锁.
Transaction2是一个用户在浏览器中的反馈操作,用户首先查询相关新闻文章,对Articles表加了共享锁,然后对文章进行反馈,写入到反馈表A中,执行结束分别释放两个锁.
如果两个事务分别执行,不会发生死锁,但是当两个事务并行执行,T3时刻Transaction1无法对表Articles加排他锁,因为其正被Transaction2占用,Transaction1陷入等待;而T4时刻Transaction2无法对表A加排它锁,因为其正被Transaction1占用,Transaction2也陷入等待,系统进入死锁状态.
4.
3.
2节中的拆分大表策略在一定程度上降低了死锁发生的概率,因为如果一个表越大,访问到该表的事务的可能性就越大,发生冲突导致死锁的概率也就越大.
为了最大限度的避免死锁的发生,最终选用了分布式数据库策略.
在下一节中,详细介绍分布式数据库的部署.
4.
3.
5分布式数据库的部署由于用户在Web应用中的操作可以分为两类,一类是浏览新闻文章信息,即对数据库的读操作;另一类操作是用户的反馈行为,这些反馈信息需要记录到数据库,即对数据库的写操作,写操作还包括RSS新闻排序程序的更新排名操作.
当数据库对一个资源进行读操作时,数据库管理系统只对该资源加共享锁,而共39西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现享锁之间是互容的,即读和读操作不会产生死锁.
只有当读和写操作同时进行,或写和写操作同时进行时才可能出现死锁.
为了降低搜索平台争用同一资源造成的死锁现象,一个好的解决方案就是构造一个只读数据库,让Web应用的所有读操作都在只读数据库上进行,而写操作写到可写数据库中.
在图4-1的RSS新闻搜索平台体系结构图中,服务器3上运行的数据库B就是只读数据库,Web应用需要的所有新闻文章信息来自于该只读数据库,而写操作则直接写到可写数据库A中.
首先考虑分布式数据库的结构,如图4-15所示.
反馈浏览用户反馈的写操作发布发布服务器2:数据库A(可读,可写)服务器3:数据库B1(只读)服务器3:数据库B2(只读)数据库连接控制程序服务器4:Web服务器图4-15分布式数据库的结构图RSS新闻下载程序下载的数据保存到数据库A中,数据库A的数据是实时更新的.
新的一批新闻文章数据下载后,经过概念抽取,排序计算后,就可以被用户浏览了,这时需要将这批新闻文章发布到服务器3的只读数据库中,例如发布到B1,这时B1就是最新的只读数据库,数据库连接控制程序就会引导服务器4的Web服务器从B1中读取数据;这时,新的新闻的下载,概念抽取,排序操作依然在继续,当新的一批数据处理完毕后,数据库A的新数据又需要发布到只读数据库了,因为这时B1被数据库连接控制程序所占用,而B2是空闲的,因此新的数据被发布到B2.
发布成功后,B2上的数据是最新的,这时数据库连接控制程序会引导Web服务器从B2上读取数据.
而下次的发布将发送至空闲的B1.
依此40西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现类推,每次发布操作会选择一个空闲的只读数据库进行.
发布成功后由数据库连接控制程序引导Web服务器读取有最新数据的只读数据库.
而用户的反馈行为由用户在浏览器中发出,Web服务器接收到后发给数据库连接控制程序,该程序会将这些反馈直接写入到服务器2的数据库A中.
究竟发布哪些表到只读数据库是可以选择的,最简单的方法就是仅仅选择发送解除规范化设计的表ArticlesCache,这样大部分查询操作在这个表上就可以完成.
但是当用户访问不在ArticlesCache的新闻时,如果仍在只读数据库上查找,可能返回得结果就是空.
为了解决这个问题,一个方法是改动数据库连接控制程序,当用户要求读取的数据在只读数据库中不存在时,就要引导Web服务器去数据库A中读取数据,但是这一方法违背了建立分布式数据库的初衷,因此需要采用另一个方法,即选择发布多个表到只读数据库.
通过这些发布的表可以获取所有新闻的信息.
可以发现,要获得所有新闻的信息,Articles表,Descriptions表,RssArticles表,R_RssArticles表,R_DescriptionConcepts表需要定时发布到只读数据库中.
在实现中使用了SQLServer2000的分发,发布,订阅功能.
图4-15中的数据库A做发布和分发数据库,数据库B1,B2做订阅数据库.
具体配置方法这里不再赘述.
在4.
3.
2中提到,按种子的语言对Articles表进行分表,可以把数据分到不同物理位置的数据库服务器中,此分布式系统构架如图4-16所示.
.
.
.
.
.
.
数据库B数据库B3中文种子数据数据库B4日文种子数据数据库B5德文种子数据Web服务器C3(位于中国)Web服务器C4(位于日本)Web服务器C5(位于德国)图4-16按语言的分布式系统结构图位于中国的用户访问中国的Web服务器,如果用户要求浏览的新闻来自于中41西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现文种子,则可以就近选择数据库B3进行读取;如果用户要求浏览的新闻来自于德文数据库,则需要到全局数据库B中查找,或者到数据库B5中查找.
这一类型的分布式数据库仅仅是设计,在系统中没有实现,因为现阶段搜索平台只针对英文,主要面向美国用户,数据库服务器和Web服务器也都设在美国.
4.
4新闻排名规则的设计与实现在RSS新闻搜索平台中,每个新闻文章都有一个排名值,就像每个页面在Google搜索引擎中都有其对应的PageRank值.
本节介绍RSS新闻搜索平台的排名规则和实现.
4.
4.
1客观排名因子文章来源于RSS种子,而RSS种子来源于发布种子的站点.
可以认为,一个高质量的站点发布的种子是高质量的,而一篇来自于高质量种子的新闻文章是高质量的.
在Web环境下,一个站点被链接的次数可以作为衡量一个网站质量好坏的标准.
在3.
1节中已经介绍了PageRank算法,可以认为PageRank值是对一个页面流行程度,重要程度的客观评价.
借用PageRank的思想,可以获取指向种子的来源站点的链接数作为文章的客观排名因子.
链接数的获取需要借助Google提供的API,把"link:theURLoftheRSSsite"发送给Google,会返回指向该站点的链接数.
注意,这里发送的URL一般是站点的一级域名.
如图4-17所示,指向www.
slate.
com的链接数是45,3000.
这样就获得了种子SlateMagzine(http://www.
slate.
com/rss/)的客观排名因子.
图4-17借助Google获取站点链接数的示例上述过程可以方便的使用一个源码分析程序完成,源码分析程序在元搜索引擎中是非常常见的.
其工作流程一般为:(1)将URL参数http://www.
google.
com/searchq=link%3Awww.
slate.
com发送给源码获取程序,获取相应网页的源代码,如图4-18所示.
(2)利用正则匹配或字符串查找函数,找到源代码中出现链接数目的位置,获取该链接数.
42西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现43图4-18含有查询站点链接数的Google页面源代码在计算排名值时常常需要对参与的数据进行归一化操作.
先来介绍最大值归一的一种设计:设Rank_O(Articles)代表一篇文章的客观排名值;FeedsLinkCount(Feeds)代表指向种子Feeds的链接数;FeedsFrom(Articles)代表文章的来源种子,max(FeedsLinkCount)当前数据库中保存的所有种子站点的链接数的最大值.
则:Rank_O(Articles)=FeedsLinkCount(FeedsFrom(Articles))/max(FeedsLinkCount)如果一篇文章文章来源于多个种子,说明这篇文章也很重要,设一篇文章的来源种子数为FeedsCount(Articles),这一参数可以通过R_RssArticles表中获取.
Max(FeedsCount)代表系统中,一篇文章对应种子数的最大值.
则一篇文章的客观排名值为:Rank_O(Articles)=o1*FeedsLinkCount(FeedsFrom(Articles))/max(FeedsLinkCount)+o2*FeedsCount(Articles)/Max(FeedsCount)o1,o2为可调节因子,可以根据需要调整两个因子所占的比重.
选择最大值归一的一个缺点就是必须选择相应数据的最大值,而最大值只有在所有相关数据出现后才能得到,这就可能延缓归一化的计算.
比如要得到max(FeedsLinkCount),必须在获取了每个feeds对应的链接数后才能得到.
在SQL的实现中可以选择聚集函数MAX进行实现.
另外,最大值归一化适用于分布比较均匀的场合,考虑如下两组情况:A(45300,49400,50000,47200,38400,23200)B(45300,49400,5000000,47200,38400,23200)分别采用最大值归一化的结果为:A'(0.
906,0.
988,1,0.
944,0.
768,0.
464)B'(0.
00906,0.
00988,1,0.
00944,0.
00768,0.
00464)可以看出,A组比B组更适用于最大值归一.
由于B组数据出现一个数量级明显大于其它成员数据的数据,因此导致大部分数据归一化的结果很小,不能起到很好的辨别作用,而且存储这样一个数据需要变量的精度很高.
这种情况下,可以选择使用指数归一化方法.
指数归一可以动态调整因子,使归一尽量平滑,消除归一化后数据的波动.
由于网站间的链接数的差别可能很大,不能保证不出现类似B组数据的产生.
而一篇文章的来源种子数最多不过十余个,不会出现数量级差别过大的情况.
因西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现此,在RSS搜索平台的最后实现中,o1因子选择使用了指数归一化方法(设a为动态调整因子,平台中设置为-0.
1),o2因子选择使用了最大值归一化方法.
这样,最终一篇文章的客观排名值为:Rank_O(Articles)=o1*(1-EXP(a*FeedsLinkCountFeedsFrom(Articles)))+o2*FeedsCount(Articles)/Max(FeedsCount)在实现过程中,需要对模式RssFeeds进行扩充,需要保存种子对应的来源站点域名(RssFeedsSiteLink)和当前的链接数(FeedsLinkCount),修改后的RssFeeds模式为:RssFeeds(RssFeedsId,RssFeedsLink,RssFeedsName,RssFeedsSiteLink,FeedsLinkCount)这样,对每篇文章的客观排名值,就可以通过函数实现,如图4-19所示.
图4-19文章客观排名值的SQL实现44西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现4.
4.
2主观排名因子对于新下载的文章,其排名值仅仅来源于客观排名因子,但是RSS新闻搜索平台提供了多种形式的反馈给用户使用.
如果用户对一篇文章进行了反馈,可以认为是用户对一篇文章感兴趣,是用户主观的承认一篇文章的重要程度.
基于反馈的排名算法在3.
3节中已经详细讨论,这里针对搜索平台的具体情况进行新闻文章的主观排名因子设计.
首先考虑RSS搜索平台提供给用户的几种反馈形式,图4-20是Web应用中对一篇文章提供的用户界面.
如果一个用户对某篇新闻文章添加了Tag(图中Tagit按钮),或添加了评注(图中addcomments链接),或把该文章通过Email发送给了其它用户(图中emailthis链接),则说明他对这篇感兴趣,或者说他认为这篇文章重要,因此,可以认为一个文章被用户此类反馈越多,这篇文章越重要,因此应该可以提升文章的排名.
同时,如果用户点击了新闻的标题阅读了该新闻,也可以认为是此类反馈.
另一种形式的反馈是投票,如图votes所示,上箭头表示投赞成票,即用户认为该文章重要,应该提升文章的排名;下箭头表示投反对票,即用户认为该文章不重要,应该降低文章的排名.
图4-20Web应用中的用户界面截屏图设Rank_S(Articles)代表文章的主观排名值,ReadNums(Articles)代表读该文章的用户数,TagNums(Articles)代表标记该文章的用户数,CommentNums(Articles)表示评注该文章的用户数,EmailNums(Articles)表示发送Email该文章的用户数,VoteNums(Articles)表示对该文章投赞成票的用户数,OpposeNums(Articles)表示对该文章投反对票的用户数,则:Rank_S(Articles)=s1*(1–EXP(b*ReadNums(Articles)))+s2*(1–EXP(c*TagNums(Articles)))+s3*(1–EXP(d*CommentNums(Articles)))+s4*(1–EXP(e*EmailNums(Articles)))+s5*(1–EXP(f*VoteNums(Articles)))-s6*(1–EXP(g*OpposeNums(Articles)))45西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现46为了记录这些反馈信息,需要在数据库中把这些信息保存在表中,这里需要设计几个表来保存这些信息,这些表的模式为:ReadArticles(ArticlesId,UserId)TagArticles(ArticlesId,UserId,TagContent)CommentArticles(ArticlesId,UserId,Comments)EmailArticles(ArticlesId,UserId)VoteArticles(ArticlesId,UserId,VoteOrOppose)这些表都在服务器2的数据库A中,不用发布到分布式数据库的只读数据库中.
用户的反馈信息通过Web服务器和数据库链接管理程序直接写入服务器2的数据库A.
文章的主观排名因子的SQL实现依然使用函数,类似于上一节中的客观排名因子的SQL实现.
4.
4.
3综合排名的设计与实现一篇文章的综合排名值由主观排名因子和客观排名因子相加得到,设Rank(Articles)代表一篇文章的综合排名值,则:Rank(Articles)=o*Rank_O(Articles)+s*Rank_S(Articles)文章的综合排名值包含了两部分,针对不同的用户和不同的时间,可以通过调整可调节系数o和s来改变权重.
例如,当一篇文章刚刚下载时,第一次计算的排名值只有客观部分,但随着时间的增长,对该文章的反馈越来越多,主观排名值越来越多,因此可以适当的调大主观调节因子s,这里s可以被设置为一个计算次数的函数,随着计算次数的增加,自动增大主观系数.
通过计算综合排名,每篇新闻文章都有了一个最终的排名值.
为了保存每篇文章的排名值,需要修改Articles的模式,添加保存排名值的字段Rank,修改后的模式为:Articles(AritlcesId,Link,PubDate,DescriptionId,Rank)综合排名的计算通常是一个耗时的过程,在实现中使用存储过程调用函数的方式来进行排名值的计算与更新,如图4-21所示.
在实际运行中发现,如果每次直接使用Update进行更新排名值,会导致Articles表的长时间锁定,而计算的结果却发现若干天前的文章排名基本是不会变化的,因此耗时的排名计算被浪费了.
因此,计算排名的存储过程只更新最近若干天的文章的排名.
在实现中,只更新最近两天的新闻排名,两天之前的新闻排名值保持最后的排名值不再变化.
西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现图4-21文章综合排名值的SQL实现这种方法虽然实现简单,但是由于计算排名时用到指数计算等耗时的操作,造成对一个资源的长时间锁定,这种锁定会增大系统的负担,增大锁等待的时间,甚至引起死锁.
在实现中,采用两种方法来避免长时间的锁定.
一种方法是采用局部计算的方法,即每次只计算一部分文章的排名值,然后再计算另一部分文章的排名值,这样不会造成对一个资源的长时间锁定,避免锁超时的发生,如图4-22所示.
另一种方法是把由排名计算外部程序计算排名值,而该程序计算排名的这部分时间不对资源加锁,直到全部计算完毕后,再更新排名值,这样大大减少锁的持续时间,如图4-23所示.
对Articles加排它锁,计算1000篇文章的排名值,释放锁.
其他应用可以对Articles加锁对Articles加排它锁,再计算1000篇文章的排名值,释放锁.
其他应用可以对Articles加锁.
.
.
全部计算结束.
数据库内:T1:对Articles加共享锁,获取需要计算排名的所有文章号.
T3:然后释放锁.
T5:对Articles加排他锁,更新已计算好的排名值.
释放锁.
排名计算外部程序(例如C#程序):T2:获取需要计算的文章号.
T4:计算排名值.
图4-22局部计算法示意图图4-23外部程序调用示意图用户的查询往往会返回很多符合条件的结果,在这个结果集中就可以按照排名值的大小按顺序返回给用户.
当排名值相同时,按发布时间的先后返回给用户.
当然,用户也可以选择直接按照发布时间查看新闻,因为人们总是对新的文章敢兴趣.
在实际系统的实现中,一篇文章的排名值还受到个人用户兴趣的影响,当前新闻热点趋势的影响.
而这些信息都需要用到由文章描述信息抽取出的概念.
利47西北工业大学硕士学位论文第四章RSS新闻搜索平台的设计与实现48用概念可以实现文本聚类,热点发现和新闻实时推荐等功能.
由于涉及过多技术细节,这里略去.
排名是信息检索的一个重要问题,而且对排名的评价总是涉及到人的主观因素,因此没有一个公认的排名算法能适应在各种环境.
现在的一个趋势是对一组特定的用户,采用特定的排名算法,或对一个通用的算法设定不同的调节系数.
4.
5小结本章详细介绍了RSS新闻搜索平台的设计实现过程.
首先描述了系统的整体构架.
并且详细介绍了数据库的模式设计,数据库性能优化方法,分布式数据库的部署策略等.
最后对新闻排序规则作了总结,分别从主观排名因子和客观排名因子两方面进行了分析,并设计了综合排名算法.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现49第五章嵌入浏览器的搜索集成工具的设计与实现随着IE,Firefox等优秀浏览器的发展,用户上网浏览网页,通过搜索引擎查询都会使用到浏览器.
随着网络应用B/S模式的流行,浏览器更是在网络应用中占据了重要的地位.
因此,通过浏览器为用户提供良好的用户界面是十分必要的.
当前主流的搜索引擎网站,门户网站都开发了自己的浏览器插件,比如GoogleToolbar,YahooToolbar,新浪点点通工具条等.
当前的主流浏览器都提供对工具条,浏览器栏的接口支持.
针对IE5.
0以上版本,设计开发了提供元搜索功能的集成搜索工具条,同时提供IE浏览动作监听和用户对可搜索深标签的添加.
5.
1浏览器插件开发原理IE5.
0以上版本提供了面板对象来支持浏览器插件.
实现IE面板对象组件的是一个ATL(ActiveTemplateLibrary)控件,它是一个轻量级的COM(ComponentObjectModel)组件.
面板对象分为三种类型,浏览器栏面板、工具栏面板和桌面工具栏面板.
而浏览器栏面板又有两种表现形式:垂直和水平的.
在实现中,选择工具栏面板实现工具条.
实现工具条面板组件需要实现基本的COM接口IUnknown和IClassFactory外,还需要实现IDeskBand、IObjectWithSite、IPersistStream三个接口.
由于嵌入浏览器的搜索引擎的集成工具栏需要和用户交互,接受用户的输入搜索查询串,所以还要实现IInputObject接口.
接口都有一个由IDL语言定义的GUID.
通过使用MSVC6.
0的ATLCOM工程向导,设计实现一个上述接口的工具条面板组件后,把该组件的GUID注册到注册表和IE浏览器中之后就可以在浏览器中使用了.
为了实现对浏览器的控制,需要注册一个浏览器帮助对象BHO(BrowserHelperObject)到注册表.
BHO通常是一个DLL,在IE每次启动时和IE一起加载启动.
在BHO中可以实现IObjectWithSite接口,获取当前浏览器对象接口(IWebBrowser2)的指针,就可以控制浏览器的行为了.
在我们设计的DIGGOLSearchToolBar中,主要提供了如下功能:(1)添加嵌入网页的可搜索深标签的功能.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现50该功能支持用户在任意网页上添加深标签.
深标签的特点在于,用户可以对网页的特定段落,特定位置,特定资源添加多个标签,进行注释.
它不同于针对网页的标签,对一个网页只能加一个标签.
这种深标签依然可以返回给服务器,作为网页的Folksonomy概念.
(2)搜索引擎集成功能,提供元搜索的搜索入口.
该功能是一个简单的元搜索引擎.
它支持用户在搜索栏内写入搜索关键字后,选择点击不同的按钮进行不同搜索引擎进行搜索.
实际上,该功能只实现了元搜索引擎的请求提交代理和检索接口代理的主要功能,但并没有提供结果融合的策略,即没有实现结果显示代理.
(3)用户搜索历史的记录.
该功能记录用户所有的浏览器访问Web行为,将访问URL信息记录到数据库中,便于进行对用户反馈的分析及用户兴趣的发现.
(4)高亮网页关键字功能.
该功能使用户可以选择网页上的任意关键字进行高亮显示,作为方便用户浏览网页的一种辅助功能.
5.
2添加深标签方法的设计这里提供按网页内容添加(Tag)和按位置添加标签两种方式,其基本流程为:(1)通过浏览器插件获取用户在网页中选取的内容或位置.
(2)通过浏览器插件在该内容或位置处插入标签图标和承载标签编辑框的窗体,以及用于操作的脚本.
(3)插入的脚本在承载标签的窗体上生成用于接受用户输入的编辑框等控件,用于接受用户输入.
(4)用户输入自定义信息后,点击关闭按钮,脚本发出连接,浏览器插件监听该连接,并获取编辑框内容,保存该内容,按用户选择把相关信息保存在本地或上传到服务器.
(5)用户再次登陆添加过标签的网页时,根据保存的相关信息在原先添加的位置自动添加标签.
用户可以利用鼠标右击菜单中的选项,删除该标签.
(6)用户可以通过本地页面查找保存在本机数据库中的标签的相关信息.
也可以通过在相应的服务器上查找用户自己的标签的相关信息,或查找其他用户共享的标签的相关信息.
(7)如果加过标签的网页是一个搜索引擎的搜索结果页,则自动把相应的搜索西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现51所用的搜索关键字和搜索引擎的搜索结果的一或多页保存在用户本机上或一个服务器上,并提供一个让用户查找本用户或其他共向用户的标签的相关信息或相应的搜索结果页的功能和用户界面.
如果加标签的网页是框架模式(Frameset)则通过浏览器插件逐层获取框架模式的对应的标码语言文档,对每个Frameset元素分别判断、操作,进行添加元素的操作,标签操作.
该过程需要浏览器插件技术和脚本技术相结合完成.
浏览器插件主要完成监听超链接,获取添加标签的位置,添加标签载体,保存标签内容等功能.
而脚本主要用于控制生成的标签,获取用户的输入标签内容,并将标签内容发送给浏览器插件以便存储.
5.
3搜索引擎集成功能的实现在5.
1节中已经提到工具条面板插件要实现接口IObjectWithSite.
该接口是IE用来对插件进行管理和通讯用的一个接口.
必须要实现这个接口的两个函数:SetSite()和GetSite().
在SetSite()函数中,获得指向当前浏览器对象接口(IWebBrowser2)的指针,有了这个指针就可以通过它来对IE进行监听和控制.
IWebBrowser2接口的函数Navigate2()可以控制浏览器浏览的页面.
这样,只要构造出每个成员搜索引擎的搜索URL规则,就可以简单的构造一个元搜索的请求提交代理.
在实现中按照客户针对美国用户的喜好,选择了最常用的三个搜索引擎作为成员搜索引擎,分别是Google,Yahoo,MSN.
检索接口代理完成的一个基本工作就是将用户的检索请求按不同的格式发送到各个独立搜索引擎,因此需要分析每个搜索引擎的搜索请求提交URL的具体形式.
假设用户的搜索关键字为"searchkeyword@",则这三个搜索引擎的搜索URL分别为:Google:http://www.
google.
com/search&q=search+keyword+%40Yahoo:http://search.
yahoo.
com/searchp=search+keyword+%40MSN:http://search.
msn.
com/results.
aspxq=search+keyword+%40可以看出,每个搜索引擎的URL构成的形式基本相同,都是基本搜索URL+搜索关键字.
由于URL中的一些特殊字符有固定的含义,因此需要将搜索关键字中的特殊字符进行转换.
比如示例搜索关键字"searchkeyword@"中的@在URL中都转换为了%40.
特殊字符的转换规则是:%+该字符的ASCII码值,而搜索串中的空格一般转化为字符'+'.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现52这样可以设计一个结构体和一个函数,结构体用于保存成员搜索引擎的基本信息,而函数用于将用户输入的搜索查询串转换为适合搜索引擎查询规范的字符串形式.
structsearchengine{Char*SEName;//搜索引擎的名字Char*SEURL;//搜索引擎的URL}Char*TransferCode(char*);//把查询串转化为适合搜索引擎查询的查询串结构体searchengine的初始内容为:{{"Google","http://www.
google.
com/search&q="},{"Yahoo","http://search.
yahoo.
com/searchp="},{"MSN","http://search.
msn.
com/results.
aspxq="}}使用结构体的原因是可以方便的增加、删除成员搜索引擎.
根据上述分析结果,只要在工具条中获取用户输入的搜索查询串,经过函数TransferCode的转换,和对应搜索引擎的*SEURL拼接成相应的搜索引擎查询URL,通过Navigate2()直接控制浏览器访问该URL,就能在浏览器中得到相应搜索引擎的搜索结果页面.
这样,就完成了各个搜索引擎的参数转换,实现了元搜索的检索接口代理.
5.
4用户搜索历史记录对用户搜索历史的记录主要利用浏览器插件对IE动作的监听功能,同样用到浏览器对象接口IWebBrowser2.
每个COM工程都必须实现IDispatch接口,通过IDispatch的Invoke()方法就能监听IE的动作了.
不过为了识别每个动作的类型,需要在工程中加入头文件ExDispID.
h,它定义了所有DWebBrowserEvents2的事件.
这些事件包括:浏览器正在浏览一个页面(DISPID_BEFORENAVIGATE2),浏览器打开了一个新的窗口(DISPID_NEWWINDOW2),浏览器正在浏览的页面已经全部显示完毕(DISPID_DOCUMENTCOMPLETE).
在每个动作完成的时刻,可以通过浏览器插件把这一动作记录下来,主要是获取用户通过浏览器访问的URL信息.
通过记录用户访问的URL信息,可以进行用户的兴趣发现.
5.
5高亮关键字的实现高亮关键字的实现是通过动态改变浏览器中显示的内容实现的.
浏览器工作西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现53的原理是将每个HTML标签转化成一个元素显示在浏览器中.
动态改变浏览器显示的内容就是在不改变页面本身HTML源码的情况下,直接修改浏览器显示的元素.
这一过程首先通过浏览器对象接口IWebBrowser2获得MarkupServices接口.
这个接口可以改变HTMLDocument的内容.
高亮关键字的流程如下:(1)通过当前网页的Document,获得相应的IMarkupService接口指针.
IMarkupServices*pMS;hr=m_pHtmlDoc2->QueryInterface(IID_IMarkupServices,(void**)&pMS);(2)通过IMarkupService指针获得IMarkupPointer指针.
IMarkupPointer*pPtr1;hr=pMS->CreateMarkupPointer(&pPtr1);(3)给定要查找的文字,通过IMarkupPointer在网页中找到对应文字出现的位置.
hr=pPtr1->FindText(poSearchStr,0,pPtr2,NULL);(4)创建一个字体的Element,由于高亮关键字.
unsignedshort*mSetFind=L"ID=IEfindSTYLE=\"background-color:#ffff33\"";IHTMLElement*pFontEl;hr=pMS->CreateElement(TAGID_FONT,mSetFind,&pFontEl);(5)把新生成的FONTElement插入到要高亮的关键字两边hr=pMS->InsertElement(pFontEl,pPtr1,pPtr2);(6)创建用于定位网页的Script脚本Element.
unsignedshort*mSetFind=src=\"find.
js\"";hr=pMS->CreateElement(TAGID_SCRIPT,mSetScript,&pScript);在本地的find.
js文件中,可以通过插入的FontElement的ID(IEfind),获得该对象的位置,进而通过脚本实现网页滚动到当前关键字位置.
(7)把新生成的ScriptElement插入到前一步生成的FontElement后.
定位pPtr1到FontElement后.
pPtr1->MoveAdjacentToElement(pFontEl,ELEMENT_ADJACENCY_AfterEnd);hr=pMS->InsertElement(pScript,pPtr1,pPtr1);通过IMarkupService接口,可以动态改变Element,这样就可以在页面上添加新的Element,修改,删除已有的Element.
通过添加脚本Element,几乎可以使网页进行各种操作.
图5-1是高亮关键字的实际效果图.
西北工业大学硕士学位论文第五章嵌入浏览器的搜索集成工具的设计与实现图5-1高亮关键字的效果图5.
6小结本节介绍了嵌入浏览器的搜索集成工具的设计和实现过程.
嵌入浏览器的搜索集成工具已经被各大搜索网站所采用,但是其主要功能无非是高亮搜索关键字和元搜索请求提交.
我们设计开发的搜索集成工具在此基础上还提供了添加深标签的方法,提供了一种新的浏览器插件的功能.
完成这一功能使用了浏览器插件和脚本结合的方法,这一方法已经申请专利.
54西北工业大学硕士学位论文第六章结束语55第六章结束语6.
1工作总结课题项目来源于中美合作"下一代智能搜索平台"项目.
由于项目采用极限编程模式,用户需求变化快,采用的工作模式特殊,需要多人合作开发和积极沟通.
笔者主要完成了浏览器插件的开发,RSS新闻搜索平台的数据库设计,并负责与客户沟通,用户需求说明确认和需求分析工作.
主要完成的工作如下:(1)完成了浏览器插件的设计与开发,开发了DIGGOL智能搜索助手的工具条和浏览器栏插件.
提供浏览器动作监听,客户端-服务器构架的支持,以及添加可搜索深标签的方法.
(2)完成RSS新闻搜索平台的数据库设计.
完成新闻排名模块的开发.
完成按照不同要求进行的搜索模块的开发.
完成用户反馈模块的开发.
完成基于概念的新闻热点发现,新闻热点关联的开发.
(3)完成基于组(Group)功能的RSS新闻搜索平台的数据库设计及相关应用开发.
(4)为了提高网站相应速度,采用多种策略进行了数据库性能优化,并完成分布式数据库的部署.
(5)及时和客户沟通,理解用户需求,完成需求分析.
针对客户在开发过程中提出的需求变更,快速开发出原型提供给用户进行确认.
6.
2后续工作展望传统的基于关键字的搜索引擎已经有了基本的框架,而第三代智能搜索还处于起步状态.
智能搜索在传统的信息检索基础上融合了数据挖掘,人工智能等许多学科.
需要研究的内容主要有如下几个方面:(1)广泛收集用户反馈信息,针对不同用户提供更加准确的查询结果.
提高查询的针对性.
(2)提供给具有相同兴趣爱好的一组人的信息搜索和共享平台.
新闻主题社区的自动发现.
(3)随着语义网络的发展,在语义网络下的搜索服务是面临的一项新的挑战.
西北工业大学硕士学位论文参考文献56参考文献[1]RicardoBaeza-Yates,BerthierRibeiro著.
现代信息检索ModernInformationRetrieval(王知津等译).
北京:机械工业出版社,2005.
[2]G.
Salton.
TheSMARTRetrievalSystem–ExperimentsinAutomaticDocumentProcessing.
PrentiveHallInc.
,EnglewoodCliffs,NJ,1971.
[3]S.
E.
RobertsonandK.
SparkJones.
Relevanceweightingofsearchterms.
JournaloftheAmericanSocirtyforInformationScience,27(30):129-146,1976.
[4]李晓明,闫宏飞,王继民.
搜索引擎――原理、技术与系统.
北京:科学出版社,2005.
[5]徐宝文,张卫丰.
搜索引擎与信息获取技术.
北京:清华大学出版社,2003.
[6]韩家炜,孟小峰,王静等.
Web挖掘研究.
计算机研究与发展.
2001年4月第38卷第4期.
[7]JimGray.
Therevolutionindatabasearchitecture.
In:WeikumG,KnigAC,DelochS,eds.
Proc.
oftheACMSIGMODInt'lConf.
onManagementofData.
ACMPress,2004,1~4.
[8]SergeyBrin,LawrencePage.
TheAnatomyofaLarge-ScaleHypertextualWebSearchEngine.
Proceedingsofthe7thInternationalWorldWideWebConference,1998.
[9]JonM.
Kleinberg.
AuthoritativeSourcesinaHyperlinkedEnvironment.
JournaloftheACM.
1999.
[10]LawrencePage,SergeyBrin.
ThePageRankCitationRanking-BringingOrdertotheWeb.
http://dbpubs.
stanford.
edu:8090/cgi-bin/makehtml.
cgidocument=1999/66[11]UdoKruschwitz.
WorldKnowledgeforthedomainofyourchoice.
IEEEInternationalConferenceonSystems,Man,andCybernetics.
2001.
[12]ThePorterStemmingAlgorithmhttp://www.
tartarus.
org/~martin/PorterStemmer/[13]张强弓,喻国宝,廖湖声等.
一种元搜索引擎的查询结果处理模型.
华南理工大学学报(自然科学版),2004年11月32卷增刊:47-51.
[14]T.
Pedersen,S.
Patwardhan,andJ.
Michelizzi.
Wordnet::similarity-measuringtherelatednessofconcepts[C].
In:ProceedingsoftheNineteenthNationalConferenceonArtificialIntelligence(AAAI-04),2004.
[15]A.
Silberschatz,H.
F.
Korth,S.
Sudarshan著;数据库系统概念DatabaseSystemConcepts(杨冬青,唐世渭译);北京:机械工业出版社,2004.
[16]施伯乐,丁宝康,汪卫.
数据库系统教程.
北京:高等教育出版社,2003.
[17]胡百敬.
MicrosoftSQLServer性能调教.
北京:电子工业出版社,2005.
[18]韩近强,陈华.
嵌入IE的搜索引擎集成工具的设计与实现.
全国搜索引擎和网上信息挖掘学西北工业大学硕士学位论文参考文献57术研讨会2003SEWM,北京大学,2003.
[19]董志勇.
Web信息检索中基于超链接的网页评估算法研究.
硕士学位论文.
河海大学.
2004.
[20]AdamMaths.
Folksonomies-CooperativeClassificationandCommunicationThroughSharedMetadata.
ComputerMediatedCommunication,2004.
[21]徐科,黄国景,崔志明.
元搜索引擎中基于用户兴趣的个性化调度模型.
清华大学学报(自然科学版),2005年第45卷第S1期:1915-1919.
西北工业大学硕士学位论文发表论文和参加科研情况说明58发表论文和参加科研情况说明[1]杨彬,康慕宁.
基于概念的权重PageRank改进算法.
情报杂志.
2006年第11期,已出版.
[2]杨彬,康慕宁.
基于用户反馈的搜索引擎选择及结果归并方法.
计算机工程.
2008年第4期,已录用.
[3]郭晨娟,杨彬,梁平.
网页加入可搜索的深标签及浏览器插件与脚本结合的方法.
申请专利号200610041811.
1,已公开.
西北工业大学硕士学位论文致谢59致谢首先感谢我的导师康慕宁教授,他在两年多的时间里一直悉心教导我,在学业上、生活上以及思想上都给予我巨大的帮助.
在整个研究生学习期间给予我了耐心指导,严格要求和热情鼓励.
他实事求是的精神,积极乐观的态度,将使我受益终生.
在此我要向康慕宁老师无私的教诲表示衷心的感谢.
感谢李战怀教授在工作和学习中给我的巨大的帮助.
他严谨的治学态度,渊博的知识使我受益匪浅.
感谢他为我提供了良好的工作环境,使我有幸能参加与美国DIGGOL公司的合作项目.
特别感谢他对我学术研究上的指导和帮助.
感谢项目组组长张文波,作为项目负责人,他积极忘我的工作态度让人钦佩.
特别感谢他对我的信任和对我日常生活上的关心与照顾.
感谢美国DIGGOL公司的梁平教授,西安迪戈科技公司的李联宁经理.
他们为我们带来了许多先进的思想和工作模式.
感谢张延园教授,蒋立源教授和李建良老师.
感谢同课题组的郭晨娟硕士、韩宇彬硕士、雷万宝硕士、彭丽硕士,刘璐硕士.
在整个项目的研发过程中,他们表现出了深厚的专业基础,良好的团队精神以及乐于助人的品格,不仅保证了项目的顺利进展,更让工作充满了乐趣,在此表示由衷的敬佩与谢意.
最后,特别感谢我的父亲杨勤耕,母亲刘璟及所有亲人,他们在我的成长过程中给予我无私的爱和全力的支持.
对所有关心,帮助我的人表示感谢!
西北工业大学学位论文知识产权声明书本人完全了解学校有关保护知识产权的规定,即:研究生在校攻读学位期间论文工作的知识产权单位属于西北工业大学.
学校有权保留并向国家有关部门或机构送交论文的复印件和电子版.
本人允许论文被查阅和借阅.
学校可以将本学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文.
同时本人保证,毕业后结合学位论文研究课题再撰写的文章一律注明作者单位为西北工业大学.
保密论文待解密后适用本声明.
学位论文作者签名:指导教师签名:年月日年月日西北工业大学学位论文原创性声明秉承学校严谨的学风和优良的科学道德,本人郑重声明:所呈交的学位论文,是本人在导师的指导下进行研究工作所取得的成果.
尽我所知,除文中已经注明引用的内容和致谢的地方外,本论文不包含任何其他个人或集体已经公开发表或撰写过的研究成果,不包含本人或他人已申请学位或其它用途使用过的成果.
对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明.
本人学位论文与资料若有不实,愿意承担一切相关的法律责任.
学位论文作者签名:年月日
Hosteons - 限时洛杉矶/达拉斯/纽约 免费升级至10G带宽 低至年$21
Hosteons，一家海外主机商成立于2018年，在之前还没有介绍和接触这个主机商，今天是有在LEB上看到有官方发送的活动主要是针对LEB的用户提供的洛杉矶、达拉斯和纽约三个机房的方案，最低年付21美元，其特点主要在于可以从1G带宽升级至10G，而且是免费的，是不是很吸引人？本来这次活动是仅仅在LEB留言提交账单ID才可以，这个感觉有点麻烦。不过看到老龚同学有拿到识别优惠码，于是就一并来分享给有需...
Raksmart VPS主机如何设置取消自动续费
今天有看到Raksmart账户中有一台VPS主机即将到期，这台机器之前是用来测试评测使用的。这里有不打算续费，这不面对万一导致被自动续费忘记，所以我还是取消自动续费设置。如果我们也有类似的问题，这里就演示截图设置Raksmart取消自动续费。这里我们可以看到上图，在对应VPS主机的【其余操作】中可以看到默认已经是不自动续费，所以我们也不要担心被自动续费的。当然，如果有被自动续费，我们确实不想续费的...
NameCheap黑色星期五和网络礼拜一
如果我们较早关注NameCheap商家的朋友应该记得前几年商家黑色星期五和网络星期一的时候大促采用的闪购活动，每一个小时轮番变化一次促销活动而且限量的。那时候会导致拥挤官网打不开迟缓的问题。从去年开始，包括今年，NameCheap商家比较直接的告诉你黑色星期五和网络星期一为期6天的活动。没有给你限量的活动，只有限时六天，这个是到11月29日。如果我们有需要新注册、转入域名的可以参加，优惠力度还是比...
googlepr值为你推荐
-
Literaturverzeichnis重庆网络公司一九互联重庆本地的网约车平台有哪些？如何识别比较正规的网约车平台？dell服务器bios设置dell R410服务器 bios设置参数如何恢复出厂设置？特朗普吐槽iPhone华为余承东吐槽iPhone X，除了贵啥优点都没有什么是支付宝支付宝是什么概念？加多宝与王老吉加多宝王老吉有什么区别吗？青岛网通测速中国联通宽带，青岛地区咋样，与网通有啥区别佛山海虹怎么分辨青口/海虹是活还是死？如何发帖子手机百度贴吧怎么发帖子？骑士人才系统问一下嘉缘人才系统和骑士人才系统相比，哪个系统会好点呢？