索引数据库与搜索引擎

1、第八章第八章 索引数据库与搜索引擎索引数据库与搜索引擎索引数据库与索引机制索引数据库与索引机制搜索引擎的诞生与发展搜索引擎的诞生与发展搜索引擎的体系结构搜索引擎的体系结构搜索引擎实例搜索引擎实例n 互联网信息的爆炸性增长p表层网络表层网络 链接相连 网站110,460,149p深层网络深层网络 数据库、动态信息 约为表层网络500倍n 搜索引擎成为最重要的Web信息检索工具p全面、准确、快速1 索引数据库与索引机制索引数据库与索引机制 搜索引擎的核心是索引数据库。索引数据搜索引擎的核心是索引数据库。索引数据库的核心是倒排索引文件。倒排索引文件库的核心是倒排索引文件。倒排索引文件即即“由文档特征

2、值指向文档标识由文档特征值指向文档标识”的文件的文件2 搜索引擎的诞生与发展搜索引擎的诞生与发展2.1 搜索引擎的诞生搜索引擎的诞生 起源：起源：FTP文件搜索（以文件搜索（以Archie为代表）为代表） 第一代搜索引擎：第一代搜索引擎：分类目录（以雅虎为代表）分类目录（以雅虎为代表） 第二代搜索引擎：第二代搜索引擎：关键词搜索引擎（以关键词搜索引擎（以Google为为代表）代表）2 搜索引擎的诞生与发展搜索引擎的诞生与发展2.2 搜索引擎的分类搜索引擎的分类 根据检索方式分类：根据检索方式分类： 分类目录、关键词搜索引擎、混合搜索引擎分类目录、关键词搜索引擎、混合搜索引擎 根据信息覆盖范围及

3、适用用户群分类：根据信息覆盖范围及适用用户群分类： 综合搜索引擎、专用搜索引擎（垂直搜索引擎）综合搜索引擎、专用搜索引擎（垂直搜索引擎） 根据搜索范围分类：根据搜索范围分类： 独立搜索引擎、集成搜索引擎（元搜索引擎）独立搜索引擎、集成搜索引擎（元搜索引擎）元搜索引擎元搜索引擎又称集合式搜索引擎。即将多个搜索引擎又称集合式搜索引擎。即将多个搜索引擎集成在一起，并提供一个统一的检索界面。集成在一起，并提供一个统一的检索界面。 一个有趣的结合，实用强大一个有趣的结合，实用强大免费有趣的搜索引擎。它将两大搜索引擎免费有趣的搜索引擎。它将两大搜索引擎Google与与Baidu融二为一。在它们之间平均融二

4、为一。在它们之间平均85链接均不相同。链接均不相同。 是一个很有创意的网站，把是一个很有创意的网站，把google和和baidu的搜索框结合成了一个可以选择的搜索框。虽然的搜索框结合成了一个可以选择的搜索框。虽然看着有点头晕，但是让我们省了不少力气看着有点头晕，但是让我们省了不少力气.提高了搜索效率。提高了搜索效率。2 搜索引擎的诞生与发展搜索引擎的诞生与发展 2.3 搜索引擎的发展趋势搜索引擎的发展趋势 个性化；个性化； 智能化；智能化； 整合化；整合化； 垂直化；垂直化； 移动化；移动化； 开放化开放化2 搜索引擎的诞生与发展搜索引擎的诞生与发展 2.3 搜索引擎的发展趋势（补充）搜索引擎

5、的发展趋势（补充） 检索结果的后处理检索结果的后处理； 基于内容的多媒体搜索；基于内容的多媒体搜索； 即时搜索，如即时搜索，如 与与LBS结合结合, 如如http:/ ； 基于基于P2P技术的搜索技术的搜索； 语音搜索。语音搜索。3 搜索引擎的系统结构搜索引擎的系统结构 一个搜索引擎由以下五个部分组成：一个搜索引擎由以下五个部分组成： 搜索器搜索器 索引器索引器 索引数据库索引数据库 检索器检索器 用户接口用户接口 3.1 搜索器搜索器 搜索器（搜索器（Spider）俗称蜘蛛、网络机器人、爬虫）俗称蜘蛛、网络机器人、爬虫，是一个自动收集网页的系统程序。，是一个自动收集网页的系统程序。 搜索器的

