《搜索引擎技术及趋势ppt培训课件》由会员分享,可在线阅读,更多相关《搜索引擎技术及趋势ppt培训课件(24页珍藏版)》请在金锄头文库上搜索。
1、随着因特网的迅猛发展、WEB信息的增加,用户要在信息海洋里查找信息,就像大海捞针一样,搜索引擎技术恰好解决了这一难题(它可以为用户提供信息检索服务)。搜索引擎(Search Engine)是随着WEB信息的迅速增加,从1995年开始逐渐发展起来的技术。据估计,全球目前的网页超过8亿,有效数据超过9T,并且仍以每4个月翻一番的速度增长。用户要在如此浩瀚的信息海洋里寻找信息,必然会“大海捞针”无功而返。搜索引擎正是为了解决这个“迷航”问题而出现的技术。搜索引擎以一定的策略在互联网中搜集、发现信息,对信息进行理解、提取、组织和处理,并为用户提供检索服务,从而起到信息导航的目的。搜索引擎提供的导航服务
2、已经成为互联网上非常重要的网络服务,搜索引擎站点也被美誉为“网络门户”。,1搜索引擎分类搜索引擎按其工作方式主要可分为三种,分别是全文搜索引擎(Full Text Search Engine)、目录索引类搜索引擎(Search Index/Directory)和元搜索引擎(Meta Search En-gine)。,(1)全文搜索引擎全文搜索引擎是名副其实的搜索引擎,国外具代表性的有Google、Fast/AllTheWeb、AltaVista、Inktomi、Teoma、WiseNut等,国内著名的有百度(Baidu)。它们都是通过从互联网上提取的各个网站的信息(以网页文字为主)而建立的数据
3、库中,检索与用户查询条件匹配的相关记录,然后按一定的排列顺序将结果返回给用户,因此他们是真正的搜索引擎。从搜索结果来源的角度,全文搜索引擎又可细分为两种,一种是拥有自己的检索程序(Indexer),俗称“蜘蛛”(Spider)程序或“机器人”(Robot)程序,并自建网页数据库,搜索结果直接从自身的数据库中调用,如上面提到的7家引擎;另一种则是租用其他引擎的数据库,并按自定的格式排列搜索结果,如Lycos引擎。,(2)目录索引目录索引虽然有搜索功能,但在严格意义上算不上是真正的搜索引擎,仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词(Keywords)查询,仅靠分类目录也可找到
4、需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的Yahoo雅虎。其他著名的还有Open Directory Pro-jec(tDMOZ)、LookSmart、About等。国内的搜狐、新浪、网易搜索也都属于这一类。,(3)元搜索引擎(META Search Engine)元搜索引擎在接受用户查询请求时,同时在其他多个引擎上进行搜索,并将结果返回给用户。在搜索结果排列方面,有的直接按来源引擎排列搜索结果,如Dogpile,有的则按自定的规则将结果重新排列组合,如Vivisimo。除上述三大类引擎外,还有以下几种非主流形式:,a)集合式搜索引擎:如HotBot在2002年底推出的引擎。该引擎类似
5、META搜索引擎,但区别在于不是同时调用多个引擎进行搜索,而是由用户从提供的4个引擎当中选择,因此叫它“集合式”搜索引擎更确切些。b)门户搜索引擎:如AOL Search、MSN Search等虽然提供搜索服务,但自身即没有分类目录也没有网页数据库,其搜索结果完全来自其他引擎。c)免费链接列表(Free For All Links,简称FFA):这类网站一般只简单地滚动排列链接条目,少部分有简单的分类目录,不过规模比起Yahoo等目录索引来要小得多。由于上述网站都为用户提供搜索查询服务,为方便起见,我们通常将其统称为搜索引擎。,2性能指标我们可以将WEB信息的搜索看作一个信息检索问题,即在由W
6、EB网页组成的文档库中检索出与用户查询相关的文档。所以我们可以用衡量传统信息检索系统的性能参数-召回率(Recall)和精度(Pricision)衡量一个搜索引擎的性能。召回率是检索出的相关文档数和文档库中所有的相关文档数的比率,衡量的是检索系统(搜索引擎)的查全率;精度是检索出的相关文档数与检索出的文档总数的比率,衡量的是检索系统(搜索引擎)的查准率。,对于一个检索系统来讲,召回率和精度不可能两全其美:召回率高时,精度低,精度高时,召回率低。所以常常用11种召回率下11种精度的平均值(即11点平均精度)来衡量一个检索系统的精度。对于搜索引擎系统来讲,因为没有一个搜索引擎系统能够搜集到所有的W
7、EB网页,所以召回率很难计算。目前的搜索引擎系统都非常关心精度。影响一个搜索引擎系统的性能有很多因素,最主要的是信息检索模型,包括文档和查询的表示方法、评价文档和用户查询相关性的匹配策略、查询结果的排序方法和用户进行相关度反馈的机制。,3主要技术一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。(1)搜索器搜索器的功能是在互联网中漫游,发现和搜集信息。它常常是一个计算机程序,日夜不停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息,同时因为互联网上的信息更新很快,所以还要定期更新已经搜集过的旧信息,以避免死连接和无效连接。,目前有两种搜集信息的策略: 从一个起始URL集合开始,
8、顺着这些URL中的超链(Hyperlink),以宽度优先、深度优先或启发式方式循环地在互联网中发现信息。这些起始URL可以是任意的URL,但常常是一些非常流行、包含很多链接的站点(如Yahoo!)。将Web空间按照域名、IP地址或国家域名划分,每个搜索器负责一个子空间的穷尽搜索。搜索器搜集的信息类型多种多样,包括HTML、XML、Newsgroup文章、FTP文件、字处理文档、多媒体信息。搜索器的实现常常用分布式、并行计算技术,以提高信息发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。,(2)索引器索引器的功能是理解搜索器所搜索的信息,从中抽取出索引项,用于表示文档以及生成文档
9、库的索引表。索引项有客观索引项和内容索引项两种:客观项与文档的语意内容无关,如作者名、URL、更新时间、编码、长度、链接流行度(Link Popularity)等等;内容索引项是用来反映文档内容的,如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和多索引项(或称短语索引项)两种。单索引项对于英文来讲是英语单词,比较容易提取,因为单词之间有天然的分隔符(空格);对于中文等连续书写的语言,必须进行词语的切分。,在搜索引擎中,一般要给单索引项赋与一个权值,以表示该索引项对文档的区分度,同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计法、概
10、率法和语言学法。索引表一般使用某种形式的倒排表(Inversion List),即由索引项查找相应的文档。索引表也可能要记录索引项在文档中出现的位置,以便检索计算索引项之间的相邻或接近关系(proximity)。 索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时,必须实现即时索引(Instant Indexing),否则不能够跟上信息量急剧增加的速度。索引算法对索引器的性能(如大规模峰值查询时的响应速度)有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量。,(3)检索器检索器的功能是根据用户的查询在索引库中快速检出文档,进行文档与查询的相关度评价,对将要输出的结果进行排
11、序,并实现某种用户相关性反馈机制。检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型四种。,(4)用户接口用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎,高效率、多方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法,以充分适应人类的思维习惯。用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询串的文本框;复杂接口可以让用户对查询进行限制,如逻辑运算(与、或、非;)、相近关系(相邻、NEAR)、域名范围(如.edu、.com)、出现位置(如标题、内容)、信息时间、长度等等。
12、目前一些公司和机构正在考虑制定查询选项的标准。,4未来动向搜索引擎已成为一个新的研究、开发领域。因为它要用到信息检索、人工智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言处理等多领域的理论和技术,所以具有综合性和挑战性。又由于搜索引擎有大量的用户,有很好的经济价值,所以引起了世界各国计算机科学界和信息产业界的高度关注,目前的研究、开发十分活跃,并出现了很多值得注意的动向。,(1)十分注意提高信息查询结果的精度,提高检索的有效性用户在搜索引擎上进行信息查询时,并不十分关注返回结果的多少,而是看结果是否和自己的需求吻合。对于一个查询,传统的搜索引擎动辄返回几十万、几百万篇文档,
13、用户不得不在结果中筛选。,解决查询结果过多的现象目前出现了几种方法:一是通过各种方法获得用户没有在查询语句中表达出来的真正用途,包括使用智能代理跟踪用户检索行为,分析用户模型;使用相关度反馈机制,使用户告诉搜索引擎哪些文档和自己的需求相关(及其相关的程度),哪些不相关,通过多次交互逐步求精。二是用正文分类(Text Catego-rization)技术将结果分类,使用可视化技术显示分类结构,用户可以只浏览自己感兴趣的类别。三是进行站点类聚或内容类聚,减少信息的总量。,(2)基于智能代理的信息过滤和个性化服务信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模型(如Web知识、信息
14、处理、与用户兴趣相关的信息资源、领域组织结构)、用户模型(如用户背景、兴趣、行为、风格)知识进行信息搜集、索引、过滤(包括兴趣过滤和不良信息过滤),并自动地将用户感兴趣的、对用户有用的信息提交给用户。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力,从而提供个性化的服务。智能代理可以在用户端进行,也可以在服务器端运行。,(3)采用分布式体系结构提高系统规模和性能搜索引擎的实现可以采用集中式体系结构和分布式体系结构,两种方法各有千秋。但当系统规模到达一定程度(如网页数达到亿级)时,必然要采用某种分布式方法,以提高系统性能。搜索引擎的各个组成部分,除了用户接口之外,都可以进行分布:搜索器可以
15、在多台机器上相互合作、相互分工进行信息发现,以提高信息发现和更新速度;索引器可以将索引分布在不同的机器上,以减小索引对机器的要求;检索器可以在不同的机器上进行文档的并行检索,以提高检索的速度和性能。,(4)重视交叉语言检索的研究和开发交叉语言信息检索是指用户用母语提交查询,搜索引擎在多种语言的数据库中进行信息检索,返回能够回答用户问题的所有语言的文档。如果再加上机器翻译,返回结果可以用母语显示。该技术目前还处于初步研究阶段,主要的困难在于语言之间在表达方式和语义对应上的不确定性。但对于经济全球化、互联网跨越国界的今天,无疑具有很重要的意义。,5学术研究目前搜索引擎领域的商业开发非常活跃,各大搜
16、索引擎公司都在投巨资研制搜索引擎系统,同时也不断地涌现出新的具有鲜明特色的搜索引擎产品,在这种情况下,对搜索引擎技术相关领域的学术研究得到了大学和科研机构的重视。如Stanford大学在其数字图书馆项目中开发了Google搜索引擎,在Web信息的高效搜索、文档的相关度评价、大规模索引等方面作了深入的研究,取得了很好的成果。NEC美国研究所的Steve Lawrence和C.Lee Giles 1998年和1999年连续两年在自然和科学杂志上撰文对搜索引擎技术的研究进行评述。著名的信息检索会议TREC也从1998年开始增加了Web Track课题,以考察Web文档与其它类型文档在检索性质上的不同
17、之处,并将测试在大规模的Web库(如100G字节)上进行信息检索的算法性能。,由美国Infornotics公司主办的搜索引擎国际会议从1996年开始,每年举行一次,对搜索引擎技术进行总结、讨论和展望,参加者有著名的搜索引擎公司、大学和研究机构的学者,对搜索引擎技术起到了很好的推动作用。另外像IEEE主办的国际万维网会议、人机交互会议已有越来越多关于搜索引擎技术研究的文章发表。国内先后有北京大学、清华大学、国家智能研究中心等高校和研究单位对搜索引擎技术开展研究,并开发出了几个较好的系统。如由北京大学计算机系网络研究室开发的“天网”,在系统规模及系统性能方面达到了国外中型搜索引擎系统的技术水平。,