计算机学科导论第3章.ppt

《计算机学科导论第3章.ppt》由会员分享，可在线阅读，更多相关《计算机学科导论第3章.ppt（37页珍藏版）》请在三一办公上搜索。

1、信息检索原理与应用,1,信息检索的基本概念信息检索的历史搜索引擎的基本原理常见的搜索引擎,2,Web is NothingwithoutSearch,信息检索原理与应用,3,信息过载（Information overload）“全世界每年产生1到2EB（1EB=1024PB,1PB=1024TB）信息，相当于地球上每个人大概产生250MB信息。其中纸质信息仅占所有信息的0.03%.”Tom Landauer认为人的大脑只能存储200M信息量，一辈子只能接触6G的信息量。“人类目前至少生产了40亿网页，而人类有史以来上万年产生了大约1亿本书；中国网上大约有3亿网页，而中华民族有史以来出版的书籍大

2、约不超过275万种”（2004年）。静态网页有上百亿，动态及隐藏网页至少是静态网页的500倍。,信息检索的基本概念,信息检索原理与应用,4,2000-2008年中国网站规模变化,信息检索的基本概念,信息检索原理与应用,5,2002-2008年中国网页规模变化,信息检索的基本概念,信息检索原理与应用,6,全球数字化进程加快1998年，美国前副总统戈尔提出数字化地球的概念。1998年，江泽民总书记提出数字中国战略构想。全世界启动了数字图书馆、数字博物馆在内的一系列工程，另外包括虚拟博物馆、数字电影、交互电视、会议电视、远程教育、遥感、GPS等在内的服务或应用也产生大量文本和多媒体数据。,信息检索的

3、基本概念,信息检索原理与应用,7,一方面，人们可以获得的信息的来源非常广泛。另一方面，人们如何快速、准确、全面地获得自己所需要的信息？信息量太大，而且信息冗余度大、质量良莠不齐、格式不一、位置分散、关联复杂、语言繁多用户需求的表达和理解非常困难信息的理解非常困难自然语言文本、图片、视频,信息检索的基本概念,信息检索原理与应用,8,信息检索是研究如何解决上述问题的一门学科！Information Retrieval这个术语产生于Calvin Mooers 1948年在MIT的硕士论文。信息检索（Information Retrieval，IR）从文档集合中返回满足用户需求的相关信息的过程。是研究

4、信息的获取(acquisition)、表示(representation)、存储(storage)、组织(organization)和访问(access)的一门学问。,信息检索的基本概念,信息检索原理与应用,9,信息检索可以看成计算机科学和图书情报学的交叉学科。以计算机为手段，处理信息对象和其他学科也融合：语言学、认知科学、检索来自英文单词Retrieval，有些人把它翻译成获取。其本义是“获得与输入要求相匹配的输出”，和我们平时所理解的搜索意义上的检索不一样。Retrieval Search,信息检索的基本概念,信息检索原理与应用,10,信息检索 v.s.搜索引擎例1：返回与信息检索相关的网

5、页搜索引擎(Search Engine,SE)例2：毛主席的生日是哪天？问答系统(Question Answering,QA)例3：返回联想PC的型号、配置、价格等信息信息抽取(Information Extraction,IE)例4：订阅有关NBA的新闻信息推荐(Information Recommending)狭义的IR通常是指Information Search，而广义的IR包含非常多的内容(SE,QA,IE,)。,信息检索的基本概念,信息检索原理与应用,11,基本概念用户需求(User Need)用户需要获得的信息严格地说，用户需求只存在于用户的内心，但是通常用文本来描述，如查找与NB

6、A相关的新闻，有时也称为主题(Topic)用户需求提交给检索系统时称为查询(Query)，如“NBA”，对同一个用户需求，不同人不同时候可以构造出不同的Query，比如上述需求也可表示成“NBA新闻”、“NBA赛况”等，Query在IR系统中往往还有内部表示,信息检索的基本概念,信息检索原理与应用,12,基本概念文档集(Collection)所有待检索的文档构成的集合文档(Document)：检索的对象可以是文本，也可以是图像、视频、语音等多媒体文档可以是无格式、半格式、有格式的,信息检索的基本概念,信息检索原理与应用,13,基本概念相关度(relevance)检索的到的文档满足用户查询需求的

7、程度。相关取决于用户的判断，是一个主观概念不同用户做出的判断很难保证一致即使是同一用户在不同时期、不同环境下做出的判断也不尽相同相关度通常只有相对意义，对一个查询，不同文档的相关度可以比较，而对于不同的查询的相关度不便比较,信息检索的基本概念,信息检索原理与应用,14,信息检索和数据库检索,信息检索的基本概念,信息检索原理与应用,15,计算机出现以前约4000年前，人类就开始有目的地组织信息，一个典型的例子就是图书中的目录。随后，逐渐出现索引的概念，即从一些词和概念指向相关信息或者文档的指针。计算机问世以前，人们主要通过手工方式来建立索引。1948C.N.Mooers在其MIT的硕士论文中第一

8、次创造了“Information Retrieval”这个术语。,信息检索的历史,信息检索原理与应用,16,196070年代人们开始使用计算机为一些小规模科技和商业文献的摘要建立文本检索系统。产生了经典的信息检索模型：布尔模型(Boolean Model)、向量空间模型(Vector Space Model)和概率检索模型(Probabilistic Model)。1980年代出现了一些商用的较大规模数据库检索系统Lexis-Nexis：为法律研究提供全文检索的联机服务系统Dialog：世界上最大的国际联机情报检索系统MEDLINE：国际性综合生物医学信息书目数据库,信息检索的历史,信息检索原

