毕业设计论文 搜索引擎

目 录 第一章 课题背景知识 .(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 信息进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对 查询记录进行排序并进行集合运算，最后从文档数据库中提取各网页的摘要信息反 馈给查询用户。 URL服 务 器 爬 行 器 存 储 服 务 器 资 源 库 页 级 别 评 定 器 URL解 析 器 标 引 器 查 询 器 分 类 器 锚 库 词 典 库 索 引 库 链 接 库 桶 桶 桶 桶 桶 桶 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 本科生毕业设计 5 的前身，也就是今天 Overture） ，和 Repository-Based Software Engineering (RBSE) spider 最负盛名。 然而 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 等公司一年前开始了个性 化方面的研发工作，但至今没有推出任何产品。 垂直化：垂直搜索引擎这种高度目标化、专业化的搜索引擎的优势在于:针对 本科生毕业设计 6 性强，对特定范围的网络信息的覆盖率相对较高，具有可靠的技术和信息资源保障， 有明确的检索目标定位，有效地弥补了通用综合性搜索引擎对专门领域及特定主题 信息覆盖率过低的问题。根据 CNNIC 的调查结果，2005 年，使用百度和 Google 的用户达到总量的 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 年前后发生了剧变。谷歌高精确度的检索服务使日本众多门户网站形成了 这样的共识“ 搜索引擎依靠谷歌就足够了 ”，因此日本国产搜索引擎全线败退。 搜索引擎是遨游网络世界的必备工具，而其中的基干技术掌握在外国企业手中。一 些日本业界专家认为，长此以往日本互联网搜索业务未来有可能被外国企业控制。 本科生毕业设计 9 抱着同样的危机感，日本政府把国产下一代搜索引擎项目提上了议事日程。经济产 业省 2005 年 12 月设立了企业、研究机构和政府部门共同参与的网络搜索引擎研究 小组，负责整理与搜索技术开发相关的资料，2006 年 7 月末由大学和 52 家企业参 与的合作项目“ 信息大航海计划 ”正式启动，准备用 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 些重要的网页，而在抓取的时候评价重要性主要的依据是某个网页的链接深度。 在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（如下图 所示） 。广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择 其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式， 因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛 会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个 起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。 网络蜘蛛在访问网站网页的时候，经常会遇到加密数据和网页权限的问题，有 些网页是需要会员权限才能访问。当然，网站的所有者可以通过协议让网络蜘蛛不 去抓取，但对于一些出售报告的网站，他们希望搜索引擎能搜索到他们的报告，但 又不能完全免费的让搜索者查看，这样就需要给网络蜘蛛提供相应的用户名和密码。 网络蜘蛛可以通过所给的权限对这些网页进行网页抓取，从而提供搜索。而当搜索 者点击查看该网页的时候，同样需要搜索者提供相应的权限验证。 网络蜘蛛需要抓取网页，不同于一般的访问，如果控制不好，则会引起网站服 务器负担过重。有多种方法可以让网站和网络蜘蛛进行交流。一方面让网站管理员 了解网络蜘蛛都来自哪儿，做了些什么，另一方面也告诉网络蜘蛛哪些网页不应该 抓取，哪些网页应该更新。 每个网络蜘蛛都有自己的名字，在抓取网页的时候，都会向网站标明自己的身 份。网络蜘蛛在抓取网页的时候会发送一个请求，这个请求中就有一个字段为 Useragent，用于标识此网络蜘蛛的身份。例如 Google 网络蜘蛛的标识为 GoogleBot，Baidu 网络蜘蛛的标识为 BaiDuSpider，Yahoo 网络蜘蛛的标识为 Inktomi Slurp。如果在网站上有访问日志记录，网站管理员就能知道，哪些搜索引 擎的网络蜘蛛过来过，什么时候过来的，以及读了多少数据等等。如果网站管理员 发现某个蜘蛛有问题，就通过其标识来和其所有者联系。 网络蜘蛛进入一个网站，一般会访问一个特殊的文本文件 Robots.txt，这个文 件一般放在网站服务器的根目录下，如： http:/ 。网 站管理员可以通过 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的属性，代表了该框架中 应显示的网页链接，在网页中搜索链接时，不应遗漏此类链接。需要说明的是，窗 体、脚本语言代码和网页中嵌入式对象也可以提供链接功能。但是，它们主要是提 供一些特殊领域的特殊功能的应用。窗体主要是用来收集用户信息，用户信息是浏 览网页的人根据自己的实际情况填写，例如，用户名和密码等。在这些用户信息不 全的情况下，返回的网页通常显示的是错误的信息的页面。这对本文所研究的垂直 搜索引擎来说是毫无意义的，因此，我们对表单不作处理。至于脚本语言代码，通 常是网页编写者按照自己的意愿和逻辑，用脚本语言写的一段代码，它也可以返回 一个网页。然而不幸的是，除非搜索引擎能正确理解脚本代码，才一能得到正确的 返回页面的URL。否则，应该回避。对于网页中的嵌入式对象，比如ActiveX控件， Java Applet等，他们都是已编译好的程序。要对它们中的链接进行识别的话，必 须全面深入其二进制代码内部结构，难度极大。 本科生毕业设计 16 第五节 中文分词 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为 单位，句子中所有的字连起来才能描述一个意思。例如，英文句子 I am a student， 用中文则为：“ 我是一个学生 ”。计算机可以很简单通过空格知道 student 是一个单 词，但是不能很容易明白“学” 、 “生”两个字合起来才表示一个词。把中文的汉字序 列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的 结果是：我/是/一个/学生。 中文分词是其他中文信息处理的基础，搜索引擎只是中文分词的一个应用。其 他的比如机器翻译（MT） 、语音合成、自动分类、自动摘要、自动校对等等，都需 要用到分词。 一、分词方法概述 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词 方法和基于统计的分词方法。 （一）基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个 “充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功 （识别出一个词） 。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆 向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短） 匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相 结合的一体化方法。常用的几种机械分词方法如下： 正向最大匹配法（由左到右的方向） ； 逆向最大匹配法（由右到左的方向） ； 最少切分（使每一句中切出的词数最小） 。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大 匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆 向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到 的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为 1/169，单 纯使用逆向最大匹配的错误率为 1/2454。但这种精度还远远不能满足实际的需要。 实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它 的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中 本科生毕业设计 17 识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小 的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结 合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对 分词结果进行检验、调整，从而极大地提高切分的准确率。 对于机械分词方法，可以建立一个一般的模型，在这方面有专业的学术论文， 这里不做详细论述。 （二）基于理解的分词方法 这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基 本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧 义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控 部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧 义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言 知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器 可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。 （三）基于统计的分词方法 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次 数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反 映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它 们的互现信息。定义两个字的互现信息，计算两个汉字 X、Y 的相邻共现概率。互 现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可 认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需 要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局 限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一” 、 “之一”、 “有的”、 “我的 ”、 “许多的” 等，并且对常用词的识别精度差，时空开销大。实际应用 的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同 时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分 词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消 除歧义的优点。 到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分词系 统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。笔者了解， 海量科技的分词算法就采用“复方分词法” ，所谓复方，相当于用中药中的复方概念， 即用不同的药才综合起来去医治疾病，同样，对于中文词的识别，需要多种算法来 处理不同的问题。 本科生毕业设计 18 二、分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢？事实远非如此。 中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中， 有两大难题一直没有完全突破。 （一）歧义识别 歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：表面的，因 为“表面”和“面的 ”都是词，那么这个短语就可以分成 “表面 的” 和“表 面的”。这种 称为交叉歧义。像这种交叉歧义十分常见，前面举的“和服” 的例子，其实就是因为 交叉歧义引起的错误。 “化妆和服装 ”可以分成“化妆/ 和/ 服装”或者“ 化妆/ 和服/装”。 由于没有人的知识去理解，计算机很难知道到底哪个方案正确。 交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整个句 子来判断了。例如，在句子“这个门把手坏了” 中， “把手”是个词，但在句子“ 请把手 拿开”中， “把手” 就不是一个词；在句子“将军任命了一名中将 ”中， “中将” 是个词， 但在句子“产量三年中将增长两倍” 中， “中将”就不再是词。这些词计算机又如何去 识别？ 如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题，是真 歧义。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应该不 是词。例如：“ 乒乓球拍卖完了 ”，可以切分成“乒乓/ 球拍/ 卖/完/ 了” 、也可切分成 “乒乓球/拍卖 /完/了” ，如果没有上下文其他的句子，恐怕谁也不知道“ 拍卖”在这里 算不算一个词。 （二）新词识别 新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确实 能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了” 中， “王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把 “王军虎”做为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新 增的人名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是 会存在问题，例如：在句子“王军虎头虎脑的” 中， “王军虎”还能不能算词？ 新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等 都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来 说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词 系统好坏的重要标志之一。 本科生毕业设计 19 第六节 布尔代数 布尔（George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为 他是数学家。布尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年思 维规律（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities） 一书，第一次向人们展示了如何 用数学的方法解决逻辑问题 5。 布尔代数运算的元素只有两个 1 （TRUE ， 真) 和 0（FALSE，假)。基本的 运算只有“与 ”（AND) 、 “或” (OR) 和“非”（NOT) 三种（后来发现，这三种运算都 可以转换成“ 与”“非” ANDNOT 两种运算） 。 事实上在布尔代数提出后 80 多年里，它确实没有什么像样的应用，直到 1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数 成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等， 全部能转换成二值的布尔运算。 二进制和布尔运算是世界上最简单的计数方法和运算。无论哪一个搜索引擎宣 称自己如何聪明、多么智能化，其实只要是追求效率，从根本上讲都不可能离开布 尔运算。ToKing 搜索引擎的倒排索引文件的实际方法将主要采用布尔代数。 第七节 CGI CGI 代表 Common Gateway Interface(通用网关界面） ，它使在网络服务器下运 行外部分应用程序（或网关）成为可能。CGI-BIN 目录是存放 CGI 脚本的地方。 这些脚本使 WWW 服务器和浏览器能运行外部程序，而无需启动另一个原因程序。 它是运行在 Web 服务器上的一个程序，并由来自于浏览者的输人触发。CGI 是在 HTTP 服务器下运行外部程序（或网关）的一个接口，它能让网络用户访问远程系 统上的使用类型程序，就好像他们在实际使用那些远程计算机一样。 CGI 能够让浏览者与服务器进行交互，如果你曾经遇到过在网络上填表或者进 行搜索，就很有可能就是用的 CGI。 尽管 CGI 易于使用，但是当大批人同时使用一个 CGI 应用程序是会反应较慢， 网络服务器 速度也会受到很大 影响。CGI 应用程序的优点是可以独立运行。 CGI 应用程序可以由大多数的编程语言编写，如 Perl（Practical Extraction and Report Language)、CC+、Java 和 Visual Basic 等。不过对于那些没有太多编程经 验的网页制作人来说，实在是一个不小的难题。 本科生毕业设计 20 CGI 应用程序的工作原理是这样的： .浏览器通过 HTML 表单或超链接请求指上一个 CGI 应用程序的 URL。 .服务器收发到请求。 .服务器执行指定所 CGI 应用程序。 .CGI 应用程序执行所需要的操作，通常是基于浏览者输人的内容。 .CGI 应用程序把结果格式化为网络服务器和浏览器能够理解的文档（通常 是 HTML 网页） 。 .网络服务器把结果返回到浏览器中。 自 CGI 产生以来，C 语言以其高效性、灵活性和通用性一直是开发交互式 WEB 应用的最有吸引力的选择。但近年来，能直接内嵌于 HTML 文档中间的各种 脚本工具，以其简便性易用性使一部分用户开始放弃了直接用 C 来开发 CGI 脚本。 但还有两类用户没有放弃用 C 来开发它们的应用，一是对性能追求较高的高端开 发者，二是嵌入式设备的开者。前者选择 C 语言来开发它们的 WEB 应用，是因为 C 高效性、灵活性和通用性是各种脚本工具无法取代的。后者选择 C 语言，是因 嵌入式设备的特点（内存、CPU 等资源有限等，不可在设备上运行如 ASP，PHP，PERL 等的脚本的运行环境）决定的（另外，目前嵌入式设备主要以 C 语言开发为主） 。 第八节 SOCKECT 网络编程 所谓 socket 通常也称作套接字，用于描述 IP 地址和端口，是一个通信链的 句柄。应用程序通常通过 套接字 向网络发出请求或者应答网络请求。 网页抓取 部分就是采用的这种技术。 本科生毕业设计 21 第二章 TOKING 海量网页搜索系统体系结构及实现 第一节 结构设计 搜索引擎的最基本的功能就是在一个可以接受的时间内返回一个和用户查询匹 配的网页