索引数据库与搜索引擎

第八章索引数据库与搜索引擎索引数据库与索引机制搜索引擎的诞生与发展搜索引擎的体系结构搜索引擎实例引言互联网信息的爆炸性增长表层网络链接相连网站110,460,149深层网络数据库、动态信息约为表层网络500倍搜索引擎成为最重要的Web信息检索工具全面、准确、快速注:引自NetCraft1索引数据库与索引机制搜索引擎的核心是索引数据库。索引数据库的核心是倒排索引文件。倒排索引文件即“由文档特征值指向文档标识”的文件2搜索引擎的诞生与发展2.1搜索引擎的诞生起源：FTP文件搜索（以Archie为代表）第一代搜索引擎：分类目录（以雅虎为代表）第二代搜索引擎：关键词搜索引擎（以Google为代表）2搜索引擎的诞生与发展2.2搜索引擎的分类根据检索方式分类：分类目录、关键词搜索引擎、混合搜索引擎根据信息覆盖范围及适用用户群分类：综合搜索引擎、专用搜索引擎（垂直搜索引擎）根据搜索范围分类：独立搜索引擎、集成搜索引擎（元搜索引擎）元搜索引擎又称集合式搜索引擎。即将多个搜索引擎集成在一起，并提供一个统一的检索界面。

一个有趣的结合，实用强大免费有趣的搜索引擎。它将两大搜索引擎Google与Baidu融二为一。在它们之间平均85％链接均不相同。

是一个很有创意的网站，把google和baidu的搜索框结合成了一个可以选择的搜索框。虽然看着有点头晕，但是让我们省了不少力气.提高了搜索效率。2搜索引擎的诞生与发展2.3搜索引擎的发展趋势个性化；智能化；整合化；垂直化；移动化；开放化2搜索引擎的诞生与发展2.3搜索引擎的发展趋势（补充）检索结果的后处理；基于内容的多媒体搜索；即时搜索，如/instant；与LBS结合,如/xian

；基于P2P技术的搜索；语音搜索。3搜索引擎的系统结构一个搜索引擎由以下五个部分组成：搜索器索引器索引数据库检索器用户接口

www索引器检索器用户接口robot…robot文档库索引库图：搜索引擎的组成和结构3.1搜索器搜索器（Spider）俗称蜘蛛、网络机器人、爬虫，是一个自动收集网页的系统程序。搜索器的功能是日夜不停地在互联网中漫游，搜集信息。不光搜集各种类型的新信息，还要定期更新已经搜集过的旧信息，以避免出现死链搜索器首先将文档格式过滤掉，变成纯文本文件信息送回，然后将其放到“网页数据库”中。该库里还记录了这些网页的URL，整个网页的HTML代码，网页标题等等信息。

网页存储格式version:1.0 //versionnumberurl:/ //URLorigin:/ //originalURLdate:Tue,15Apr200308:13:06GMT //timeofharvestip:2 //IPaddressunzip-length:30233 //Ifincluded,thedatamustbecompressedlength:18133 //datalength

//ablanklineXXXXXXXX //thefollowingsaredatapartXXXXXXXX….XXXXXXXX //dataend

//insertanewline1）网页选取策略广度优先：是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。

深度优先：

是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。高权重优先：是指对搜索到的文档集合进行评级，利用计算得到的结果从中挑选评级最高的链接作为下一个搜索的对象。2）重复爬取策略一致策略：即以一定的频率对所有网页进行重复爬取，不区分变更频率不同的网页比率策略：即对于更新频率较高的网页，重复爬取的频率也较高。3）友好性策略网站管理员可以通过设置网络机器人排除协议设置网站是否允许蜘蛛爬取、可爬取的网页范围，进而限制搜索器的爬取行为（在ROBOT.TXT文件中进行设置，该文件必须放在网站根目录下）。爬取行为的频率主要有搜索引擎自身设定。4）并行爬取策略并行爬取策略是针对多个并行搜索器而言的。搜索引擎要采用一定的策略协调各个搜索器的行为。搜索器一般将Web空间按照域名、IP地址或国家域名划分，每个搜索器负责一个子空间的穷尽搜索。

搜索器的实现常用分布式、并行计算技术，以提高信息发现和更新的速度。3.2索引器索引器的功能是理解搜索器所搜索的纯文本信息，从中抽取出索引项（属性），生成倒排索引文件，进而建立索引数据库。

倒排索引即由索引项查找相应的文档。索引项有客观索引项和内容索引项倒排索引具体步骤具体步骤分析网页：提取正文信息并进行分词；统计词出现的频率及位置；提取其它相关信息，如被其他网页链接次数等；建立倒排索引：形成由文档号到索引词的正向索引；重组正向索引，建立从关键词到文档号集合的倒排索引；相关度及重要性计算：通过关键词频率、位置、表面特征及超链分析等因素来决定某一个网页针对某一个关键词的重要性。单词-文档矩阵文档集合例1简单的倒排索引带有单词频率的倒排索引带有单词频率、文档频率和出现位置信息的倒排索引倒排表记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系（proximity）正向索引例2倒

排

索

