搜索引擎语义排序的设计与实现论文.docx
《搜索引擎语义排序的设计与实现论文.docx》由会员分享，可在线阅读，更多相关《搜索引擎语义排序的设计与实现论文.docx（40页珍藏版）》请在冰点文库上搜索。
搜索引擎语义排序的设计与实现论文
1引言
随着互联网的不断发展和日益普及，信息技术的不断发展,网上的信息量在爆炸性增长，网络已经深入到了人们生活的各个方面，影响并改变了人们生活方式和思维方式。
中国互联网络信息中心（CNNIC）在京发布第33次《中国互联网络发展状况统计报告》。
《报告》显示，截至2013年12月，中国网民规模达6.18亿，互联网普及率为45.8%，网站数达320万，域名数目已达1844万，全球Web页面的数目已经超过200亿，中国的网页数估计也超过了40亿。
在如此浩瀚的海洋里寻找信息，就像“大海捞针”一样，急切需要一种工具使我们可以迅速找到我们想要的内容，这就是搜索引擎发展的巨大市场和动力。
著名的因特网搜索引擎包括Baidu、Google、Sohu等。
搜索引擎指自动从因特网搜集信息，经过一定整理以后，提供给用户进行查询的系统。
因特网上的信息浩瀚万千，而且毫无秩序，所有的信息像汪洋上的一个个小岛，网页链接是这些小岛之间纵横交错的桥梁，而搜索引擎，则为用户绘制一幅一目了然的信息地图，供用户随时查阅。
它包括信息搜集、信息整理和用户查询三部分。
“飞梦”搜索引擎系统通过Hertix实现了自动将Web上的海量网页抓取到本地。
然后解析网页，提取其中的有用内容，为网页建立本体词库，对解析网页生成的信息文件进行分词，并建立索引，将索引存入数据库中。
通过语义排序实现将索引按照一定的排序规则排序，并将排好序的的结果存于缓存，以供用户查询。
“飞梦”搜索引擎系统为用户提供了简洁的查询页面，用户通过此界面完成与系统的交互。
当用户在查询界面上输入要检索的信息后，系统将在可以接受的时间内，返回用户所需的结果集。
本系统实现了搜索引擎的基本功能，能够使用户可以简单，快捷，精确的对感兴趣的东西进行检索。
2课题背景
2.1搜索引擎的概念
由于网络信息的飞速增长，我们不得不面对浩瀚的网络资源，这极大地改变了人们获取信息的方式,面对浩如烟海的网络信息,如何才能迅速、方便地获取有效信息,日益成为人们关心的问题,搜索引擎的出现极大地缓解了这一矛盾。
它为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。
因此它也成为除了电子邮件以外最多人使用的网上服务。
搜索引擎是一种应用在Web上的，为用户提供检索服务的软件系统,它以一定的策略在Web上搜集和发现信息,并对信息进行分析、提取、组织等处理后形成供检索用的数据库。
从使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词语或者短语，搜索引擎会在数据库中进行搜寻，如果找到与用户要求内容相符的网站，便采用特殊的算法——通常根据网页中关键词的匹配程度，出现的位置/频次，链接质量等——计算出各网页的相关度及排名等级，然后根据关联度高低，按顺序将这些网页链接返回给用户。
这个与用户输入内容相关的信息列表（常常会是很长一个列表，例如包含1万个条目）。
这个列表中的每一条目代表一篇网页，至少有3个元素：
（1）标题：
以某种方式得到的网页内容的标题。
最简单的方式就是从网页的
标签中提取的内容。
（尽管在一些情况下并不真正反映网页的内容）。
（2）URL：
该网页对应的“访问地址”。
有经验的Web用户常常可以通过这个元素对网页内容的权威性进行判断，例如上面的内容通常就比（某个假想的个人网站）上的要更权威些（不排除后者上的内容更有趣些）。
（3）摘要：
以某种方式得到的网页内容的摘要。
最简单的一种方式就是将网页内容的头若干字节（例如512）截取下来作为摘要。
通过浏览这些元素，用户对相应的网页是否真正包含他所需的信息进行判断。
比较肯定的话则可以点击上述URL，从而得到该网页的全文。
搜索引擎提供信息查询服务的时候，它面对的只是查询词。
而有不同背景的人可能提交相同的查询词，关心的是和这个查询词相关的不同方面的信息，但搜索引擎通常是不知道用户背景的，因此搜索引擎既要争取不漏掉任何相关的信息，还要争取将那些“最可能被关心”的信息排在列表的前面。
这也就是对搜索引擎的根本要求。
除此以外，考虑到搜索引擎的应用环境是Web，因此对大量并发用户查询的响应性能也是一个不能忽略的重要性能指标。
2.2搜索引擎的发展历史
2.2.1搜索引擎的起源
所有搜索引擎的祖先，是1990年由Montreal的McGillUniversity三名学生（AlanEmtage、PeterDeutsch、BillWheelan）发明的Archie（ArchieFAQ）。
AlanEmtage等想到了开发一个可以用文件名查找文件的系统，于是便有了Archie。
Archie是第一个自动索引互联网上匿名FTP网站文件的程序，但它还不是真正的搜索引擎。
Archie是一个可搜索的FTP文件名列表，用户必须输入精确的文件名搜索，然后Archie会告诉用户哪一个FTP地址可以下载该文件。
世界上第一个Spider程序，是MITMatthewGray的WorldwideWebWanderer，用于追踪互联网发展规模。
刚开始它只用来统计互联网上的服务器数量，后来则发展为也能够捕获网址（URL）
2.2.2第一代搜索引擎
第一代搜索引擎出现于1994年。
这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。
而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。
在实现技术上也基本沿用较为成熟的IR（InformationRetrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。
1994年4月，斯坦福大学的两名博士生，美籍华人杨致远和DavidFilo共同创办了Yahoo！
。
随着访问量和收录链接数的增长，Yahoo目录开始支持简单的数据库搜索。
因为Yahoo!
的数据是手工输入的，所以不能真正被归为搜索引擎，事实上只是一个可搜索的目录。
Yahoo!
中收录的网站，因为都附有简介信息，所以搜索效率明显提高。
2.2.3第二代搜索引擎
大约在1996年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50，000，000网页的索引数据库，每天能够响应10，000，000次用户检索请求。
1997年11月，当时最先进的几个搜索引擎号称能建立从2，000，000到100，000，000的网页索引。
Altavista搜索引擎声称他们每天大概要承受20，000，000次查询。
2000年搜索引擎2000年大会上，按照Google公司总裁LarryPage的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。
每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。
在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。
著名的因特网搜索引擎包括FirstSearch、Google、HotBot等。
1997年8月，Northernlight搜索引擎正式现身。
它曾是拥有最大数据库的搜索引擎之一，它没有StopWords，它有出色的CurrentNews、7100多出版物组成的SpecialCollection、良好的高级搜索语法，第一个支持对搜索结果进行简单的自动分类。
2.2.4当前著名的搜索引擎简介
1998年10月之前，Google只是斯坦福大学（StanfordUniversity）的一个小项目BackRub。
1995年博士生LarryPage开始学习搜索引擎设计，于1997年9月15日注册了的域名，1997年底，在SergeyBrin和ScottHassan、AlanSteremberg的共同参与下，BachRub开始提供Demo。
1999年2月，Google完成了从Alpha版到Beta版的蜕变。
Google公司则把1998年9月27日认作自己的生日。
Google以网页级别（Pagerank）为基础，判断网页的重要性，使得搜索结果的相关性大大增强。
Google公司的奇客（Geek）文化氛围、不作恶（Don’tbeevil）的理念，为Google赢得了极高的口碑和品牌美誉。
2006年4月，Google宣布其中文名称“谷歌”，这是Google第一个在非英语国家起的名字。
1996年8月，sohu公司成立，制作中文网站分类目录，曾有“出门找地图，上网找搜狐”的美誉。
随着互联网网站的急剧增加，这种人工编辑的分类目录已经不适应。
sohu于2004年8月独立域名的搜索网站“搜狗”，自称“第三代搜索引擎”。
2000年1月，两位北大校友，超链分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士后）在北京中关村创立了XX（Baidu）公司。
2001年8月发布B搜索引擎Beta版（此前Baidu只为其它门户网站搜狐新浪Tom等提供搜索引擎），2001年10月22日正式发布Baidu搜索引擎，专注于中文搜索。
Baidu搜索引擎的其它特色包括：
XX快照、网页预览/预览全部网页、相关搜索词、错别字纠正提示、mp3搜索、Flash搜索。
2002年3月闪电计划（BlitzenProject）开始后，技术升级明显加快。
后推出贴吧、知道、地图、国学、百科、文档、视频、博客等一系列产品，深受网民欢迎。
2005年8月5日在纳斯达克上市，发行价为USD27.00，代号为BIDU。
开盘价USD66.00，以USD122.54收盘，涨幅353.85%，创下了5年以来美国股市上市新股当日涨幅最高纪录。
2003年12月23日，原慧聪搜索正式独立运做，成立了中国搜索。
2004年2月，中国搜索发布桌面搜索引擎网络猪1.0，2006年3月中搜将网络猪更名为IG（InternetGateway）。
2.3搜索引擎的分类
2.3.1全文索引
全文搜索引擎是名副其实的搜索引擎，国外代表有Google，国内则有著名的XX搜索。
它们从互联网提取各个网站的信息（以网页文字为主），建立起数据库，并能检索与用户查询条件相匹配的记录，按一定的排列顺序返回结果。
根据搜索结果来源的不同，全文搜索引擎可分为两类，一类拥有自己的检索程序（Indexer），俗称“蜘蛛”（Spider）程序或“机器人”（Robot）程序，能自建网页数据库，搜索结果直接从自身的数据库中调用，上面提到的Google和XX就属于此类；另一类则是租用其他搜索引擎的数据库，并按自定的格式排列搜索结果，如Lycos搜索引擎。
2.3.2目录索引
目录索引虽然有搜索功能，但严格意义上不能称为真正的搜索引擎，只是按目录分类的网站链接列表而已。
用户完全可以按照分类目录找到所需要的信息，不依靠关键词（Keywords）进行查询。
目录索引中最具代表性的莫过于大名鼎鼎的Yahoo、新浪分类目录搜索。
2.3.3元搜索引擎
1995年，一种新的搜索引擎形式出现了——元搜索引擎（MetaSearchEngine）。
用户只需提交一次搜索请求，由元搜索引擎负责转换处理后提交给多个预先选定的独立搜索引擎，并将从各独立搜索引擎返回的所有查询结果，集中起来处理后再返回给用户。
第一个元搜索引擎，是Washington大学硕士生EricSelberg和OrenEtzioni的Metacrawler。
元搜索引擎（METASearchEngine）接受用户查询请求后，同时在多个搜索引擎上搜索，并将结果返回给用户。
著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等，中文元搜索引擎中具代表性的是搜星搜索引擎。
在搜索结果排列方面，有的直接按来源排列搜索结果，如Dogpile；有的则按自定的规则将结果重新排列组合，如Vivisimo。
2.3.4垂直搜索引擎
垂直搜索是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。
相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式，通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。
其特点就是“专、精、深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和深入。
2.3.5其他非主流搜索引擎形式
（1）集合式搜索引擎
该搜索引擎类似元搜索引擎，区别在于它并非同时调用多个搜索引擎进行搜索，而是由用户从提供的若干搜索引擎中选择，如HotBot在2002年底推出的搜索引擎。
（2）门户搜索引擎
AOLSearch、MSNSearch等虽然提供搜索服务，但自身既没有分类目录也没有
网页数据库，其搜索结果完全来自其他搜索引擎。
（3）免费链接列表（FreeForAllLinks简称FFA）
一般只简单地滚动链接条目，少部分有简单的分类目录，不过规模要比Yahoo！
等目录索引小很多。
3系统需求分析
3.1搜索引擎的工作原理
为了帮助大家更好的理解本系统，首先向大家介绍一下搜索引擎的工作原理。
搜索引擎系统由四部分构成：
信息搜集模块、分析索引模块和检索服务模块、。
信息搜集模块采用一种像真人一样可以浏览网页的Robot程序,这类程序能自动地在网上漫游,从一个或一组URL开始访问,然后下载相应的网页,抽取页面中的链接,按照某种算法决定下一步要访问的URL地址,常用的算法有广度优先和深度优先。
Robot（机器人）一词对编程者有特殊的意义。
ComputerRobot是指某个能以人类无法达到的速度不断重复执行某项任务的自动程序。
由于专门用于检索信息的Robot程序像蜘蛛（spider）一样在网络间爬来爬去，因此，搜索引擎的Robot程序被称为spider程序。
Robot程序不停地重复这个访问过程,搜集信息资料,存储到本地数据库,直至再没有满足条件的新的URL地址或超出了某些条件限制。
分析索引模块将Robot程序采集的信息进行比较分析,删除那些内容基本相似的转载网页,以及未加任何修改,内容完全相同的镜像网页,然后,对留存的网页信息,剔除HTML等的标志符号,提取出网页源文件内容特征的关键词,汇集成索引数据库,并随时顺着链接跟踪网上新加入的主页,为其建立索引。
索引数据库就是一个很大的查询表,主要的字段有：
网站的名称、标题、URL地址、摘要等。
对Web页面内容进行全文索引,即对Web页中每一个单词进行标引。
从网页中按某些分类或特征对信息进行抽取。
例如:
Lycos仅标引文件名、文件标题和全文前20行的内容。
而AltaVista的索引处理则最为全面,不仅对网页的所有文本、图像及链接等进行索引,而且还记录单词之间的相对位置。
一般来说,标引的索引词越多,检索的全面性越高,分析索引模块是搜索引擎提供检索服务的基础。
3.2系统功能需求
本系统的功能需求是：
搜索引擎系统从一个或一组已URL开始访问互联网,下载相关的网页信息及新的链接,以一定的策略遍历新链接,并读取新链接的信息内容,将它们加入到本地数据库。
然后,由分析索引模块对这些数据进行处理组织后,形成索引数据库。
用户通过用户模块提交查询服务,在搜索框中输入检索式,系统就会自动完成检索,并按一定的排列方式返回检索结果。
对它有如下基本要求。
能够接受用户通过浏览器提交的查询词或者短语，记作q，例如“联想”，“IBM”，“hp”等等。
在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表。
系统根据功能可分为两个部分：
检索界面,可以接受用户提交的检索要求；检索结果,将检索到的资料整理组织后按一定顺序提供给用户。
搜索引擎的检索结果通常包含大量文献,为了将最有“价值”的网页提供给用户,搜索引擎一般都能按查询的相关程度对检索结果进行排列,最相关的文献通常排在最前面。
3.3系统性能需求
（1）系统要有很好的可移植性。
（2）系统必须有很好的可维护性，代码的格式规范。
（3）系统要有健壮性。
（4）界面设计要求简洁、美观、大方。
（5）系统运行必须稳定，消耗资源少，代码效率高。
（6）系统运行环境：
Windows操作系统，火狐浏览器。
（7）系统开发环境：
myeclips，Oracle10g数据库。
4系统总体设计
4.1“飞梦”搜索引擎系统总体介绍
4.1.1“飞梦”搜索引擎系统工作机制
首先通过网页爬虫技术将网页链接或者摘要搜集到数据库中，然后定时将缓存更新，用户在查询时可直接从缓存中读取信息，大大提高了响应速度。
用户的请求在得到响应后应先将查询结果存于缓存，然后调用排序算法进行二次排序，最后将排序好的结果响应给用户。
4.1.2几种常见的语义WEB排序技术
（1）基于Web页面内容排序
基于Web页面内容的排序算法，主要源自传统信息检索中常用的文本文档加权标引算法，其基本思想是通过计算Web页面中与查询关键词相匹配的索引项，对Web页面主题内容的表征程度进行排序．基于Web页面内容的排序算法非常丰富，其中以基于词频和位置的加权排序算法应用最为广泛，有些算法尽管可以获得更好的排序效果，但往往由于分析处理过于复杂而不能满足海量Web信息检索快速响应的需要．
（2）基于Web页面链接排序
Web页面的链接反映的是Web页面之间形成的“参考”、“引用”或“推荐”关系，如果某一Web页面被较多页面链接，则表示它相对被人关注，其内容应该是比较重要或比较有用的，基于Web页面链接分析的排序算法正是基于这一思想来度量Web页面的重要性（质量）进行排序其中以PageRank算法最具代表性．PageRank算法以“随机冲浪”模型为理论基础，而HITS算法使用Authority和Hub页面相互加强模型，二者都利用了页面和超链接组成的有向图，根据连接关系进行递归运算来确定Web页面的重要性得分．但是，PageRank算法在计算时没有考虑用户的具体查询内容和Web页面实际表达内容，对与页面相链接的其他页面是否和该页面主题相关也没有考虑，因此在排序时容易产生主题漂移（topicdrift）．另外，页面的PageRank值单纯依靠人链数量的多寡及入链的PageRank值进行计算，使得许多内容质量很高的页面可能因为人链数量过少只能获得较低的排名，旧页面的排序往往比新页面更为有利，因为新页面获得的链接数量通常要少于旧页面，搜索引擎优化（SEO）人员也很容易通过增加页面入链数量等方式来获得更高的页面排名。
（3）基于检索用户排序
搜索引擎查询结果是否相关、排序是否合理最终取决于用户的主观判断．不同用户的动机、知识、兴趣、社会阅历等差异很大，因而对检索结果的评价也会产生较大的偏差，理想的检索排序算法应该对来自用户的个人因素加以考虑．基于检索用户的排序主要分为2种：
一种是基于检索用户群体的排序，如AskJeeves公司提出的DirectHit算法；一种是基于检索用户个体的排序，也称为个性化检索排序，用户个性的
表达可以通过2种方式完成：
一种是用户主动提交个人信息或直接对系统进行相关反馈；另一种是系统通过分析该用户在客户端或服务器端的检索行为加以确定．
4.1.3语义本体概念
本体知识库是语义搜索引擎进行推理和知识积累的基础和关键，而Ontology（本体）则是知识库的基础。
一般来说，本体提供一组术语和概念来描述某个领域，知识库则使用这些术语来表达该领域的事实。
例如医药本体可能包含“白血病”、“皮肤病”等术语的定义，但它不会包含具体某一病人的诊断结果，而这正是知识库所要表达的内容。
比如张三患有皮肤病、李四患有皮肤病和白血病、王五患有白血病，其中的皮肤病、白血病就是本体。
而各个病症的实例（张三、李四、王五）及其病症描述就是知识库的内容。
对它有如下基本要求：
能够接受用户通过浏览器提交的查询词或者短语。
在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表。
这个列表的每一条目至少包含三个元素（标题，网址链接，摘要）
4.1.4语义搜索
搜索引擎技术伴随着WWW的发展是引人注目的。
“飞梦”搜索引擎是基于Web的，基于语义排序的搜索引擎。
顾名思义，所谓语义搜索，是指搜索引擎的工作不再拘泥于用户所输入请求语句的字面本身，而是透过现象看本质，准确地捕捉到用户所输入语句后面的真正意图，并以此来进行搜索，从而更准确地向用户返回最符合其需求的搜索结果。
语义web服务是语义WEB服务技术的有机结合，通过对WEB服务添加语义标注，使得数据能被计算机自动处理和理解，让计算机可以在因特网海量信息中找到所需的任何信息，从而将万维网中现存的信息发展成一个巨大的的全球信息库、数据库，语义WEB服务搜索是一个满足服务请求者快速便捷的定位可用语义WEB服务资源的过程。
随着因特网上语义web服务数量急剧增加，语义WEB服务的调用和组合都必须基于语义WEB服务搜索来完成。
因此语义WEB服务搜索技术是语义WEB服务技术走向成熟和大规模应用的一个必备条件和重要标志。
4.1.5基于本体的语义排序
自语义WEB服务概念提出以来，关于语义WEB服务搜索方面的研究工作也受到研究人员的关注和重视，做了很多有益的探索。
其中涉及的研究主题主要包含语义WEB服务资源的索引研究，语义WEB服务服务资源的匹配策略研究等。
深入了解这些工作后可以得知，在语义WEB服务搜索的多个研究主题中，其中一个不可缺少环节就是，语义WEB服务匹配结果排序机制。
本文在综合概括和分析各种关系与语义WEB服务匹配结果排序机制的基础上提出了一种基于本体域的语义距离度量模型的语义WEB服务匹配结果的排序机制，详细阐述了该排序机制的原理，利用该排序机制，将语义WEB服务引用概念间的语义关系转换成可以精确比较的量化度量值，对于属于相同语义匹配类型的匹配候选服务与服务请求也能够分别计算语义距离，从而区分出相同类型的候选服务与服务请求的匹配程度。
基于语义距离度量模型的排序机制能够得到精确的语义距离度量值，从而达到改善用户对语义WEB服务的体验目地。
举例来说吧，当一个用户在搜索框中输入“孟字去掉子”时，深谙语义搜索的搜索引擎就能够判断出，用户想要找的并不是含有“孟”、“去掉子”等字眼的内容，而是想要查找与“皿”这个字相关的内容；同样，当用户搜索“表现春天的图片”时，搜索引擎会向其呈现出各种与春天相关的图片，而不仅仅局限于该图片的标题是否包含“春天”字样。
“可以接受的时间”，也就是响应时间。
这是衡量搜索引擎可用性的一个基本指标，也是和传统信息检索系统的一个差别。
对于基于BS架构的软件来说，响应时间不能太长，通常在“秒”这个量级。
当用户在检索框中输入要检索的信息时，系统将“匹配”与之相对应的结果集。
“匹配”，指的是数据库中以某种形式包含有request，这种形式包括三种情况：
1，全文匹配2，包含关系3，关联关系。
由于Web上的信息量大，而且搜索引擎的查询方式简单。
简单，意味着抽象；抽象，意味着有更多的具体事物可能是它的体现。
对于一个长长的列表，很少有用户有耐心都审视一遍。
因此返回的结果集将会在结果界面返回,并且对其进行分页。
用户首先在文本框中输入要检索的关键字，然后，单击搜索按钮。
图4-1搜索界面
4.2系统逻辑设计
4.2.1系统时序图
升级会员 