6、功能是日夜不停地在互联网中漫游，搜搜索器的功能是日夜不停地在互联网中漫游，搜集信息。集信息。不光不光搜集各种类型的新信息，还要定期搜集各种类型的新信息，还要定期更新已经搜集过的旧信息，以避免出现死链更新已经搜集过的旧信息，以避免出现死链 搜索器首先将文档格式过滤掉，变成纯文本文件搜索器首先将文档格式过滤掉，变成纯文本文件信息送回，然后将其信息送回，然后将其放到放到“网页数据库网页数据库”中。中。该库里还记录了这些网页的该库里还记录了这些网页的URL，整个网页的，整个网页的HTML代码，网页标题等等信息。代码，网页标题等等信息。 网页存储格式网页存储格式version: 1.0/ version

7、 numberurl: http:/ URLorigin: http:/ original URLdate: Tue, 15 Apr 2003 08:13:06 GMT / time of harvestip: 2 / IP addressunzip-length: 30233 / If included, the data must be compressedlength: 18133/ data length/ a blank lineXXXXXXXX/ the followings are data partXXXXXXXX.XXXXXXXX/ data end

8、/ insert a new line1）网页选取策略）网页选取策略 广度优先：广度优先：是指网络蜘蛛会先抓取起始网页中链是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。继续抓取在此网页中链接的所有网页。 深度优先：深度优先： 是指网络蜘蛛会从起始页开始，一个是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。转入下一个起始页，继续跟踪链接。 高权重优先：高权重优先：是指对搜索到的文档集合进行评

9、级，是指对搜索到的文档集合进行评级，利用计算得到的结果从中挑选评级最高的链接作利用计算得到的结果从中挑选评级最高的链接作为下一个搜索的对象。为下一个搜索的对象。2）重复爬取策略）重复爬取策略 一致策略：一致策略：即以一定的频率对所有网页进即以一定的频率对所有网页进行重复爬取，不区分变更频率不同的网页行重复爬取，不区分变更频率不同的网页 比率策略：比率策略：即对于更新频率较高的网页，即对于更新频率较高的网页，重复爬取的频率也较高。重复爬取的频率也较高。3）友好性策略）友好性策略 网站管理员可以通过设置网络机器人排除网站管理员可以通过设置网络机器人排除协议设置网站是否允许蜘蛛爬取、可爬取协议设置网

10、站是否允许蜘蛛爬取、可爬取的网页范围，进而限制搜索器的爬取行为的网页范围，进而限制搜索器的爬取行为（在（在ROBOT.TXT文件中进行设置，该文件文件中进行设置，该文件必须放在网站根目录下）。爬取行为的频必须放在网站根目录下）。爬取行为的频率主要有搜索引擎自身设定。率主要有搜索引擎自身设定。 4）并行爬取策略）并行爬取策略 并行爬取策略是针对多个并行搜索器而言并行爬取策略是针对多个并行搜索器而言的。搜索引擎要采用一定的策略协调各个的。搜索引擎要采用一定的策略协调各个搜索器的行为。搜索器的行为。 搜索器一般将搜索器一般将Web空间按照域名、空间按照域名、IP地址地址或国家域名划分，每个搜索器负责

11、一个子或国家域名划分，每个搜索器负责一个子空间的穷尽搜索。空间的穷尽搜索。 搜索器的实现常用分布式、并行计算技术搜索器的实现常用分布式、并行计算技术，以提高信息发现和更新的速度。，以提高信息发现和更新的速度。3.2 索引器索引器 索引器的功能是索引器的功能是理解理解搜索器所搜索的纯文搜索器所搜索的纯文本信息，从中抽取出索引项（属性），生本信息，从中抽取出索引项（属性），生成成倒排索引倒排索引文件，进而文件，进而建立索引数据库建立索引数据库。 倒排倒排索引即由索引项查找相应的文档。索引即由索引项查找相应的文档。 索引项有索引项有客观索引项和内容索引项客观索引项和内容索引项倒排索引倒排索引具体步骤

