（电力电子与电力传动专业论文）中文搜索引擎的设计与实现.pdf

东华大学硕士论文 a b s t r a c t a b s t r a c t i t lr ty 钧璐，谢t ht h e 洲o p m e n ta n dm 0 ( 1 a m j z a 6 o fm eh l t 锄e t ，a n d 也e 锄唧 o fi o w c o s t 粤鼍p h i c a ll l s 盯i n t e r f a c e 趾dl a 唱争c 删t ys t o m g ed e 、，i c 嚣，血ef i e l do fi n f o 加1 a t i o n 训酬h a su n d l 田黜咖钮d o 鹏c h 锄g 鹤n o ec a n 觚饥m t e l yi m o wh o wm a n yp a g 器t h e 玳帆咄谢h i l e 嚣石m a t 嚣a s a y i n gt h a tt h e6 9 u c a na 【o d e d1 0b i u i o mt | om a l 【el l o ft h e h u g e 锄o i m to fd a t h eo n l yw a yi st ou s 锄cw e b 疵he n g i n 嚣t oa u t o m a t i c a n yo 喀a n i m e d a 饥 呦锄g i n 鹤i sm a d et o h 试他山eg o a lo fs t 0 i a g e ，盯g a 血刹伽锄da c o e 鹦o ft h e 耐- 彻n a t i i t c i 璐t t l e 们t w o i l l 蜥g i n 髓锄b c 髑e d 幻l o c ；吐eah u g e 删珊坷o f i n f 0 佃t i o n 埘曲眺弱w e l l 雒m e 血。帅i n f - 锄a t i c 姐b eq u i c 埘f 0 l m 正 1 1 1 t 锄e t 眦he n g i n ei sm ec c 瞪o fi n f 0 r m a t i o n 心懈e v a lt e d m o l o g y a tp l 姗t t h e 砌 锄g i i l 鼯m a ti sw i d e l y 删o nt h ei i i t 锄e t i n c l u d i n gt h ec h i n e a r c he n g i i l 圆，h 勰n ol e 鹞t h a n t 饥，s u i c h 鹪g o o g l e ，h e a do f t l l eg e m lp u 耳妁a r c h 衄g i i l e 锄d 谢o l 玛噼o f v 枷c a lw 曲 a r c ht o o l sb a do ni 珊如s 仃yc l 勰s i f i c a t i o n h o w e v e r m e 他a 砖s t i l lal o n gd i s t a n c eb 吐w e e nt h e c h i n e s 鲫油g i n e 姐di t ss i m i l 缸p r o d u c t sa b r o a 也s u c h 勰l o w v 啪g e ，t l 怆n o th i g h c o 柙t i o nm t e ，t h eb a d c u m c yo f 形t r i e 、m ，s l o wu p d a t i n g ，u m l b l et oc o n t l l i n gt h ed ) m a m i c 曲脚l g 锊o f 玳心触i n f 0 咖枷o n ，a n dd i 伍c u l i t ) ro nc o n 昀l 弛dm a n a 鼍r a n 锄to ft h e 啪t 既叱 b 戗：撇o ft l l 骼cp b l 锄，t h i sp a p 盯b 够e d c h i n 链e 砌a i 舀n ep i 礤；e 吣蛐e o p 石m 删咖咖g ) r 鲫也e 侧五酬。巧e c t 姐dt l l ed e s i 印o f i t s 咖g 咖硝t o l v e 吐坞l o w c 0 唰m t e a n d t l l e l o w 孤翻删p i 曲l 伽哆 t h i sa r t i d em a ：k 鹤a8 t u d y 叽t h eb 鸹i c 础t ：t l l r e 觚dt e c h o l o g yo fl h e 舒殂廿a l - p m p 嘴 鼬饥g i n e a n d g a v 鹤a 洲l e dd e s d 硼0 n 岫d 鹤i 弘m 蛐l o g ) r o f h 0 w t o 衄岫a 刚 c h 抵es e a r c h 钮舀鹏b 鹞e d s i r g j m1 1 i i sa r t i c l ee s p i a l l ym 璐缸锄瞄h 0 啊t o h i e 鸭l h e i n t 鲫a ld a 屯曲勰es y s 锄o f a a r c _ h 钮g i 地够w e u 勰s h o 讹gt h ei m p l 锄t sa n da l 鲥也：n 盥o f c 姻t c l o a n d s p r 丑n k 妇l o g ) ，w h i c h s i 咖h a s 勰i t s o w n 脚o r d 暑：鼬饥g i ，i n l 伽枷侧曲a l ，p a g es t r 删蛆蚋删咄坂：h n o l 0 醪 东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文， 是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已明确注 明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的 作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：剞漫 日期：t 炉8 年岁月1日 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。 本人授权东华大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本版权书。 本学位论文属于 不保密4 学位论文作者签名：叫盟 日期：如s 年；月旧 指导教师签名焉多寥睦 日期：2 汐驴宇车多旁驴日 东华大学硕士论文 l 概述 1 1 课题背景及意义 第1 章概述 信息的生产、传播、搜集与查询是人类最基本的活动之一。经历了大约4 0 0 0 年的时间，人们为了进一步地检索和利用信息，已经对信息进行了组织。典型的 例子是一本书的目录表。由于信息量的激增远远超过了几本书的范围，因此，建 立专门的数据结构，以确保已存储信息的快速存取变得十分重要。 经过了几个世纪的时间，人们把索引作为分类体系以手工方式建立起来。随 着时间的推移，现代计算机的出现使自动生成大型索引成为可能。 图书馆是最早采用计算机检索信息的公共机构之一。信息检索直到最近，一 直被认为主要由图书馆管理员和情报专家所关注的有限领域。在2 0 世纪9 0 年代 初，引入万维网这一事实彻底改变了这种看法。 w 曲正在成为人类知识和文明的全球储存库，这个存储库空前地允许在一个 史无前例的范围内实现思想和信息的共享。尽管如此，w 曲也带来了它自身的新 问题。在w 曲上找到有用信息的过程往往令人厌烦和困难。例如，为了满足自 己的信息需求，用户可以在w 曲链接的空间里检索感兴趣的信息。然而，这个 链接空间是巨大的并且几乎是不可知的，这样的检索效率通常很低。对于初级用 户来说，这个问题就更是艰难了，也许他们的全部努力都以失败而告终。其主要 障碍在于，信息的定义和结构的质量通常都很差，这些引发了人们对信息检索及 其技术的重新关注，信息检索几乎一夜之间占据了引人注目的位置。 如果我们考虑今天w 曲上的搜索引擎，就会得出这样的结论：这些搜索引 擎仍然在使用索引，而且这些索引与一百年前图书馆使用的索引很相似。那么， 有些什么变化呢? 由于现代计算机技术的进步和w 曲的迅速发展，有三个引人注目的主要变 化1 1 1 。首先，利用各类信息资源变得非常便宜，这样就允许较以前更多的用户进 行检索。第二，数字通信的进步使得利用网络的途径更多，这就是说，即使在较 远的位置，信息资源也是可以利用的。第三，自由发布任何人认为有用的信息， 大大的促进了w 曲的普及。 东华大学硕士论文l 概述 低成本、高存取和出版自由已经基本上可以让人们将w 曲作为一个现代的 数字图书馆来使用。然而，目前有三个主要问题已引起了人们的广泛关注。首先， 尽管实现了高度的交互，但是人们发现有时仍然很难检索到与他们的信息需求相 关的信息。第二，随着存取需求的快速增长，快速响应变得越来越紧迫。第三， 检索任务的质量在很大程度上受到用户与系统相互作用的影响。 中文搜索引擎在规模、收录内容、标引深度等方面均与国外同行有所差距， 其主要问题表现在以下几个方面【2 】。 用户界面不易准确表达用户的搜索意图。搜索引擎告诉用户有成百上千个符 合条件的链接，而要筛选出真正有用的资源却比较困难。 专题性的搜索引擎少。目前，国内搜索引擎中面向主题的寥寥无几。 现有的w 曲搜索引擎在检索功能方面存在一些缺陷。 搜索引擎中情报检索语言存在的问题。 在处理咨询时一，多数中文搜索引擎没有考虑到地域性。 部分搜索引擎的索引数据库更新不及时，搜索出来的信息有些已经过时，甚 至存在错误链接或“死链接 。 对网络信息检索效果的评价没有一个统一的标准。 搜索引擎的选择多根据经验进行初步选择，还没有形成一套固定的选择原则 和方法。 信息组织的局部有序性与整体无序性。 网上收集资料的经济条件、设备条件限制多，加之带宽和传输速度的限制， 用户要花大量的时间去等待，效率低下。 为了解决在搜索引擎发展中的诸多问题，多年来人们一直在研究新一代的搜 索引擎。其发展目标就是采用新兴的搜索技术为用户提供更方便易用、更精确的 搜索工具来满足用户的信息查询需要。 为此，本文在对现有系统的分析和相关理论与技术研究的基础上，提出了对 中文搜索引擎从系统检索对象和自身系统的设计结构进行优化等对策，尝试解决 其中的查准率和检索精度的问题，从而改进中文搜索引擎的检索质量。 2 东华大学硕士论文 l 概述 1 2 国内外发展现状 近年来，随着互联网的发展以及现代化、廉价的图形用户界面和大容量存储 设备的出现，信息检索领域已经发生了巨大的变化。在过去的2 0 年中，信息检 索领域已经得到发展和壮大，并且超越了它标引文本和在某一集合中检索出有用 文档的最初目标p 4 】。现在，有关信息检索的研究包括建模、文档分类和归类、 系统构建、用户界面、数据可视化、信息过滤和查询语言等。 w 曲上的搜索引擎利用h 珊l 文档间的链接关系，在w 曲上一个网页一个 网页地“爬取 ，将那些网页“抓回系统后进行分析处理。1 9 9 3 年m a t n l e wg l 可 开发了w 0 r l dw i d ew 曲e 册，它是第一个利用h t m l 网页之间的链接关系 来监测w 曲发展规模的“机器人一程序【卯。 现代搜索引擎的思路源于w 姐d e f c r ，不少人在m a 劬e wg r a y 工作的基础上 对它做了改进。1 9 9 4 年7 月，m i d l 础m a u l d i n 将j o l l i ll c a v i t t 的程序接入到其索 引程序中，创建了大家现在熟知的l y s ，成为第一个现代意义的搜索引擎。在 那之后，随着w 曲上信息的爆炸性增长，搜索引擎的应用价值也越来越高，不 断有更新、更强的搜索引擎系统的推出。特别引人注目的是g 0 0 百e ，虽然是个 姗姗来迟者，但是由于其采用了独特的p a g e r a l l l 【技术，使它很快后来居上，成 为当前全球最受欢迎的搜索引掣6 】。 在中国，对搜索引擎的研究起源于“中国教育科研网”一期工程中的子项目， 北京大学计算机系的项目组在1 9 9 7 年1 0 月在该网上推出了天网搜索1 o 的版本 【_ 丌。在这之后，几位在美国留学的华人学者回国创业，成立了百度公司，于2 0 0 0 年推出了“百度 商业搜索引擎，并一直处于国内的领先地位。 随着网上信息越来越多，单纯靠人工整理网站目录取得较高精度查询结果的 优势逐渐退化，对w 曲上的信息进行高质量的人工分类已经不太现实。目前有 两个发展方向。一是利用文本自动分类技术，在搜索引擎上提供对每篇网页的自 动分类。另一个发展方向是将自动网页爬取和一定的人工分类目录相结合，希望 形成一个既有高信息覆盖率，也有高查询准确性的服务。 国内现在从事搜索研究的人员主要在大学，也有部分在研究所或公司。目前 进行的大多数研究项目是由政府资助进行的，如国家自然科学基金、8 6 3 计划、 九五n 计划等。他们提出，为了提高中文搜索引擎的查询结果精度和检索的有效 3 东华大学硕士论文1 概述 性，并且解决查询结果过多的现象可以采用以下几种方案【引。 构建基于内容的搜索引擎。基于内容的搜索的比较成熟的解决方案是依靠语 义网络、汉语分词、句法分析、处理同义词等信息处理技术最大程度地了解 用户的信息需求。 将用户提问转化为系统已知的问题，然后对已知问题进行解答，以求降低对 自然语言理解技术的依赖性。 用正文分类技术将结果分类，使用可视化技术显示分类结构，用户可以只浏 览自己感兴趣的类别。 进行站点类聚或内容类聚，减少信息的总量。 让用户对返回结果进行选择，进行二次查询是一种非常有效的手段。 目前，互联网上信息量在不断增加，信息的种类也在不断增加。一个搜索引 擎要覆盖所有的网上信息查询需求已出现困难，因此各种主题搜索引擎、个性化 搜索引擎、问答式搜索引擎纷纷兴起。并且如今的搜索引擎存在搜索速度慢、死 链接太多、重复信息或不相关信息较多，难以满足人们的各种信息需求，搜索引 擎将向智能化、精确化、交叉语言检索、多媒体检索、专业化等适应不同用户需 求的方向发展。 总之，今后的搜索引擎将会更加方便利用，用户将有更多的选择，可以根据 需要扩大或缩小检索范围；有辅助检索土具，如主题词表，利用它进行交互式提 问；可以帮助用户选择检索表达式，确定检索范围；除了被动地接受用户的查询请 求外，搜索引擎也可以利用智能代理技术进行主动的信息检索；可根据用户事先 定义的信息检索要求，在网络上随时一监视信息源，如指定的网页、新闻组、电 子邮件、数据库信息的变化等，并将用户所需的信息通过p u s h 技术、电子邮件 或其他方式，主动提供给用户，用户无须反复地搜索所需信息，大大减少了用户 的检索时间【l o 1 1 ，1 矾。 1 3 课题的目标与主要工作 1 3 1 本课题的主要目标 在p a g e r 锄k 排序算法的基础上尝试给出改进算法，以实现对查询结果能够 4 东华大学硕士论文1 概述 有更好的评价与决策。 针对索引的网页，给出一种智能过滤算法，使得系统能够更好的从杂乱的网 页源文件中分辨出关键内容，从而提高系统对网页分析时的精度。 设计出一个优秀的文件系统来存放搜索引擎的数据，使得整个系统在应对外 部服务请求时能够更好、更快的相应。 实现一个完整的搜索引擎系统，以验证系统内各个算法与结构的有效性。 1 3 2 本课题的主要工作 聚焦研究问题，认真思考和定位课题所研究的问题。这样实质上是对准备研 究问题的反复思考过程。发现问题是研究的起点，“是什么，“为什么一与 “怎样做 从而实现聚焦研究问题，反复思考和完成课题。 在仔细研习传统信息检索理论的同时，发扬艰苦奋斗、吃苦耐劳精神，以科 学负责的态度，实现课题的论证、计划与实现方案的制定、资料收集和结题 等工作。 研究国内外的搜索引擎的知识体系、模型以及已经投入使用的成熟商用化的 产品，分析它们的理论研究现状及其存在的问题。 研究如何建立行之有效、精简、适合个人研究使用的搜索引擎系统，并提出 一套拥有自己风格的信息检索体系模型。 在课题研究方向指导下，制定出系统实现的具体步骤与模块化设计方案。 根据该搜索引擎体系的要求，研究哪些功能从传统的信息检索体系中直接套 用过来，以加快系统开发速度避免重复他人的劳动，从而将更多的精力投入 理论研究中。 通过对实现后的搜索引擎的实际使用，验证本课题提出的各类算法的有效 性。 1 3 3 创新之处 搜索引擎的设计问题本身就有很多挑战，而专业的搜索引擎无论是在网页源 数据分析和数据存储方面以及提交给用户前的排序评价都有自己的特殊要求。本 文的主要创新之处： 5 东华大学硕士论文l 概述 利用网页文件标签的特点，采用c a l s t c l o s e d 网页结构分析技术实现网页中无 用信息的过滤，比如广告信息和网页整体的视觉修饰信息。从而使得对网页 的文本分析可以更精确。同时利用该技术还可详细记录网页创建者对网页主 要内容的文字提示，使得标签信息成为对评价排序系统内文本相关性计算的 一个补充参数。 在p a g e r a n k 的基础上，根据以往研究的经验，提出了一种改进型的算法 s p r a n k 。该算法不仅利用了网页间相互引用的信息，同时利用模拟用户的浏 览习惯技术将用户的个人网页浏览偏好也融入了其中，从而实现了更精确的 对网页自身重要性的客观评价。 1 4 论文的章节安排 论文以作者自己设计的s i r g i n 全中文搜索引擎为基础，比较系统地介绍了互 联网搜索引擎的工作原理、实现技术及其系统构建方案。作者尝试向读者揭示， 为什么向搜索引擎输入一个关键词或者短语，就能够在秒钟内得到那么多相关的 文档及其摘要，而点击其中的链接就能够被引导到文档的全文，且其中相当一部 分可能正是用户需要的。 本文的内容围绕着如何从无到有实现一个完整的专业搜索引擎系统，并且将 搜索引擎的设计分解为一个三段式的流程，其中作为最主要的中间流程，文章又 根据中文搜索引擎特点，把中文网页的语法分析和搜索引擎原本所需的索引构筑 方式分解为两部分来叙述，具休安排如下： 第一章概要的介绍了本文的研究背景、研究思路、研究内容、创新之处和组 织结构。 第二章从理论上介绍搜索引擎的基本工作原理和它作为一种网络应用软件 的体系结构，在此基础上，给出了本搜索引擎s 迁g i n 的整体结构，并介绍了各个 模块的功能。 第三章作为搜索引擎的三段式设计流程中的第一部分，给出了s i 咖抓取网 络上网页的具体方式，并详细阐述了s i 啦是如何获取网络上的重要网页和避免 网页重复搜集的技术。 第四章作为中间流程的上半部分，详述了s i 咖系统对于抓取到本地的网页 6 东华大学硕士论文l 概述 源数据的处理方式，并详细的介绍了s i 哂n 的c a s t c l o s e d 网页结构分析技术是如 何来对网页进行滤波和标记网页内容结构的，最后还介绍了后半部分设计方式所 需要涉及的基础理论知识。 第五章作为中间流程的下半部分，以s i 咖的w 曲服务检索系统为基础， 分析和介绍了s i 咖在索引创建、文件结构上的理论规范，以及为确保高效性所 采取的设计与实现技术。 第六章主要介绍s i 哂n 三段式工作流程的最后环节查询服务。首先给出 了s i 咖查询服务系统结构，然后给出了s p r 锄k 排序评价算法，最后结合s 姆n 给出查询服务的具体实现。 7 东华大学硕士论文 2 搜索引擎的工作原理及s i 唱i n 的体系结构设计 第2 章搜索引擎的工作原理及s i r g i n 的体 系结构设计 2 1 搜索引擎的基本概念 对信息的有效检索直接受到两个因素的影响：用户任务和检索系统对文档所 采用的逻辑观点1 6 1 。 2 1 1 用户任务 检索系统的用户不得不将他们的信息需求转换成系统提供的语言进行查询。 对于检索系统来说，这通常意味着指定符合信息需求语义的一组词。从用户的角 度来看，这个过程可以看作信息的检索和浏览，见图1 。经典的检索系统通常允 许对信息进行检索，而w 曲上的超文本系统通常能够提供快速浏览，搜索引擎 则尝试将这些任务结合起来，提供完善的检索能力。 图l 执行任务的用户和检索系统的相互作用 在w 曲的语言中，用户的检索和浏览都属于提取行为，也就是说，用户以 某种交互的方式请求信息。不过目前也有另一种趋势，就是检索系统以自动持久 的方式在网络上进行检索，然后过滤出用户所需要的信息，然后提交给用户，这 就属于推送的方式【1 7 1 。这种方式对时时刻刻都在发生变化的网络来说，是一个 非常好的方式，也许将来会成为主流。 8 东华大学硕士论文 2 搜索引擎的工作原理及s i r g i n 的体系结构设计 2 1 2 文档逻辑 由于历史的原因，人们常常通过一组标引词或关键词来表示集合中的文档。 这种关键词可以是从文档的文本中直接提取出来的，也可以是人的主观指定的。 但是不管这些有代表性的关键词是如何产生的，它们都提供了文档的逻辑视图。 现代计算机能够使采用完整的词集合表示文档内容变为可能。在这种情况 下，我们说检索系统采用了文档的全文本逻辑视图。然而，对于大规模的集合来 说，即使是现代最先进的计算机也不得不减少有代表性的关键词的集合。中文中， 一般通过排除的、地、得等助词可以实现关键词集合的减少。同时，也 许还会同时使用压缩技术。 显然，全文本是最完整的文档逻辑视图，但是它的使用通常要付出较高的运 算代价。如图2 所示，信息检索系统也许采用几种中间级的逻辑视图。除了采用 任何中间级表示外，检索系统也能区分出某个文档中通常表示的内部结构，比如 段、节等。 全文本标引词 图2 文档得逻辑视图：从全文到一组标引词 如图2 所示，我们将某一文档得逻辑表示成一个连续统一体，在这个连续统 一体中，文档的逻辑视图从全文表示转换成由人的主观指定更高水平的表示。 2 2 基本要求 基于w 曲的搜索引擎是一个网络应用软件，对它有如下要求基本要求【1 9 1 。 能够接受用户通过浏览器提交的查询词或者短语。 9 东华人学硕上论文2 搜索i ；i 擎的工作原理及s i 喀i n 的体系结构设计 在一个可接受的时间内返回一个和该用户查询匹配的网页信息列表。 可接受的时间，也就是响应时间。对于在w 曲上向广大用户提供服务的软 件来说，这个时间不能太长，通常也就在秒这个数量级。这是衡量搜索引擎 可用性的一个基本指标，也是和传统信息检索系统的一个差别。更进一步的，这 样的响应时间要求不仅要能满足单个用户查询，而且要能在系统设计负载的情况 下满足所有的用户。 “匹配”，指的是网页中包含有用户查询词或者短语的信息，最常见的就是 网页中直接包含有这些词或者短语。不过，从后面的论述可以看出，如果一个搜 索引擎以百分之百满足这种简单的包含关系为目标，即使实现了也不能达到最好 的效果。 “列表，这蕴含着某种排序方式。在绝大多数的情况下，这个列表是相当 长的。这不仅是由于w 曲上信息量大，也是由于搜索引擎的查询方式简单所造 成的。对于一个长长的列表，几乎没有用户有耐心都审视一遍，所以如何提供用 户一个有效而简短的列表就是未来要研究的方向之一。 2 3 工作流程 现代大规模高质量搜索引擎一般采用如图3 所示的称之为三段式的工作流 程，即：网页搜索、预处理和查询服纠2 1 1 。 图3 搜索引擎三段式工作流程 2 3 1 网页搜集 搜索引擎这样一个软件系统操作的数据不仅包括内容不可预测的用户查询， 还要包括在数量上动态变化的海量网页，并且这些网页不会主动送到系统来，而 是要由系统去抓取。 首先要考虑的是抓取的时机。我们都有经验，在网络比较畅通的情况下，从 网上下载一篇网页大约需要1 秒钟左右，因此如果在用户查询的时候即时去抓取 成千上万的网页，一个个的分析处理，再和用户的查询进行匹配，这是不可能满 l o 东华大学硕士论文 2 搜索引擎的工作原理及s i 唱i n 的体系结构设计 足搜索引擎的响应时间要求。面对大量的用户，无法想象每来一次查询，系统就 上网搜索一次。 由此，可以看到，大规模搜索引擎服务的基础是应该是一批预先搜集好的网 页f 2 2 ，2 3 矧。但是为了保证数据的新的程度，还必须建立一套系统网页数据库 的维护策略。可以有两种基本的考虑。 定期搜索，每次搜集替换上一次的内容，我们称之为“批量搜集 。由于每 次都是重新来一次，对于大规模的搜索引擎来说，每次搜集的时间通常会花几周。 而由于这样做的开销较大，一般两次搜集的时间间隔不会很短。但是这样做的好 处是系统实现简单，主要缺点是“时新性不高，还有重复搜集所带来的额外带 宽消耗。 增量搜集，这是指开始时搜集一批，往后只是：搜集新出现的网页；搜 集那些在上次搜集后有过改变的网页；发现自从上次搜集后已经不再存在了的 网页，并从库中删除。除了新闻类的网站外，一般的网站内容变化并不是很经常 的，这样做每次搜集的网页量不会很大，于是就可以经常启动搜索过程。这样的 系统表现出的时新性就会比较高，但是主要缺点是系统实现复杂【2 7 1 。这个复杂 不仅仅指搜集的过程，而且在于后面要谈到的建立数据索引的过程。 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见 的是一种爬取行为：将w 曲上的网页集合看成是一个有向图，搜集过程从给定 起始i j l 地集合s 开始，沿着网页中的链接，按照先深、先宽或者某种别的策略 遍历，不停的从s 中移除u 也，下载相应的网页，解析出网页中的超连接i j l 甩， 看是否已经被访问过，从未访问过的那些i j i 也加入集合s 。整个过程就犹如一 个蜘蛛在蛛网上爬行。另外一种可用的方式是在第一次全面的网页搜集后，系统 维护相应的u r l 集合s ，以后的搜索直接基于这个集合。每搜集到一个网页， 如果它含有了新的也，则将其对应的网页抓回来，并将这些切甩加入集合s ； 如果s 中切虬对应的网页已经失效，则将它从s 中删除。还有一种方法是让网 站拥有者主动向搜索引擎提交他们的网址。系统然后向这些网站派出蜘蛛程序， 扫描这些网站并将其信息加入数据库【3 0 1 。 东华大学硕士论文2 搜索引擎的工作原理及s i 唱i n 的体系结构设计 2 3 2 预处理 得到原始网页的集合后，离面向网络用户的检索服务之间还有相当的距离。 一个合适的数据结构是查询子系统工作的核心和关键。目前，最有效的数据结构 是“倒排文件 ；倒排文件是用文档中所含有的关键词作为索引，文档作为索引 目标的一种结构。预处理就是指处理从网页集合到这样的倒排文件的过程中几个 主要问题。其大致包括四个方面：关键词的提取，内容相同的网页的消除，链接 分析和网页重要程度的计算。 随便取一篇网页的源文件除了我们从浏览器中能够看到的正常文字内容 外，还有大量的h t m l 标记。另外，由于h t m l 文档来源的多样性，许多网页 上的内容比较随意，不仅文字不讲究规范、完整，而且还可能包含许多和主要内 容无关的信息。这些情况给有效的信息查询带来的挑战，在文章后面还有进一步 论述。这里指出，为了支持后面的查询服务，需要从网页源文件中的提取出能够 代表它内容的一些特征。于是，作为预处理阶段的一个基本任务，就是要提取出 网页源文件的内容部分包含的关键词。 与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便 利，因此可以看到w 曲上的信息存在大量的重复现象。这种现象对于广大的用 户来说是有正面意义的，但对于搜索引擎来说，则主要是负面的，它不仅会在搜 集过程中消耗机器时间和网络带宽资源，而且在查询结果显示中容易引起用户的 抱怨。因此，消除内容重复的网页是预处理阶段的一个重要任务。 前面提到，大量的h t m l 标记给网页的预处理带来了一些麻烦。从信息检 索的角度来看，如果系统面对的仅仅是内容的文字表述，我们所能依据的只有“共 有词汇假设 ，即内容所包含的关键词集合，最多再加上词频和词再文档集合中 出现的频率之类的统计量。不过有了m m l 标记后，情况则有可能改善，例如， 在同一篇文档中， 和 之间的信息就可能比 和 之间的信息重 要。h t m l 文档中包含的指向其它文档的链接信息不仅给出了网页之间的关系， 而且还对判断网页内容有重要的作用。 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的 顺序是很重要的一个问题。显然对同样的查询返回同样的结果并不能使得所有人 都满意，因此搜索引擎实际上追求的是一种统计意义上的满意。如何对查询结果 1 2 东华大学硕士论文 2 搜索引擎的工作原理及s i 哂n 的体系结构设计 进行排序有很多因素需要考虑。顾名思义，既然在预处理阶段形成的，就是和用 户查询无关的。一般认为，被引用多的就是重要的。“引用这个概念可以通过 h t m l 的超连接很好的体现。网页和网页存在着一种相互链接的对偶关系，这种 关系让人们可以在网页上建立一些重要性指标。这些指标有的可以在预处理阶段 计算，有的则要在查询阶段计算，但都只是作为在查询服务阶段最终形成结果排 序的参数。 2 3 3 查询服务 用户通过搜索引擎看到的应该是一个“列表 ，一个包含查询结果的已经排 序过了的列表。如何从系统数据库种的集合生成一个列表，是服务子系统的主要 工作。从搜索引擎系统功能划分的角度，有时候将倒排文件的生成也作为服务子 系统的一部分功能，但将它划分到预处理阶段更方便些。一般主要从三方面来看 待服务子系统：查询方式和匹配、结果排序和文档摘要。 查询方式指的是系统允许用户提交查询的形式。考虑到不同用户的不同背景 和不同需求，不可能有一种普遍适用的方式。一般认为，对于普通网络用户来说， 最自然的方式就是需要什么就输入什么。但也有其它一些情况下，用户关心的可 能是间接信息。尽管如此，用一个词或者短语来直接表达信息需求，希望网页中 含有该词或者短语中的词，依然是主流的搜索引擎查询模式。在设计搜索引擎的 中，我们默认这样一个基本假设：用户是希望网页包含所输入的查询文字的。 在得到了用户查询相关的文档集合后，这个集合中的元素需要以一定的形式 通过计算机显示屏呈现给用户。就目前的技术来看，列表是最常见的形式。给定 一个查询结果集合r ，所谓列表，就是按照某种评价方式，确定出r 中元素的一 个顺序，让这些元素以这种顺序呈现出来。但是，有效的定义一种评价方式是很 困难的，从原理上讲它不仅和查询的词有关，而且还和用户的背景以及用户的查 询历史有关。不同需求的用户可能输入同一个查询，即使是同一个用户，在不同 地点不同时间输入相同的查询可能也是针对不同的需求。在搜索引擎研究的早 期，人们采用了传统信息检索领域很成熟的基于词频的方法。然而，由于网页编 写的自发性、随意性较强，仅仅针对词的出现来决定文档的顺序，在w 曲上做 就会表现出明显的缺陷，需要有其它技术来做补充。一般我们通过预处理阶段为 1 3 东华大学硕士论文2 搜索引擎的工作原理及s i 画n 的体系结构设计 每篇网页形成一个独立于查询词的重要性指标，将它和查询过程中形成的相关性 指标结合形成一个最终的排序。 搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元 素：标题、网址和摘要。其中，摘要需要从网页正文中生成。 2 4s i r g i n 的体系结构设计 在上述工作原理的基础上，作为一个网络应用软件，本文给出了一个中文搜 索引擎s i 咖的体系结构，如图4 所示，这样的结构是完全符合前面图3 所指出 的三段式的工作流程的，使得s i 姆n 具有良好的规范性和可扩展性，另外s 迎面 的这个结构在搜索引引擎的设计中是通用的，任何类型的搜索引擎都可以给予这 个结构来设计。 图4 搜索引擎的体系机构 图中，搜集器完成网页搜集的工作，这部分将搜集到的网页存放到原始网页 库。搜集器和原始网页库就构成了整个搜索引擎的前端搜集部分。 接着由索引器来完成一系列的预处理工作，比如对中文中的信息进行虑除处 理，将网页上的无用信息比如代码注释以及广告等去除，然后将网页索引入库。 搜索过程要保证每个网页不被重复抓取。由于一篇网页可能被多个网页链接，如 果不加以检查和控制，网页就会被多次抓取。如果遇到循环链接，还可能将系统 馅死。而历史日志分析器就是要解决这个问题，它将每次抓取的网页链接地址作 个记录，以防止被重复抓取。索引器、历史日志分析器和索引数据库就构成了整 1 4 东华大学硕士论文 2 搜索引擎的工作原理及s i 晒n 的体系结构设计 个搜索引擎的中端的对整个数据进行预处理。 余下的部分是整个搜索引擎后端的查询服务部分，其中检索器和用户接口则 负责处理面向用户的服务，检索器将匹配数据从数据库中取出，进行处理后派发 给用户接口，排序后递交给用户查询结果。而用户的日志用来记录用户的查询行 为，以及减少系统开销。 2 5 本章小结 本章介绍了搜索引擎的基本工作原理和它作为一种网络应用软件在具体实 现上的体系结构。在后面的几章中，将以s i 晒n 搜索引擎这样一个实际的例子， 具体展开在这些原理基础上实现的一种方案。 东华大学硕上论文3s i 画n 的w 曲信息的搜集方式 第3 章s i r g i n 的w e b 信息的搜集方式 从前面的论述中，我们知道搜索引擎一般采用三段式的工作流程，即：网页 搜集，预处理和查询服务。这里将着重介绍s i r g i n 是如何从网络中获取网页资源 的。 3 1 网页搜集 超文本传输协议简称h 1 f r r p ，它是w e b 的基础协议【3 l j 。h t r p 是一个简单的协 议。客户进程建立一条同服务器进程的t c p 连接，然后发出请求并读取服务器进 程的应答。服务器进程关闭连接表示本次响应结束。服务器进程返回的内容包含 两个部分，一个“应答头”，一个“应答体”，后者通常是一个h t m l 文件，我们称 之为“网页”。 s 迅面利用h t t p 协议与w e b 上的网站进行通信。其基本流程见图5 。这部分 是整个系统最初开始的地方。搜集程序一开始是从一个初始的u r l 集合开始进行 网络搜索的，因为一开始的时候是没有任何l 刀乇l 数据信息的。这个集合可以通过 人为的输入来获得。i j l 甩派发控制器监视各个网络蜘蛛的工作状态，当有蜘蛛空 闲时，它就将l 刀王l 地址派发给空闲的蜘蛛。而蜘蛛则把搜集到的网页存放在一个 叫做网页池的地方。系统的其它分析子程序则通过这个网页池来获得网络上的信 息。图5 中新u 江的数据是来自u i u 链接提取程序。这部分子程序需要从网页中 分离出可用的u i u 以保证当初始的也库枯竭后，u 也派发器仍然能得到切地 链接。 1 6 东华大学硕士论文 3s i r g i n 的w 曲信息的搜集方式 图5 网页搜集的基本流程 大规模的搜索引擎每天需要搜索上百万的网页，而且是持续进行的，我们就 必须要考虑是如何利用尽量少的资源来完成预定的网页搜集量。s i r g i j l 作为个人 p c 端的搜索引擎，由于条件限制无法实现多台计算机同时来做一项工作，但是即 使是用一台计算机来搜集网页，也应该注意并发性的开发和利用。s i r g i i l 同时启 动多个抓取线程，利用操作系统提供的异步通信机制，让多个网络通信时间重叠 起来。应该指出，并不是计算机设备越多越好。在用若干台计算机形成一个机群 的安排下，它们共同分享出口网络带宽，随着设备量的增加，这个网络带宽很快 就成为瓶颈。 在用蜘蛛访问网站时还要注意一个情况。这个情况发生在网络的另一端，即 服务器方，它可能来不及提供所需的网页。技术上，就是要有一个访问策略或者 也规划，不要让搜集器启动的抓取进程都集中在少数几个网站上。这个规划需 要在图5 的u r l 派发控制器来完成。还需要注意，将搜集活动的关注过分集中在 几个网站上，或者在一小段时间里从一个网站抓取太多的网页还可能引起其他的 严重后果。不加控制的网页抓取，给网站造成的现象有时候和制造拒绝服务攻击 的黑客造成的现象一样，因为管理良好的网站常常会有一个监视器运行，监视是 否有来源于单个p 地址的过分密集的访问。一旦出现这种情况，要么会通告该m 地址的拥有者注意行为，或者会干脆屏蔽来自它的访问，更有甚者，还可能在网 上公布该口地址作为黑名单。因此，适当地规划网页的抓取，限制单位时间内对 一个网站抓取网页的数量，是大规模搜索引擎必须要认真对待的问题。 网页搜集过程中还有一个基本的问题是要保证每个网页不被重复抓取。由于 1 7 东华人学硕士论文 3s i 喀i n 的w 曲信息的搜集方式 一篇网页可能被多篇网页链接，在蜘蛛爬取过程中就可能多次得到该网页的 u 江。于是如果不加检查和控制，网页就会被多次抓取。遇到循环链接的情况， 还会使爬取器陷死。 3 2 多道搜集线程并行工作 通常情况下局域网的延迟在l - 1 0 m s ，带宽为l o 一1 0 0 0 m b p s ，i n t e n l e t 的延迟在 1 0 0 5 0 0 m s ，带宽为0 0 1 0 2m b p s 3 2 1 。s i 哂n 利用一台机器同时启动多个蜘蛛并发 的创建多个t c p 连接，并发的下载网页。这种方式加快了w e b 信息的搜集，但是 要避免由于同一时间内与同一服务器连接过多而给服务器端造成的严重性能问 题。 图6s i 哂n 避免对服务器造成攻击的策略 为了克服这个问题，s i 咖利用了一种循环采集的方式，以避免对同一服务 器造成性能负担。其具体方式见图6 。系统在u u 派发控制器内部维护一张n 长度的u i 也的域名列表。当每次有新的切 也进来后，由检测器先检查这个切 u 的域名是否已经在域名列表内，如果不在表中，则说明系统已经有一段时间没有 去访问那个网站了，那么检测器就会把这个域名添加进列表的尾部，将表内最早 的记录给剔除。如果u i 也的域名已经在列表内，那么说明系统刚刚访问过这个 网站，检测器就把这个也暂时存放到u i 也缓存中。i j l 也缓存也是采用与域 名列表相同的先进先出的软件结构。s 堍i n 中，也派发控制器会优先从l 丌地 缓存中提取切也链接，只有当u 】 u 缓存为空，或者与域名列表冲突时才会去读 取u 库。 1 8 东华大学硕士论文 3s i 唱i n 的w 曲信息的搜集方式 3 3 避免网页重复搜集 重复搜集，是指物理上存在的一个网页，在没有更新的前提下，被搜集程序 重复访问。造成重复搜集的原因，一方面是搜集程序没有清楚记录已经访问过的 u 也，另一方面是由于域名与p 多重对应关系造成的。 第一种情况可以通过记录已访问的u r l ，然后每次对新到的u r l 进行与以访 问u i 也中的记录进行比较即可。第二尝情况比较复杂。因为不同的u r l ，可能指 历书 向同一个p 地址，这就导致重复搜集。弋 域名与m 的对应关系存在4 种情况：一对一，一对多，多对一，多对多。一 对一不会造成重复搜集，后三种情况都有可能造成重复搜集。 为解决这个问题s 垤m 采用保存三张表的策略，一张保存已经访问过的i j i 也 表，一张保存已经访问过了的p 地址表，另外一张就是待判定的也连接。s 迎通 把两张“已访问表 的内容分别作m d 5 摘要，获得其唯一标识。待定的u i 也卜 根据已经访问过的两张表的加5 集合判断是否已经抓取过。这种方法可以在查 找的时候做到o ( 1 ) 的时间复杂度。 3 4 利用蜘蛛搜集重要网页 w e b 上的信息具有异质性和动态性，由于受时间和存储空间的限制，即使是 最大的搜索引擎也不可能将全球所有的网页全部搜集过来，一个好的搜集策略是 优先搜集重要的网页，以便能够在最短的时间内把最重要的网页抓取过来。在此 要求下，要优先搜集重要的网页。 蜘蛛作为一种从网络上获取网页的程序，如今已经被搜索引擎和网络缓存设 备广泛的使用了，但是如何设计出一种好的蜘蛛，则是一项富有挑战性的工作。 从表面上看，蜘蛛必须在它处理自己工作的过程中避免重复的登陆某一网站或者 某个相同的链接。而其自身同时还要处理大量的数据。蜘蛛必须要能够小心翼翼 地处理蚬u 链接，以使其能够从浩瀚地w e b 上获取最有用地数据。 网络上的网页就象一个深不见底的海洋。即使网络蜘蛛可以忽略计算机资源 并无限时间的工作下去，也不可能抓取到所有的网页，于是我们的目的就变成了 尽可能抓取多而且重要的网页。基于这个思想，s i 咖使用了基于p a g 姝锄k 方式 1 9 东华大学硕士论文 3s i 啦的w 曲信息的搜集方式 并加以改进的一种网页重要性排序策略，称作s p r a n k 方式。s 姆n 的蜘蛛利用 s p r a n k 结果来获得更好得爬取结果。 s i 哂n 有这么一个假设，w e b 上的所有网页对于网络蜘蛛来说并不都是它感 兴趣的。举例来说，如果网络蜘蛛想搜集关于“时尚”的信息，那么那些与时尚 主题相关的网页就显得十分重要，就应该被优先抓取。同样的，s i 哂n 把蜘蛛设 定为对“网络评价度感兴趣。所以那些“网络评价度”高的网页则会被优先获 取。“网络评价度”是s i 哂n 对其已知网页的一个重要性评价。 网页的“重要度”，目前还是一个值得研究探讨的问题。一般的，可以认为它 具有以下四种特征【3 5 】。1 ：网页的入度大，表明被其他网页引用的次数多；2 ： 某网页的父网页入度大；3 ：网页的镜像度高，说明网页内容比较热门，从而显 得重要；4 ：网页的目录深度小，易于用户浏览到。 s i 啦的蜘蛛优先搜集从“网络评价度 高的网页引出的链接。然后采用公 式( 1 ) 重新计算“网络评价度。 s p r a n l ( i + 1 = s p r a n k ( s i + s n ) ( 1 ) 其中s p r a l l k i 是指在获得新的网页后的新网页集合的“网络评价度 。 s p 是计算“网络评价度”的公式。s i 和s n 分别表示i 状态的网页集合和新 获得的网页集合。新获得的网页集合是指高于平均重要度的网页引出的链接网 页，只有这部分网页会被s i 哂n 的蜘蛛抓取。 需要指出的是，搜索引擎开始工作时，既不知道要访问的网页u l 也被哪些其他 网页指向，也不知道网页内容是什么，所以对于表征网页重要性的第l 、2 、3 项特征在搜集工作开始时无法确定。这些因素只能在获得网页或几乎所有的w 曲 链接结构之后才