基于中文分词的搜索引擎的设计与实现

毕业设计论文题目基于中文分词的搜索引擎的设计与实现毕业设计（论文）任务书毕业设计（论文）题目基于中文分词的搜索引擎的设计与实现毕业设计（论文）要求及原始数据（资料）1综述国内外搜索引擎技术研究现状；2深入了解搜索引擎的基本原理；3熟练掌握中文分词算法的原理与应用，训练基于LUCENE全文检索引擎工具包编写程序的能力；4设计并实现基于中文分词的搜索引擎；5训练检索文献资料和利用文献资料的能力；6训练撰写技术文档与学位论文的能力。毕业设计（论文）主要内容1综述搜索引擎的开发背景以及意义；2深入了解搜索引擎的基本原理；3了解中文分词算法的分类、特点，确定合适的中文分词算法。4熟悉基于LUCENE全文检索引擎工具包开发搜索引擎的帮助文档；5深入分析中文分词算法的原理并编码实现基于中文分词的搜索引擎；6测试开发的基于中文分词的搜索引擎是否符合需求；7对搜索引擎的搜索结果进行分析评价。学生应交出的设计文件（论文）1内容完整、层次清晰、叙述流畅、排版规范的毕业设计论文；2包括毕业设计论文、源程序等内容在内的毕业设计电子文档及其它相关材料。主要参考文献（资料）1李艳红校园网内中文搜索引擎的设计与实现D西安电子科技大学,20072谢兵土豆网视频搜索引擎系统的设计与实现D上海交通大学,20103刘兴建中文搜索引擎的应用、分析和比较J福建电脑,2010,114周君，王艳红一种基于词典的中文分词法的设计与实现J黑龙江科技信息,2008,255高磊，徐东平启发式算法在搜索引擎的应用J电脑知识与技术,2007,126卢亮，张博文搜索引擎原理、实践与应用M电子工业出版社，2007，557李颖，李志蜀，邓欢基于LUCENE的中文分词方法设计与实现J,2008,4558梁斌走进搜索引擎M电子工业出版社，2007，1912509彭波搜索引擎的混合索引技术J计算机工程与应用，2004，40（22）1810费红晓，康松林，朱小娟，等基于词频统计的中文分词研究J计算机工程与应用，2005，11（7）6911王莉云，王华，陈刚，等基于LUCENE的全文检索系统的设计与实现J计算机工程与设计，2007，28（24）6012LUCENEEB/OL2002HTTP/LUCENTAPACHEORG/JAVA/DOCS/INDEXHTML13WANGQINGBO,DAIYAFEINESHOTANINFRASTRUCTUREFORSCALABLEWIDEAREALOCATIONANDROUTING14ACRESPOANDHGARCIAMOLINAROUTINGINDICESFORPEERTOPEERSYSTEMSINICDCS,JULY200215SYLVIARATNASAMY,SCOTTSHENKER,IONSTOICAROUTINGALGORITHMSFORDHTSSOMEOPENQUESTIONSINIPTPS02,JANUARY200216CALLANJPANDMCONNELLQUERYBASEDSAMPLINGOFTEXTDATABASESACMTRANSACTIONSONINFORMATIONSYSTEMS,19297130,200117张秋余，张红，马彦宏基于概念的中文搜索引擎技术J计算机科学，2004（21）18余海燕，张仲义基于单汉字索引的全文检索系统的优化研究J中文信息学报，2001，15（4）1420专业班级软件1019班学生要求设计（论文）工作起止日期2014年3月17日2014年6月27日指导教师签字日期2014年3月17日教研室主任审查签字日期系主任批准签字日期摘要网络中的资源非常丰富，但是如何有效的搜索信息却是一件困难的事情。建立搜索引擎就是解决这个问题的最好方法。本文首先详细介绍了基于英特网的搜索引擎的系统结构，然后从网络机器人、索引引擎、WEB服务器三个方面进行详细的说明。为了更加深刻的理解这种技术，我使用JAVA编程技术实现了一个自己的搜索引擎基于中文分词的搜索引擎。基于中文分词的搜索引擎是从指定的WEB页面中按照超连接进行解析、搜索，并把搜索到的每条新闻进行索引后加入数据库。然后通过WEB服务器接受客户端请求后从索引数据库中搜索出所匹配的新闻。本人在介绍搜索引擎的章节中除了详细的阐述技术核心外还结合了基于中文分词的搜索引擎的实现代码来说明，图文并茂、易于理解。关键词搜索引擎；网络机器人；WEB服务器；中文分词ABSTRACTTHERESOURCESINTHEINTERNETAREABUNDANT,BUTITISADIFFICULTJOBTOSEARCHSOMEUSEFULINFORMATIONSOASEARCHENGINEISTHEBESTMETHODTOSOLVETHISPROBLEMTHISARTICLEFISTINTRODUCESTHESYSTEMSTRUCTUREOFSEARCHENGINEBASEDONTHEINTERNETINDETAIL,THENGIVESAMINUTEEXPLANATIONFORMSPIDERSEARCH,ENGINEANDWEBSERVERINORDERTOUNDERSTANDTHETECHNOLOGYMOREDEEPLY,IHAVEPROGRAMMEDANEWSSEARCHENGINEWITHJAVASKILLBYMYSELFTHENEWSSEARCHENGINEISEXPLAINEDANDSEARCHEDACCORDINGTOHYPERLINKFROMAAPPOINTEDWEBPAGE,THENINDEXSEVERYSEARCHEDINFORMATIONANDADDSITTOTHEINDEXDATABASETHENAFTERRECEIVINGTHECUSTOMERSREQUESTSFROMTHEWEBSERVER,ITSOONSEARCHSTHERIGHTNEWSFORMTHEINDEXENGINE,INTHECHAPTEROFINTRODUCINGSEARCHENGINE,ITISNOTONLYELABORATETHECORETECHNOLOGY,BUTALSOCOMBINEWITHTHEMODERNCODE,PICTURESINCLUDED,EASYTOUNDERSTANDKEYWORDSSEARCHENGINESPIDERSEARCH,WEBSERVERCHINESEANALYZER目录摘要IABSTRACTII第一章绪论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（二）IKANALYZER的分词处理过程32第六章搜索引擎的测试34一、测试目的与意义34二、测试过程34（一）中文分词测试34（二）搜索结果测试35三、测试结论36结论37一、论文总结37（一）网络机器人37（二）网页分析37（三）中文分词37（四）建立索引文件37（五）WEB服务器37（六）动态的扩展词库37二、进步的工作37（一）改善网络机器人使之行业化37（二）改善中文分词器38参考文献39致谢40外文原文41中文翻译48第一章绪论一、论文的研究背景面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。因此它也成为除了电子邮件以外最多人使用的网上服务。互联网络从早期的ARPANET到目前的INTERNET已经发展了近五十年，它的迅速发展和广泛普及导致网上信息爆炸性增长。据UNIVERSITYOFIOWA最近一项调查显示，截至2005年1月全球可以索引的网页已经达到至少115亿。如果这些信息能被有效地利用，互联网将是一个巨大的信息宝库。但由于INTERNET是一个开放、分布、异构的信息空间，INTERNET这个“数字时代的图书馆”并不像真正的图书馆那样支持有组织的信息管理和检索。它本身固有的3个特点已经明显地阻碍了人们充分使用INTERNET上的信息资源1INTERNET上的信息无组织、无固定结构、分布无规律性；2INTERNET是一个动态性极强的信息源；3INTERNET上的信息量每天呈指数增长，而对用户个体而言只有少数相关。由此看来，虽然INTERNET是一个广阔的信息海洋，但漫游其间而不迷失方向有时会是相当困难的。如何快速准确地在网上找到需要的信息已变得越来越重要。搜索引擎是基于上述原因而产生的，它以一定的策略在互联网中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从而起到信息导航的目的，是用户打开互联网这个信息宝库的一把钥匙。目前，关于搜索引擎的概念还没有一个明确的定义。可以从狭义和广义两个角度理解。从狭义的角度来说，搜索引擎由信息收集软件，索引数据库和查询接口三部分组成。信息收集软件从一个已知的文档集中读取信息，并检查这些文档的链接指针，找出新的信息空间，然后取回这些新空间中的文档，将它们加入到索引数据库。查询接口通过索引数据库为用户的查询请求提供服务。即搜索引擎指的是基于某种技术在整个网上自动执行网页全文搜索的网上指南工具。从广义的角度上讲，搜索引擎是因特网上的一类网站，这类网站与一般的网站不同的是它是提供查询，搜索的网站，或称查询站点，导航站点，即因特网上具有检索功能的网页。一般说来，搜索引擎由搜索器，索引器，检索器和用户接口等四个部分组成。搜索引擎的搜索器在网络中爬行，发现和搜集信息。索引器负责从搜索器采集地信息中抽取出索引项，用于表示文档以及生成文档库的索引表。检索器根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现用户相关性反馈机制。用户接口负责与用户交互。二、国内外研究现状搜索引擎是随着WEB信息的迅速增加而发展起来的，是一种网民查询互联网信息的搜索型工具，通过为用户提供信息检索服务，起到导航信息的目的。搜索引擎的基本概念出现于20世纪70年代，但它真正发展和应用却是90年代的事情，并在90年代中期得到快速的发展。目前网上的搜索引擎有160种以上，其中比较著名的7个全球性导航站有YAHOO，ALTAVISTA，LYCOS，HOTBOT，INFOSEEK,WEBCRAWLER,EXCITE。据CNNIC于2005年1月发布的统计资料，搜索引擎的使用己占到网络应用的650，并成为中国当前第二大互联网应用，仅次于收发EMAIL。搜索引擎技术伴随着WWW的发展是引人注目的。搜索引擎大约经历了三代的更新发展第一代搜索引擎出现于1994年。这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。在实现技术上也基本沿用较为成熟的IR（INFORMATIONRETRIEVAL）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。在1994年3月到4月，网络爬虫WORLDWEBWORMWWWW平均每天承受大约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个网页，平均速度是每秒485个网页，一天可以搜集超过4，000，000网页。搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。著名的因特网搜索引擎包括FIRSTSEARCH、GOOGLE、HOTBOT等。在中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务。目前的搜索引擎，每天使用爬虫在互联网上获取大量网页，这花去了大量的时间，随着WWW信息的指数增加，搜索引擎搜索速度慢，死链接太多，重复信息或不相关信息较多，难以满足人们的各种信息需求，搜索引擎将向智能化，精确化，交叉语言检索，多媒体检索，专业化等适应小型用户需求的方向发展。三、本文工作本文主要是完成了基于中文分词搜索引擎系统的设计与实现，主要完成了如下工作（1）网络机器人模块的设计与实现从网络上不断爬取网页，自动实现分析网页中包含的链接并且进入链接爬取网页。并且把爬取的网页保存在本地机器上并给网页编号。（2）网页链接抓取模块的设计与实现把网络机器人爬取的网页加以分析，去除网页中的控制命令和格式，只保留内容。（3）中文分词模块的设计与实现对网页分析后的内容进行中文切分词，同时在用户对索引进行检索时也会将用户输入的内容进行切分处理，从而到索引文件中找到相应的内容。（4）建立索引文件模块的设计与实现对切分词语分析之后的网页内容建立词索引。每个词如果出现在网页中，且这个词属于词典中的词，则把网页的相关内容写入倒排表。将词语在某篇文档中出现的具体位置写入辅助文件。（5）WEB服务器模块的设计与实现部署WEB应用，对用户输入的查询内容实现切分词语，根据切分后的词语，查找索引文件，对多关键词实现了内容的和运算,然后将搜索的内容排序输出。（6）动态的扩展词库模块的设计与实现可以向词库中添加单个新词，也可以批量的向词库中导入大量新词，可以避免重复添加。四、本文结构各章内容安排如下第一章绪论。本章主要介绍了本课题的研究意义，背景知识和中文分词搜索引擎的关键技术。第二章搜索引擎概述。本章主要介绍搜索引擎的定义，搜索引擎的分类，搜索引擎的工作原理，搜索引擎的发展趋势。第三章搜索引擎的原理。本章主要对搜索引擎的原理进行分析，为后期的搜索引擎的设计实现提供理论与思想基础，对搜索引擎的三大组成部分网络机器人、索引的建立与搜索和WEB服务器进行了详细介绍，并介绍了三大搜索引擎的工作流程，最后介绍了搜索引擎的主要指标及分析。第四章中文分词。本章主要介绍了中文分词技术在搜索引擎中的应用，并介绍了中文分词常用技术。第五章搜索引擎的设计与实现。本章主要介绍搜索引擎三大组成部分网络机器人、索引的建立与搜索和WEB服务器的设计与实现。第六章搜索引擎的测试。本章对已经实现的搜索引擎系统进行测试确保系统可以正常运行使用。第七章结论。对本课题的工作做总结，并提出下一步的工作内容。第二章搜索引擎概述一、搜索引擎的定义搜索引擎是一种在WEB上应用的软件系统，它以一定的策略在W曲上搜集和发现信息，在对信息进行处理和组织后，为用户提供WEB信息查询服务。从使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词语或者短语，然后很快返回一个可能和用户输入相关的信息列表常常会是很长一个列表，例如包含1万个条目。它包括信息搜集，信息整理和用户查询三部分。二、搜索引擎的分类（一）按检索工具发展过程分类按照检索工具的发展过程可分为第一代搜索引擎、第二代搜索引擎和下一代搜索引擎。1第一代搜索引擎第一代搜索引擎以ALTAVISTA、YAHOO和INFOSEEK为代表，出现于1994年前后，搜索结果的好坏往往用反馈结果的数量来衡量，也就是说，第一代搜索引擎“求全”。2第二代搜索引擎第二代搜索引擎以GOOGLE和DIRECTHIT为代表，还包括中国的百度、天网搜索等，这些引擎的主要特点是提高了查准率，可以用“求精”来描述。3下一代搜索引擎下一代搜索引擎目前尚无产品出现，只是处于研究和探讨阶段，有资料称下一代搜索引擎将是“求专“和“求易“，可以理解成专业化和智能化；也有学者称下一代搜索引擎的方向是智能化和个性化。（二）按检索范围分类按照提供的信息服务范围与用途的不同，搜索引擎可分为综合性搜索引擎和专业性搜索引擎。1综合性搜索引擎即综合性的信息检索系统，利用它几乎可以检索任何方面的信息资源，但有时会出现字形相同而实际上互不相关的内容，或因检出的内容太泛而无法一一过目。2专业性搜索引擎则是专业信息机构根据专业需求，将因特网上资源进行筛选整理、新组织而形成的专业性的信息检索系统。专业性搜索引擎能针对用户特定需求来提供信息，特定用户只要登录到相应的搜索引擎即可迅速、准确地找到符合要求的精准信息。因此，高质量专业性搜索引擎是学科专业领域的研究人员获取网上信息资源的重要工具，是因特网搜索引擎研究开发的方向。（三）按工作方式分类按照其工作方式主要可分为三种，分别是全文搜索引擎、目录索引类搜索引擎和元搜索引擎。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网络机器人程序图21系统结构图（二）搜索引擎的工作流程搜索引擎并不真正去搜索互联网，它搜索的实际上是预先整理好的网页索引数据库，搜索引擎也不能真正理解网页上的内容，它只能机械的匹配网页上的文字。真正意义上的搜索引擎，通常指的是收集了互联网上几千万到几十亿个网页并对网页中的每一个文字即关键词进行索引，建立索引数据库的全文搜索引擎。当用户查找某个关键词的时候，所有在页面内容中包含了该关键词的网页都将作为搜索结果被搜出来。在经过复杂的算法进行排序后，这些结果将按照与搜索关键词的相关度高低，依次排列。现在的搜索引擎已普遍使用超链分析技术，除了分析索引网页本身的文字，还分析索引所有指向该网页的链接的URL、ANCHORTEXT、甚至链接周围的文字。所以，有时候，即使某个网页A中并没有某个词比如“恶魔撒旦”，但如果有别的网页B用链接“恶魔撒旦”指向这个网页A，那么用户搜索“恶魔撒旦”时也能找到网页A。而且，如果有越多网页C、D、E、F用名为“恶魔撒旦”的链接指向这个网页A，或者给出这个链接的源网页B、C、D、E、F越优秀，那么网页A在用户搜索“恶魔撒旦”时也会被认为更相关，排序也会越靠前。第三章搜索引擎的原理一、网络机器人（一）什么是网络机器人网络机器人又称为SPIDER程序，是一种专业的BOT程序。用于查找大量的WEB页面。它从一个简单的WEB页面上开始执行，然后通过其超链接在访问其他页面，如此反复理论上可以扫描互联网上的所有页面。基于因特网的搜索引擎是SPIDER的最早应用。例如搜索巨头GOOGLE公司，就利用网络机器人程序来遍历WEB站点，以创建并维护这些大型数据库。网络机器人还可以通过扫描WEB站点的主页来得到这个站点的文件清单和层次机构。还可以扫描出中断的超链接和拼写错误等。（二）网络机器人的结构分析INTERNET是建立在很多相关协议基础上的，而更复杂的协议又建立在系统层协议之上。WEB就是建立在HTTPHYPERTEXTTRANSFERPROTOCOL协议基础上，而HTTP又是建立在TCP/IPTRANSMISSIONCONTROLPROTOCOL/INTERNETPROTOCOL协议之上，它同时也是一种SOCKET协议。所以网络机器人本质上是一种基于SOCKET的网络程序。1如何解析HTML因为WEB中的信息都是建立在HTML协议之上的，所以网络机器人在检索网页时的第一个问题就是如何解析HTML。在解决如何解析之前，先来介绍下HTML中的几种数据。表31HTML数据类型表数据类型说明文本除了脚本和标签之外的所有数据注释程序员留下的说明文字，对用户是不可见的简单标签由单个表示的HTML标签开始标签和结束标签用来控制所包含的HTML代码我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进行解析即可。（1）超连接标签超连接定义了WWW通过INTERNET链接文档的功能。他们的主要目的是使用户能够任意迁移到新的页面，这正是网络机器人最关心的标签。（2）图像映射标签图像映射是另一种非常重要的标签。它可以让用户通过点击图片来迁移到新的页面中。（3）表单标签表单是WEB页面中可以输入数据的单元。许多站点让用户填写数据然后通过点击按钮来提交内容，这就是表单的典型应用。（4）表格标签表格是HTML的构成部分，通常用来格式化存放、显示数据。我们在具体解析这些HTML标签有两种方法通过JAVATM中的SWING类来解析或者通过BOT包中的HTMLPAGE类来解析，本人在实际编程中采用后者。BOT包中的HTMLPAGE类用来从指定URL中读取数据并检索出有用的信息。下面给出该类几种重要的方法。表32HTMLPAGE类方法列表类方法说明声明HTMLPAGE构造函数构造对象并指定用于通讯的HTTP对象PUBLICHTMLPAGEHTTPHTTPGETFORMS方法获取最后一次调用OPEN方法检索到的表单清单PUBLICVECTORGETFORMSGETHTTP方法获取发送给构造函数的HTTP对象PUBLICHTTPGETHTTPGETIMAGE方法获取指定页面的图片清单PUBLICVECTORGETIMAGEGETLINKS方法获取指定页面的连接清单PUBLICVECTORGETLINKSOPEN方法打开一个页面并读入该页面，若指定了回调对象则给出所有该对象数据PUBLICVOIDOPENSTRINGURL,HTMLEDITORKITPARSERCALLBACKA2SPIDER程序结构网络机器人必须从一个网页迁移到另一个网页，所以必须找到该页面上的超连接。程序首先解析网页的HTML代码，查找该页面内的超连接然后通过递归和非递归两种结构来实现SPIDER程序。（1）递归结构递归是在一个方法中调用自己本身的程序设计技术。虽然比较容易实现但耗费内存且不能使用多线程技术，故不适合大型项目。（2）非递归结构这种方法使用队列的数据结构，当SPIDER程序发现超连接后并不调用自己本身而是把超连接加入到等待队列中。当SPIDER程序扫描完当前页面后会根据制定的策略访问队列中的下一个超连接地址。虽然这里只描述了一个队列，但在实际编程中用到了四个队列，他们每个队列都保存着同一处理状态的URL。表33队列详解队列说明等待队列在这个队列中，URL等待被SPIDER程序处理。新发现的URL也被加入到这个队列中处理队列当SPIDER程序开始处理时，他们被送到这个队列中错误队列如果在解析网页时出错，URL将被送到这里。该队列中的URL不能被移入其他队列中完成队列如果解析网页没有出错，URL将被送到这里。该队列中的URL不能被移入其它队列中在同一时间URL只能在一个队列中，我们把它称为URL的状态。发现URL等待队列运行队列完成队列错误队列完成URL图31队列变化过程图以上的图表示了队列的变化过程，在这个过程中，当一个URL被加入到等待队列中时SPIDER程序就会开始运行。只要等待队列中有一个网页或SPIDER程序正在处理一个网页，程序就会继续他的工作。当等待队列为空并且当前没有任何网页时，SPIDER程序就会停止它的工作。二、索引的建立与搜索一索引的建立与搜索过程网络机器人将遍历得到的页面存放在临时数据库中，如果通过SQL直接查询信息速度将会难以忍受。为了提高检索效率，需要建立索引，按照倒排文件的格式存放。如果索引不及时跟新的话，用户用搜索引擎也不能检索到。用户输入搜索条件后搜索程序将通过索引数据库进行检索然后把符合查询要求的数据库按照一定的策略进行分级排列并且返回给用户。二基于LUCENE的索引与搜索1什么是LUCENE全文检索LUCENE是JAKARTAAPACHE的开源项目。它是一个用JAVA写的全文索引引擎工具包，可以方便的嵌入到各种应用中实现针对应用的全文索引/检索功能。2LUCENE的原理分析（1）全文检索的实现机制LUCENE的API接口设计的比较通用，输入输出结构都很像数据库的表记录字段，所以很多传统的应用的文件、数据库等都可以比较方便的映射到LUCENE的存储结构和接口中。总体上看可以先把LUCENE当成一个支持全文索引的数据库系统。表34LUCENE索引解析表关键词说明索引数据源DOCFIELD1,FIELD2DOCFIELD1,FIELD2INDEXER/_|LUCENEINDEX|/SEARCHER结果输出HITSDOCFIELD1,FIELD2DOCFIELD1DOCUMENT一个需要进行索引的“单元”，一个DOCUMENT由多个字段组成FIELD字段HITS查询结果集，由匹配的DOCUMENT组成（2）LUCENE的索引效率通常书籍后面常常附关键词索引表（比如北京12,34页，上海3,77页），它能够帮助读者比较快地找到相关内容的页码。而数据库索引能够大大提高查询的速度原理也是一样，想像一下通过书后面的索引查找的速度要比一页一页地翻内容高多少倍而索引之所以效率高，另外一个原因是它是排好序的。对于检索系统来说核心是一个排序问题。由于数据库索引不是为全文索引设计的，因此，使用LIKE“KEYWORD“时，数据库索引是不起作用的，在使用LIKE查询时，搜索过程又变成类似于一页页翻书的遍历过程了，所以对于含有模糊查询的数据库服务来说，LIKE对性能的危害是极大的。如果是需要对多个关键词进行模糊匹配LIKE“KEYWORD1“ANDLIKE“KEYWORD2“其效率也就可想而知了。所以建立一个高效检索系统的关键是建立一个类似于科技索引一样的反向索引机制，将数据源（比如多篇文章）排序顺序存储的同时，有另外一个排好序的关键词列表，用于存储关键词文章映射关系，利用这样的映射关系索引关键词出现关键词的文章编号，出现次数（甚至包括位置起始偏移量，结束偏移量），出现频率，检索过程就是把模糊查询变成多个可以利用索引的精确查询的逻辑组合的过程。从而大大提高了多关键词查询的效率，所以，全文检索问题归结到最后是一个排序问题。由此可以看出模糊查询相对数据库的精确查询是一个非常不确定的问题，这也是大部分数据库对全文检索支持有限的原因。LUCENE最核心的特征是通过特殊的索引结构实现了传统数据库不擅长的全文索引机制，并提供了扩展接口，以方便针对不同应用的定制。可以通过一下表格对比一下数据库的模糊查询表35LUCENE索引与数据库对比表关键词LUCENE全文索引引擎数据库索引将数据源中的数据都通过全文索引一一建立反向索引对于LIKE查询来说，数据传统的索引是根本用不上的。数据需要逐个便利记录进行GREP式的模糊匹配，比有索引的搜索速度要有多个数量级的下降。匹配效果通过词元TERM进行匹配，通过语言分析接口的实现，可以实现对中文等非英语的支持。使用LIKE“NET“会把NETHERLANDS也匹配出来，多个关键词的模糊匹配使用LIKE“COMNET“就不能匹配词序颠倒的XXXNETXXXCOM匹配度有匹配度算法，将匹配程度（相似度）比较高的结果排在前面。没有匹配程度的控制比如有记录中NET出现5词和出现1次的，结果是一样的。结果输出通过特别的算法，将最匹配度最高的头100条结果输出，结果集是缓冲式的小批量读取的。返回所有的结果集，在匹配条目非常多的时候（比如上万条）需要大量的内存存放这些临时结果集。可定制性通过不同的语言分析接口实现，可以方便的定制出符合应用需要的索引规则（包括对中文的支持）没有接口或接口复杂，无法定制结论高负载的模糊查询应用，需要负责的模糊查询的规则，索引的资料量比较大使用率低，模糊匹配规则简单或者需要模糊查询的资料量少三、WEB服务器客户一般通过浏览器进行查询，这就需要系统提供WEB服务器并且与索引数据库进行连接。客户在浏览器中输入查询条件，WEB服务器接收到客户的查询条件后在索引数据库中进行查询、排列然后返回给客户端。WEB服务器是在网络中为实现信息发布、资料查询、数据处理等诸多应用搭建基本平台的服务器。WEB服务器如何工作在WEB页面处理中大致可分为三个步骤，第一步，WEB浏览器向一个特定的服务器发出WEB页面请求；第二步，WEB服务器接收到WEB页面请求后，寻找所请求的WEB页面，并将所请求的WEB页面传送给WEB浏览器；第三步，WEB服务器接收到所请求的WEB页面，并将它显示出来。TOMCAT是一个开放源代码、运行SERVLET和JSPWEB应用软件的基于JAVA的WEB应用软件容器。TOMCAT由APACHEJAKARTA子项目支持并由来自开放性源代码JAVA社区的志愿者进行维护。TOMCATSERVER是根据SERVLET和JSP规范进行执行的，因此我们就可以说TOMCATSERVER也实行了APACHEJAKARTA规范且比绝大多数商业应用软件服务器要好。四、搜索引擎的工作流程（一）全文搜索引擎工作流程全文搜索引擎的“网络机器人或“网络蜘蛛”是一种网络上的软件，它遍历W曲空间，能够扫描一定P地址范围内的网站，并沿着网络上的链接从一个网页到另一个网页，从一个网站到另一个网站采集网页资料。它为保证采集的资料最新，还会回访已抓取过的网页。网络机器人或网络蜘蛛采集的网页，还要有其它程序进行分析，根据一定的相关度算法进行大量的计算建立网页索引，才能添加到索引数据库中。我们平时看到的全文搜索引擎，实际上只是一个搜索引擎系统的检索界面，当你输入关键词进行查询时，搜索引擎会从庞大的数据库中找到符合该关键词的所有相关网页的索引，并按一定的排名规则呈现给我们。不同的搜索引擎，网页索引数据库不同，排名规则也不尽相同，所以，当我们以同一关键词用不同的搜索引擎查询时，搜索结果也就不尽相同。搜索引擎的工作流程，可以看作三步从互联网上抓取网页一建立索引数据库一在索引数据库中搜索排序。1从互联网上抓取网页利用能够从互联网上自动收集网页的SPIDER系统程序，自动访问互联网，并沿着任何网页中的所有也爬到其它网页，重复这过程，并把爬过的所有网页收集回来。2建立索引数据库由分析索引系统程序对收集回来的网页进行分析，提取相关网页信息包括网页所在URL、编码类型、页面内容包含的所有关键词、关键词位置、生成时间、大小、与其它网页的链接关系等，根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面文字中及超链中每一个关键词的相关度或重要性，然后用这些相关信息建立网页索引数据库。3在索引数据库中搜索排序当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相关网页针对该关键词的相关度已经算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。最后，由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。搜索引擎的SPIDER一般要定期重新访问所有网页各搜索引擎的周期不同，可能是几天、几周或几个月，也可能对不同重要性的网页有不同的更新频率，更新网页索引数据库，以反映出网页文字的更新情况，增加新的网页信息，去除死链接，并根据网页文字和链接关系的变化重新排序。这样，网页的具体文字变化情况就会反映到用户查询的结果中。（二）目录搜索引擎和全文搜索引擎一样，分类目录的整个工作过程也同样分为收集信息、分析信息和查询信息三部分，只不过分类目录的收集、分析信息两部分主要依靠人工完成。分类目录一般都有专门的编辑人员，负责收集网站的信息。随着收录站点的增多，现在一般都是由站点管理者递交自己的网站信息给分类目录，然后由分类目录的编辑人员审核递交的网站，以决定是否收录该站点。如果该站点审核通过，分类目录的编辑人员还需要分析该站点的内容，并将该站点放在相应的类别和目录中。所有这些收录的站点同样被存放在一个“索引数据摩中。用户在查询信息时，可以选择按照关键词搜索，也可按分类目录逐层查找。如以关键词搜索，返回的结果跟全文搜索引擎一样，也是根据信息关联程度排列网站。需要注意的是，分类目录的关键词查询，它的查询结果也只是被收录网站首页的UI也地址，而不是具体的页面。分类目录就像一个电话号码薄一样，按照各个网站的性质，把其网址分门别类排在一起，大类下面套着小类，一直到各个网站的详细地址，一般还会提供各个网站的内容简介，用户不使用关键词也可进行查询，只要找到相关目录，就完全可以找到相关的网站注意是相关的网站，而不是这个网站上某个网页的内容，某一目录中网站的排名一般是按照标题字母的先后顺序或者收录的时间顺序决定的。五、搜索引擎的主要指标及分析搜索引擎的主要指标有响应时间、召回率、准确率、相关度等。这些指标决定了搜索引擎的技术指标。搜索引擎的技术指标决定了搜索引擎的评价指标。好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。表36搜索引擎技术指标表关键词说明召回率一次搜索结果中符合用户要求的数目与用户查询相关信息的总数之比准确率一次搜索结果中符合用户要求的数目与该次搜索结果总数之比相关度用户查询与搜索结果之间相似度的一种度量精确度对搜索结果的排序分级能力和对垃圾网页的抗干扰能力第四章中文分词众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子IAMASTUDENT，用中文则为“我是一个学生”。计算机可以很简单通过空格知道STUDENT是一个单词，但是不能很容易明白“学“、“生“两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称之为切词。我是一个学生，分词的结果是我，是，一个，学生。一、中文分词和搜索引擎中文分词到底对搜索引擎有多大影响对于搜索引擎来说，最重要的并不是找到所有结果，因为在上百亿的网页中找到所有结果没有太多的意义，没有人能看得完，最重要的是把最相关的结果排在最前面，这也称为相关度排序。中文分词的准确与否，常常直接影响到对搜索结果的相关度排序。二、中文分词技术中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解其处理过程就是分词算法。三、中文分词算法现有的分词算法可分为三大类基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。（一）基于字符串匹配的分词方法这种方法又叫做机械分词方法，它是按照一定的策略将要分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功识别出一个词。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大最长匹配和最小最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下1正向最大匹配法由左到右的方向；2逆向最大匹配法由右到左的方向；3最少切分使每一句中切出的词数最小。还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配错误率是1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。一种方法是改进扫描方式，称为特征扫描或标志切分，优先在将要分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进行机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。（二）基于理解的分词方法这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试验阶段。（三）基于统计的分词方法从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字如果同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的“等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典常用词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。海量科技的分词算法就采用“复方分词法，所谓复方，相当于用中药中的复方概念，即用不同的药材综合起来去医治疾病，同样，对于中文词的识别，需要多种算法来处理不同的问题。（四）歧义识别与新词识别有了成熟的分词算法，是否就能容易的解决中文分词的问题呢事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。1歧义识别歧义是指同样的一句话，可能有两种或者更多的切分方法。例如表面的，因为“表面”和“面的”都是词，那么这个短语就可以分成“表面的”和“表面的“。这种称为交叉歧义。像这种交叉歧义十分常见。由于没有人的知识去理解，计算机很难知道到底哪个方案正确。交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整个句子来判断了。例如，在句子“这个门把手坏了“中，“把手“是个词，但在句子“请把手拿开“中，“把手”就不是一个词；在句子“将军任命了一名中将”中，“中将“是个词，但在句子“产量三年中将增长两倍”中，“中将”就不再是词。这些词计算机又如何去识别如果交叉歧义和组合歧义计算机都能解决的话，在歧义中还有一个难题，是真歧义。真歧义意思是给出句话，由人去判断也不知道哪个应该是词，哪个应该不是词。例如“乒乓球拍卖完了“，可以切分成“乒乓球拍，卖完了”、也可切分成“乒乓球，拍卖完了”，如果没有上下文其他的句子，恐怕谁也不知道“拍卖”在这里算不算一个词。2新词识别新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但又确实能称为词的那些词。最典型的是人名，人可以很容易理解句子“王军虎去广州了“中，“王军虎”是个词，因为是一个人的名字，但要是让计算机去识别就困难了。如果把“王军虎”作为一个词收录到字典中去，全世界有那么多名字，而且每时每刻都有新增的人名，收录这些人名本身就是一项巨大的工程。即使这项工作可以完成，还是会存在问题，例如在句子“王军虎头虎脑的”中，“王军虎”还能不能算词新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。（五）正向迭代最细粒度切分算法正向迭代最细粒度切分算法是一个开源分词项目IKANALYER分词器的切分算法，其中分词工具类IKQUERYPARSER起着至关重要的作用，它对搜索关键词采用从最大词到最小词层层迭代检索方式切分，比如搜索词“中华人民共和国成立了”，首先到词库中检索该搜索词中最大分割词，即分割为“中华人民共和国”和“成立了”，然后对“中华人民共和国”切分为“中华人民”和“人民共和