12、具体步骤具体步骤具体步骤分析网页：分析网页：提取正文信息并进行分词；统提取正文信息并进行分词；统计词出现的频率及位置；提取其它相关信计词出现的频率及位置；提取其它相关信息，如被其他网页链接次数等；息，如被其他网页链接次数等；建立倒排索引：建立倒排索引：形成由文档号到索引词的形成由文档号到索引词的正向索引；重组正向索引，建立从关键词正向索引；重组正向索引，建立从关键词到文档号集合的倒排索引；到文档号集合的倒排索引；相关度及重要性计算：相关度及重要性计算：通过关键词频率、通过关键词频率、位置、表面特征及超链分析等因素来决定位置、表面特征及超链分析等因素来决定某一个网页针对某一个关键词的重要性。某一

13、个网页针对某一个关键词的重要性。单词单词-文档矩阵文档矩阵文档集合文档集合例例1简单的倒排索引简单的倒排索引带有单词频率的倒排索引带有单词频率的倒排索引 带有单词频率、文档频率和出现位置信息的倒排索引带有单词频率、文档频率和出现位置信息的倒排索引 倒排表记录索引项在文档中倒排表记录索引项在文档中出现的位置，以便检索器计出现的位置，以便检索器计算索引项之间的相邻或接近算索引项之间的相邻或接近关系（关系（proximity）正向索引正向索引例例2倒倒排排索索引引词词位位置置倒倒索索引引索引表也可能要记录索引项在索引表也可能要记录索引项在文档中出现的位置，以便检索文档中出现的位置，以便检索器计算索引

14、项之间的相邻或接器计算索引项之间的相邻或接近关系。近关系。 根据相关度算法，根据相关度算法，计算出网页与关键计算出网页与关键词的相关系数和权词的相关系数和权重值重值3.3 索引数据库索引数据库 索引数据库是搜索引擎的核心，既是索引索引数据库是搜索引擎的核心，既是索引器提供的产品，又是搜索器进行工作的基器提供的产品，又是搜索器进行工作的基础。础。 索引数据库由一个接口模块和四类文件构索引数据库由一个接口模块和四类文件构成。四类文件是：主索引（成。四类文件是：主索引（MIF）、倒排索）、倒排索引（引（IXF）、倒排地址表（）、倒排地址表（IAL）、纯文本）、纯文本文件。文件。主索引主索引多级倒排索

15、引文件多级倒排索引文件词编号词编号词词记录地址记录地址1搜索搜索100322核心核心100893组织组织100654信息信息10106词词倒排索引倒排索引文件的存文件的存放位置放位置指向指向IAL的相对地址指针的相对地址指针AP倒排地址表倒排地址表3.4 检索器检索器 检索器的功能是根据用户的查询在索引库检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序。度评价，对将要输出的结果进行排序。 检索器的工作包括检索器的工作包括查询匹配、结果排序和查询匹配、结果排序和文档摘要三个部分文档摘要三个部分。 查询结果

16、的文档摘要主要有两种生成机制：查询结果的文档摘要主要有两种生成机制：静态摘要和动态摘要。静态摘要和动态摘要。一般现阶段的搜索一般现阶段的搜索引擎运用动态摘要生成技术。引擎运用动态摘要生成技术。搜索结果排序技术搜索结果排序技术 （1）影响结果排序的主要因素）影响结果排序的主要因素 （2）排序算法）排序算法（1）影响结果排序的主要因素）影响结果排序的主要因素 内容相关度内容相关度基于相关度算法（搜索引擎基于相关度算法（搜索引擎怎么评价）怎么评价） 网站或网页权威度网站或网页权威度基于链接分析（即其基于链接分析（即其它网站怎么评价）它网站怎么评价） 网站或网页的实用度网站或网页的实用度基于用户访问模

17、式基于用户访问模式（即用户怎么评价）（即用户怎么评价） （2）排序算法）排序算法 这里我们主要介绍这里我们主要介绍Google的三种链接分析的三种链接分析算法：算法： PageRank算法算法 HillTop算法算法 Hits算法算法 Pagerank算法算法PageRank（网页等级）：（网页等级）：一种能够自动判断一种能够自动判断网页重要性的技术。网页重要性的技术。基本原理：基本原理： 从许多优质的网页链接过来的网页，从许多优质的网页链接过来的网页，必定还是优质网页必定还是优质网页决定因素：决定因素：反向链接数（反向链接数（数量数量） 反向链接源页面的反向链接源页面的Pagerank值值

