[硕士论文精品]基于hownet多特征结合的句子相似度计算

硕士学位论文摘要随着互联网的快速发展，网上信息越来越多，如何在这些海量信息中快速准确地找到所需要的信息也越来越困难。虽然传统的搜索引擎如GOOGLE等已经取得了很大的成功，但这类搜索引擎只能获取与用户查询请求相关的文档，用户必须自己从这些文档中查找相关信息；其查询是一系列关键词而非自然语言问句，事实上，用户可能更习惯于用自然语言来描述一个问题；多数情况下，用户所需要的只是问题的确切答案，而不是与该问题相关的一系列网页。自动问答技术是自然语言处理领域中一个非常热门的研究方向，它综合运用了各种自然语言处理技术。而在信息检索领域中，语义相似度起着重要的作用，提高语义相似度的精度有重要的理论和实际意义。计算机对于中文的处理相对于西文的处理存在更大的难度，集中体现在对文本分词的处理上。分词是中文句子相似度计算的基础和前提，采用高效的分词算法能够极大地提高句子相似度计算结果的准确性。本文在对常用的中文分词算法分析比较的基础上，提出了一种基于双数组TRIE树中文分词算法及歧义消除策略，对分词词典的建立方式、分词步骤及歧义字段的处理提出了新的改进方法，提高了分词的完整性和准确性。在中文信息处理中，句子相似度的计算广泛应用于信息检索、机器翻译、自动问答系统、自动文摘等领域，是一个非常基础而关键的问题，长期以来一直是人们研究的热点和难点。本文分析比较了现有的句子相似度计算方法，然后提出了一种新方法，结合基于知网语义相似度计算和基于向量空间的TF木IDF方法，随后利用此方法结合前面提出的分词方法，给出了中文句子相似度的实现算法，并以问答式信息检索系统为例进行了测试，对所用方法进行了验证。实验证明使用本文的分词方法后，不仅时间效率和空间利用率得到很大提高，而且提出的句子相似度方法效果也不错。关键字自然语言处理问答系统知网分词语义相似度HTTP/INFO3DOUCOM/口碑营销ABSTRACTWITHTHERAPIDDEVELOPMENTOFINTERNET，THEREAREMOREANDMOREINFORMATIONONLINEHOWTOGETTHEINFOMATIONWENEEDQUICKLYANDACCURATELYHASBECOMEINCREASINGLYDIFFICULTWH订ETRADITIONALSEARCHENGINESSUCHASGOOGLEHAVEACHIEVEDGREATSUCCESS，THESESEARCHENGINESCANONLYRETURNWEBSITESWHICHARERELEVANTTOUSERINQUIRIESUSERSMUSTHAVETHEIROWNSEARCHFORREVEVANTINFOMATIONFROMTHESEWEBSITESTHEINQUIRIESAREASERIESOFKEYWORDS，RATHERTHANNATURALLANGUAGEFROMATINFACT，USERSMAYBEMOREACCUSTOMEDTOUSINGNATURALLANGUAGETODESCRIBEAPROBLEMINMOSTCASES，USERSNEEDTHEEXACTANSWERTOTHEPROBIEM，RATHERTHANASERIESOFRALATEDWEBSITESQATECHNOLOGYISAVERYHOTRESEARCHDIRECTIONINTHE6ELDOFNATURALLANGUAGEPROCESSINGITCOMBINESALARGEVARIETYOFNLPTECHNOLOGIESINTHISPAPER，WETRYTOINVESTIGATESOMETECHNOIOGIESFORCHINESEQASYSTEMSINTHEFIELDOFINFORMATIONRETRIEVAL，SEMANTICSIMIIARITYPLAYSANIMPORTANTROLE，TOIMPROVETHEACCURACYOFSEMANTICSIM“ARITYHASIMPORTANTTHEORETICALANDPRACTICALSIGNI6CANCEITSMOREDIFFICULTF|ORCONLPUTERSTOPROCESSCHINESETHANTOWESTERNLETTERSINTHEPROCESSINGOFWORDSEGMENTATIONWORDSEGMENTATIONISTHEFOUNDATIONANDPRECONDITIONOFCHINESESENTENSESIMILARITYCONLPUTING，THEACCURACYOFLHERESULTCANBEGREATLYIMPROVEDWHENADOPTINGMOREE艏CIENTARITHMETICINTHISPAPER，AKINDOFIMPROVEDCHINESEWORDSEGMENTATIONMETHODBASEDONDOUBLEARRAVTRIEANDTHESTRATEGYTOELIMINATETHEAMBIGUITYISPUTFORWARDONTHEANALYSISANDCONTRASTOFCOMMONCHINESEWORDSEGMENTATIONARITHMETICWEPROPOSEANIMPOROVEDMETHODABOUTDICTIONARYMECHANISMS，SEGMENTATIONSTEPSANDAMBIGUITY，THEINTEGRALITYANDACCURACYOFWORDSEGMENTATIONWILLBEENHANCEDINCHINESEINFORMATIONPROCESSING，SENTENCESIM订ARITYCOMPUTINGISWIDELYUSEDINTHEAREAOFINFORMATIONRETRIEVAL，MACHINETRANSLATION，AUTOMATICQUESTIONANSWERJNG，TEXTMININGANDETCITSAQUESTIONOFMUCHESSENTIALANDIMPONANTTHATPEOPLESTUDYASAHOTSPOTANDDIFFICULTYF0RALONGTIMEINTHISPAPER，ONTHEBASISOFANALYSISANDCONTRASTOFEXISTINGSENTENSESIMILARITYCOMPUTINGMETHODS，ANEWSENTENSESIMILARITYCOMPUTINGMETHODISPUTFORWARDWHICHMAKEUSEOFTFIDFMETHODBASEDONVSMANDSEMANTICMETHODBASEDONHOWNETCOMBINDWITHTHEWORDSEGMENTATIONARITHMETICWHICHMENTIONEDABOVETHEREA“ZATIONOFCHINESETEXTWORDSEGMENTATIONANDSIMILARITYCOMPUTINGWITHCOMPUTERSYSTEMISPUTFBRWARDANDCARRYTHROUGH硕士学位论文MANYTESTINGQUESTIONANSWERINGRETRIEVALSYATEMISTESTEDASEXAMPLETOVALIDATETHEMETHODTHATUSEDEXPEFIMENTALRESULTSSHOWTHATARERMAKINGUSEOFTHEPRESENTEDWORDSEGMENTATIONAIGORITHM，THETIMEANDSPACEUTILIZATIONEFNCIENCYHASBEENGREATLYIMPROVEDANDPROPOSEDMETHODSOFSENTENCESIMILARITYEFFECTISGOODKEYWORDSNATURALLANGUAGEPROCESSING；QUESTIONANSWERING；HOWNET；WORDSEGMENTATION；SEMANTICSIMILARITYIVHTTP/INFO3DOUCOM/口碑营销基于HOUNET多特征结合的句子相似度计算插图索引图31以“中“字开头的部分TRIE树结构19图32分词流程22图41树状的义原层次结构“28图51用于查找候选问题集的结构”40图52系统实现流程4L硕士学位论文附表索引表31知网主要词性标注符号集23表32构造双数组TRIE树时间25表33占用空间25表34给定语料分词速度25表41知网HOWNET知识描述语言中的符号及其含义“28表42知网词典文件结构29表43知网HOWNET知识描述语言实例”29表44词语相似度计算实验结果，36表51问答系统实验结果比较一45HTTP/INFO3DOUCOM/口碑营销湖南大学学位论文原创性声明本人郑重声明所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名珠参矿权日期矽锣年，月二乞日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1保密口，在年解密后适用本授权书。2不保密团。请在以上相应方框内打“”作者签名导师签名柴纽权I劬日期劢节年岁月Z乙日嗍刁年月N日硕士学位论文第1章绪论11课题研究背景与意义问答系统QUESTIONANSWERINGSYSTEM是指能够对计算机用户输入的使用自然语言描述的问旬做出回答的计算机程序【LL。问答系统集自然语言处理、信息检索、知识表示为一体，正日益成为国际上研究的热点。它能够让用户用自然语言提问，又能够为用户返回一个简洁、准确的答案，而不是一些相关的网页。因此，自动问答系统和传统的依靠关键字匹配的搜索引擎相比，能够更好地满足用户的检索需求，更准确地找出用户所需要的答案，具有方便、快捷、高效等特点12J。早在上世纪60年代人工智能研究刚开始的时候，人们就提出了让计算机用自然语言来回答人们的问题即自然语言问答系统。问答系统在上世纪80年代的自然语言处理领域曾风靡一时，因为TURING实验告诉人们如果计算机能够像人一样与人进行对话，就可以认为计算机有智能，所以研究者们为了探索语言理解技术，纷纷研究自然语言问答系统。但由于当时的条件限制，所有的实验都是在非常受限的领域，甚至是固定段落上进行的，所以自动问答一直被限制在特殊领域的专家系统。此后，由于大规模文本处理技术的兴起，问答系统的研究受到了冷落P】。最近几年，随着网络和信息技术的快速发展，同时人们想更快地获取信息的愿望也重新促进了自动问答技术的发展。有越来越多的公司和科研院所参与自动问答技术的研究，比如微软和IBM等公司。在每年一度的文本信息检索TREC会议上，自动问答QUESTIONANSWERINGTRACK是最受关注的主题之一，越来越多的大学和科研机构参与了TREC会议的QUESTIONANSWERINGTRACK。在2000年LO月召开的ACL2000国际计算语言学学术会议上，有一个专题讨论会，题目是”OPENDOMAINQUESTIONANSWERING”。英文问答系统早在1999年就开始由TREC会议主办进行这类型的比赛；日文的比赛于2003年由日本国立情报学研究所NII的NTCIR会议NTCIRW6RKSHOP所主办；欧洲同样于2003年由CLEFCROSSLANGUAGEEVAIUATIONFORUM会议主办欧洲语言的比赛。根据2004年的报告【4】，目前最佳英文问答系统的水平已经可以达到70左右的正确率。也就是说，一百个自然语言问句中，有七十题可以直接回答精准而正确的答案。此最佳英文系统由LANGUAGECOMPUTERCORPORATION所发展，逻辑推理能力为其致胜关键。在日文系统方面，正确率稍微低了些，但也有5L。日本电信电话公司NTT是目前成绩最好的团队。欧洲方面，QACLEF在规模上相当大，参与比赛的语言高达九种，加上跨语言问答的项目，比赛内容最为丰富。其中法文、葡萄牙文等语言系统于2005年都已经可以HTTP/INFO3DOUCOM/口碑营销基于HONET多特征结合的句子相似度计算达到六成多的正确率PJ。相较于其他语言，中文虽然是世界上第二大语言，但中文问答系统比赛直到2005年才开始由日本NTCIR会议所主办，目前最佳的正确率为中研院的5516J。目前，国外已经开发出一些相对成熟的问答系统。麻省理工开发出问答系统START，从1993年开始发布在INTERNET上，网址为HTTPSTARTCSAILMITEDU。可以回答一些有关地理、历史、文化、科技、娱乐等方面的简单问题。例如用户提问“HOWFARISNEPTUNEFROMTHESUN”，START系统将会回答“THEMEANDISTANCEBETWEENNEPTUNEANDTHESUNIS2，798，800，000MI4，504，300，000KM”。另外还有其他比较成熟的问答系统像ANSWERBUS，它是个多语种的自动问答系统，不仅可以回答英语的问题，还可以回答法语、西班牙语、德语、意大利语和葡萄牙语的问题【刀，其网址为HTTPWWWANSWERBUSCOMINDEXSHTML。LASSO系统是藉由自然语言处理方法分析使用者输入的问句引，将问句依其形态加以归类，并提取出问句的中心焦点后，从大量文件中找出符合使用者需求的答案。国内在问答系统方面的研究相对国外较为不足，主要有中科院计算所、复旦大学、哈尔滨工业大学、沈阳航空工业学院、香港城市大学、台湾中研院等些单位。但是整体来说，参与中文自动问答技术的研究的科研机构比较少，而且基本没有成型的中文自然语言问答系统。自然语言问答系统的人机界面、精确性和实时性是汉语自然语言问答系统的三大研发目标【9】。其中，精确性是自然语言问答系统的首要目标。为了达到这一目标，在用户问句处理方面，需要对用户输入的问句进行正确的分词和词性标注、同义词扩充、名实体标注、句法分析、答案类型标注等等处理，对于领域文本知识库也要进行同样的处理。尤为重要的是，需要一个综合考虑用户问句与文本片段的语言语义信息，精确计算用户问句与文本库中句子的相似度大小，使得蕴含答案的句子获得一个相对较高的计算结果，较早的返回给用户，从而提高信息检索系统的精确性，并提高答案自动抽取的精度和效率。句子相似度的计算是自然语言问答系统的核心所在，其计算方法的精确性和实时性关系到整个系统的精确性和效率。因此，本文的重点是对句子相似度及其计算方法进行深入研究。本文句子相似度的研究主要是以自然语言问答检索系统为应用背景，在自动问答检索系统中旬子相似度的计算是一个非常重要的理论基础。问答系统中很多地方都需要用到语句相似度的计算，自动问答系统句子相似度的计算大致可分为两类问题与问题之间的相似度计算和问题与答案之间的相似度计算。在常问问题库中需要用到问题与问题之间的相似度，在答案抽取模块中需要用到问题和候选答案之间的相似度，甚至在答案抽取模块中的多文档自动文摘也要用到句子相似度来对句子进行聚类。本文的研究对象主要是用户提出的问题与常用问题库问题之间的相似度，还包括用户提出的问句和候选答案间的相似度。2硕士学位论文在研究句子相似度的过程中，首先对知网系统做一些概念性的介绍然后利用知网系统来进行汉语词的相似度计算；最后研究句子相似度计算。12本文研究内容本课题主要有以下几个方面的研究工作1研究基于双数组TRIE树的分词算法；2介绍了知网中的关系层次网络；3研究了义原相似度计算方法；4研究了相似句子查找算法；5问答式信息检索系统的实现，并给出实验结果。13论文结构本文的工作主要集中在句子相似度计算技术研究上，包括分词算法的实现；相似度计算算法的实现；如何利用知网来进行相似度计算；训练和测试语料库的建设，系统参数确定等方面。全文共分5章，结构如下第L章绪论首先讨论了问答式信息检索系统的背景和意义，概要介绍了国内外对这一课题的研究现状和分析，相关的研究方法，综述了相关领域的研究工作。最后指出了本文的研究内容及其组织。第2章中文分词研究和句子相似度研究综述介绍了国内外的一些研究状况和最新进展，并介绍了分词方法和传统的四种句子相似度计算方法和它们的主要问题。第3章基于双数组TRIE树分词算法的研究介绍了常用的一些中文分词算法和双数组TRIE树的算法思想，并在双数组TRIE树的基础上构造了词典结构树，利用改进的双向联想匹配提出一个分词算法。第4章基于知网汉语词相似度计算首先，介绍了知网层次关系网的基本概念；其次，根据义原层次树的特性，调整义原节点的权值，利用义原层次树的距离、义原层次树的深度等信息计算义原相似度。再次，在义原的基础上计算概念的相似度。最后，计算词语的相似度。第5章句子相似度计算在FAQ中的应用提出汉语句子语义相似度计算方法，设计问答检索系统，将机器计算结果与人类的主观判断结果进行比较，并对实验数据进行分析，确定能够得到最佳结果的参数值，同时验证了方法的有效性。3HTTP/INFO3DOUCOM/口碑营销基于LOUNET多特征结合的句子相似度计算最后，对全文开展的工作进行了总结，并指出了进一步的研究工作。4硕士学位论文第2章中文分词研究及句子相似度研究综述21中文分词的意义汉语自动分词是中文自然语言处理系统的第一道基本“工序力，只有逾越这个障碍，中文处理系统才称得上初步打上了“智能“的印记，构建于词平面之上的各种后续语言分析手段才有展示身手的舞台。否则，系统便只能被束缚在字平面上。具体来说，自动分词在很多现实应用领域中文文本的自动检索、过滤、分类及摘要，中文文本的自动校对，汉外机器翻译，汉字识别与汉语语音识别的后处理，汉语语音合成，以句子为单位的汉字键盘输入，汉字简繁体转换等中都扮演着极为重要的角色。22主要的分词技术概述221机械分词法这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的“机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功识别出一个词。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大最长匹配和最小最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下1正向最大匹配算法简称为MM算法【10】。基本思想是设D为词典，MAX表示词典D中的最大词长，STR为待切分字符串。每次按正向顺序取长度为MAX长的字符串与词典中的词进行匹配。若匹配成功，则得出该字符串为一个词，继续后移MAX个字符串进行匹配。否则，字符串减一个从后减字继续进行匹配，直到匹配成功。2逆向最大匹配法逆向最大匹配算法，就是把正向最大匹配算法的文本扫描顺序改为逆向，基本思想还是一样。改为逆向扫描的好处是提高了切分的准确率。统计结果表明，单纯使用正向最大匹配的错误率为L169，单纯使用逆向最大匹配的错误率为L245。但这种精度还远远不能满足实际的需要。3最少切分算法基本思想是切分时使每一个句子的词最少。理由是最少切分的结果的分词准确率比较高。然而该算法不能识别组合歧义，时间复杂度也高。5HTTP/INFO3DOUCOM/口碑营销基于HOU，NET多特征结合的句子相似度计算4双向匹配算法双向匹配算法就是将正向最大匹配算法和逆向最大匹配算法结合起来【111，先进行一趟正向最大匹配算法，然后进行一趟逆向最大匹配算法。然后，对比两遍扫描的结果，若成词的地方一致，则说明字段为一个词；否则，则说明存在歧义现象，需要进一步的处理。5逐词匹配算法逐词匹配算法，就是顺序扫描文本，每匹配成功一个词，就检查该词是否属于歧义字段，是则处理，否则继续扫描。另外，还有将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助112】，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。222基于理解的分词方法通常的分析系统，都力图在分词阶段消除所有歧义切分现象。而有些系统则在后续过程中来处理歧义切分问题，其分词过程只是整个语言理解过程的一小部分。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统并不完善。223基于统计模型的分词方法该分词算法的基本思想是从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。这种方法只需对语料库中的字组频率进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一、“之一“、“有的“、“我的”、“许多的“等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典常用词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。在很多文章中已凸显对分词的大量关注RIE使用统计方法进行自动分词的研究【13L；ANDREW使用最大熵马尔科夫模型的方法进行自动分词的研究114L；XUE6硕士学位论文等使用合并分类器的方法进行自动分词的研究【151；GAO等提出一种基于信源模型的中文分词方法，又进一步把它发展成线性混合模型。各种统计模型对中文分词贡献，都是在假定输入的字符或者字串服从某种分布的情况下进行处理的，实际中的中文字符分布到底是什么样子，无从得知。23分词算法比较1最大匹配分词算法是一种简单的基于词表的分词方法，有着非常广泛的应用。这种方法只需要最少的语言资源仅需要一个词表，不需要任何词法、句法、语义知识，程序实现简单，开发周期短，是一个简单实用的方法，但对歧义字段的处理能力不够强大。2全切分方法首先切分出与词表匹配的所有可能的词，然后运用统计语言模型和决策算法决定最优的切分结果。这种切分方法的优点是可以发现所有的切分歧义，但解决歧义的方法很大程度上取决于统计语言模型的精度和决策算法，需要大量的标注语料，并且分词速度也因搜索空间的增大而有所缓慢。3最短路径分词方法的切分原则是使切分出来的词数最少。这种切分原则多数情况符合汉语的语言规律，但无法处理例外的情况，而且如果最短路径不止一条时，系统往往不能确定最优解。4统计方法具有较强的歧义区分能力，但需要大规模标注或预处理语料库的支持，需要的系统开销也较大。24句子相似度的研究现状现在国内外有很多学者在研究句子相似度的计算方法【L引。在国外例如哥伦比亚大学的GOLDSDEIN等人通过最大边缘相关的方法进行相似度计算，学者CHRISHQDING等采用了隐含语义索引的方法。LAMBROS等提出同时依据句子的表层结构和内容计算相似度的方法【17L。在计算相似度时，系统使用了两级动态规划技术，应用动态规划算法允许在两个长度不同的句子之间计算语句相似度。NIRENBURG等提出了两种串匹配的方法【18】，即更规范的“切块匹配重组方法和整句级匹配的方法，这两种方法所采用的相似度衡量机制都是词组合法。该系统的相似度计算采用罚分制，两个句子匹配所得到的总罚分值由句子中每个对应单词对的比较所得的罚分组合而成。CARROLL和SUMITA都建立了“距离或“相似度刀衡量机制。CARROLL用基于两个测试点的三角形法来计算句子之间的相似度，一个测试点是被比句子的长度，另一个是被比句子的内容，一些误匹配用相似度得分中的“费用“来体现。SUMITA等的相似度计算是基于单个词的，规定两个语言片段的距离由它们所包含的词之间的距离与相应权值的乘积之和来决定。NILADRI提出了一种基于线性模型的相似度度量模式，其相关系数由多重回归技术确定，他将句子的相似7HTTP/INFO3DOUCOM/口碑营销基于HOURNET多特征结合的句子相似度计算性或者更准确地说是非相似性看成是一系列决定句子不相似的成分的共同作用的结果。国内对于汉语句子的相似度计算研究方面也取得了一定的成果。张民等设计了种基于词的汉语句子相似度计算方法FL91。由于进行相似度计算的两个句子往往长度相差较大，单词的个数不致，因此，两个句子中每个单词都可能是相互相关的，这种相关性可通过相对位置加权处理。该方法考虑了词一级的相关性、词同义词的同现以及评价值的向后叠加，并设计了一个递归定义的算法，不仅可以给出句子级相似，而且也可以给出“亚句子级相似。陈利人等提出了句子相似度包括结构相似度和语义相似度的概念【201，认为句子相似度计算包括两个步骤首先，经过词的结构相似度计算，得到句子的结构相似度；然后，在句子结构相似的基础上，再进行句子语义相似度的计算。穗志方、俞士汶根据语句相似度定义和计算的特殊要求【2，为被比句子设计了一种折衷的句子分析方法一骨架依存分析法，进而设计了一种基于骨架依存树的语句相似度计算模型。杨思春等利用具有部分格语义的语法功能句型模式来实现句子相似度计算【221。该模式类似于通常语法意义上的句型，但比抽象的句型要详细得多，它既反映了一个句子的主要骨架成分，又表达了一个句子的基本特征语义。因此，在定义和计算句子相似度时，可以直接根据两个句子的模式对其进行相似判断，即把两旬的相似判断等价地转化为两句模式的相似判断。此外，李素建基于知网和同义词词林【23241，提出了语句相关度的定量计算模型；吕学强等考虑词形相似度和词序相似度两个因素【2”，提出了句子相似度模型和最相似句子的查找算法；车万翔等利用改进编辑距离进行中文相似句子的检索F26，27】；秦兵等采用TFIDF法和基于语义的方法F281，面向常问问题集计算问旬间的相似度；崔桓等在基于网络的问答系统中综合考虑关键词的顺序、关键词之间的距离、以及问旬和答案的长度等信息，用于计算其相似度。25句子相似度的概念及计算方法251句子相似度的概念相似度是一个很复杂的概念，在语义学、哲学和信息理论中被广泛的讨论。目前，关于相似度的定义还没有个通用方法，因为其涉及到语言、语句结构和其他一些因素。同样的，句子相似度是一个主观性较强的概念，脱离具体的应用背景谈论句子相似度，很难得到一个统一的定义。在问答信息检索系统中，句子相似度更多地反映句子间的语义上的匹配符合程度。例如，我喜欢吃玉米和我爱吃包谷这两个句子就是语义相似的。当相似度达到某个设定的阈值时，就认为这两个语句相似。句子相似度通常这样定义两个句子在语义上的匹配符合程度，值为【0，1】之8硕士学位论文问的实数，值越大表明两个句子越相似。当取值为L时，表明两个句子在语义上完全相同；值越小则表明两个句子相似度越低，当取值为0时，表明两个句子在语义上完全不同。在句子相似度计算中，按照对语句的分析深度来看，主要存在四种方法1基于向量空间模型的方法。该方法把句子看成词的线性序列，不对语句进行语法结构分析，相应的语句相似度衡量机制只能利用句子的表层信息，即组成句子的词的词频、词性等信息。由于不加任何结构分析，该方法在计算语句之间的相似度时不能考虑句子整体结构的相似性；2对被比较的两个句子进行深层的句法分析，找出依存关系，并在依存分析结果的基础上进行语义相似度计算；3对基于语义分析的相似度计算；4编辑距离的相似度计算。但是，这四种方法也都存在着自身的缺点，给计算带来了一定的误差；因此在不同的应用领域，应根据需要选择不同的计算方法，这样就可以更加全面、准确地衡量句子之间的相似度。252基于向量空间模型的TFIDF方法这种方法适用于信息检索领域，其基本思路是借助向量之间的距离来逼近文本之间的相似性。TFIDF的主要思想就是如果某个词或短语在一个句子中出现的频率TF高，并且在其它句子中很少出现，则认为此词或短语具有很好的类别区分能力；但是如果包含某词或短语的句子数很少，则此短语也有很好的识别能力【291。下面利用TFIDF方法计算两个句子之间的相似度。定义L语料库中所有句子包含的不同词语集合表示为职C阢，既，既其中C表示中文语料库，所IL，2，玎为中文语料库做分词处理后统计的不同词语。定义2词语在句子里的词频TF玩21乙体上式中刀I是该词语在该句子中出现的次数，而分母则是所有词语出现次数之和。1一个词语预测句子主题能力越强，权重就越大，反之，权重就越小。2应删除词的权重应该是零。如果一个词语只在很少的句子中出现，通过它就很容易锁定搜索目标，它的权重就应该很大。反之一个词语在大量句子中出现，就仍然不很清楚搜索内容，这要借助一个权重计算公式。定义3逆向文档频率IDF；娥札G尚22其中，IDI代表语料库中的句子总数，LPW，DI代表包含词语WI的句子数目9HTTP/INFO3DOUCOM/口碑营销基于HO、，NET多特征结合的句子相似度计算即麒0句子数目。那么每个词语的权重计算公式GI斫幸F彤23就可以得出语料库中每个句子向量QIGI，92GN，IL，2，肌，朋表示语料库中句子总数。用同样的方法来构造目标句子权重向量DDL，如，巩，最后向量之间夹角的余弦值来计算两个句子间的相似度。定义4相似度公式生吼以所掰QF，D1兰兰一24、G；彳Y七L七盅LTFIDF的概念被公认为信息检索中最重要的发明，在搜索、文献分类和自动问答等领域有广泛的应用【2引。TFIDF方法综合考虑了不同的词在句子中的出现频率和这个词在整个语料库中对不同句子的分辨能力。这种方法不需要任何对文本内容的深层理解，它能够在语料库中应用，很重要的一个原因是语料库是非受限域的自然语言文本，而且语料库通常都很大。这种方法面对的最大的困难之一就是向量空间的高维性，容易造成数据稀疏问题，增加计算时间复杂度。所以在对性能要求比较严格的情况下，必须对向量空间进行降维。253基于语义依存的句子相似度计算依存句法是由法国语言学家LTESNIERE在其著作结构句法基础中提出，对语言学的发展产生了深远的影响，特别是在计算语言学界备受推崇。依存语法通过分析语言单位内成分之间的依存关系揭示其句法结构，主张句子中动词是支配其他成分的中心成分，而它本身却不受其他任何成分的支配，所有受支配成分都以某种依存关系从属于支配者。依存句法分析可以反映出句子中各成分之间的语义修饰关系，它可以获得长距离的搭配，并跟句子成分的物理位置无关。利用依存结构计算句子间的相似度【301，关键的一步是如何获得句子各成分间的依存关系信息。20世纪70年代，ROBINSON提出依存语法中关于依存关系的四条公理，在处理中文信息的研究中，中国学者提出了依存关系的第五条公理【3111一个句子中只有一个成分是独立的；2其它成分直接依存于某一成分；3任何一个成分都不能依存于两个或两个以上的成分；4如果4成分直接依存于B成分，而C成分在旬中位于彳和B之间，那么C或者直接依存于B，或者直接依存处于彳和曰之间的某一成分。5中心成分左右两边的其它成分相互不发生关系。10硕士学位论文目前国内，哈尔滨工业大学信息检索研究室开发了依存句法分析器。该依存分析系统使用的训练数据是该实验室标注的汉语依存树库，在平均句长为20词的测试集中，该系统的准确率为70左右。其依存体系共包括24个依存关系类型，准确率是指结点及关系类型均分析正确的依存弧总数，占测试集中全部依存弧数量的比例。在利用依存结构进行相似度计算时，只考虑那些有效搭配对之间的相似程度。所谓有效搭配对是指全句核心词和直接依存于它的有效词组成的搭配对。这里有效词定义为动词、名词以及形容词，它是由分词后的词性标注决定的。相似度计算公式如下公式25彬跏跚，觋2瓦面丽盖丽丽25形为句子L和句子2有效搭配对匹配的总权重，砌F，C伽刀FL为句子L的有效搭FL配对数，尸口F，C鲫刀F2为句子2的有效搭配对数。这种方法从句法深度进行考虑，考虑到了词与词之间的依存关系，对句子的理解更加充分，从而更准确的得到句子相似度的值。但是，现有的句法分析技术还不够成熟，还无法将所有的句法信息特征全部考虑进来，所以就产生了一定的误差。254基于语义距离的语句相似度计算计算基于词义的语句相似度时，需要借助于一个本体知识库本体网络层次图。本体是对客观存在的一个系统、全面的解释，其核心是表示客观现实的抽象本质。STUDER等人对本体进行了深入的研究，给出了关于本体的一个最完整的定义“本体是共享概念的明确的形式化规范说明一【321。它包含四层含义1概念模型；2明确化；3形式化；4共享性。在中文语义相似度计算中，要利用中文本体库知网HOWNET3引。它是一个以汉语和英语的词语所代表的概念为描述对象，以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。它着重反映概念的共性与个性、概念之间和概念的属性之间的各种关系。在知网中，义原是最基本的、意思不能分割的最小语义单位。将它们组合成词语的概念，这些概念组合成词语，词语再组合成句子【341。1义原相似度计算由于所有的概念都最终归结于用义原个别地方用具体词来表示，所以义原的相似度计算是概念相似度计算的基础。由于所有的义原根据上下位关系构成了一个树状的义原层次体系，这里采用简单的通过语义距离计算相似度的办法【2引。假设两个义原在这个层次体系中的路径距离为D，可以得到这两个义原PL和P2之间HTTP/INFO3DOUCOM/口碑营销基于HO、，NET多特征结合的句子相似度计算的相似度跏环P2赤26其中PL和P2表示两个义原，D是PL和P2在义原层次体系中的路径长度，是一个正整数。口是一个可调节的参数。2概念相似度计算对于两个概念SL和，如果SL有册个义原尸LL，P12，PLM，有刀个义原P2L，尸22，尸2N，而义原尸LI和尸2J之间的相似度用M尸LI，尸2J表示。规定SL和的相似度为各个义原的相似度的最大值【241。也就是跏，S，M氅加只，只，27LI州，L一。3词语相似度计算对于两个汉语词语蹦和，如果矾有肼个义项概念SLL，S12，SLM，有刀个义项概念L，2，N。规定，矾和的相似度各个概念的相似度之最大值，也就是说跏，_渊焉譬。跏ST，SJ28这样把两个词语之间的相似度问题归结到了两个概念的相似度问题。4句子相似度计算对于两个汉语句子L和以，如果以有朋个词语矾I，阢2，矾M，也有刀个词语L，耽2，耽N，则词阢I1F朋和岷1_，刀之间的相似度可用蜘暇，吸，表示，那么句子和以的相似度为Q6，跏L，J2上LL229|FLLL式中口FMAXS砌WLF，W21，鲥聊WLF，W22，斫聊WLFW2。；6JMAX鲥，W2J，WIT，舒朋W2，W12，鲥埘W2，WL。在相似度计算时，该种方法充分考虑了句子中每个词的深层信息，使表层不同，深层意义相同的词被挖掘出来。但由于词典的不全面和一些未登录词的词义代码的缺失，也给计算带来了一定的误差【3”。255编辑距离计算方法编辑距离，又称LEVENSHTEIN距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插12硕士学位论文入一个字符，删除一个字符。编辑距离最初面向的是不考虑语义的字符处理，在字符串相似度计算、自动文摘、拼写检查、图像识别、音乐识别、语音识别、数据清理等众多领域都有着广泛的应用，在句子的相似度计算方面，也取得了一些成果，例如GLEUSCH利用编辑距离计算句子相似度并用于机器翻译评价【36J。在编辑距离方法的基础上，又提出了一些新的方法。车万翔利用改进编辑距离方法用于中文相似句子的检索【271。该方法的主要思想是以普通编辑距离算法为基础，采用词语取代单个的汉字或字符作为基本的编辑单元参与运算。同时使用了HOWNET和同义词词林两种语义资源，计算词汇之间的语义距离，加入词语的语义相似信息确定词语之间的替换代价，并且赋予不同编辑操作不同的权重。在不用经过词义消歧和句法分析的情况下，兼顾了词汇的顺序和语义等信息，使之更加符合中文句子相似度计算的要求。26存在的主要问题用计算机来实现自然语言理解，汉语比英语具有更大的困难。英语是形合语言，造句要求词的形态变化符合规则，注重句法平面。而汉语是意合语言，造句要求词的意义搭配符合情理，注重语义平面。所以，汉语句子的相似度计算难度更大，而目前关于汉语句子的相似度计算的方法多少存在一些不够完美的问题。单纯的使用语义词典的计算方法，没有充分利用句子中的其他特征，没有考虑句子的内部结构和词语之间的相互作用和联系，因此准确率并不高。而基于编辑距离的方法通常被用于句子的快速模糊匹配领域，但是其规定的编辑操作并不灵活。编辑距离算法是以字为基本计算单位，而在汉语中，单个的字往往是不具备意义的。还有使用较多的基于向量空间模型的TFIDF方法，也有一些不足之处。首先，只有当句子所包含的词语足够多时采用该方法效果才会比较好。例如该方法使用在问答系统的常用问题库中，用于比较问句和问题答案对的问句的相似度时，FAQ库中所面对的是单个的句子，句子包含的词的个数往往不足体现这种效果。它是一种基于统计的方法，基于统计的计算方法需要有大规模的语料库支持，大规模的语料库的构建本身就是一件比较困难，需要消耗大量人力和时间的工作，并且还存在着数据稀疏问题。其次，TFIDF方法只考虑了词在上下文中的统计特性，丢弃了句子的结构信息和语义信息，因此具有一定的局限性。本文提出的计算方法从多个方面考察句子的相似性，提出基于多种特征结合的句子相似度计算方法。多特征是指关键词集、关键词词性、关键词的权重、关键词个数、语义信息等。并对组成词语的概念相似度进行分析，进而对组成概念的义原相似度进行分析和计算。通过实验比较得到了明显改善，该算法充分利用句子的结构和语义信息，提高了相似度计算的准确性和效率。13HTTP/INFO3DOUCOM/口碑营销基于HOU，NET多特征结合的句子相似度计算第3章基于双数组TRIE树分词算法的研究中文词语分析是中文信息处理中非常重要的基础工作，在语句分析、词义消歧和信息抽取等方面有着重要的作用，词语分析结果的质量将直接影响后续工作。中文文本进行语义相似度计算之前，需要对文本进行的预处理主要是词语分析，包括分词、标注词性、剔除高频虚词、剔除停用词、同义词归类和语义排歧等。31分词词是最小能够独立活动的有意义语言成分，是自然语言的基石，是语言更高层次自动分析的基础。英文是以词为单位的，词和词之间是靠空格自然隔开，而中文是以字为基本单位，句子中所有的字连起来才能表达一个意思。由字成词，再构成块和句子，词与词之间没有显示的界限。把中文汉字序列切分成有意义的词，就是中文分词，也称为切词。311中文分词技术现有的分词算法可分为三大类【37L基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。到底哪种分词算法的准确度更高，目前并无定论。对于任何一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都需要综合不同的算法。对于中文词的识别，需要多种算法来处理不同的问题。312分词中的难题有了成熟的分词算法，是否就能容易的解决中文分词的问题呢事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破歧义识别和新词识别。1歧义识别歧义是指一句话可能用两种或者更多的切分方法来表达不同的意思，分为交叉歧义、组合歧义和真歧义三种。交叉歧义相对组合歧义来说是还算比较容易处理，组合歧义就必需根据整个句子来判断了。真歧义意思是给出一句话，由人去判断也不知道哪个应该是词，哪个应该不是词。歧义识别的目的就是要通过较好地理解文本上下文语境，选择合适的词语切分方法。2新词识别新词，专业术语称为未登录词。也就是那些在字典中都没有收录过，但实际上能称为词的那些词。最典型的就是人名，人可以很容易理解句子R王小兰离开深圳回老家了J中，R王小兰J是个词，因为是一个人的名字，但要是让计算机14硕士学位论文去识别就困难了。新词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又是人们经常使用的词，因此对于信息检索来说，分词系统中的新词识别十分重要。目前新词识别准确率已经成为评价一个分词系统好坏的重要标志之一。313本文的方法本文是利用一部知网语义词典来构造双数组进行分词。一般来讲，词典结构基于HASH方法。关键技术在于HASH函数的设计，采用合理的方式来调节数据块的分配，控制分布的均匀性，减少冲突，提高空间利用率。针对HASH的词典结构，主要有以下几种搜索算法1整词二分法结构首字散列表、词索引表、词典正文；优点数据结构简单、占用空间小；缺点全词匹配，效率相对来说不高。2TRIE索引树法结构首字散列表、TRIE索引树结点；优点分词中，不需预知待查询词的长度，沿树链逐字匹配；缺点构造和维护比较复杂，单词树枝多，浪费了一定的空间。3逐字二分法结构同整词二分法；优点查询采用逐字匹配，提高了一定的匹配效率；缺点由于词典结构未改变，效率的提高有限。TRIE树是搜索树的一种，它利用关键码的字符，自左向右，每次插入一个得到TRIE树。这种树数据结构复杂，查询效率较低。AOEJ提出了用2个线性数组来进行TRIE树的表示，即双数组TRIEDOUBLEARRAYTRIE，较之TRIE树占用较少的空间同时保证查询的效率。3131双数组TRIE树DAT基本原理TRIE树是搜索树的一种，它在本质上是一个确定的有限状态自动机DFA，每个节点代表一个状态，根据输入变量的不同，进行状态转移，当到达结束状态或者无法转移时完成查询。TRIE树可用于确定词条的快速检索F3引，对于给定的一个字符串D口2口扎口刀，采用TRIE树搜索最多经过刀次匹配即可完成一次查找即最坏是D仰，而与词库中词条的数目无关，缺点是空间空闲率高，它是中文匹配分词算法中词典的一种常见实现。双数组TRIE树是TRIE树的一种变形，是TRIE树的一个简单而有效的实现，在HTTP/INFO3DOUCOM/口碑营销基于HOU，NET多特征结合的句子相似度计算保证TRIE树检索速度的前提下，可以提高空间利用率而提出的一种数据结构。DAT由两个整数数组构成，一个是6口SP【】，另一个是幽P如】，它们均为线性数组1391。6口SP数组和数组中的元素是一一对应的，6伽E数组中的每一个元素相当于TRIE树的一个节点，其值作状态转移的基值；C