[硕士论文精品]智能中文搜索引擎若干关键技术的研究与实现

浙江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现摘要随着INTCMET的快速发展，WEB信息的迅速增加，人们越来越依赖于搜索引擎来获取互联网上有用的信息。目前传统中文搜索引擎系统一般都采用关键词匹配模式，没有很好地解决关键词跟网页之IIJ的相关性；同时在搜索推荐词的生成方法上，也往往只是在用户搜索关键词上加入前缀、后缀字符串作为相应的推荐词，没有深入到语义理解层次，不能很好地反映用户真正意图，智能化程度较低。因此，如何更好地理解中文网页信息、改进搜索关键词与网页的相关性、提供基于语义联想的搜索推荐词已成为新一代智能中文搜索引擎系统亟待解决的若干核心问题。该文对智能中文搜索引擎系统中的若干关键技术进行了较深入的研究，其研究内容主要包含以下几点1设计了一种类TILE树的高效词典组织结构。把中文分词过程分成两个阶段，在第一阶段采用BIGRAM模型并辅以一定的规则，在第二阶段采用基于词的最大正向匹配算法，最后把这两个阶段的结果合并，较好地解决了汉词切分中一直存在的歧义现象难以排除、新词识别困难等难题。实验结果显示词典模块达到了较快的切分速度和较高的切分准确率，这为高质量概念词的产生和后续网页处理提供了前提；2给出了一种基于语义联想的搜索推荐词生成方法，该方法基于概念集群的思想，能够有效地引导用户搜索，有别于传统搜索引擎系统的搜索推荐词生成方法，扩大了搜索的深度和外延；提出了一种新的网页排序算法，该算法基于系统的概念集群和关键词对网页的RANK值权重值，较好地反映了用户搜索关键词与网页的相关性；同时使用同义词词林中文语料库，对用户查询进行优化，实现了同义或近义词提示功能，丰富了用户的搜索体验，从而提升了搜索引擎系统的智能性；3设计了智能中文搜索引擎系统的总体框架，给出了具体的实现方案，并对海量数据环境下PAGERANK的计算、概念集群的形成、索引的生成提出了一些改进方法，最后在实际运营的大型服务器集群上实现了一个原型系统，并给出了详细的实验结果。关键词中文搜索引擎，中文分词，TILE树，概念集群，网页排名浙江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现ABSTRACTWITHTHERAPIDDEVELOPMENTOFHLTEMET，SEARCHENGINEHASBECOMEANECESSARYTOOLFORPEOPLEWHOWANTTOOBTAININFORMATIONFROMINTERACTATPRESENT，MOSTOFTHETRADITIONALSEARCHENGINESAREBASEDONTHEMATCHINGOFKEYWORDS，WHICHCALLTSOLVETHEPROBLEMOFASSOCIATIONSBETWEENWEBPAGEANDKEYWORDEFFICIENTLY；ASTOTHEWAYOFRELEVANTTERMSUGGESTION，TRADITIONALSEARCHENGINESMAKEITBYADDINGPREFIXORSUFFIXTOTHESEARCHINGKEYWORDSTHISAPPROACHDOESNTROACHTHELEVELOFSEMANTICUNDERSTANDINGITCALLTREFLECTTHEUSERSPURPOSEWELLANDNEEDSIMPROVINGSOHOWTOUNDERSTANDTHECHINESEWEBINFORMATIONWELLANDIMPROVETHERELATIVITYBETWEENKEYWORDANDWEBPAGE，ASWELLASPROVIDEASEMANTICWAYOFRELEVANTTERMSUGGESTIONHAVEALREADYBECOMESEVERALKEYISSUESOFNOVELINTELLIGENTCHINESESEARCHENGINEWHICHNEEDTOBESOLVEDIMPERATIVELYWEHAVEAFURTHERSTUDYONINTELLIGENTCHINESESEARCHENGINESYSTEM，ANDIMPLEMENTSEVERALKEYTECHNOLOGIESONITTHEMAININNOVATIONSOFTHESISAREASFOLLOWS1DESIGNATRIELIKEDATASTRUCTUREFORCHINESEWORDSEGMENTATIONDICTIONARYPROPOSEANEWAPPROACHFORCHINESEWORDSEGMENTATIONTHEPROCESSISSUBDIVIDEDINTOTWOPHASESINTHEFIRSTPHASE，WECOMPLETEAMBIGUITYELIMINATIONANDNAMEENTITYIDENTIFICATIONTASK，USINGBIGRAMMODELTOGETHERWITHCERTAINRULESINTHESECONDPHASE，WEACHIEVETHEIDENTIFICATIONOFNEWWORDS，USINGMAXIMUMMATCHINGMETHODOUREXPERIMENTALRESULTSHOWSTHATTHESCHEMEIMPROVESTHEPERFORMANCEANDPRECISIONOFTHEDICTIONARYGREANY，WHICHPROVIDESPREMISEOFHIGHQUALITYCONCEPTWORDGENERATINGANDFOLLOWINGWEBPROCESSING2PUTFORWARDAREFRESHWAYOFRELEVANTTERMSUGGESTIONITISBASEDONTHINKINGOFCONCEPTCLUSTER,WHICHISDIFFERENTFROMTHETRADITIONALSEARCHENGINESBYUSINGTHERESULTOFCONCEPTCLUSTERANDTHEKEYWORDSWEIGHTT0WEBPAGESWEPRESENTANEWRANKALGORITHMFORWEBPAGES，WHICHWECALLCCRCONCEPTCLUSTERRANKOUREXPERIMENTALRESULTSHOWSTHATITREFLECTSTHERELATIVITYBETWEENKEYWORDANDWEBPAGEWELLANDGETSTHERETRIEVALRESULTONSEMANTICLEVEL，EXPANDINGTHEDEPTHANDWIDTHOFRETRIEVALASWELLINTHEMEANTIMEWEOPTIMIZEUSERQUERYMODULEBYUSINGSYNONYMWORDLISTS，WHICHACHIEVESSYNONYMOUSTIPSFUNCTION3DESIGNTHEFRAMEWORKOFTHEINTELLIGENTCHINESESEARCHENGINESYSTEM，OFFERINGAPOSSIBLEIMPLEMENTALSCHEME，ANDALSOPROPOSESOMEREVISEDALGORITHMFORPAGERANKCOMPUTE，CONCCPTCLUSTERGENERATIONANDINDEXCONSTRUCTIONINTHEMASSIVEDATAENVIRONMENTFINALLYWEIMPLEMENTAPROTOTYPESYSTEMONTHELARGEPRACTICALSERVERCLUSTERSANDGIVETHEDETAILEDEXPERIMENTALRESULT望塑坚查堂堡主兰垡堡壅塑堂皇塞堡窭苎堇王羞堡垫查堕旦塞兰塞翌KEYWORDSCHINESESEARCHENGINE，CHINESEWORDSEGMENTATION，TRIETREE，CONCEPTCLUSTER,PAGERANKI浙江大学硕上学位论文智能中文搜索引擎若十关键技术的研究与实现11研究背景第一章绪论随着互联网技术的不断发展以及存储设备价格的不断下降，越来越多的信息被放到互联网上，人们越来越依赖搜索引擎来获取互联网上有用的信息，对搜索引擎的研究已成为信息检索领域研究的热点。出于搜索引擎系统涉及人工智能、信息检索、数据挖掘、计算机网络、自然语言处理等多领域的知识和技术，所以对搜索引擎的开发研究是一项具有挑战性、综合性的工作。目前，主流搜索引擎系统一般都采用基于关键词匹配的方式来进行信息检索，这种方式往往不能揭示信息之间的语义信息，导致系统的查全率和查准率不是很高，对用户的一个查询请求，搜索引擎系统一般都会返回大量无关的匹配信息，用户需要在这个返回结果中进行二次查找，负担比较重。如何更好地理解用户查询，改善查询关键词与网页的相关性，使搜索引擎更加智能化，将是以后搜索引擎技术发展的一个主要方向。目前对智能化的研究，主要有以下两种思路一种是朝着语义理解的方向，出现了基于本体论或者语义网的概念检索模型；另一种是通过进一步提炼用户的需求，多次和用户进行交互逐步求精来改善查询效果。12研究意义与目的目前主流搜索引擎在排序算法上往往只考虑网页的链接关系、关键词在网页中出现的次数、关键词在网页中位置信息来判断搜索关键词对网页的相关性，只停留在表面的一些特征分析上，没有深入到语义理解层次。对用户的查询请求也一般采用纯关键词匹配模式用户输入A词，那么只返回包含A词的网页；用户输入B词，同样只返回包含B词的网页；用户同时输入A、B两个关键词时，那么返回同时包含A、B两个词的网页，当不存在这样的网页时，那么要么返回包含A词的网页，要么返回包含B词的网页。这种模式一方面使得搜索引擎系统返回大量与用户真实需求无关的匹配信息，用户需要在这些返回结果中进行二次查找，负担比较重；另一方面用户输入A词，可能他想要的结果中并不包含A词，而只是跟A词语义相关。比如说用户输入“恐怖分子”这个关键词，但有网页是介绍本拉登的一些破坏行动，网页中并没有出现“恐怖分子”这个关键词，而这可能就是用户真正想要的结果，目前的搜索引擎就无法找到该网页。同时，在搜索推荐词的生成方式上，主流搜索引擎系统大都是在搜索关键词江大学硕士学位论文智能中文搜索引擎若十关键技术的研究与实现基础上加入前缀、后缀字符串作为新的搜索推荐词，比如说在百度中搜索“浙江大学”这个关键词，那么它给出的搜索推荐词为“浙江师范大学”、“浙江工业大学”、“浙江大学研究生院”等，这主要是根据数据库中历史查询记录得到关键词对应的推荐词，手工的成分很多，它没有深入到语义理解层次，不能很好地反映用户真正意图，智能化程度较低。另外，目前主流搜索引擎系统往往不能很好地处理中文语言中存在的一词多义、多词一义现象，比如说用户输入“计算机”，那么包含“电脑”的网页是不会被检索到的。因此，如何更好地理解中文网页信息、改进搜索关键词与网页的相关性、提供基于语义联想的搜索推荐词引导用户搜索已成为新一代智能中文搜索引擎系统亟待解决的若干核心问题。本文对智能中文搜索引擎系统中的若干关键技术进行了较深入的研究，给出了一种新的搜索推荐词生成方法；提出了一种基于语义理解的新的网页排序算法，并对用户查询进行了优化。13论文组织本文共分七章，主要结构和内容如下第一章重点介绍了本文的研究背景和研究意义。第二章重点介绍了搜索引擎系统的分类及其关键技术，并对当前搜索引擎系统的现状进行了分析。同时介绍了智能中文搜索引擎系统目前的研究方法。第三章重点介绍了在智能中文搜索引擎系统中有着重要作用的词典模块的设计与实现，包括词典组织结构、汉词切分算法的设计与实现等内容，并给出了详细的实验结果。第四章重点介绍了概念集群的建立、维护以及搜索推荐词的生成等工作，并给出了概念集群的部分实验结果。同时详细介绍了索引模块的设计工作。第五章重点介绍了几种比较典型的网页排序算法，提出了一种新的网页排序算法CCR，并用同义词词林语料库对用户查询进行了优化。第六章重点介绍了智能中文搜索引擎系统的总体框架和具体处理流程，并对海量数据环境下概念集群的形成、索引的生成提出了一些改进方法，最后在实际运营的大型服务器集群上实现了一个原型系统，并给出了详细的实验结果。第七章对本文所做工作进行了总结和展望。最后是参考文献和致谢。2浙江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现第二章搜索引擎分类及其关键技术概述随着互联网信息的快速增长，人们越来越依赖搜索引擎来获取互联网上有用的信息。据中国互联网信息中心CNNIC对2005年中国搜索引擎市场的的调查报告显示，搜索引擎已经成为继电子邮件服务后互联网上的第二大网络服务，其中，大概有55左右的用户每天都会使用搜索引擎，39左右的用户每天多次使用搜索引擎，80左右的用户则每个星期至少使用一次搜索引擎，可见，人们越来越离不开搜索弓I擎。同时，人们对搜索引擎系统的要求也越来越高。因此，了解搜索引擎的分类、原理、主要的技术、发展趋势还是很有必要的。21搜索引擎分类目前搜索引擎系统根据实现的技术原理主要可以分为以下三大类1目录式搜索引擎目录式搜索引擎，也被称为第一代搜索弓L擎，典型代表是YAHOO。它的工作原理是把网页信息按照不同的类别划分到不同的目录下，在每个目录下面标出了归于这个类别网页的名称、网页的URL以及网页内容的简单描述。在查询阶段，用户顺着分类目录，逐层查找就能准确定位到要找的网页。优点是由于目录的构建一般由手工完成，所以分类比较准确，方便用户查询，搜索出来的结果往往比较准确。这一类搜索引擎一般提供直接关键词检索和目录导航两种方式。缺点是由于分类过程大都由手工完成，因此，搜集的网页是有限的，并且，分类目录的更新比较慢，更新的代价也比较大。2全文搜索引擎全文搜索引擎，也被称为第二代搜索引擎，典型代表是GOOGLE和BAIDU。人们一般所说的搜索引擎就是指这类搜索引擎，这类搜索引擎是目前主流的搜索引擎。它的工作原理是用网络蜘蛛SPIDER从互联网上把原始的网页抓取下来，放到本地数据库上，然后对这些原始网页进行加工处理，在后台建立网页索引数据库。在查询阶段，系统在后台索引数据库中查找与用户搜索关键词匹配的网页，对这些匹配网页按一定的排序算法进行排序处理，然后把排序值高的前K张网页结果返回给用户，它是一种面向网页全文的搜索方式。优点它不需要人工干预，网页更新速度快，被索引的网页数目多，这样大大提高了信息的查全率。毫浙江大学硕士学位论文智能中立搜索引擎若干关键技术的研究与实现缺点由于SPIDER抓取下来的网页是海量的，因此索引库的规模也是很庞大的，并且它的规模需要不断地扩大，这就带来了很多技术难题。同时，随着索引网页数目的不断增加，信息的查全率是有了较大地提高，但查准率往往得不到保证。另外，SPIDER的工作方式一定程度上会加重网络和被访问网页服务器的负担。3元搜索引擎元搜索引擎也被称为搜索引擎的搜索引擎。它调用前面两类搜索引擎系统返回的结果，并对这些结果进行优化生成自己的结果返回给用户，典型代表是DOGPILE、VIVISIMO、BBMAO。它的工作原理是对用户的查询请求，调用多个独立的搜索引擎，然后对多个搜索引擎返回的结果，进行去重、重排序等二次加工，并注明结果来源的搜索引擎名字，把处理结果返回给用户。一般由搜索请求提交、搜索接口代理、搜索结果显示三部分组成。优点这类搜索引擎一般不存储索引库，所以硬件的代价比较小，而且由于它返回的结果是由多个独立的搜索引擎加工、整理得到，所以信息的查全率比较高。缺点由于每种搜索引擎采用的排序技术不同，所以对由多个独立的搜索引擎返回的结果很难有一个准确的评价体系，这就导致了信息的查准率不能得到有效的保证，同时，由于建立在各个独立的搜索引擎基础上，使得这类搜索引擎的查询速度没有全文搜索引擎快。22中文搜索引擎关键技术概述前面已经介绍了搜索引擎的种类以及各自的原理，下面重点介绍一下全文中文搜索引擎系统人们常说的搜索引擎系统的工作流程和关键技术，为了叙述方便，以下简称中文搜索引擎系统为搜索引擎系统。搜索引擎系统一般由抓取网页、加工整理、查询服务三个阶段构成。下图21给出了一般搜索引擎系统的处理流程。4I江人学硕IJ学位论文智能中文搜索引擎若干关键技术的研究与实现图21搜索引擎处理流程图1抓取网页阶段主要涉及到SPIDCR网页抓取技术，网络蜘蛛SPIDER，它主要通过网页的链接地址URL来查找其它网页，一般从网站的某一个页面通常是首页开始，读取网页的内容，找到在网页中的其它链接地址，然后通过这些链接地址寻找下一张网页，这样一直循环下去，直到把互联网上所有的网页都抓取完为止。目前SPIDER的抓取策略主要分为两种一种是按照深度优先、宽度优先或者启发式方式发现新的网页链接；另一种是把互联网上的网页信息按照域名或者IP地址划分为几个子域，然后一个SPIDER负责抓取一个子域中的网页。同时网络蜘蛛还有55江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实粤一个特点，就是抓取网页的类型和范围是可以配置的，它可以抓取互联网上的所有网页，也可以只抓取含有MP3文件链接的网页，或者新闻网站中网页，这就为目前出现的各种特色搜索垂直搜索提供了可能和方便。2加工整理阶段这个阶段的主要工作是对原始网页进行加工处理，在后台建立网页索引数据库倒排索引，并计算出网页的排序值PAGERANK值。这一阶段是搜索引擎系统的核心阶段，涉及的关键技术主要包括海量数据存储、动态缓存、中文分词技术、分布式计算、自然语言处理、相关词推荐技术、索引技术、网页排序技术等。本文关注的重点是中文分词技术、自然语言处理技术、相关词推荐技术、索引技术以及网页排序技术，因为上述这几个技术还有很大的改进空间。比如说中文分词技术，目前主流的搜索引擎技术没有很好地解决汉词切分歧义和未登入词识别问题，比如说在GOOGLE中输入“毛泽东北京华烟云”，其切分结果为“毛泽东北京华烟云”，而正确的结果是“毛泽东，北京华烟云”，因此为了更好地理解中文网页信息，需要对中文分词技术作深入的研究。还有搜索相关词推荐技术，主流搜索引擎大都在搜索关键词的基础上加入前缀、后缀字符串作为新的搜索推荐词，没有深入到语义理解层次，智能化程度比较低，有进一步完善的空间。3查询服务阶段这个阶段主要是响应用户的查询请求，由于汉语中存在多词一义现象，而主流搜索引擎普遍采用的是基于关键词匹配的搜索模式，这种方式常常会漏掉很多用户想要的结果。比如说用户输入“电脑”，那么包含“计算机”关键词的网页就不会被检索出来，这就需要完善用户查询接口。23中文搜索引擎现状分析搜索引擎系统的出现，给人们查找互联网信息带来了很大方便。随着互联网信息的爆炸式增长，搜索引擎已经成为人们检索互联网信息的主要工具。但是，单单依靠目录式搜索引擎提供的目录分类导航和全文搜索引擎提供的关键词搜索，其搜索结果并不十分理想。目录式搜索引擎一般采用人工的方式对网页进行分类，因此被分类的网页资源是相当有限的，这样大大降低了信息的查全率。对于全文搜索引擎，由于采用的是纯关键词匹配方式，信息的查全率和查准率还是相当地低，用户输入一个关键词，主流搜索引擎一般都会返回大量匹配结果，而很多结果根本不是用户想要的，用户需要在庞大的返回结果中再次寻找有用的信息，智力负担比较重。虽然GOOGLE、BAIDU采用PAGERANK技术来提高信息的查准率，但是由于PAGERANK技术是基于网页阆的链接关系，来得到网页的相对权重，并非网页与用户真实检索请求之间的关联程度，因此返回的结果中包含了大浙江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现量与用户请求无关的结果。基于上述现状，给出一种有效的搜索推荐词生成方式，引导用户搜索，显得十分必要。客观地说，目前主流搜索引擎在提高信息的查全率和网页之间的相关度方面已经达到了较高的水平，但在关键词对网页的相关性，搜索相关词推荐等方面有待新的技术突破，这也是本文研究的重点。2A智能中文搜索引擎概述未来的搜索引擎系统主要是朝着两个方向发展，一个是个性化，另一个是智能化。具有一定智能特性的搜索引擎系统一般也称为智能搜索引擎，它研究的重点是使搜索引擎系统能够更好地返回用户真正想要的结果，而非大量与用户请求无关的结果。目前国内对智能中文搜索引擎的研究还处于尝试阶段，主要的研究方法有如下两种1基于本体论方法其基本思想是是对概念化对象的准确表述。概念化对象的定义式为C，其中D表示特定的领域，W表示领域内事务的集合，R表示领域内概念之间的关系。本体论方法是采用特定的形式化语言对概念化对象的准确描述，需要专家知识和领域语料库的支持，一般只适合小范围的特定领域研究，不适合大规模、通用领域应用。2基于语义网方法其基本思想是用概念、客体、客体性质、事件或行为作为节点，客体之间的关系作为弧，构成特定领域的语义网络，其一个简单的结构示意图如下图22一个简单语义网络示意图这样对互联网上的原始网页信息，通过特定规则和模式提取某个领域的概念知识，形成元数据库，建立概念索引当用户查询过来时，先把查询请求转化为特定领域的概念，然后通过概念索引在元数据库中查找匹配的信息。语义网的建立一般都需要专家知识的支持，同时，特定的规则和模式一般只能应用到某个小的领域，不适合大规模、通用领域应用。目前研究重点是跟神经网络结合，通过模拟人的思维来提升系统的智能特性。7浙扛大学硕学位论文智能中文搜索引擎若干关键技术的研究与实现本文的研究方法本文研究的领域是互联网领域，而非特定的某个小领域，因此，上述两种研究方法基于本体论的方法和基于语义网的方法并不适合。本文给出的智能中文搜索引擎是一种浅智篚的中文搜索引擎，它是在普通中文搜索引擎基础上加入概念集群、概念集群排序值后的搜索引擎。借鉴本体论和语义网的研究方法，本文首先对网页文档进行分词及相关的后续处理，得到系统的概念词，形成概念；然后通过计算概念词之间的同现概率形成概念之间的关系及概念集群，给出了一种具有语义联想功能的搜索推荐词生成方法，智能地引导用户搜索，提高了搜索引擎系统的查准率；同时利用上述得到的概念集群，提出了一种新的网页排序算法CCRCONCEPTCLUSTERRANK，该网页排序算法有别于经典的网页排序算法PAGERANK算法基于网页与网页之间的链接关系，来得到网页的相对权重，较好地反映用户搜索关键词与网页的关联程度，从而提升了系统的智能特性。25本章小结这一章节主要介绍了搜索引擎系统的分类和实现搜索引擎系统的关键技术。在对搜索引擎系统的现状进行了深入分析后，发现目前的搜索引擎系统智能化程度比较低，在关键词与网页的相关性、搜索相关词推荐等方面有待新的技术突破，对这些技术的研究与实现成为本文关注的重点。最后对智能中文搜索引擎系统的研究方法进行了介绍，并描述了本文的研究方法。82嗡江大学硕学位论文智能中文搜索引擎若干关键技术的研究与实现第三章词典模块的设计与实现这一章，主要介绍在智能中文搜索系统实现中有着重要作用的词典模块。由于中文中词与词之间没有间隔，因此，中文搜索引擎中首先要解决就是汉词切分问题，这是理解中文网页信息、进行智能处理的前提。本文后续章节实现的概念集群的质量、索引的效果都跟分词模块有着密切关系。因此，如何准确、高效地排除汉语中存在的歧义现象以及智能地识别出新词，为后续智能处理提供高质量的概念词，成为本章关注的重点。本章实现的词典模块主要用于二个方面一个方面是用于网页分析模块产生概念词、网页一关键词正排矩阵，网页分析模块为本文后续章节实现的概念集群、倒排索引和概念集群排序值CCRCONCEPTCLUSTERRAILK提供初始数据；另一方面是用户查询过来的时候，对用户输入字符串进行快速、准确地切分。词典模块性能直接影响到整个智能中文搜索引擎系统的性能。31词典研究现状概述作为中文信息处理的核心和汉语自然语言理解的基础，词典模块有着广泛的应用前景。应用领域包含信息检索、自动标引、文本自动分类、自动文摘、智能拼音输入、手写识别输入、中英文互译、语音合成、语音识别、机器翻译等自然语言处理领域。在英文中，单词与单词之间可以用空格或者标点符号进行分隔，这样只需要处理后缀串的情况，就可以进行后续的处理。而中文则不同，中文中词与词之间没有闻隔，而“词是最小的能够独立活动的有意义的语言成分【1】”，因此就有了研究分词技术的必要了。文献【2】中指出了目前困扰分词准确性的几个难题。1歧义切分2未登录词新词识别3分词规范其中，由于歧义现象的存在见下表31使得分词的结果不惟一，严重影响了切分的准确性，这是必须解决的一个问题；还有一个问题就是未登录词的识别问题，包括地名、人名、音译名、机构名的识别，这个主要是给后续各种信息处理提供方便，以及辅助解决歧义现象排除难题。9浙江人学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现鬻獭壤纛鬻麟黼麟蠛蒸麟黧麟黼蒯鬃I1他的确定居在上海他，的确定居厂在，上海他的，确定，居，在，上海2研究生命起源研究生命，起源研究生腧，起源3他说的确实在理他说的，确实，在理他IYA的确，实在，理表31汉语切分歧义现象举例国内对分词系统的研究早在80年代初就开始了，而且有不少研究成果和分词系统问世。典型的有清华大学SEGTAG系统、哈工大统计分词系统、厦门大学分词系统、北大计算语言所分词和词类标注系统等。现有分词系统的一些潜在问题1没有一个相对统一的评价体系和处理模型。2把歧义现象排除、新词识别作单独处理，没有进行有效地结合。上述问题的存在，导致在新词、歧义现象存在的情况下，现有分词系统的准确率、召回率、切分速度往往没有宣称的那样理想。32词典组织结构的设计与实现321词典组织结构概述对词典组织结构的研究，前人已经做了大量工作，并形成了几种比较成熟的汉语词典组织结构3145，现对其中的几种组织结构作一个简单介绍1基于HASH的词典机制这种方法的关键技术是HASH函数，以及如何采用合适的策略来避免HASH冲突，但这种方法的最大缺点是HASH冲突的检测，一定程度上影响了处理速度。2基于B树的词典机制这种方法的关键技术是用B树作为组织结构，虽然一定程度上减少了存储的空间，但是以这种方法作为词典组织结构在最后查找的时候，是按词匹配的方式进行的，效率不是很高。3基于整词二分的词典机制3这种方法把词典结构分为首字散列表、词索引表、词典正文等三层，通过第一层的HASH映射和第二层词索引表，找到第三层词典正文，然后在词典正文中通过折半方法进行整词二分定位。这种方法的优点是可以节省空间，快速实现，但是这种方法实质上还是按词匹配的方式进行的，效率比较低下。4基于TR树的词典机制E53TRM树，是对上述几种结构的一种改进，采用的是按字匹配的方式，检索LO江大学硕十学位论文智能中文搜索弓I擎若干关键技术的研究与实现效率十分高，它的缺点是比较消耗存储空间，系统实现起来比较复杂。下图31给出了添加“人民”，“研究生”，“计算机”三个关键词后，TRIE树的结构示意图。图31TRIE树的结构示意图5其它词典组织机制其它的词典组织机制有文献5中提出的基于双字哈希机制的词典组织机制和文献4中提出的一种基于PATRICIATREE的汉语词典组织机制等，它们对上述的TRIE树结构作了一定改进，但是实现起来比较复杂。322一种高效的词典组织结构综合考虑TRIE树检索效率高、支持模糊查找等优点以及比较浪费空问的不足，本文设计了一种高效的类TRIE树结构作为词典的组织结构，其结构示意图如下图32所示移浙江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现图32类TRIE树组织结构示意图本文把类TRIE树分为两个不同的层直接层和非直接层，直接层的深度是可以配置的，对于简体中文GB2312编码一般把直接层深度赋为1因为简体中文中汉字个数比较多，上图32中直接层的深度为1。直接层和非直接层的区别在于在TRIE树创建的时候，从上一层进入下一层时，直接层后面接字符下标指针数组，非直接层后面接字符指针对有序数组。字符下标指针数组中的每个元素指向结点类型1的结点TRIENODEL，在这种结点中不存储字符本身，这样可以省下很多空间又不影响检索效率；字符指针对有序数组中的每个元素指向结点类型2的结点TIRENODE2，在这种结点中存储字符本身，并且在插入的时候，按字母的编码顺序依次插入，这样在检索阶段可以用二分查找法快速地进行定位，同时这种结点中它有多少孩子结点是预先分配好的，这样可以提高关键词插入的速度如果该结点插入的孩子结点多于预先分配的最大结点个数时，则进行动态分配。对于TIRENODEL和TRIENODE2的具体结构参见下图33。同时考虑至4直接用汉字GB2312编码编码值作为TRIE树边的话，还是会浪费一定的空间，L浙江大学硕上学位论文智能中文搜索引擎若干关键技术的研究与实现所以，采用HASH函数对它进行映射，即对每个汉字都减去GB2312编码的最小值0XBOAL再作为TRIE树的边。最后在词典中的词条都加载到内存以后，采用特定的压缩算法进一步释放多余的内存空间压缩算法基本篇幅，就不详述了。这样在字符串查找阶段，对于直接层的，直接把字对应的GB2312编码作一个HASH映射后作为索引边，到达下层结点对于非直接层，则采用二分查找得到下层结点的指针，速度也很快由于汉词一般为2字串或3字串。可以对直接层深度进行灵活控制，如果系统的硬件环境很好，内存很大256M以上，那么可以把这个值取得大一点；如果系统的硬件环境不是很好，内存不是很大256M以下的话，那么可以把这个值取得小一点，力求做到速度和空间的最大均衡。字节点类型1含4个字段ID，NUSED，BAILOC，CHILDID字段用于标识字符串，NUSED字段用于表示实际己经使用的分支数，NALLOC字段用于表示预先分配的分支数，CHILD表示该节点与它的孩子节点字符下标指针数组之间的偏移量。注ROOT为偏移值，与ROOT同一层的左右两边的省略号表示变种TILE树的其它属性值节点类型2含4个字段ID，NUSED，HALLOO,ARRAYID字段用于标识字符串，NUSED字段用于表示实际已经使用的分支数，NAILOE字段用于表示预先分配的分支数ARRAY表示该节点与它的孩子节点CP_PAIR类型数组之间的偏移量。STRUCTCP_PAIRCHILD，搴与孩子节点的相对偏移量TCBR到相应孩子节点的相关字符值这个在直接层中不需要用到图33类TRIE树存储结构示意图江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现同时，基于后续处理的考虑，在词典库中加入了同步操作机制和内存共享机制，使得词典模块为多进程、多线程共享版本。33汉词切分算法的设计与实现331汉词切分算法概述确定了词典的组织结构以后，下一步的工作就是切分算法的研究了。切分算法的优劣直接影响切分的准确性，同时在切分阶段必须解决词典模块存在的两大难点歧义现象排除和新词识别。对于汉词切分算法研究，前人6789做了很多工作，已经给出了许多经典的算法。概括起来这些算法大致可以分成三类一类是基于规则的切分算法这一类算法包含最大匹配算法正向、逆向、两者结合，最短路径，N最短路径7，全切分等；另一类是基于理解的切分算法这一类算法在分词的同时进行句子结构、上下文语义分析，用句法信息和语义信息来处理歧义现象，由于自然语言处理的复杂性，目前此类算法还处于试验阶段；最后一类是基于概率的切分算法这一类算法包括最大概率切分算法，N元语法NGRAM切分算法101X。下面对其中的几种切分算法作一个简单的介绍1最大正向匹配切分算法最大正向匹配切分算法简称MM法MAXIMUMMATCHINGMETHOD。它的基本思想是首先字符指针指向待切分STR串的串首，然后到切分词典中找最长的匹配词条，如果匹配成功，则该子串为一个词，指针后移该词长度个汉字字符后继续上述过程，直到整个字符串扫描结束，否则指针后移一个汉字字符继续上述过程，直到整个字符串扫描结束。这种算法的优点是切分速度快，实现简单；缺点是不能有效排除歧义现象。比如说对于“研究生命起源”这样一个短语，按照这种方法切分的结果为“研究生命起源”，而正确的切分结果为“研究生命，起源”。2最大逆向匹配切分算法最大逆向匹配法简称为RMM法REVERSEMAXIMUMMATCINGMETHOD。它的基本思想与MM法相同，不同的是分词时指针的扫描方向，其实质是对待切分的字符串从后面开始进行MM扫描。RMM算法优点也是切分速度快，实现简单，而且在切分的准确率上，比MM有一定的提高，缺点也是不能有效排除歧义现象。14浙江大学硕十学位论文智能中文搜索引擎若干关键技术的研究与实现3最大正向逆向匹配切分算法它的基本思想是同时进行MM和RMM扫描，然后把结果合并得到最后的结果。优点由于是MM和RMM的结合，所以准确率提高不少，能消解部分歧义现象。4最短路径切分算法它的基本思想是先对待切分的字符串建立切分词图，然后在这个有向图中找一条最短路径，切分词图中边的权值都赋为1。最短路径算法是切分出汉词数目最少的一种切分方法。它的优点是切分出来的词数是最少的；缺点是可能会遗漏一些正确的结果。5N。最短路径切分算法7它的基本思想是在最短路径切分算法基础上，对它进行改进，也就是取N条最短路径的切分结果，而非单单一条路径，这样可以提高汉词切分的召回率4为后续的处理提供保障。6全切分算法它的基本思想是对于待切分的字符串，把切分词典中有的词条全部都切分出来，优点很明显，可以大大提高切分的召回率，缺点是计算复杂度高，系统开销很大。7最大概率切分算法它的基本思想是对于待切分的字符串，先把切分词典中有的词条全部切分出来，然后建立切分词图，对切分词图中的边赋予一定的概率值，然后在多条可能的路径中取联合概率最大的一条路径作为最后的切分结果。这种方法实质上是一种变形的最短路径切分算法。与最短路径方法不同的地方在于最大概率切分算法用词频作为切分词图有向边的权重值。它的优点是可以比较有效地解决歧义现象排除问题。8N元语法统计NGRAM切分算法N元语法统计切分算法是一种典型的概率切分算法，对于一个给定的句子SW1W2W。，根据信息论中的噪声一信道7原理，可得句子S的切分概率PS如下式31所示聃EW2W2WMPWL童,W2WOPWSJW2W0PW。JWL、】LKL卅NPIWLW2WM一1公式31乍F上述公式31中，PW。卜NWM1表示在词串W1WM_1出现的情况下出现词W。的概率，W1WM1为词W。的历史信息，为了方便计算考虑的词的历史信息不能太长，一般取N1个词作为历史信息，只考虑前N1个词的上述求解模型被称为N元语法统计模型。锈江大学碗士学位论文智能中文搜索引擎若干关键技术的研究与实现N元模型的切分算法就是找到使得P概率最大的切分路径。当NI时，该切分算法就是UNIGRAM模型切分算法，也称一元语法模型切分算法；当N2时，该切分算法就是BIGRAM模型切分算法，也称二元语法模型切分算法；当N3时，该切分算法就是TRIGRAM模型切分算法，也称三元语法模型切分算法。332一种新的汉词切分方案在汉词切分算法上，前面已经介绍几种经典的切分算法，但是单单利用规则或者概率方法往往很难达到理想的切分性能。本文的方法是基于规则和基于概率的结合，充分利用两种方法各自的优点。并把切分过程分成两个阶段，有效地解决汉词切分中出现的歧义现象难以准确排除，新词、命名实体识别1314困难等难题。切分算法的模块构成及流程示意图如下所示图34词典切分方案示意图本文把汉词切分过程分为两个阶段第一阶段是歧义瑰象摊除阶段排除歧义，对命名实体进行识别；第二阶段是新词识别阶段识别新词。333歧义现象排除阶段这一阶段，主要排除汉词切分中的歧义现象包括交叉歧义和组合歧义，同时对命名实体进行识别。分析本文331章节介绍的NGRAM模型求解公式31不难得到如下结论1当N取值很小N1时没有考虑词的上下文信息，认为词与词之间是独立的，这时NGRAM模型就江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现退化为最大概率切分模型。这时切分准确率不是太高，但是计算量小，训练语料库不需要很多。2当N取值很大N3时虽然充分考虑了词的上下文信息，但是计算量是海量的，假设切分语料库中M个汉词，那么计算复杂度大于等于OM3，当NL比较大时，模型的计算是比较困难的。基于上面的分析结论，本文首先采用二元语法统计模型对汉词切分串进行分解，这样既可以保证分词的准确率考虑了词的上下文信息，又能比较快速、简单地实现。二元语法模型BIGRAM模型本文331章节介绍NGRAM模型求解公式31，那么BIGRAM模型求解公式如下所示尸日RGMAXN1公式3_PWIIM2BIGRAM模型的切分方法是找出概率值晟大的词串SW1W2W。作为最后的切分结果，其中烈W；IWJT，表示在关键词WI1出现的前提下出现关键词WI的概率。这是根据信息论中噪声一信道7原理建立的模型。二元语法模型BIGRAM模型求解求解上面的模型，关键是求PWIWI1的值。PWILW1PWI1WOPW1知道了PWI1W1也就是WI1WI一起出现的概率和PWI1也就是WI1出现的概率以后，问题就迎刃而解了。这里就要介绍我们的核心词库了，我们的核心词库中大概收录了23万词条，在对大规模语料库进行切分统计后，得到了每个关键词的概率，也记录在词库中，这样根据极大似然估计很容易计算PWIH1PW，WIPWI11的值，使上述模型得以求解。数据噪音问题以公式32作为BIGRAM模型求解公式存在如下两个问题1当句子S很长时，由公式32得到的P回往往很小多个小于1的分数相乘结果趋向于零，常常造成数据的溢出下溢，需要对公式32进行修E。2由于W1WI可能是词典中没有的汉词，那么上面模型求出的值就为0，这种现象叫做数据稀疏问题文献12对它作了详细的描述，也必须进行平滑处理。数据平滑处理对于问题1，本文在公式32的基础上引入LN对数操作，修改后的公式如下江大学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现P仰_1NVS讪日似PWF州懒珥HPMIARGMAXII111PWZ一1INPWI1M公式33乞F对于问题2，文献【12】给出了不少数据平滑处理的方案，比如说ADDONE、ADDDELTA、GOODTURING算法等等。本文采用ADDDELTA12数据平滑处理算法对公式33进行修正。ADDDELTA算法对于在词典中没有出现的词WI1WJ，用九值对它进行修正，使它为非0值，其具体的计算公式如下只枞COUNTWLWZWMANW上述公式中，N为训练语料库中总的汉词数目，V为训练语料库中不同的汉词数目。正数九一般取为05。用规则对结果进行修正用上述模型可以很好地解决大部分歧义现象，但是对于有些比较特殊的短语切分出来的效果还是不太理想，因此我们使用规则对上述模型进行修正。主要是利用人名的前缀如“李”，“王”等，地名的后缀如“省”，“市”等以及机构的后缀如“协会”等对由二元语法模型BIGRAM模型切分出来的结果进行前缀或后缀方式加以修正。同时对于如下几种比较特殊的情况也用特定规则加以修正1时间、数值情况，比如说“2004年”，“壹元”等等。2重叠词情况，比如说“一阵阵”，“喜洋洋”，“打打球”，“嘻嘻哈哈”等等。3网址等与英文有关的情况，比如说“WWW163TOM”等等。这里用到了一些特殊的语料库比如说人名词典、地名词典、机构名词典以及特定的规则库等。通过上面的过程也完成了对比较常用的中文命名实体的识别，比如说人名、地名、机构名、时间等。334新词智能识别阶段这一阶段也被称为合成词生成阶段，主要是利用扩展词库目前220万左右，还在不断增加。扩展词典的产生是由机器自学习算法结合人工修正的方式产生的。其实现算法如下扩展词库产生算法嬗浙江大学硕士学位论文智能中立搜索引擎若干关键技术的研究与实现1初始扩展词库为空。2记录用户的历史查询记录，把用户查询频率商，而在核心词库和扩展词库中没有的关键词，放到缓冲文件中。3以一定的周期，把缓冲文件中词条信息加入到扩展词库中人工加以修正。4重复步骤2。通过上述算法，随着时间的推移，扩展词库中的词条会不断地增加。而且增加的都是一些新词、热点词。有了上面得到的扩展词库，对由第一阶段生成的切分汉词进行基于词的最大正向匹配算法，就得到了相应的合成词新词，比如说“一个馒头引发的血案”，在核心词库中这个词是没有的，经过第一阶段的切分，它被切分成“一个馒头引发I的血案”5个关键词，然后这5个词被送到第二阶段，采用的词库是扩展词库，假设“一个馒头引发的血案”在这个扩展词库中是有的，那么第二阶段生成的合成词为“一个馒头引发的血案”。通过这种方式较好地解决了中文分词中存在的新词识别困难的这个难题。基于词的最大正向匹配算法跟本文331章节中叙述的最大正向匹配算法本质上是一致的，只是基于词的最大正向匹配算法是以词为最小切分单元，而本文33I章节中叙述的最大正向匹配算法则是以字为最小切分单元。把第一阶段生成的切分结果并上第二阶段生成的合成词识别的新词，并除去组成合成词的各个关键词根据应用需要也可以选择保留组成系统最终的切分结果。34词典性能评价指标词典的性能评价指标主要由如下几个指标1切分准确率切分准确率切分正确的汉词数，总的汉词数100。切分准确率是评价词典性能的最重要指标，切分准确率越高，那么词典的性能也越好。2切分速度切分速度切分出来的汉词总数，总的切分时间。在切分准确率有保证的前提下，切分速度越快越好，当词典用于搜索引擎系统，这个性能指标很重要。35实验结果按照本文322章节介绍的词典组织结构和本文332章节介绍的切分算法，I江人学硕士学位论文智能中文搜索引擎若干关键技术的研究与实现本文实现了中文分词系统WISEDICTIONARY，分为两个版本，一个是WINDOWS版本不经过新词识别阶段，另一个是LINUX版本经过新词识别阶段，以适应多种应用的需要。本文测试了中文分词系统的性能，其开发测试环境和性能测试结果如下开发测试环境操作系统REDHAT90WINDOWS2000PROFESSIONALCPUP424G内存DDR512M开发工具GCCMICROSOFTVISUALC60性能测试结果本文从1998年人民日报语料库中选取了总词数大约为10万的4个测试子集，测试中文分词系统WISEDICTIONARYLINUX版本的切分准确率，结果如下表32所示隧灞孽獭鬻糕囊鏊I灞国蚓纂篓隧瀵夔蘩溯瓣黧懑獭糕蠛篓测试子集116，65416。1569701测试子集219，32618。78597。20测试子集322，85022，2189723测试子集442，21041，0139719总计101，04098，17297，16表32中文分词系统性能测试结果测试结果显示，该分词系统的平均切分准确率为9716。我们对该分词系统的WINDOWS版本也进行了测试，测试结果显示该分词系统的切分速度为6000词秒左右跟切分的文本大小有关，这个速度是歧义排除阶段的测试结果，如果再经过新词合成阶段，那么这个速度要稍慢些。从切分速度和切分准确率上看，该系统能够较好地满足商用系统的需要。同时，由于采用了压缩算法，使得词典模