18、（质量质量）反向链接源页面的链接数反向链接源页面的链接数 （被选中的几率指标被选中的几率指标） 具体算法：具体算法：将某个页面的将某个页面的 PageRank 除以这个除以这个页面的正向链接数页面的正向链接数,由此得到的值分别和正向链由此得到的值分别和正向链接所指向的页面的接所指向的页面的 PageRank 相加，即得到了相加，即得到了被链接的页面的被链接的页面的 PageRank。 Hits算法算法 算法对返回的匹配页面计算两种值算法对返回的匹配页面计算两种值,一种是一种是枢纽值枢纽值(Hub Scores)，另一种是，另一种是权威值（权威值（Authority Scores）这两个值是相互

19、依存、相互影响的。所这两个值是相互依存、相互影响的。所谓枢纽值，指的是页面上所有导出链接指向页面谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值指的是所有导入链接所在的权威值之和。权威值指的是所有导入链接所在的页面的枢纽值之和。的页面的枢纽值之和。 HillTop算法算法 ： HillTop也是一项搜索引擎结果排序的专利。也是一项搜索引擎结果排序的专利。 HillTop算法的指导思想和算法的指导思想和PageRank的是的是一致的，都是通过网页被链接的数量和质一致的，都是通过网页被链接的数量和质量来确定搜索结果的排序权重。但量来确定搜索结果的排序权重。但HillTop认为认为只计

20、算只计算 来自具有相同主题的相关文档来自具有相同主题的相关文档链接对于搜索者的价值会更大：即主题相链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权重计算的贡献比关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。主题不相关的链接价值要更高。用户行为模式如何影响网站排名？用户行为模式如何影响网站排名？ 例如：例如：说一个用户直接在说一个用户直接在Google主页搜索主页搜索某一个关键词，用户点击了第一个结果，某一个关键词，用户点击了第一个结果，然后五秒钟之内点击了浏览器的返回键，然后五秒钟之内点击了浏览器的返回键，再次来到再次来到Google主页，然后又点击了第三主页，然后

21、又点击了第三个结果。再过个结果。再过30分钟以后，这个用户才再分钟以后，这个用户才再次回到次回到Google主页。那么主页。那么Google就可以得就可以得出结论，第三个网站比第一个网站更能给出结论，第三个网站比第一个网站更能给用户提供有用的信息。如果这种模式大量用户提供有用的信息。如果这种模式大量反复，那么反复，那么Google就有可能把这两个网站就有可能把这两个网站的排名互换。的排名互换。3.5 用户接口用户接口 用户接口的作用是用户接口的作用是输入用户查询、显示查输入用户查询、显示查询结果、提供用户相关性反馈机制询结果、提供用户相关性反馈机制。 用户接口的设计和实现使用人机交互的理用户接

22、口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。论和方法，以充分适应人类的思维习惯。分为简单接口和复杂接口。分为简单接口和复杂接口。 当前，这方面研究集中在对用户信息需求当前，这方面研究集中在对用户信息需求的挖掘与发现、改进用户交互方式（信息的挖掘与发现、改进用户交互方式（信息可视化）等方面。可视化）等方面。总结：总结：搜索引擎工作流程搜索引擎工作流程 搜集搜集 累计式搜集，增量式搜集；累计式搜集，增量式搜集； 索引索引 重复网页消除；关键词提取；链接分析；重复网页消除；关键词提取；链接分析；倒排索引倒排索引 检索检索 查询匹配；结果排序；文档摘要查询匹配；结果排序；文档摘要

23、搜集搜集索引索引检索检索 从具体运行方式上说，系统根据站点从具体运行方式上说，系统根据站点/网页的网页的URL信息和网页之间的链接关系，利用网络蜘蛛在互信息和网页之间的链接关系，利用网络蜘蛛在互联网上收集数据；收集的数据分别通过链接信息联网上收集数据；收集的数据分别通过链接信息分析器和文本信息分析器处理，保存在链接数据分析器和文本信息分析器处理，保存在链接数据库和文本索引数据库中，同时，网页质量评估器库和文本索引数据库中，同时，网页质量评估器依据网页的链接关系和页面结构特征对页面质量依据网页的链接关系和页面结构特征对页面质量进行评估，并将评估的结果保存在索引数据库中；进行评估，并将评估的结果保