引词

位

置

倒

索

引索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系。

根据相关度算法，计算出网页与关键词的相关系数和权重值3.3索引数据库索引数据库是搜索引擎的核心，既是索引器提供的产品，又是搜索器进行工作的基础。索引数据库由一个接口模块和四类文件构成。四类文件是：主索引（MIF）、倒排索引（IXF）、倒排地址表（IAL）、纯文本文件。主索引多级倒排索引文件词编号词记录地址1搜索100322核心100893组织100654信息10106词倒排索引文件的存放位置指向IAL的相对地址指针AP倒排地址表3.4检索器检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序。

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

……（2）排序算法这里我们主要介绍Google的三种链接分析算法：PageRank算法HillTop算法Hits算法Pagerank算法PageRank（网页等级）：一种能够自动判断网页重要性的技术。基本原理：

从许多优质的网页链接过来的网页，必定还是优质网页决定因素：反向链接数（数量）反向链接源页面的Pagerank值（质量）反向链接源页面的链接数（被选中的几率指标）

具体算法：将某个页面的PageRank除以这个页面的正向链接数,由此得到的值分别和正向链接所指向的页面的PageRank相加，即得到了被链接的页面的PageRank。Hits算法算法对返回的匹配页面计算两种值,一种是枢纽值(HubScores)，另一种是权威值（AuthorityScores）这两个值是相互依存、相互影响的。所谓枢纽值，指的是页面上所有导出链接指向页面的权威值之和。权威值指的是所有导入链接所在的页面的枢纽值之和。HillTop算法：

HillTop也是一项搜索引擎结果排序的专利。HillTop算法的指导思想和PageRank的是一致的，都是通过网页被链接的数量和质量来确定搜索结果的排序权重。但HillTop认为只计算来自具有相同主题的相关文档链接对于搜索者的价值会更大：即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。用户行为模式如何影响网站排名？例如：说一个用户直接在Google主页搜索某一个关键词，用户点击了第一个结果，然后五秒钟之内点击了浏览器的返回键，再次来到Google主页，然后又点击了第三个结果。再过30分钟以后，这个用户才再次回到Google主页。那么Google就可以得出结论，第三个网站比第一个网站更能给用户提供有用的信息。如果这种模式大量反复，那么Google就有可能把这两个网站的排名互换。3.5用户接口

用户接口的作用是输入用户查询、显示查询结果、提供用户相关性反馈机制。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。分为简单接口和复杂接口。

当前，这方面研究集中在对用户信息需求的挖掘与发现、改进用户交互方式（信息可视化）等方面。总结：搜索引擎工作流程搜集累计式搜集，增量式搜集；索引重复网页消除；关键词提取；链接分析；倒排索引检索查询匹配；结果排序；文档摘要搜集索引检索从具体运行方式上说，系统根据站点/网页的URL信息和网页之间的链接关系，利用网络蜘蛛在互联网上收集数据；收集的数据分别通过链接信息分析器和文本信息分析器处理，保存在链接数据库和文本索引数据库中，同时，网页质量评估器依据网页的链接关系和页面结构特征对页面质量进行评估，并将评估的结果保存在索引数据库中；查询服务器负责与用户的交互，它根据用户的检索需求，从索引数据库中读取对应的索引，并综合考虑查询相关性与页面质量评估结果之间的关系，给出查询结果列表反馈给用户。4搜索引擎实例GOOGLE百度案例：google网址：Google是由美国斯坦福大学的两位博士生拉里·佩吉和谢尔盖·布林于1998年创建的。目前是全球最大、最专业的搜索引擎1998年,当时在加州门洛帕克(MenloPark),拉里·佩奇与谢尔盖·布林租用了这间房子的车库作为建立Google的据点,每个月Google要交$1,700(£961)租金给房东SusanWojcicki.2000年11月11日:Google的联合创始人,时任CEO的拉里·佩奇(LarryPage,左)和主席谢尔盖·布林(SergeyBrin)在位于山景城的Google总部内,靠着懒人椅(beanbags

)2006年5月10日:一名Google雇员踩着一架脚踏滑板车(所有员工均可使用),穿越位于加州山景城的公司园区.①检索范围②检索方式简单检索高级检索简单检索逻辑“与”：两词间加空格逻辑“或”：用“OR”表示逻辑“非”：两词间加“-”（“-”号前加空格）强制检索：双引号指定网域：site:指定文件类型：filetype:文件类型逻辑与功能逻辑非功能逻辑或功能强制检索指定网域指定文件类型③特色直达与检索词最相关的网页网址：

百度（Baidu）是目前全球最优秀的中文信息检索与传递技术供应商。中国所有提供搜索引擎的门户网站中，超过80%以上都由百度提供搜索引擎技术支持，现有客户包括新浪、搜狐（Chianren）、央视国际、腾讯等。案例：百度①检索范围②检索方式简单检索高级检索简单检索逻辑“与”：两词间加空格逻辑“或”：两词间加“|”（前后加空格）逻辑“非”：两词间加“-”（“-”号前加空格）强制检索：双引号指定网域：site:指定文件类型：filetype: