毕业设计论文 搜索引擎

目 录 第一章 课题背景知识 . (1) 第一节 搜索引擎原理 . (1) 第二节 搜索引擎分类 . (2) 第三节 搜索引擎技术的发展历史 . (4) 第四节 搜索引擎现状 . (5) 第五节 搜索引擎展望 . (6) 第二章 技术诠释 . (10) 第一节 HTTP 及 HTML . (10) 第二节 网络蜘蛛 . (11) 第三节 网页噪声 . (13) 第四节 页面分析 . (13) 第五节 中文分词 . (16) 第六节 布尔 代数 . (19) 第七节 CGI. (19) 第八节 SOCKECT 网络编程 . (20) 第三章 TOKING 海量网页搜索系统体系结构 及实现 . (21) 第一节 结构设计 . (21) 第二节 数据流图 . (22) 第三节 网页抓取部分 . (31) 第四节 网页预处理部分 . (35) 第五节 信息查询服务部分 . (42) 第六节 用户反馈 . (46) 第七节 功能拓展 . (46) 第八节 优化用户感受 . (50) 第四章 系统测评 . (52) 第一节 抓取速度 . (52) 第二节 分词效率 . (52) 第三节 搜索评价 . (53) 参考文献 . (54) 致 谢 . (55) 附 录 . (56) 本科生毕业设计 1 第一章 课题背景知识 70 年代中期，美国国防部高级研究计划局 DARPA (Defense Advanced Research Projects Agency)开始了互联网技术的研究。而 WWW (World Wide Web)自 1989 年诞生以来，近二十年来发展迅猛，它已成为人类社会信息资源中的一个重要组成部分，越来越多的社会信息资源实体开始选择 Web 作为其载体。 著名的 netcraft(via Digg)刚刚完成了最新的互联网调查，结果显示到 2006 年 3月 31 日止，互联网上一共有 80655993 个网站。而单是在 06 年 3 月这一个月里，世界上的网站数量就增长了 310 万个。而在 2003 年 8 月所得的调查结果为 4000 万个，这说明了互联网上的网 站数量在过去的 3 年里就已经翻了一番，增长速度 十分 惊人。著名的网站排名的国际网站 在 2007 年 4 月更是收录了全球大约有34762836735 个网址。 由此，人们在信息海洋中搜索自己所需要的信息的能力显得愈发重要，搜索引擎成了人们在网上检索信息的必要工具。 第一节 搜索引擎原理 搜索引擎， 应该被定位成 一个计算机应用软件系统，或者一个网络应用软件系统。从网络用户的角度看，它根据用户提交的类自然语言查询词或者短语 ，返回一系列很可能与该查询相关的网页信息，供用户进一步判断和选取。为了有效地做到这一点，它大致上被分成三个子系统；即网页搜集，网页预处理和查询服务。 网页搜集主要负责网页的抓取，由 URL 服务器、爬行器、存储器、分析器和URL 解析器组成 ， 爬行器是该部分的核心；网页 预处理 主要负责对网页内容进行分析，对文档进行标引并存储到数据库里，由标引器和分类器组成，该模块涉及许多文件和数据，有关于桶的操作是该部分的核心； 查询服务 主要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级别评定器组 成，其中网页等级的计算是该部分的核心。 搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间自动启动并读取网页 URL服务器上的 URL列表，按深度优先或广度优先算法，抓取各 URL所指定的网站，将抓取的网页分配一个唯一文档，存入文档数据库。并将当前页上的所的超连接存入到 URL服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页文档进行切词处理，并按词在网页中出现的位置和频率计算权值，然后将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样用户就可以查询最新 的网页信息。查询器首先对用户输入的信息本科生毕业设计 2 进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对查询记录进行排序并进行集合运算，最后从文档数据库中提取各网页的摘要信息反馈给查询用户。 U R L 服务器 爬行器 存储服务器 资源库 页级别评定器 U R L 解析器 标引器 查询器 分类器 锚库 词典库 索引库 链接库 桶 桶 桶 桶 桶 桶 Web页搜索标引入库用户查询图 1-1-1 搜索引擎通用总体系统结构图 第二节 搜索引擎分类 搜索引擎按其工作方式主要可分为三种，分别是全文搜索引擎（ Full Text Search Engine）、目录索引类搜索引擎（ Search Index/Directory）和元搜索引擎（ Meta Search Engine）。 一、 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有 Google、Fast/AllTheWeb、 AltaVista、 Inktomi、 Teoma、 WiseNut 等，国内著名的有百度（ Baidu）。它们都是通过从互联网上提取的各个网站的信息（以网页文字为主）而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列顺序将结果返回给用户，因此他们是真正的搜索引擎。 本科生毕业设计 3 图 1-2-1 全球著名全文搜索引擎 LOGO 二、 目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词（ Keywords）查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表性的莫过于大名鼎鼎的Yahoo 雅虎。其他著名的还有 Open Directory Project（ DMOZ）、 LookSmart、 About等。国内的搜狐、新浪、网易搜索也都属于这一类。 图 1-2-2 全球著名目录索引 LOGO 三、 元搜索引擎 (META Search Engine) 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并将结果返回给用户。著名的元搜索引擎有 InfoSpace、 Dogpile、 Vivisimo 等，中文元搜索引擎 中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接按来源引擎排列搜索结果，如 Dogpile，有的则按自定的规则将结果重新排列组合，如 Vivisimo。 四、 其他 除上述三大类引擎外，还有以下几种非主流形式： （一） 集合式搜索引擎：如 HotBot 在 2002 年底推出的引擎。该引擎类似 META搜索引擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的 4 个引擎当中选择，因此叫它 “集合式 ”搜索引擎更确切些。 （二） 门户搜索引擎：如 AOL Search、 MSN Search 等虽然提供搜索服务，但自身即没 有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 （三） 免费链接列表（ Free For All Links，简称 FFA）：这类网站一般只简单地滚动排列链接条目，少部分有简单的分类目录，不过规模比起 Yahoo 等目录索引来要小得多。 （四） 垂直搜索引擎： 有针对性的搜索引擎。 一次搜索的结果可能有成千上万条，而在这过于庞大的信息群中，有用信息只是其中的小部分。通用搜索引擎的弊端在网络信息的急剧膨胀下突显起来，搜索越来越难以控制，用户需求和市场服务间的巨大反差产生了强大的 “搜索噪音 ”，垂直搜索引擎的应运而生， 成为搜索引擎本科生毕业设计 4 发展史上的一块里程碑。 第三节 搜索引擎技术的发展历史 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大众信息检索需求的专业搜索网站便应运而生了。 现代意义上的搜索引擎的祖先，是 1990 年由蒙特利尔大学学生 Alan Emtage 发明的 Archie。虽然当时 World Wide Web 还未出现，但网络中文件传输还是相当频繁的，而且由于大量的文件散布在各个分散的 FTP 主机中，查询起来非常不便，因此Alan Emtage 想到了开发一个可以以文件名查找文件的系统，于是便有了 Archie。 Archie 工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于 Archie 深受用户欢迎，受其启发，美国内华达 System Computing Services 大学于 1993 年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外，已能检索网页。 当时， “机器人 ”一词在编程者中十分流行。电脑 “机器人 ”（ Computer Robot）是指某个能以人类无法 达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的 “机器人 ”程序象蜘蛛一样在网络间爬来爬去，因此，搜索引擎的 “机器人 ”程序 也 被称为 “蜘蛛 ”程序。 世界上第一个用于监测互联网发展规模的 “机器人 ”程序是 Matthew Gray开发的World wide Web Wanderer。刚开始它只用来统计互联网上的服务器数量，后来则发展为能够检索网站域名。 与 Wanderer相对应， Martin Koster 于 1993 年 10月创建了 ALIWEB，它是 Archie的 HTTP 版本。 ALIWEB 不使用 “机器人 ”程序，而是靠网站主动提交信息来建立自己的链接索引，类似于现在我们熟知的 Yahoo。 随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因此，在 Matthew Gray 的 Wanderer 基础上，一些编程者将传统的 “蜘蛛 ”程序工作原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟踪一个网站的链接开始，就有可能检索整个互联网。到 1993 年底，一些基于此原理的搜索引擎开始纷纷涌现，其中以 JumpStation、 The World Wide Web Worm（ Goto 的前身，也就是 今天 Overture），和 Repository-Based Software Engineering (RBSE) spider最负盛名。 本科生毕业设计 5 然而 JumpStation 和 WWW Worm 只是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果，因此毫无信息关联度可言。而 RBSE 是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。 最早现代意义上的搜索引擎出现于 1994 年 7 月。当时 Michael Mauldin 将 John Leavitt 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的 Lycos。同年 4 月，斯坦福（ Stanford）大学的两名博士生， David Filo 和美籍华人杨致远（ Gerry Yang）共同创办了超级目录索引 Yahoo，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其检索的信息量也与从前不可同日而语。比如 Yahoo 号称收录的网页达到 200 亿 。 随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应目前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索引擎技术和搜索数据库服务提供商。象国外的 Inktomi（已被 Yahoo 收购），它本身并不是直接面向用户的搜索引擎，但 像 包括 Overture（原 GoTo，已被 Yahoo 收购）、LookSmart、 MSN、 HotBot 等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类，搜狐和新浪用的就是它的技术。因此从这个意义上说，它们是搜索引擎的搜索引擎。 第四节 搜索引擎现状 随着网 络信息 内容的爆炸式增长和形式的不断翻新，搜索引擎越来越不能满足网络使用者 的各种信息需求。从 1996 年起，搜索引擎技术开始注重网页质量与相关性的结合，这主要是通过三种手段： 是对网上的超链结构进行分析，如 INFOSEEK 和 GOOGLE； 是对用户的点击行为进行分析，如 DIRECTHIT(被 ASK JEEVES 收购 )； 是与网站目录相结合。最新的趋势则是搜索的个性化 、 本地化 和垂直化 。 个性化：入门网站的个性化已经比较成熟了，但是搜索引擎的个性化并没有得到解决，不同的人使用相同的检索词得到的结果是相同的。也就是说搜索引擎没有考虑人的地域、性别、年龄等方面的差别。 DIRECTHIT 等公司一年 前开始了个性化方面的研发工作，但至今没有推出任何产品。 垂直化：垂直搜索引擎这种高度目标化、专业化的搜索引擎的优势在于 :针对性强，对特定范围的网络信息的覆盖率相对较高，具有可靠的技术和信息资源保障，有明确的检索目标定位，有效地弥补了通用综合性搜索引擎对专门领域及特定主题信息覆盖率过低的问题。根据 CNNIC 的调查结果， 2005 年，使用百度和 Google 的本科生毕业设计 6 用户达到总量的 90%；而 2006 年这一数值下降到 87.4%，这其中就有垂直搜索的分流作用。 本地化：本地化是一个比个性化更明显的趋势。随着互联网在全球的迅速普 及，综合性的搜索引擎已经不能满足很多非美国网民的信息需求。近来， YAHOO!、INKTOMI、 LYCOS 等公司不断推出各国、各地区的本地搜索网站，搜索的本地化已经是势不可挡。 第五节 搜索引擎展望 一、技术展望 各大公司都把下一代搜索引擎的查询方式的创 新 性，作为自己竞争的筹码，以下是对下一代搜索引擎技术的一些构想。 未来，搜索引擎 技术将重点发展在以下几个方面 ： （一） 自然语言理解技术 自然语言理解是计算机科学中的一个富有挑战性的课题。从计算机科学特别是从人工智能的观点看，自然语言理解的任务是建立一种计算机模型， 这种计算机模型能够给出像人那样理解、分析并回答自然语言。以自然语言理解技术为基础的新一代搜索引擎，我们称之为智能搜索引擎。由于它将信息检索从目前基于关键词层面提高到基于知识 (或概念 )层面，对知识有一定的理解与处理能力，能够实现分词技术、同义词技术、概念搜索、短语识别以及机器翻译技术等。因而这种搜索引擎具有信息服务的智能化、人性化特征，允许网民采用自然语言进行信息的检索，为他们提供更方便、更确切的搜索服务。 （二） P2P P2P 是 peer-to-peer 的缩写，意为对等网络。其 宗旨在于 加强网络上 人与 人的交流 、 在 文件交换、分布计算等方面大有前途。长久以来，人们习惯的互联网是以服务器为中心，人们向服务器发送请求，然后浏览服务器回应的信息。而 P2P 所包含的技术就是使联网电脑能够进行数据交换，但数据是存储在每台电脑里，而不是存储在既昂贵又容易受到攻击的服务器里。网络成员可以在网络数据库里自由搜索、更新、回答和传送数据。所有人都共享了他们认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。 （三） 移动搜索引擎 随着手机接入互联网的能力越来越强，以及移动业务日益倾向于内容驱动，搜索引擎的移动化也成为不可避免的趋势 。许多运营商已经在其内容网站上使用当地本科生毕业设计 7 搜索引擎来帮助消费者找到所需信息，一些主要的搜索引擎公司如 Google、百度、爱问等已着力于移动搜索，其搜索引擎的移动化版本已经问世并开始运营。 （四） 垂直搜索 服务及本地化 垂直搜索引擎的搜索器只搜索特定的主题信息，按预先己经定义好的专题有选择地收集相关的网页。这样大大降低了收集信息的难度，提高了信息的质量。由于所收集的学科领域小，信息量相对较少，可以采用 “专家分类标引 ”的方法对收集到的信息进行组织整理，进一步提高信息的质量，建立一个高质量的、专业信息收集全的数据库。 每一 种 行 业 都可以做一个垂直搜索。目前搜索领域才刚刚起步，尤其是垂直搜索，还有很大的空间。比如说家电、建材、家居、医疗健康等等方面，甚至还可以在更细的领域做更加深的搜索。美国去年第四季度出现了专门给老年人 服务的 搜索引擎。 本地搜索前景 也 很好，面临的挑战就是把全中国所有的店家信息收集上来需要很多投入。 赛迪顾问执行总裁李峻预测，垂直搜索、本地搜索等未来搜索引擎市场仍将保持 30%左右的增长速度。 一些垂直搜索将会成为值得深度挖掘的方向，如旅游搜索、求职搜索等行业细分的搜索引擎，而且搜索引擎技术和渠道的创新核心还在于商 业模式的不断完善。 （五） 多媒体搜索引擎 随着宽带技术的发展，未来的互联网是多媒体数据的时代。开发出可查寻图像、声音、图片和电影的搜索引擎是一个新的方向。目前瑞典一家公司已经研制推出被称作 “第五代搜索引擎 ”的动态的和有声的多媒体搜索引擎。图像、视频将很快取代文本成为互联网上主要的信息。 二、市场展望 iResearch 预测到 2007 年中国搜索引擎市场规模将达到 56.2 亿元人民币，未来3 年的年增长率平均保持在 55%以上 1。中国本土的搜索引擎：百度、中搜、搜狗、一搜等相继推出后，都取得了不错的反响，特别是百 度在 2005 年 8 月 5 日正式在纳斯达克上市，上市首日股票疯狂上涨：最高达 151 美元，把搜索引擎的市值推到了高潮。微软对搜索引擎的研发也伴随着大规模的招兵买马，微软亚洲研究院也成立了专门的搜索小组。李开复先生加盟 Google 后，让很多人预测 Google 一定 会吃掉中 文 搜索引擎这个 巨大 的市场。而李开复先生在闪电加盟后，在 “开复学生网 ”上发表了一篇题为 “Google和中国 -追随我心的选择 ”， Google 的搜索文化对技术人员的吸引可见一斑，等等数字和事件表明，搜索引擎在互联网上有着强劲的生命力和发展潜力，同时也是互联 网公司丰厚利润的来源之一。 本科生毕业设计 8 图 1-5-1 2002-2006 年中国搜索引擎市场规模及增长 2 2005 年 8 月，法国总统希拉克大张旗鼓地发布了 “Quaero”计划，它很快被显现为一种欧洲的决心 推出与 Google 搜索竞争的相同产品。这款名为 “Quaero”的搜索引擎，不仅能搜索文本，而且还能搜索图片和视频。 Quaero 的拉丁文语义是 “我搜索 ”，该项目获得了 2.5 亿欧元资助 (3.3 亿美元 )，法德两国主要技术公司参加了开发。而在德国，一些德国企业将参加另外的德国版搜索引擎 “Theseus”的开发，该引擎 更加集中于文本分析。法德两国开发商将在合作、竞争及互补的环境下实施欧洲新一代搜索引擎的开发计划。 和其他许多国家一样，在日本提起搜索引擎，人们首先想到的是谷歌，此外还有雅虎和微软麾下的 MSN。根据今年 3 月的一项调查，在日本检索服务利用率排名中居首位的是雅虎，其利用率达 64.5%，其次是谷歌和 MSN，日本开发的 GOO 虽然名列第四，但实际利用率只有 5.5%，与前三名的差距很明显。中国百度也已经进入日本市场，欲与群雄共逐鹿。 其实日本着手开发搜索引擎要早于美国，日本电信电话公司、日本电气公司和东芝公司等都曾拥有过 各自独立的搜索引擎。直到 20 世纪 90 年代后期，这些日本国产搜索引擎还在相互竞争。但随着美国谷歌的出现，互联网信息检索业界的格局在 2000 年前后发生了剧变。谷歌高精确度的检索服务使日本众多门户网站形成了这样的共识 “搜索引擎依靠谷歌就足够了 ”，因此日本国产搜索引擎全线败退。 搜索引擎是遨游网络世界的必备工具，而其中的基干技术掌握在外国企业手中。一些日本业界专家认为，长此以往日本互联网搜索业务未来有可能被外国企业控制。抱着同样的危机感，日本政府把国产下一代搜索引擎项目提上了议事日程。经济产业省 2005 年 12 月 设立了企业、研究机构和政府部门共同参与的网络搜索引擎研究小组，负责整理与搜索技术开发相关的资料， 2006 年 7 月末由大学和 52 家企业参与本科生毕业设计 9 的合作项目 “信息大航海计划 ”正式启动，准备用 3 年时间开发出下一代互联网搜索引擎，挑战谷歌等搜索引擎的市场霸主地位，并打算在 2007 年度预算中申请 50 亿日元 (约合 4300 万美元 )作为研发费用，争取 5年后使下一代搜索引擎进入实用阶段。 据日本媒体报道，日本下一代搜索引擎不仅能像现在一样依靠关键词从互联网上的信息海洋中提取所需信息，运用现在逐渐普及的电子标签，还可以及时掌握有关全 球产品的信息，或者以从视频资料中剪辑的录音为基础，检索音频资料。日本下一代搜索引擎的终端设备不仅有电脑，还可能是电视机、 手机 、汽车导航仪等。今后只要操纵遥控器就能通过新搜索引擎找到电视节目中出现过的人物或某个地区的资料，查询并购买电视中出现过的某款商品等。 业内人士指出，雅虎、谷歌、 MSN 每年分别投资数亿美元用于技术研发，这带来问题是在目前体制下怎样才能超越上述企业的技术水 准。谷歌等搜索引擎霸主的战略也包含将检索对象从文本扩展到视频和音频资料，此外日本及欧洲大型企业的不少资深技术人员常跳槽到谷歌和雅虎，这可能有助于谷歌等开发下一代搜索引擎终端设备。因此像法国的 “Quaero”计划和日本的 “信息大航海计划 ”等等的实施能否取得预期效果现在很难准确预料。但不可否认的是：搜索引擎市场将进入一个群雄逐鹿的疯狂竞争时代。 随着搜索经济的崛起，人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业，会根据搜索引擎的知名度以及日流量来选择是否要投放广告等。对于消费者而言，使用互联网 搜索引擎是进入网络世界的一个重要入口，这意味着巨大的商机。微软将 2007 财政年度的研发开支预算调高至 75 亿美元，较预期高出约 13 亿美元，此举显示出微软与 Google、雅虎在互联网搜索市场上一决高下的决心。搜索引擎也将不再是技术，而是经济。 本科生毕业设计 10 第一章 技术诠释 第一节 HTTP 及 HTML 超文本传输协议（ HTTP）是应用层协议，由于其简捷、快速的方式，适用于分布式和合作式超媒体信息系统。自 1990 年起， HTTP 就已经被应用于 WWW 全球信息服务系统。客户进程建立一条同服务器进程的 TCP 连接，然后发出请求并 读取服务器进程的应答。服务器进程关闭连接表示本次响应结束。服务器进程返回的内容包含两个部分，一个 “应答头 ”（ response header），一个 “应答体 ”（ response body），后者通常是一个 HTML 文件，我们称之为 “网页 ”。 通常 HTTP 消息包括客户机向服务器的请求消息和服务器向客户机的响应消息。这两种类型的消息由一个起始行，一个或者多个头域，一个只是头域结束的空行和可选的消息体组成。 HTTP 的头域包括通用头，请求头，响应头和实体头四个部分。每个头域由一个域名，冒号（ :）和域值三部分组成。域名是 大小写无关的，域值前可以添加任何数量的空格符，头域可以被扩展为多行，在每行开始处，使用至少一个空格或制表符。 HTTP 协议采用了请求 /响应模型。客户端向服务器发送一个请求，请求头包含请求的方法、 URI、协议版本、以及包含请求修饰符、客户信息和内容的类似于 MIME的消息结构。服务器以一个状态行作为响应，相应的内容包括消息协议的版本，成功或者错误编码加上包含服务器信息、实体元信息以及可能的实体内容。 Web 服务器的 HTTP 应答一般由以下几项构成：一个状态行，一个或多个应答头，一个空行，内容文档。设置 HTTP 应答 头往往和设置状态行中的状态代码结合起来。 典型的请求消息： GET http:/class/download.microtool.de:80/somedata.exe Host:download.microtool.de Accept:*/* Pragma:no-cache Cache-Control:no-cache Referer:http:/class/download.microtool.de/ User-Agent:Mozilla/4.04en(Win95；I；Nav) Range:bytes=554554- 典型的响应消息 ： HTTP/1.0200OK 本科生毕业设计 11 Date:Mon,31Dec200104:25:57GMT Server:Apache/1.3.14(Unix) Content-type:text/html Last-modified:Tue,17Apr200106:46:28GMT Etag:a030f020ac7c01:1e9f Content-length:39725426 Content-range:bytes554554-40279979/40279980 一个完整的 HTML 文档以 开始，以 结束。大部分的 HTML命令都像这样成对出现。 HTML 文档含有以 开始、以 结束的首部和以 开始、以 结束的主体部分。标题通常由客户程序显示在窗口的顶部。 第二节 网络蜘蛛 网络蜘蛛即 Web Spider，是一个很形象的名字。把互联网比喻成一个蜘蛛网，那么 Spider 就是在网上爬来爬去的蜘蛛 。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止。如果把整个互联网当成一个网站，那么网络蜘蛛就可以用这个原理把互联网上所有的网页都抓取下来。 首先蜘蛛读取抓取站点的 URL 列表，取出一个站点 URL，将其放入未访问的URL 列表（ UVURL 列表）中，如果 UVURL 不为空刚从中取出一个 URL 判断是否已经访问过，若没有访问过则读取此网页，并进行超链分析及内 容分析，并将些页存入文档数据库，并将些 URL 放入已访问 URL 列表（ VURL 列表），直到 UVRL为空为止，此时再抓取其他站点，依次循环直到所有的站点 URL 列表都抓取完为止。 对于搜索引擎来说，要抓取互联网上所有的网页几乎是不可能的，从目前公布的数据来看，容量最大的搜索引擎也不过是抓取了整个网页数量的百分之四十左右。这其中的原因一方面是抓取技术的瓶颈，无法遍历所有的网页，有许多网页无法从其它网页的链接中找到；另一个原因是存储技术和处理技术的问题，如果按照每个页面的平均大小为 20K 计算（包含图片）， 100 亿网页的 容量是 1002000G 字节，即使能够存储，下载也存在问题（按照一台机器每秒下载 20K 计算，需要 340 台机器不停的下载一年时间，才能把所有网页下载完毕）。同时，由于数据量太大，在提供搜索时也会有效率方面的影响。因此，许多搜索引擎的网络蜘蛛只是抓取那些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。 本科生毕业设计 12 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下图所示）。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网 页。这是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。 网络蜘蛛在访问网站网页的时候，经常会遇到加密数据和网页权限的问题，有些网页是需要会员权限才能访问。当然，网站的所有者可以通过协议让网络蜘蛛不去抓取，但对于一些出售报告的网站，他们希望搜索引擎能搜索到他们的报告，但又不能完全免费的让搜索者查看，这样就需要给网络蜘蛛提供相应的用 户名和密码。网络蜘蛛可以通过所给的权限对这些网页进行网页抓取，从而提供搜索。而当搜索者点击查看该网页的时候，同样需要搜索者提供相应的权限验证。 网络蜘蛛需要抓取网页，不同于一般的访问，如果控制不好，则会引起网站服务器负担过重。有多种方法可以让网站和网络蜘蛛进行交流。一方面让网站管理员了解网络蜘蛛都来自哪儿，做了些什么，另一方面也告诉网络蜘蛛哪些网页不应该抓取，哪些网页应该更新。 每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站标明自己的身份。网络蜘蛛在抓取网页的时候会发送一个请求，这个请求中就有一 个字段为 User agent，用于标识此网络蜘蛛的身份。例如 Google 网络蜘蛛的标识为 GoogleBot，Baidu 网络蜘蛛的标识为 BaiDuSpider， Yahoo 网络蜘蛛的标识为 Inktomi Slurp。如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引擎的网络蜘蛛过来过，什么时候过来的，以及读了多少数据等等。如果网站管理员发现某个蜘蛛有问题，就通过其标识来和其所有者联系。 网络蜘蛛进入一个网站，一般会访问一个特殊的文本文件 Robots.txt，这个文件一般放在网站服务器的根目录下，如： /robots.txt 。网站管理员可以通过 robots.txt 来定义哪些目录网络蜘蛛不能访问，或者哪些目录对于某些特定的网络蜘蛛不能访问。例如有些网站的可执行文件目录和临时文件目录不希望被搜索引擎搜索到，那么网站管理员就可以把这些目录定义为拒绝访问目录。Robots.txt 语法很简单，例如如果对目录没有任何限制，可以用以下两行来描述： User-agent: * Disallow: 当然， Robots.txt 只是一个协议，如果网络蜘蛛的设计者不遵循这个协议 ，网站管理员也无法阻止网络蜘蛛对于某些页面的访问，但一般的网络蜘蛛都会遵循这些协议，而且网站管理员还可以通过其它方式来拒绝网络蜘蛛对某些网页的抓取。 本科生毕业设计 13 第三节 网页 噪声 当 Web 中获取所需信息的同时， 会常常看见大量和所关心内容无关的导航条、广告信息、版权信息以及调查问卷等，称之为 “噪 声 ”内容。 在某些情况下 ，可能从这些噪音内容中得到一些意外的惊喜； 但多数 时候， 因 这些 噪声 消耗 掉了很多的 注意力。同时，噪 声 内容通常伴随着相关的超链。因此，噪 声 会导致相互链接的网页常常并无内容相关性。这样，网页内容的混乱不仅给基于网页内容的 研究工作带来困难，也给基于网页超链指向的研究工作带来困难。另外，随着 Web 各种研究与应用的深入发展，仅仅是原始网页内容已经不能满足需求，还要求能够提供便于计算机处理的元数据信息，例如关键词、摘要、网页内容类别等。然而，现在大部分网页仍然是普通 HTML 网页，并不包含必要的元数据。 因 此，本节讨论一个网页表示模型建立和实现的方法，这一方面使我们能够自动从网页中提取相关的元数据，另一方面也去除了和网页主题内容无关的噪音内容，进而在原始 Web 上搭建一个噪 声小、描述清晰、更易于处理和利用的网页信息平台。 在网页分类领域 ，由于噪 声 内容与主题无关，训练集中的噪 声 内容会导致各个类别的特征不够明显，而待分类网页中的噪 声 内容则会导致该网页类别不明确，因而影响了网页自动分类的效果。因此提出了通过去掉网页中的噪 声 内容来提高网页分类质量的方法。 在网页信息提取领域，自动识别模式的方法必须要从整个网页中提取模式，而不是只针对主题内容提取。因此，在净化后的网页上作信息提取不仅可以排除噪 声信息对信息提取的干扰，提高信息提取的准确性，而且可以使得网页中的结构简单化，提高信息提取的效率。 上述分析我们看到， 网页 噪 声 对基于网页的研究工作的影响是普遍 而严重的，虽然各个领域采用的方法各不相同，但处理的目的都是为了去除网页中的噪 声 内容，得到真正的主题内容。 第四节 页面分析 由于 WWW网上的信息主要是以 HTML文档的形式存放的，因此要根据 HTML文档的特点，对其进行扫描分析，以提取信息。 HTML文档有五个定义好的组件 : 、文本 本科生毕业设计 14 、注释 、简单标签 、起始标签 、结束标签 文本就是在 HTML页面上看到的 词句的内容。除了脚本代码， HTML文档中的所有数据，只要不是标签的组成部分，都被认为是文本。文本是格式化的， 并且受包围它的标签的控制。就像前面所提到的那样，如果数据位于文本之外，将不会被看作文本。但是程序在理解 HTML页面时，脚本代码具有与文本相似的特性。脚本代码包含在标签 之间。确保搜索引擎程序不会将脚本代码与文本数据混淆是很重要的。 文本实际上就是显示在浏览器中的文字，其显示方式由包围它的标签来网以决定。根据本课题的要求，文本无疑是我们所需要的重要的信息源之一。页相关的 主题是通过文本来表达的，所以文本信息必须被完全提取出来，便进一步处理。 注释表示 HTML文档中不会显示给用户的那部分内容。他们通常是 HTML程序员所做的说明，这些说明通常是表达编程思路的，所以这类数据对本课题来说是毫无用处。因此在解析 HTML文档时，将注释忽略。简单标签是由单个表示的 HTML标签。最普遍的简单标签是行中断符 ()标签和图像标签 ( )，它们都没有相应的结束标签。简单标签主要是用来控制显示格式或使用图像美化界面用的。 大多数 HTML标签都是由开始标签和结束标签组成的。开始标签非常 像简单标签。开始标签与简单标签直接的唯一区别是 :开始标签有一个相应的结束标签，该结束标签出现在后面。开始标签和结束标签用来控制其所包含的 HTML代码的功能。 在所有的开始和结束标签中，标签 是最有用的。标签 在 HTML中叫做链接标签，它决定了当在浏览器中点击该标签的文本时所要打开的网页的 URL。下面是一个例子 : Click Here 从上面的例子中我们可以看出，标识它所链接的 URL是该标签的 href属性决定，href的值就代表了一个 URL. Href属性值有两种表达方式 :一种是绝对路径，也就是说它的值是一个完整的 URL， 程序可以直接使用它 ；另一种相对路径，它的表示方式只有目录或文件名，表示相对于木网页的所在目录的位置。使用相对路径的目的是提高网页的可移植性。标签 中的链接并不是唯一将用户带到其它页面的基础结构标签。 Web站点还能建立图像映像，当用户点击它们时，也能将用户带到相应的新页面。图像映像由客户端和服务器图像映像组成，但是服务器图像映像几乎完全被客户端所取代。这是因为服务器端的图像 映像，需要一个服务器插件来注册用户本科生毕业设计 15 点击的图像区域。而这在客户端图像映像中是完全包含在 HTML文件中 3。 客户端图像映像不需要服务器端的脚本表示来解释可多处点击的图像的 hot”区。实际上，客户端图像映像比服务器端图像映像更为有效，而且还允许访问者在Web浏览器的状态区中看到映像区域真正关联的 URL。该状态文本还会在用户鼠标在图像映像区域移动的时候出现。客户端映像图像将包含一个如下所示的映像。该映像将每个图像区域链接到一个 URL: 在该 HTML文件的后面，该映像以类似于下面的方式使用 : 通过以上分析图像映像当中的超级链接可以由图像的 简单标签中的 href属性得到。除了以上两种情况外，框架中的 src属性也可以设置超级链接。框架标签属于开始标签和结束标签，下面是一个例子。 在上面的例子中可以看出，该标签中有一个名为 src的属性， 代表了该框架中应显示的网页链接，在网页中搜索链接时，不应遗漏此类链接。需要说明的是，窗体、脚本语言代码和网页中嵌入式对象也可以提供链接功能。但是，它们主要是提供一些特殊领域的特殊功能的应用。窗体主要是用来收集用户信息，用户信息是浏览网页的人根据自己的实际情况填写，例如，用户名和密码等。在这些用户信息不全的情况下，返回的网页通常显示的是错误的信息的页面。这对本文所研究的垂直搜索引擎来说是毫无意义的，因此，我们对表单不作处理。至于脚本语言代码，通常是网页编写者按照自己的意愿和逻辑，用脚本