9、理与应用,17,1986：Internet正式形成1990s第一个网络搜索工具：1990年加拿大蒙特利尔McGill大学开发的FTP搜索工具Archie第一个WEB搜索引擎：1994年美国CMU开发的Lycos（现代搜索引擎的始祖）1995：斯坦福大学博士生开发的Yahoo1998：斯坦福大学博士生开发的Google1997：北京大学计算机系在CERNET上推出了天网搜索2000：百度成立,信息检索的历史,信息检索原理与应用,18,搜索引擎：在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表。,搜索引擎的基本原理,信息检索原理与应用,19,网页搜集当用户提交查询时，搜索引擎并不是立刻

10、在网络上开始“搜索”，而是在系统内部事先已经“搜集”到的网页内部进行搜索。网页搜索的策略定期搜集每隔固定的时间，对全体网页进行重新搜集和替换实现简单、实时性不够增量搜集开始搜集一批网页搜集新出现的网页搜集那些之后有过改变的网页删除之后不再存在的网页实现复杂、实时性高主动提交网站拥有者主动向搜索引擎提交它们的网址（商业搜索）,搜索引擎的基本原理,信息检索原理与应用,20,网络爬虫（spider）宽度优先搜索得到的网页集合要比深度优先搜索得到的集合重要程度更高,搜索引擎的基本原理,信息检索原理与应用,21,预处理关键词的提取,搜索引擎的基本原理,信息检索原理与应用,22,预处理关键词的提取网页文档

11、源文件的大小通常是其中内容大小的4倍,搜索引擎的基本原理,信息检索原理与应用,23,预处理消除重复的网页网页的重复率平均大约为4对搜索引擎有着重要的负面影响浪费搜索网页的机器、带宽资源在显示时消耗了显示屏资源,搜索引擎的基本原理,信息检索原理与应用,24,预处理网页重要度计算权威的网页通常是用户需要的PageRank算法PageRank 能够对网页的重要性做出客观的评价，它 并不计算直接链接的数量，而是将从网页 A 指向网页 B 的链接解释为由网页 A 对网页 B 所投的一票。这样，PageRank 会根据网页 B 所收到的投票数量来评估该页的重要性。Page Rank 的核心思想：在互联网上

12、，如果一个网页被很多其它网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。Google 的两个创始人拉里佩奇（Larry Page）和谢尔盖布林(Sergey Brin)把这个问题变成了一个二维矩阵相乘的问题，并且用迭代的方法解决了这个问题。,搜索引擎的基本原理,信息检索原理与应用,25,搜索引擎的基本原理,信息检索原理与应用,26,预处理构件文档集合的索引倒排索引倒排索引源于实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。

13、倒排索引被广泛用于搜索引擎系统对海量网页的存储，其效率要高于其它索引结构。,搜索引擎的基本原理,信息检索原理与应用,27,预处理构件文档集合的索引倒排索引原始文档文章1：Tom lives in Guangzhou,I live in Guangzhou too.文章2：He once lived in Shanghai.关键词文章1：tom live guangzhou i live guangzhou文章2：he live shanghai,搜索引擎的基本原理,信息检索原理与应用,28,查询利用倒排索引文件，迅速给出相关的文档集合主流搜索引擎的查询模式：用一个词或者短语直接表达信息需求，相

14、关的网页中含有该词或者该短语中的词容易实现，语义性较弱“如何学好C/C+？”从文档集合中产生一个文档排序列表主流搜索引擎的结果展示模式：网页按照重要程度和相关程度进行排序（排序的因素一般有上百种）据统计，搜索引擎用户平均翻页次数小于2文档摘要搜索引擎的每条结果：标题+网址+摘要,搜索引擎的基本原理,信息检索原理与应用,29,查询,搜索引擎的基本原理,信息检索原理与应用,30,Yahoo！1994年4月美国斯坦福大学电机工程系的博士生：David Filo和Jerry YangYAHOO=Yet Another Helpful Operation OriginYAHOO=Yet Another

15、Hierarchical Officious OracleYAHOO=Yet Another Hierarchically Organized OracleYAHOO=Yet Another Hypertext Online OrganizerYAHOO=You Always Have Other Options,常见的搜索引擎,信息检索原理与应用,31,Yahoo！,常见的搜索引擎,信息检索原理与应用,32,Google1998年9月7日，加州一个车库美国斯坦福大学计算机系的博士生：Sergey Brin和Larry Pagegoogol1个Googol所代表的数字为1后面加上 100 个零

16、。Googol 是一个非常大的数字，宇宙中没有什么物质的数量可以达到1个 Googol-无论星星、尘埃还是原子。,常见的搜索引擎,信息检索原理与应用,33,Google,常见的搜索引擎,信息检索原理与应用,34,Ask1996年6月AskJeeves被设计成回答用户提问的自然语言引擎。搜索时，它首先给出的是数据库中可能存在的答案，然后才是网站链接。,常见的搜索引擎,信息检索原理与应用,35,Ask,常见的搜索引擎,信息检索原理与应用,36,Vivisimo1998年美国国家科学基金会资助的一个实验项目采用了一种专门开发的启发式算法来集合或聚类原文文献完全自动化的，不需要人为进一步干扰，也不需要维护,常见的搜索引擎,信息检索原理与应用,37,Vivisimo,常见的搜索引擎,