基于中文分词的搜索引擎的设计与实现（程序代码+任务书+说明书+外文翻译+演示文稿）

0摘要网络中的资源非常丰富，但是如何有效的搜索信息却是一件困难的事情。建立搜索引擎就是解决这个问题的最好方法。本文首先详细介绍了基于英特网的搜索引擎的系统结构，然后从网络机器人、索引引擎、Web服务器三个方面进行详细的说明。为了更加深刻的理解这种技术，我使用Java编程技术实现了一个自己的搜索引擎基于中文分词的搜索引擎。基于中文分词的搜索引擎是从指定的Web页面中按照超连接进行解析、搜索，并把搜索到的每条新闻进行索引后加入数据库。然后通过Web服务器接受客户端请求后从索引数据库中搜索出所匹配的新闻。本人在介绍搜索引擎的章节中除了详细的阐述技术核心外还结合了基于中文分词的搜索引擎的实现代码来说明，图文并茂、易于理解。关键词搜索引擎；网络机器人；Web服务器；中文分词1AbstractTheresourcesintheinternetareabundant,butitisadifficultjobtosearchsomeusefulinformation.Soasearchengineisthebestmethodtosolvethisproblem.Thisarticlefistintroducesthesystemstructureofsearchenginebasedontheinternetindetail,thengivesaminuteexplanationformSpidersearch,engineandwebserver.Inordertounderstandthetechnologymoredeeply,Ihaveprogrammedanewssearchenginewithjavaskillbymyself.Thenewssearchengineisexplainedandsearchedaccordingtohyperlinkfromaappointedwebpage,thenindexseverysearchedinformationandaddsittotheindexdatabase.Thenafterreceivingthecustomersrequestsfromthewebserver,itsoonsearchstherightnewsformtheindexengine,Inthechapterofintroducingsearchengine,itisnotonlyelaboratethecoretechnology,butalsocombinewiththemoderncode,picturesincluded,easytounderstand.KeyWords:SearchEngine;Spidersearch,;WebServer;ChineseAnalyzer目录摘要.IAbstract.II第一章绪论.1一、论文的研究背景.1二、国内外研究现状.1三、本文工作.2四、本文结构.3第二章搜索引擎概述.4一、搜索引擎的定义.4二、搜索引擎的分类.4（一）按检索工具发展过程分类.4（二）按检索范围分类.4（三）按工作方式分类.4三、搜索引擎的原理.5（一）搜索引擎的结构.5（二）搜索引擎的工作流程.6第三章搜索引擎的原理.7一、网络机器人.7（一）什么是网络机器人.7（二）网络机器人的结构分析.7二、索引的建立与搜索.9(一)索引的建立与搜索过程.9(二)基于lucene的索引与搜索.9三、Web服务器.11四、搜索引擎的工作流程.12（一）全文搜索引擎工作流程.12（二）目录搜索引擎.13五、搜索引擎的主要指标及分析.13第四章中文分词.14一、中文分词和搜索引擎.14二、中文分词技术.14三、中文分词算法.14（一）基于字符串匹配的分词方法.14（二）基于理解的分词方法.15（三）基于统计的分词方法.15（四）歧义识别与新词识别.15（五）正向迭代最细粒度切分算法.16第五章搜索引擎的设计与实现.17一、网络机器人的设计与实现.17（一）如何构造Spider程序.17（二）如何提高程序性能.19（三）网络机器人的代码分析.19二、基于Lucene的索引与搜索的设计与实现.21（一）中文分词器的选择.21（二）Lucene与Spider结合的代码实现.21三、基于Tomcat的Web服务器程序的设计与实现.25（一）用户接口设计.25（二）在Tomcat上部署项目.30四、中文分词模块的设计与实现.31（一）中文分词器的比较与选择.31（二）IK-Analyzer的分词处理过程.32第六章搜索引擎的测试.34一、测试目的与意义.34二、测试过程.34（一）中文分词测试.34（二）搜索结果测试.35三、测试结论.36结论.37一、论文总结.37（一）网络机器人.37（二）网页分析.37（三）中文分词.37（四）建立索引文件.37（五）Web服务器.37（六）动态的扩展词库.37二、进步的工作.37（一）改善网络机器人使之行业化.37（二）改善中文分词器.38参考文献.39致谢.40外文原文.41中文翻译.480第一章绪论一、论文的研究背景面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。互联网络从早期的ARPANet到目前的Internet已经发展了近五十年，它的迅速发展和广泛普及导致网上信息爆炸性增长。据UniversityofIowa最近一项调查显示，截至2005年1月全球可以索引的网页已经达到至少115亿。如果这些信息能被有效地利用，互联网将是一个巨大的信息宝库。但由于Internet是一个开放、分布、异构的信息空间，Internet这个“数字时代的图书馆”并不像真正的图书馆那样支持有组织的信息管理和检索。它本身固有的3个特点已经明显地阻碍了人们充分使用Internet上的信息资源：(1)Internet上的信息无组织、无固定结构、分布无规律性；(2)Internet是一个动态性极强的信息源；(3)Internet上的信息量每天呈指数增长，而对用户个体而言只有少数相关。由此看来，虽然Internet是一个广阔的信息海洋，但漫游其间而不迷失方向有时会是相当困难的。如何快速准确地在网上找到需要的信息已变得越来越重要。搜索引擎是基于上述原因而产生的，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的，是用户打开互联网这个信息宝库的一把钥匙。目前，关于搜索引擎的概念还没有一个明确的定义。可以从狭义和广义两个角度理解。从狭义的角度来说，搜索引擎由信息收集软件，索引数据库和查询接口三部分组成。信息收集软件从一个已知的文档集中读取信息，并检查这些文档的链接指针，找出新的信息空间，然后取回这些新空间中的文档，将它们加入到索引数据库。查询接口通过索引数据库为用户的查询请求提供服务。即搜索引擎指的是基于某种技术在整个网上自动执行网页全文搜索的网上指南工具。从广义的角度上讲，搜索引擎是因特网上的一类网站，这类网站与一般的网站不同的是它是提供查询，搜索的网站，或称查询站点，导航站点，即因特网上具有检索功能的网页。一般说来，搜索引擎由搜索器，索引器，检索器和用户接口等四个部分组成。搜索引擎的搜索器在网络中爬行，发现和搜集信息。索引器负责从搜索器采集地信息中抽取出索引项，用于表示文档以及生成文档库的索引表。检索器根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现用户相关性反馈机制。用户接口负责与用户交互。二、国内外研究现状搜索引擎是随着web信息的迅速增加而发展起来的，是一种网民查询互联网信息的搜索型工具，通过为用户提供信息检索服务，起到导航信息的目的。搜索引擎的基本概念出现于20世纪70年代，但它真正发展和应用却是90年代的事情，并在90年代中期得到快速的发展。目前网上的搜索引擎有160种以上，其中比较著名的7个全球性导航站有YAHOO，ALTAVISTA，LYCOS，HOTBOT，INFOSEEK,WEBCRAWLER,EXCITE。1据CNNIC于2005年1月发布的统计资料，搜索引擎的使用己占到网络应用的65.0%，并成为中国当前第二大互联网应用，仅次于收发Email。搜索引擎技术伴随着WWW的发展是引人注目的。搜索引擎大约经历了三代的更新发展：第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。在实现技术上也基本沿用较为成熟的IR（InformationRetrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。在1994年3月到4月，网络爬虫WorldWebWorm(WWWW)平均每天承受大约1500次查询。大约在1996年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50，000，000网页的索引数据库，每天能够响应10，000，000次用户检索请求。1997年11月，当时最先进的几个搜索引擎号称能建立从2，000，000到100，000，000的网页索引。Altavista搜索引擎声称他们每天大概要承受20，000，000次查询。2000年搜索引擎2000年大会上，按照Google公司总裁LarryPage的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页。搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。著名的因特网搜索引擎包括FirstSearch、Google、HotBot等。在中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务。目前的搜索引擎，每天使用爬虫在互联网上获取大量网页，这花去了大量的时间，随着WWW信息的指数增加，搜索引擎搜索速度慢，死链接太多，重复信息或不相关信息较多，难以满足人们的各种信息需求，搜索引擎将向智能化，精确化，交叉语言检索，多媒体检索，专业化等适应小型用户需求的方向发展。三、本文工作本文主要是完成了基于中文分词搜索引擎系统的设计与实现，主要完成了如下工作：（1）网络机器人模块的设计与实现从网络上不断爬取网页，自动实现分析网页中包含的链接并且进入链接爬取网页。并且把爬取的网页保存在本地机器上并给网页编号。（2）网页链接抓取模块的设计与实现把网络机器人爬取的网页加以分析，去除网页中的控制命令和格式，只保留内容。（3）中文分词模块的设计与实现对网页分析后的内容进行中文切分词，同时在用户对索引进行检索时也会将用户输入的内容进行切分处理，从而到索引文件中找到相应的内容。2（4）建立索引文件模块的设计与实现对切分词语分析之后的网页内容建立词索引。每个词如果出现在网页中，且这个词属于词典中的词，则把网页的相关内容写入倒排表。将词语在某篇文档中出现的具体位置写入辅助文件。（5）Web服务器模块的设计与实现部署Web应用，对用户输入的查询内容实现切分词语，根据切分后的词语，查找索引文件，对多关键词实现了内容的和运算,然后将搜索的内容排序输出。（6）动态的扩展词库模块的设计与实现可以向词库中添加单个新词，也可以批量的向词库中导入大量新词，可以避免重复添加。四、本文结构各章内容安排如下：第一章：绪论。本章主要介绍了本课题的研究意义，背景知识和中文分词搜索引擎的关键技术。第二章：搜索引擎概述。本章主要介绍搜索引擎的定义，搜索引擎的分类，搜索引擎的工作原理，搜索引擎的发展趋势。第三章：搜索引擎的原理。本章主要对搜索引擎的原理进行分析，为后期的搜索引擎的设计实现提供理论与思想基础，对搜索引擎的三大组成部分网络机器人、索引的建立与搜索和Web服务器进行了详细介绍，并介绍了三大搜索引擎的工作流程，最后介绍了搜索引擎的主要指标及分析。第四章：中文分词。本章主要介绍了中文分词技术在搜索引擎中的应用，并介绍了中文分词常用技术。第五章：搜索引擎的设计与实现。本章主要介绍搜索引擎三大组成部分网络机器人、索引的建立与搜索和Web服务器的设计与实现。第六章：搜索引擎的测试。本章对已经实现的搜索引擎系统进行测试确保系统可以正常运行使用。第七章：结论。对本课题的工作做总结，并提出下一步的工作内容。3第二章搜索引擎概述一、搜索引擎的定义搜索引擎是一种在Web上应用的软件系统，它以一定的策略在w曲上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。从使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词语或者短语，然后很快返回一个可能和用户输入相关的信息列表(常常会是很长一个列表，例如包含1万个条目)。它包括信息搜集，信息整理和用户查询三部分。二、搜索引擎的分类（一）按检索工具发展过程分类按照检索工具的发展过程可分为：第一代搜索引擎、第二代搜索引擎和下一代搜索引擎。1.第一代搜索引擎第一代搜索引擎以AltaVista、Yahoo和Infoseek为代表，出现于1994年前后，搜索结果的好坏往往用反馈结果的数量来衡量，也就是说，第一代搜索引擎“求全”。2.第二代搜索引擎第二代搜索引擎以Google和DirectHit为代表，还包括中国的百度、天网搜索等，这些引擎的主要特点是提高了查准率，可以用“求精”来描述。3.下一代搜索引擎下一代搜索引擎目前尚无产品出现，只是处于研究和探讨阶段，有资料称下一代搜索引擎将是“求专和“求易，可以理解成专业化和智能化；也有学者称下一代搜索引擎的方向是智能化和个性化。（二）按检索范围分类按照提供的信息服务范围与用途的不同，搜索引擎可分为综合性搜索引擎和专业性搜索引擎。1.综合性搜索引擎即综合性的信息检索系统，利用它几乎可以检索任何方面的信息资源，但有时会出现字形相同而实际上互不相关的内容，或因检出的内容太泛而无法一一过目。2.专业性搜索引擎则是专业信息机构根据专业需求，将因特网上资源进行筛选整理、新组织而形成的专业性的信息检索系统。专业性搜索引擎能针对用户特定需求来提供信息，特定用户只要登录到相应的搜索引擎即可迅速、准确地找到符合要求的精准信息。因此，高质量专4业性搜索引擎是学科专业领域的研究人员获取网上信息资源的重要工具，是因特网搜索引擎研究开发的方向。（三）按工作方式分类按照其工作方式主要可分为三种，分别是全文搜索引擎、目录索引类搜索引擎和元搜索引擎。1.全文搜索引擎国外具有代表性的有Google、Inktomi、Teoma、WiseNut等，国内著名的有百度(Baidu)。都是通过从互联网上提取的各个网站的信息(以网页文字为主)而形成的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的顺序将结果返回给用户。2.目录索引类搜索引擎虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅仅是按目录分类的网站链接列表而已。用户完全可以不用关键词(Keywords)查询，仅靠分类目录也可找到需要的信息。索引中最具代表性的莫过于大名鼎鼎的雅虎(Yahoo)。其他著名的还有DMOZ、LookSmart、About等。国内的搜狐(搜狗)、浪搜索(爱问)、网易搜索也都属于这一类。3.元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜将结果返回给用户。著名的元搜索引擎有Infospace、Dogpile等，其中Dogpile为目前最受欢迎的元搜索引擎，它可以调用le、Yahoo、MSN、AskJeeves、LookSmart等20多个独立搜索引擎，中文元搜索引擎中具代表性有万纬搜索、北斗搜索等。三、搜索引擎的原理（一）搜索引擎的结构搜索引擎是根据用户的查询请求，按照一定算法从索引数据中查找信息返回给用户。为了保证用户查找信息的精度和新鲜度，搜索引擎需要建立并维护一个庞大的索引数据库。一般的搜索引擎由网络机器人程序、索引的建立与搜索、Web服务器、索引数据库等部分组成。WWW文档网络机器人程序建立Lucene索引从数据库中搜索信息Tomcat服务器Lucene索引文件WWW浏览器WWW浏览器JSP网络机器人程序5图2-1系统结构图（二）搜索引擎的工作流程搜索引擎并不真正去搜索互联网，它搜索的实际上是预先整理好的网页索引数据库，搜索引擎也不能真正理解网页上的内容，它只能机械的匹配网页上的文字。真正意义上的搜索引擎，通常指的是收集了互联网上几千万到几十亿个网页并对网页中的每一个文字(即关键词)进行索引，建立索引数据库的全文搜索引擎。当用户查找某个关键词的时候，所有在页面内容中包含了该关键词的网页都将作为搜索结果被搜出来。在经过复杂的算法进行排序后，这些结果将按照与搜索关键词的相关度高低，依次排列。现在的搜索引擎已普遍使用超链分析技术，除了分析索引网页本身的文字，还分析索引所有指向该网页的链接的URL、AnChorText、甚至链接周围的文字。所以，有时候，即使某个网页A中并没有某个词比如“恶魔撒旦”，但如果有别的网页B用链接“恶魔撒旦”指向这个网页A，那么用户搜索“恶魔撒旦”时也能找到网页A。而且，如果有越多网页(C、D、E、F)用名为“恶魔撒旦”的链接指向这个网页A，或者给出这个链接的源网页(B、C、D、E、F)越优秀，那么网页A在用户搜索“恶魔撒旦”时也会被认为更相关，排序也会越靠前。6第三章搜索引擎的原理一、网络机器人（一）什么是网络机器人网络机器人又称为Spider程序，是一种专业的Bot程序。用于查找大量的Web页面。它从一个简单的Web页面上开始执行，然后通过其超链接在访问其他页面，如此反复理论上可以扫描互联网上的所有页面。基于因特网的搜索引擎是Spider的最早应用。例如搜索巨头Google公司，就利用网络机器人程序来遍历Web站点，以创建并维护这些大型数据库。网络机器人还可以通过扫描Web站点的主页来得到这个站点的文件清单和层次机构。还可以扫描出中断的超链接和拼写错误等。（二）网络机器人的结构分析Internet是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议之上。Web就是建立在HTTP(HypertextTransferProtocol)协议基础上，而HTTP又是建立在TCP/IP(TransmissionControlProtocol/InternetProtocol)协议之上，它同时也是一种Socket协议。所以网络机器人本质上是一种基于Socket的网络程序。1.如何解析HTML因为Web中的信息都是建立在HTML协议之上的，所以网络机器人在检索网页时的第一个问题就是如何解析HTML。在解决如何解析之前，先来介绍下HTML中的几种数据。表3-1HTML数据类型表数据类型说明文本除了脚本和标签之外的所有数据注释程序员留下的说明文字，对用户是不可见的简单标签由单个表示的HTML标签开始标签和结束标签用来控制所包含的HTML代码我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进行解析即可。（1）超连接标签超连接定义了WWW通过Internet链接文档的功能。他们的主要目的是使用户能够任意迁移到新的页面，这正是网络机器人最关心的标签。（2）图像映射标签图像映射是另一种非常重要的标签。它可以让用户通过点击图片来迁移到新的页面中。（3）表单标签表单是Web页面中可以输入数据的单元。许多站点让用户填写数据然后通过点击按钮来提交内容，这就是表单的典型应用。7（4）表格标签表格是HTML的构成部分，通常用来格式化存放、显示数据。我们在具体解析这些HTMl标签有两种方法：通过JavaTM中的Swing类来解析或者通过Bot包中的HTMLPage类来解析，本人在实际编程中采用后者。Bot包中的HTMLPage类用来从指定URL中读取数据并检索出有用的信息。下面给出该类几种重要的方法。表3-2HTMLPage类方法列表类方法说明声明HTMLPage构造函数构造对象并指定用于通讯的HTTP对象PublicHTMLPage(HTTPhttp)GetForms方法获取最后一次调用Open方法检索到的表单清单PublicVectorgetForms()GetHTTP方法获取发送给构造函数的HTTP对象PublicHTTPgetHTTP()GetImage方法获取指定页面的图片清单PublicVectorgetImage()GetLinks方法获取指定页面的连接清单PublicVectorgetLinks()Open方法打开一个页面并读入该页面，若指定了回调对象则给出所有该对象数据Publicvoidopen(Stringurl,HTMLEditorKit.ParserCallbacka)2.Spider程序结构网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连接。程序首先解析网页的HTML代码，查找该页面内的超连接然后通过递归和非递归两种结构来实现Spider程序。（1）递归结构递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但耗费内存且不能使用多线程技术，故不适合大型项目。（2）非递归结构这种方法使用队列的数据结构，当Spider程序发现超连接后并不调用自己本身而是把超连接加入到等待队列中。当Spider程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。8虽然这里只描述了一个队列，但在实际编程中用到了四个队列，他们每个队列都保存着同一处理状态的URL。表3-3队列详解队列说明等待队列在这个队列中，URL等待被Spider程序处理。新发现的URL也被加入到这个队列中处理队列当Spider程序开始处理时，他们被送到这个队列中错误队列如果在解析网页时出错，URL将被送到这里。该队列中的URL不能被移入其他队列中完成队列如果解析网页没有出错，URL将被送到这里。该队列中的URL不能被移入其它队列中在同一时间URL只能在一个队列中，我们把它称为URL的状态。发现URL等待队列运行队列完成队列错误队列完成URL图3-1队列变化过程图以上的图表示了队列的变化过程，在这个过程中，当一个URL被加入到等待队列中时Spider程序就会开始运行。只要等待队列中有一个网页或Spider程序正在处理一个网页，程序就会继续他的工作。当等待队列为空并且当前没有任何网页时，Spider程序就会停止它的工作。二、索引的建立与搜索(一)索引的建立与搜索过程网络机器人将遍历得到的页面存放在临时数据库中，如果通过SQL直接查询信息速度将会难以忍受。为了提高检索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及时跟新的话，用户用搜索引擎也不能检索到。用户输入搜索条件后搜索程序将通过索引数据库进行检索然后把符合查询要求的数据库按照一定的策略进行分级排列并且返回给用户。(二)基于lucene的索引与搜索1.什么是Lucene全文检索Lucene是JakartaApache的开源项目。它是一个用Java写的全文索引引擎工具包，可以方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。2.Lucene的原理分析（1）全文检索的实现机制9Lucene的API接口设计的比较通用，输入输出结构都很像数据库的表=记录=字段，所以很多传统的应用的文件、数据库等都可以比较方便的映射到Lucene的存储结构和接口中。总体上看：可以先把Lucene当成一个支持全文索引的数据库系统。表3-4Lucene索引解析表关键词说明索引数据源doc(field1,field2.)doc(field1,field2.)indexer/_|LuceneIndex|-/searcher结果输出Hits(doc(field1,field2)doc(field1.)Document一个需要进行索引的“单元”，一个Document由多个字段组成Field字段Hits查询结果集，由匹配的Document组成（2）Lucene的索引效率通常书籍后面常常附关键词索引表（比如：北京：12,34页，上海：3,77页），它能够帮助读者比较快地找到相关内容的页码。而数据库索引能够大大提高查询的速度原理也是一样，想像一下通过书后面的索引查找的速度要比一页一页地翻内容高多少倍而索引之所以效率高，另外一个原因是它是排好序的。对于检索系统来说核心是一个排序问题。由于数据库索引不是为全文索引设计的，因此，使用like%keyword%时，数据库索引是不起作用的，在使用like查询时，搜索过程又变成类似于一页页翻书的遍历过程了，所以对于含有模糊查询的数据库服务来说，LIKE对性能的危害是极大的。如果是需要对多个关键词进行模糊匹配：like%keyword1%andlike%keyword2%.其效率也就可想而知了。所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制，将数据源（比如多篇文章）排序顺序存储的同时，有另外一个排好序的关键词列表，用于