24、存在索引数据库中；查询服务器负责与用户的交互，它根据用户的检查询服务器负责与用户的交互，它根据用户的检索需求，从索引数据库中读取对应的索引，并综索需求，从索引数据库中读取对应的索引，并综合考虑查询相关性与页面质量评估结果之间的关合考虑查询相关性与页面质量评估结果之间的关系，给出查询结果列表反馈给用户。系，给出查询结果列表反馈给用户。4 搜索引擎实例搜索引擎实例 GOOGLE 百度百度案例：案例：google 网址：网址：http:/ Google是由美国斯坦福大学的两位博士是由美国斯坦福大学的两位博士生拉里生拉里佩吉和谢尔盖佩吉和谢尔盖布林于布林于1998年创年创建的。建的。 目前是全球最大、

25、最专业的搜索引擎目前是全球最大、最专业的搜索引擎 1998 年年, 当时在加州门洛帕克当时在加州门洛帕克 (Menlo Park), 拉里拉里佩奇佩奇 与与 谢谢尔盖尔盖布林布林 租用了这间房子的车库作为建立租用了这间房子的车库作为建立 Google 的据点的据点, 每个每个月月 Google 要交要交 $1,700 (961) 租金给房东租金给房东 Susan Wojcicki. 2000 2000 年年 11 11 月月 11 11 日日: Google : Google 的联合创始人的联合创始人, , 时任时任 CEO CEO 的的 拉里拉里佩奇佩奇 (Larry Page, (Larr

26、y Page, 左左) ) 和主席谢尔盖和主席谢尔盖布林布林 (Sergey Brin) (Sergey Brin) 在位于山景城的在位于山景城的 Google Google 总部内总部内, , 靠着懒人椅靠着懒人椅 (bean bags(bean bags )2006 2006 年年 5 5 月月 10 10 日日: : 一名一名 Google Google 雇员踩着一架脚踏滑板车雇员踩着一架脚踏滑板车 ( (所有员所有员工均可使用工均可使用), ), 穿越位于加州山景城的公司园区穿越位于加州山景城的公司园区. .检索范围检索范围检索方式检索方式简单检索简单检索高级检索高级检索简单检索简单检

27、索 逻辑逻辑“与与”：两词间加：两词间加空格空格 逻辑逻辑“或或”：用：用“OR”表示表示 逻辑逻辑“非非”：两词间加：两词间加“-”（“-”号前加号前加空格）空格） 强制检索强制检索：双引号双引号 指定网域指定网域：site: 指定文件类型指定文件类型：filetype:文件类型文件类型逻辑与功能逻辑与功能逻辑非功能逻辑非功能逻辑或功能逻辑或功能强制检索强制检索指定网域指定网域指定文件类型指定文件类型特色特色直达与检索词直达与检索词最相关的网页最相关的网页 网址：网址：http:/ 百度（百度（Baidu）是目前全球最优秀的中文信）是目前全球最优秀的中文信息检索与传递技术供应商。中国所有提供

28、息检索与传递技术供应商。中国所有提供搜索引擎的门户网站中，超过搜索引擎的门户网站中，超过80%以上都以上都由百度提供搜索引擎技术支持，现有客户由百度提供搜索引擎技术支持，现有客户包括新浪、搜狐（包括新浪、搜狐（Chianren）、央视国际）、央视国际、腾讯等。、腾讯等。案例：百度案例：百度检索范围检索范围检索方式检索方式 简单检索简单检索 高级检索高级检索简单检索简单检索 逻辑逻辑“与与”：两词间加空格：两词间加空格 逻辑逻辑“或或”：两词间加：两词间加“|”（前后加空格（前后加空格） 逻辑逻辑“非非”：两词间加：两词间加“-”（“-”号前加号前加空格）空格） 强制检索：双引号强制检索：双引号 指定网域：指定网域：site: 指定文件类型：指定文件类型：filetype:文件类型文件类型特色特色网页快照网页快照 如果原链接已经死掉或者因为网络的原因如果原链接已经死掉或者因为网络的原因暂时链接不通，那么可以通过网页快照看暂时链接不通，那么可以通过网页快照看到该页面信息。当然，快照内容不是该页到该页面信息。当然，快照内容不是该页最新页面；最新页面； 如果原地址打开很慢