[硕士论文精品]q 基于限定领域的问句相似度

天津师范大学硕士学位论文摘要问答系统为人们提供了自然语言的人机交互方式，相对于传统的关键词方式搜索引擎来说，其具有显著的优势。在受限领域，基于问题库的问答系统在对问题答案的定位上，有更准确，快捷和高效的特点，在日常生活的各个领域，有着非常重要的应用前景，是当前研究的热点问题。本文围绕台球领域自动问答系统实现过程中的领域知识库构建、问题库的的收集和组织、相似问句的查找及答案提取等关键核心技术进行了一系列的研究和探讨，实质性工作和取得的主要成就如下L、对现有的自动分词方法进行分析，并根据限定领域的特点，选择适当的分词算法并进行适当的设计。2、对词语间的语义相关度的计算方法和中文的句法进行了比较详细的研究，对本系统的进一步发展打下了比较坚实的基础。3、对中文语句的相似度计算进行了深入的研究，对比了现有比较成熟的问句相似度算法的优缺点，并针对限定领域的特点，提出了一种针对台球领域的问句相似度计算方法，并将它应用到面向台球领域的自动问答系统中。4、设计并实现了面向台球领域的自动问答系统。构建了领域知识库和领域问题库，采用本文所提出的基于关键词的倒排索引的问句相似度计算方法，进行问句相似度的计算，实现系统的自动问答。面向台球领域的自动问答系统的测试结果表明了此方法可行，有比较好的实用效果。关键词问答系统、问题集、台球领域、自动分词、问句相似度计算HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文ABSTRACTQUESTIONANSWERINGSYSTEMPROVIDESTHEHUMANMACHINEINTERFACEBYMEANSOFNATURAL1ANGUAGECOMPARINGTOTHETRADITIONALSEARCHENGINEWHICHISBASEDONTHEKEYWORD，QUESTIONANSWERINGSYSTEMHASPROMINENTADVANTAGESINTHERESTRICTEDDOMAIN，QUESTIONANSWERINGSYSTEMONTHEQUESTION1IBRARYISMOREACCURATE，SIMPLYANDEFFICIENCYATLOCALIZATIONTOTHEQUESTIONANSWER，INEACHDOMAINOFDAILY1IFE，ITISTHEKEYPROBLEMOFPRESENTRESEARCHANDWILLBEABRILLIANTAPPLICATIONINTHEFUTURETHISPAPERDOSEASERIESOFRESEARCHWHICHRESOLVEMETHODOFAKNOWLEDGEBASECONSTRUCTEDINTHEDOMAIN，METHODOFQUESTIONANSWERRETRIEVAL，THEC01LECTIONANDORGANIZATIONOFQUESTION1IBRARYINTHERESTRICTEDDOMAIN，QUESTIONCLASSIFICATIONINTHEIMPLEMENTPROCESSOFQUESTIONANSWERINGSYSTEMBASEDONBILLIARDSDOMAINTHEMAINWORKSINTHISPAPERAREASFOLLOWSFIRSTLY，ANALYSEDTHEEXISTINGMETHODSOFCHINESEWORDSEGMENTATIONANDACCORDINGTOTHETRAITSOFRESTRICTEDDOMAIN，SELECTEDTHEAPPROPRIATEMETHODOFCHINESEWORDSEGMENTATIONANDALSODESIGNITSECONDLY，STUDIEDTHEMETHODOFCOMPUTINGSEMANTICSIMILARITYBETWEENCHINESEWORDSANDTHECHINESEQUESTIONSENTENCEPATTERNSINDETAIL，THISSTUDIES1AIDASOLIDFOUNDATIONFORTHEDEVELOPMENTOFTHEQUESTIONANSWERINGSYSTEMTHIRDLY，HASCONDUCTEDTHETHOROUGHRESEARCHTOCHINESESENTENCESIMILARITYCOMPUTATION，HASCONTRASTEDTHEEXISTINGQUITEMATUREINTERROGATIVESENTENCESIMILARITYALGORITHMGOODANDBADPOINTS，ANDAIMSATTHEDEFINITIONDOMAINTHECHARACTERISTIC，PROPOSEDONEKINDINVIEWOFTHEPINGPONGDOMAINSINTERROGATIVESENTENCESIMILARITYCOMPUTATIONALMETHOD，ANDAPPLIESITFACEINTHEPINGPONGDOMAINAUTOMATICINTERROGATORRESPONDERSYSTEMFOURTHLY，DESIGNEDANDHASREALIZEDFACETHEPINGPONGDOMAINII天津师范大学硕士学位论文AUTOMATICINTERROGATORRESPONDERSYSTEMHASCONSTRUCTEDTHEDOMAINKNOWLEDGELIBRARYANDTHEDOMAINQUESTIONSTOREHOUSE，USESBASEDONKEYWORDREVERSEINDEXINTERROGATIVESENTENCESIMILARITYCOMPUTATIONALMETHODWHICHTHISARTICLEPROPOSED，CARRIESONTHEINTERROGATIVESENTENCESIMILARITYTHECOMPUTATION，REALIZESSYSTEMSAUTOMATICQUESTIONANDANSWERHADINDICATEDFACETHEPINGPONGDOMAINSAUTOMATICINTERROGATORRESPONDERSYSTEMSTESTRESULTTHISMETHODISFEASIBLE，HASTHEQUITEGOODPRACTICALEFFECTKEYWORDQUESTIONANSWERINGSYSTEM，QUESTIONLIBRARY，BILLIARDSDOMAIN，CHINESEWORDSEGMENTATION，SENTENCESIMI1ARITYCOMPUTATIONIIIHTTP/INFO3DOUCOM/网络推广独创性声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得苤垄至莲盘堂或其它教育机构的学位或证L；而使川过的材料。与我一同IF作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名蚴日期丛幽学位论文版权使用授权书本人完全了解天津师范大学有关保留、使用学仿论文的规定，即学校有权将学位论文的全部或部分内容编入有关数据库进行检索，并采川影印、缩印或扫描筹复制手段保存、汇编以供夯阅和借阅。同意学校向国家有关部FJ或机构送交论文的复印件利磁盘。保密的论文在解密后应遵守此规定签名蚴导师签名矢近日期趁幽天津师范大学硕士学位论文第一章绪论11论文的背景研究问答系统QUESTIONANSWERINGSYSTEM是指能够对计算机用户输入的使用自然语言描述的闷句做出回答的计算机程序N1。问答系统集自然语言处理、信息检索、知识表示为一体，正同益成为国际上研究的热点。它既能够让用户用自然语言提问，又能够为用户返回一个简洁、准确的答案，而不只是一些基于关键词的似是而非的答案。因此，问答系统和传统的依靠关键字匹配的相关的检索系统相比，能够更好地满足用户的检索需求，更准确地找出用户所需要的答案，具有方便、快捷、高效等特点心1。早在上世纪60年代人工智能研究刚开始的时候，人们就提出了设计一种让计算机用自然语言来回答人们的问题的系统，即自然语言问答系统。问答系统在上世纪80年代的自然语言处理领域曾风靡一时，因为TURING实验告诉人们如果计算机能够像人一样与人进行对话，就可以认为计算机有智能，所以研究者们为了探索语言理解技术，纷纷研究自然语言问答系统。但是由于当时的条件限制，所有的实验都是在非常受限的领域，甚至是固定段落上进行的，所以自动问答一直被限制在特殊领域的专家系统。此后，由于大规模文本处理技术的兴起，问答系统的研究受到了冷落D1。最近几年，随着网络和信息技术的快速发展，同时人们想更快地获取信息的愿望也重新促进了自动问答技术的发展。有越来越多的的公司和科研院所参与自动问答技术的研究，比如微软和IBM等公司。在每年一度的文本信息检索TREC会议上，自动问答QUESTIONANSWERINGTRACK是最受关注的主题之一，越来越多的大学和科研机构参与了TREC会议的QUESTIONANSWERINGTRACK【41。在2000年LO月召开的ACL2000国际计算语言学学术会议上，有一个专题讨论会，题目是“OPENDOMAINQUESTIONANSWERING”。目前，国外已经开发出一些相对成熟的问答系统。麻省理工学院开发出问答系统START，从1993年开始发布在INTERNET上，网址为H主主卫；么么墨主垒主璺墨垒I虫I主里鱼坚么，可以回答一些有关地理、历史、文化、科技、娱乐等方面的简单问题。例如用户提问“HOWMANYCOUNTRIESINTHEWORLD”，START系统将会回答“IHAVEINFORMATIONABOUTTHEFOLLOWING263COUNTRIESINTHEWORLD”。另外还有其他比较成熟的问答系统像ANSWERBUS，一L一HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文它是个多语种的自动问答系统，不仅可以回答英语的问题，还可以回答法语、西班牙语、德语、意大利语和葡萄牙语的问题瞄1，其网址为HTTPMISSHOOVERSIUMICHEDU“ZZHENGQANEW。LASSO61系统是运用自然语言处理方法分析使用者输入的问句，将问句依其型态加以归类，并提取出问句的中心焦点后，从大量文件中找出符合使用者需求的答案出来。国内也有一些高校和研究机构对自动问答系统进行研究，中科院计算所、哈尔滨工业大学、复旦大学、北京理工大学、香港科技大学等。但是整体来说，参与中文自动问答技术研究的科研机构比较少，而且基本没有成型的中文自然语言问答系统。自然语言问答系统的人机界面、精确性和实时性是汉语自然语言问答系统的三大研发目标口1。其中，精确性是自然语言问答系统的首要目标。为了达到这一目标，在用户问句处理方面，需要对用户输入的问句进行正确的分词和词性标注、同义词扩充、名实体标注、句法分析、语义分析、答案类型标注等等处理，对于领域文本知识库也要进行同样的处理。尤为重要的是，需要一个综合考虑用户问旬与文本片断的语言语义信息，精确计算用户问句与文本库中句子的相似度大小的方法，使得蕴含答案的句子获得一个相对较高的计算结果，较早的返回给用户，从而提高信息检索系统的精确性，并提高答案自动抽取的精度和效率。句子相似度的计算是自然语言问答系统的核心所在，其计算方法的精确性和实时性关系到整个系统的精确性和效率。在自动问答系统中句子相似度的计算是一个最重要的理论基础。问答系统中很多地方都需要用到语句相似度的计算，自动问答系统中旬子相似度的计算大致可分为两类问题与问题之间的相似度计算和问题与答案之间的相似度计算。在问题库中需要用到问题与问题之间的相似度，在答案抽取模块中需要用到问题和候选答案之间的相似度，甚至在答案抽取模块中的多文档自动文摘也要用句子相似度来对句子进行聚类。本文主要的研究对象是用户提出的问题与问题库中问题之间的相似度。12问答系统现有的类型国1随着国内外越来越多的机构投入到问答系统的研究，目前自动问答技术已经取得了一定的成绩，出现了许多优秀的问答系统，其现有类型主要有聊天机器人、基于知识库的问答系统、问答式检索系统，以及基于自由文本的问答系统等。2天津师范大学硕士学位论文121聊天机器人F1966年实现的“E1IZA”是第一个聊天机器人，它运用自然语言以聊天的方式与人交互。ELIZA扮演一个心理学者的角色，往往用反问来应对用户的提问。1973年，有人做了模仿精神病人的图灵测试的实验，所编的程序为PARRY，PARRY没有语法分析部分，只是通过大约6000条模式匹配规则来实现它的功能，但能够成功地欺骗很多人。近年来出现的聊天机器人，多是以通过“图灵测试“为目的参加“LOEBNER”比赛的程序，如ALIC素W2第二个条件表示第一基本义原描述式反映了一个概念的最主要特征，所以它的权值一般定义的较大，要大于08。根据公式32可以得到两个概念之间的语28天津师范大学硕士学位论文义相似度。知网中一个词语往往有多个概念，对于两个汉语词语W和W2，如果W。有N个义项概念CU，CM，CLNW。有IN个义项概念C舯C。，C扫。我们规定，词语W。和W的相似度为各个概念的相似度之最大值，也就是说跏彤，M强跏CL，C2，LIN，I脚公式33这样，我们就把两个词语之间的相似度问题归结到了两个概念之间的相似度问题。29HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文第四章中文问句特性分析及中文句法处理41句法分析简述411经典的形式句法理论句法分析的主要任务是把句子中的词语序列映射为句法成分的层次结构，句法分析是在词法分析的基础上进行，词法分析的正确性影响句法分析的正确性。任何句法分析都有一个按某种语法形式和符号约定的规则库，这是句法分析的基础，目前句法分析主要以下几种语法类型1、短语结构语法美国语言学家乔姆斯基在20世纪50年代创造了形式语法，是用数学方法研究自然语言和人工语言的语法理论N引。在形式语法中，一共定义了4类语法，这类语法统称为短语结构语法PHRASESTRUCTUREGRA舳AR，PSG。一个PSG形式定义如下G巧，只S其中，V，是终结符词汇集，它包含的词是语言中的最小单位。VN是非终结符词汇集，包括一些用以表示文法的中间符号。巧U合称为词汇表V。P是产生式规则集，每个产生式可以表示为QP，Q是V中一个或多个符号构成的序列，B是V中零个或多个符号构成的序列。S是文法的起始符号，SV。2、扩展转移网络1969年美国人工智能专家WAW00DS推出了扩展转移网络AUGMENTEDTRANSITIONNETWORK，ANT模型N86|，是自然语言语法多功能表示及语言自动分析的方法。转移网络有识别语句的功能，如果决定从一个状态转移到另一个状态的输入不是一个个字母，而是一个个的词，那么转移网络就可能用来识别自然语言中的短语和句子。从句子中抽象出一个共同的结构形式，可以使一个网络识别多个同类的句子。2、词汇功能语法词汇功能语法LEXICONFUNCTIONGRAMMAR，LFG认为句子由两个相互独立的层次来描述，即成分结构层次和功能结构层次N7181。成分结构层次描述句子成分之间满足的规则，功能结构层次描述句子的主语、谓语等部分要满足的语法功30天津师范大学硕士学位论文能关系。这种语法功能关系体现为特征结构的一致，特征结构由属性和属性值的偶对来表示。只有同时满足两个层次的规则要求才能形成成功的分析。4、功能合一文法MKAY于1985年提出功能合一文法FUNCTIONALUNIFICATIONGRA姗AR，FUGN7博1。功能描述由一组描述元组成，每一个描述元表示为E缸P；，可以是一个“属性一值”偶对，也可以是另一个功能描述。功能合一文法系统使用复杂特征集来定义词汇、句法规则、语义规则。整个句子的描述，通过合一运算把几个功能描述合并为一个功能描述。FUG的优点在于它把语言看作一个传递和负载信息的符号系统，认为句子的信息可以由更小的单位，如词汇或短语合并而得到，这种合并可以用合一运算来实现。合一运算既包括了语法规则的信息，也包括语义合法性判断，因此它把句子的语法结构和语义表示较好地结合起来。412句法分析常用算法4121基于上下文无关文法CFG的分析方法虽然各种语法形式相差很大，不过在句法分析的过程中采用的基于规则的分析算法都是类似的。常用的句法分析算法有N力N引自顶向下算法、自底向上算法、左角分析算法、CYK算法、MARUCS确定性分析算法、EARLEY算法、TBMITA算法GRL算法、CHART算法等。其中，白底向上分析和自顶向下分析算法是最基本的算法，但实际运用效果不理想，TOMITA算法和CHART算法是目前应用得较为广泛的句法分析算法。1、自顶向下分析算法。该算法是自顶向下回溯算法的分析方法，它逐个地枚举推导直至找到一个能生成输入句子结构的推导。自顶向下的分析假定一个节点可以替换为下面的节点，从根到叶，逐步分枝，从抽象到具体，从整体到部分，寻找与叶子相匹配的句法结构。2、自底向上分析算法。这种方法是从句子的单词序列出发，以自底向上的方式建立一些局部分析，又具体到抽象，一步步地归并，最后到达根节点S。因此它首先应该使用N、V、M等最具体的改写规则，按照规则中箭头所指的反方向使用规则。31HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文3、CHART算法。线图分析CHARRTPASRNIG算法的主要思想是在分析调度器的控制下，每次尽可能选择最佳的成分边进行组合扩展，从而迅速得到句子的最佳分析树，分析效率较高。CHART算法中最重要的数据结构是“线图”CHART和“日程表”AGENDA。线图是把词与词之间的问隔作为节点，把词和短语当作连接节点的边。日程表是一个边的集合，用于存放己经产生，但还没有加入到CHART中的边。CHART分析的过程是一个不断产生新边的过程，每一条新产生的边首先放到日程表中。4122基于概率上下文无关文法PCFG的分析方法自然语言灵活多变，以上下文无关文法为基础构造的规则系统必定是有歧义的。歧义消解成为句法分析中的一个重要问题。单纯依靠文法形式的改进来改造无歧义的文法规则系统，在目前看来非常困难。由于难以利用文法规则系统本身来消除歧义，因此依靠另外的手段来从多个分析结果中选出最优解。基于大规模的真实语料库进行概率统计是目前最常用的方法，其基本过程是N明啪1构造一个合适的语言概率模型，利用大规模的真实语料对模型中的基本参数进行训练，然后在此概率模型中对每个句法结果通常是句法结构树进行评分，并以这个分值作为优选的依据。这样，在语言概率模型中，句法歧义消解的问题就转化为对句法结构树进行评分的问题。概率型上下文无关模型是上下文无关文法CFG的扩展，一部概率上下文无关文法和普通的上下文无关文法的区别在于在概率上下文无关文法中，每条产生式规则都拥有一个概率值。概率上下文无关文法可形式定义为下面的四元组G，尸其中，VX是非终结符号的集合，1，2，”；VT是终结符号的集合，巧加1，W2，WY；NL是文法的开始符号；P是一组带有概率信息的产生式所组成的集合，每条产生式形如【一F7，尸JFJ，7斗F是普通的上下文无关规则，P。寸F7是产生式的概率，并且P7专F71，即左部相同的所有产生式的概率之和为1。令。W1W2W卅为一个句子终极符号串，若给定概率上下文无关文法32天津师范大学硕士学位论文G，句法分析的任务实际上就是在众多可能的分析树中寻找一棵具有最大概率值的分析树T，这个过程通常用下面的公式描述F鹕MA【尸FLW加，G一棵分析树的概率是得到该分析树所用到的产生式的概率的乘积。T代表句子W，。的一棵分析树，假设为得到该分析树，共用到N条产生式规则硝专F。后1刀，则分析树T的概率为PO卫P以寸F概率上下文无关文法在句法排歧方面的能力有限，因为概率上下文无关文法评价分析树时倾向于给那些使用了高频规则的句法树以较高的概率值，如果句法树中使用了低频规则，概率值会较小，另外，利用概率上下文无关文法去评价一棵分析树，没有考虑词对结构的影响。42中文特性分析及其句法处理421中文特性分析作为一种孤立语分析语，汉语的根本特点是缺乏严格意义上的形态标志和形态变化。同西方语言相比，汉语的句法分析将面临以下困难洲乜1、汉语句子需要分词，易产生歧义切分。中文文本是“字”的字符串，文章内的词与词之间没有任何区分字符。但是字与字组合成词，是有一定组合规律的，这些规律，有的是相对确定的，有的在不同的意境会有不同的切分规则，十分复杂，常常会产生歧义问题。有两种不同的类型固有歧义和组合歧义。固有歧义是根据不同意境所出现的分词歧义，如“物理学是一门基础科学”和“物理学起来很难”，其中“物理学“的切分。组合歧义切分是指某个字段，它本身并不组成一个词，但是它在不同语境的条件下，产生不同的组合切分。如“他的确切地址在这儿和“这块肉的确切的不错”中的“的确切”。这是汉语处理中非常突出的问题，几乎找不到一个通用的解决这种歧义现象的方法，常常只是一个词一个词地个别处理，使个性规则大幅度增加，造成了汉语分析的一个难题。33HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文2、谓语的组成问题西方文字谓语一般只能由动词组成，而汉语的谓语可以是动词，例如“主任回来了“；可以是形容词，如“恩情比海深”；还可以是名词，如“这马一只眼“。3、多动词联用问题动词的个数，英语中每个谓语只能使用一个“FINITEVERB”。汉语可不同，可以有多个，如“我忘了带钥匙“，IFORGETMYKEY；我倒了一杯茶给他喝。IOFFEREDHIMACUPOFTEA4、中心谓语动词的确定汉语句子中的中心动词难以确定，如“讨论的目的是为了制定教学改革计划“，又如“这是开发建设发展有特色的民族工业”。迄今为止，还没有一个对汉语通用的确定中心动词的有效的方法。5、主语和施事问题一般说来，主语和施事是一致的，如“我吃饭”。主语是“我”，动作的发出者，是施事。但常常有这样的反常现象“老头晒太阳“、“肉夹模”，不是“老头晒了太阳”，而是“太阳晒了老头”，也不是“肉夹模”，而是“模夹肉“。6、形态变化问题西方语合一般通过词本身的形态变化来表达语法意义性、数、时一等。而汉语就没有这种形态变化。例如IHAVEWRITTENTHELETTER我写了信，I锄WRITINGALETTER我正在写信。同样都是行为动词“写”，汉语只有一个“写“字，英语则用词形变化来表示己经完成和正在进行的时态。由于自然语言的特点，给计算机的自然语言处理带来很大的困难，在句法分析中就涉及到以上诸方面的影响。422中文句法分析中的困难由于汉语言的特性，中文信息计算机处理中的句法分析的困难主要体现在处理中的歧义问题，完整的中文句法分析包括词法和句法两个语言层次，两个层次都存在相应的歧义，主要有词语边界歧义、词性兼类、词义歧义和句法结构歧义座I盘守OL、词语边界歧义34天津师范大学硕士学位论文词语边界歧义指的是指计算机在切分某个汉字串时，有多种词语边界划分形式。汉语词语边界歧义包括组合歧义和交叉歧义瞳列，定义如下。定义31组合歧义喝交叉歧义设有一汉字串CC。，C，C。，如果C构成词且存在整数0如，I。，_，。，2，L，L2，满足CNCL，CF2一勺2，C加分别构成词；1其中，正咒109肘M，N为词语彬在该问句中出现的次数，M为问句语料库中包含词语彬的问旬数量，M为语料库中的问句总数量。以上正的综合表达式反映了一个关键词的出现频率和这个关键词对不同问句的分辨能力，即一个词语在某个问句中出现的次数越多，则它对该问句越重要，如果在整个问句语料库中出现的次数越多，则其分辨能力越低。例如汉语中“的”出现的频率非常高，即TF值N值很大，但由于“的”在很多句子中都出现，其IDF值109M聊将是一个很小的数值，所以对于分辨各个问句并没有太大的帮助。设任意两个问句的N维向量分别表示为P和F，则其相似度计算如下39HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文即问句相似度为两个问句向量的余弦夹角。TFIDF方法综合考虑了不同的词语在问句中的出现频率TF值和这个词在整个语料库中对不同句子的分辨能力IDF值，不需要对文本内容的任何深层理解。但是在实际应用中，该方法难以达到预期结果，原因如下首先，TFIDF是一种统计方法，只有当语料库具有一定的规模，句子中包含的词语数量足够多时，相关的词语才会重复出现，这种统计方法的效果才能体现出来，而对于一般的句子相似度计算，面对的往往是单个的句子，句子中包含的词语数量还不足以体现这种方法的效果；其次，该方法只考虑了词在上下文中的统计特性，而没有考虑词语本身的语义信息，具有一定的局限性。512语义词典方法语义词典方法主要是利用知网、同义词词林等现有的、较为成熟的语义资源，通过计算问句之间的词语相似度，进而计算问句的相似度。如秦兵2003口们对问句相似度的计算研究。假设词语的相似度可以通过某种方式计算得到，则任意两个句子A和B，A包含的词为彳。，么，么。，B包含的词为E，岛，或，词41FS朋和B1歹N之间的相似度表示为S4，艿，句子A与B之问的语义相似度跏彳，B可通过下式计算跏彳，B口，掰FI其中口，MAX04，蜀，5么，B2，5彳F，吃”；语义词典方法在处理两个句子中相同词很少，但两个句子语义相同的情况，效果要优于TFIDF方法。但由于目前对词的语义标注理论还不成熟，词语消岐研究也是一个难点问题，单纯依靠词语的信息有时侯并不能完全真实反映真实问句40天津师范大学硕士学位论文所表达的含义，而且该方法在计算句子的相似度时，以相似度最大的匹配词选取来计算，没有考虑句子的结构信息，因此准确率还难以达到令人满意的程度。513依存树方法句子相似度计算应该既要考虑句子的结构信息和词汇语义信息，又要力图避免句法分析所带来的高难度和高复杂度，基于该思想，穗志方1998首先提出了基于骨架依存树的语句相似度计算模型乜71，即只分析出句子的整体句法结构。其中，整体句法结构用句子的谓语中心词及其直接支配成分来表示，分析结果可看作一棵简化了的依存树，称为骨架依存树。骨架依存树仅限两层，第一层为根结点，即句子的谓语中心词，第二层为叶结点，是句中谓语中心词的直接支配成分；另外，还需要标注出谓语中心词与其直接支配成分之间存在的依存关系和相对位置。李彬2003也提出了一种基于语义依存的汉语句子相似度计算方法乜8J，该方法把语义与依存文法分析结合起来，有效地刻画了句子的表达意思。在计算依存树之间的相似度时，并没有匹配所有的搭配对，而是计算那些有效搭配对之间的相似程度，从而使计算的时间复杂度大大降低。依存树方法基于对句子的句法结构分析，理论上是一种较好的计算模型。但是，目前对句子各成分之间的依存关系分析准确率还不高。其中，第一种方法采取了人机交互方式，要求用户对自动执行的依存分析结果进行确认或做必要的修改。第二种方法所采用的分析器对依存弧的标记准确率只有86。相似度计算基础的不牢固导致该类方法难以取得较高的准确率，实际应用性不强。514编辑距离方法编辑距离指从一个以字符为单位的字符串转换为另一个字符串所需要的最小编辑操作的代价数犯。标准的编辑操作有“插入”、“删除“和“替换“三种。假设为有限符号字母表，。是定义在上的所有有限长度字符串集合。并设工一XZ。是中的一个字符串，其中，表示X中的第I个符号，X“，表示X中从一开始到X，结束的子串，1F，”。串ZF，的长度LXF，|_一F1；如果IJ，则一，为一空串，并有IIO。41HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文编辑操作是一个串对口，6S，占，并且A和B的长度只能为0或1，常被写作AB的形式。基本的编辑操作又可细分为3种类型，即插入操作EB，替换操作AB和删除操作AE。编辑操作的代价用一个代价函数7表示，其中Y口，6为一个非负实数。我们把字符串X转换为串Y所需要经过的编辑操作序列称为X到Y的编辑转换S，假设S对应的编辑操作序列为E，8，E。，S的代价被定义为7SL厂白给定五Y，X到Y的编辑距离艿五Y可定义如下万Z，YMIN耖SL劝石至抄的编辑序列上式也可递归定义为式中，万占，占O。如果AB，则7口，61，否则Y4，60。根据公式51的定义，编辑距离可以通过动态规划算法计算，算法的时空复杂度为D1石I1YI。另外，如果只需要计算最终的结果，而不关心具体的编辑路径，空间复杂度可以非常简单的降为DMIN1X|IYI。编辑距离最初面向的是不考虑语义的字符处理，在字符串相似度计算、自动文摘、拼写检查、图象识别、音乐识别、语音识别、数据清理等众多领域都有着广泛地应用。在汉语句子的相似度计算方面，也取得了一些成果，如车万翔利用改进编辑距离用于中文相似句子的检索泅1。该方法的主要思想是以普通编辑距离算法为基础，采用词语取代单个的汉字或字符作为基本的编辑单元参与运算，加入了词语的语义相似信息确定词语之间的替换代价，并适当降低插入、删除操作的代价，使之更加符合中文句子相似度计算的要求。问题库是问答系统中的一个重要组成部分，它把用户经常提到的问题和相关42乃0一哪工XG心地胎L产YTKM儿L扣ZLHM眠M天津师范大学硕士学位论文答案保存起来，对于用户输入的问题，可以直接将问题所对应的答案返回给用户，而不需要经过问题理解、信息检索、答案抽取等复杂处理过程，提高了效率。输入问题与问题库中的问题匹配精度直接影响查找的准确性，提高问题匹配精度将使查找的准确率大大提高。本文提出的面向限定领域的问句相似度算法的优点是可以保证当一个语句的分句或短语整体发生了移动后仍与原来的语句相似。语句相似度计算应用到问题库中，将会使查找的准确性大大提高。本文提出的基于关键词的倒排索引查找算法不仅高效，而且平均时间受问题库规模的影响很小。52基于关键词倒排索引的问句相似度计算方法的研究由于本文所要设计的自动问答系统所针对的是台球领域，在前面已经论述过，在这个限定领域中，专业性比较强，在分词中很少会出现歧义的现象，因此，在问句的相似度计算方面，领域关键词就起到了很重要的作用，而相对来说，在需求不高的情况下，不需要对问句进行语义分析就可以得到比较高的问句匹配度。这在后面的系统测试中也得到了证实。因此，在此假设下，本文设计并实现了基于关键词倒排索引的问句相似度计算方法。521语句相似度语句相似度是指两个语句相似的程度。相似度达到某个设定的阀值时，就认为这两个语句相似。语句相似度由词形相似度、语句长度相似度、词序相似度决定，词形相似度起主要作用，语句长度相似度起次要作用，词序相似度的作用最小。5211词形相似度语言L中的一个语句S是L中的单字和特殊符号以下简称单字的一个有序集合。S的长度即是S中单字的个数，此处用三P以S表示。勋MP肋耐X，】，表示语句X、Y中相同单字的个数，当一个单字在X、Y中出现的次数不同时，以出现次数少的计数。语句X、Y的词形相似度耽以孵聊X，】，由公式5一L决定耽一C耶，2意糍公式5一L从上式中易得出肋舰彳，YO，143HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文此公式的意义为两个语句相同的字数越多，两个语句越相似。例如X斯诺克台球指的是什么Y什么是斯诺克台球则耽棚X，驴未2085212语句长度相似度三E以X，P刀】，分别表示语句X和语句Y的长度，即两个语句中的单字的个数。语句长度相似度三册跏X，聊由公式52决定阴跏C硼一笔筹篙铲公式52从上式中易得出口，L跏X，】，O，1此公式的意义为两个语句的长度越接近，两个语句越相似。如上例中，三P冗X10，三P，ZY8，则P，L跏X，YO895213词序的相似度锄纱踟EX，Y表示在X、Y中都出现且都只出现一次的单字的集合。P锄P肖，Y表示锄纱锄PX，】，中的单字在X中的位置序号构成的向量，尸MDX，Y表示P锄PX，】，中的分量按对应单词在Y中的词序排列生成的向量。在上例中锄纱锄PX，Y“斯”，“诺”，“克”，“台“，“球”，“是“J“什”，“么”，X中单字与序号的对应关系为斯诺克台球指的是什么0123456789则P锄EX，】，O，L，2，3，4，7，8，9，由各分量对应的单字在Y中的顺序为什么是斯诺克台球897O】23444天津师范大学硕士学位论文则尸MD工，Y8，9，7，O，1，2，3，4。RE仍置Y表示PN阳X，Y各相邻分量的逆序数。则上例中RE仍石，Y语句X，Y的词序相似度为L一熹罴，当F锄纱踟酗ILID玎纱D胛EX，Y|_1。、L，当L锄纱锄GX，】，I1O，剖伽纱锄PX，】，LO公式53从上式中易得出0，忱坶砌石，】，0，1。这样定义语序相似度的优点是当一个分句或短语整体发生长距离移动后，仍与原来的语句很相似。算法复杂度为D，Z，其中ML伽纱伽EX，】，L。5214语句相似度语句X，Y的相似度刀纪，2CE跏X，Y由下式决定甩纪胛CGMX，】，A肋趔聊X，】，如P以丽垅X，Y眺RMX，Y公式54其中，入。，入。，入。是常数，且满足入。十入。入。1，显然，甩砌CP跏X，】，0，1。在语句相似度中，词形相似度起着主要作用，语句长度相似度和语序相似度起着次要的作用，因此入，入，入。取值时应该有入。天。，入。经过测试，现取入。08，入。O15，入。005。则上例中的两个问句的相似度为0808O15O89O05071O81由此在检索应用中可设置一个阀值作为相似的一个条件，当两个语句的相似度高于这个阀值时，就可以认为这两个语句相似。利用语句相似度可以提高检索的效率和准确性。45IHTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文522基于关键词倒排索引的问旬相似度计算方法在问答系统中，用户输入一个问题后，首先在问题库中进行问题匹配，若匹配度达到预定的值时，输出相应的答案，问答结束。设输入的问旬为INPUT，问题库中的问题集为Q，Q是问题集中的一个问句，QQ，则问题匹配的过程可以用下式描述QAI。GMAXISZ，竹办妒“F，GGQ其中Q表示找到问题集中与输入问题最相似的问句。根据以上公式，要查找与INPUT最相似的语句，需计算INPUT与问题集中的所有问句的相似度，从中选出最大的一个1。如果采用遍历法，许多与INPUT相似度为O或相似度很低的都要参于计算，算法效率低下，而且会受到问题集库规模的影响。为此，本文提出在问题库中建立候选问题集和基于关键词的倒排索引表和语句长度表来解决问题集中的匹配速度问题。5221候选问题集的建立建立候选问题集的目的是缩小查找范围，使后续的相似度计算在相对较小的范围内进行。从以上相似度计算公式中可以看出，与INPUT相似度最大的语句的勋聊P肋耐X，Y值也就较大，所以从所有的问题集问句中选出与问题相同的字数的前缸个通常设为问题集中问题总数的50就会包含与Q最相似的语句。我们把这前尼个问题组成候选问题集。候选问题集的建立本质上就是一个求鼬聊P胁耐却以，口的最大值的前后。个的集合。这个过程在后面论述的相似语句查找中动态地完成。5222基于关键词的倒排索引在候选问题集中计算前毛个勋朋P肠耐Z印“F，G时，如果将问题集中的问句一一读出来和INPUT进行比较，效率比较低。为了能够快速统计问题集中究竟有多少问句含有某个字，设计了如下数据结构，如图51所示。46天津师范大学硕士学位论文常问问题集索引表图51常见问题集的数据结构图51中的问题集中记录了所有原始问题与答案对，POS表记录了问题集中每个问句在库文件中的位置，索引表中的耐。，以，肋耐。是问题集中的问句所包含的关键词经过排序后所形成的链表，每个肠耐，指向一个S链表，这个S链表中的每个节点记录问题集中含有黝耐，的一个问句的语句号。算法L词倒排索引表和语句长度表建立算法。输入Q输出词倒排索引表INVERTINDEX和语句长度表LENGTHTABLE。1FOREACHQINQ一47咽叼咽咽HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文2求出Q的偏移量POSQ3把POSQ及LENQ插入LENGTHTABLE表中4FOREACHWORDINQ5把POSQ插入至0INVERTINDEXHASHWORDWORD一LINKWORD中6输出INVERTINDEX和LENGTHTALBE。算法中的Q为问题集中所有问句的集合，可以用数组结构来表示。INVERTINDEX为词倒排索引表，其每个记录为二元组，其中LINKWORD为词WORD出现的语句偏移量的链表，该索引表按词以散列方式组织，能够实现快速建表和查找。设散列函数为HASHWORDWORD，可用任何一种方法解决散列地址冲突问题。为了使算法简单，这里假设没有冲突，即可直接通过INVERTINDEXHASHWORDWORD一LINKWORD存取WORD的索引集合。语句长度表LENGTHTABLE的每个记录为二元组，其中POS表示一个语句的偏移量，LEN表示该语句的长度。该表也以散列方式组织。设散列函数为HASHPOSPOS，即可通过LENGTHTABLEHASHPOSPOS一LEN存取偏移量为POS的语句的长度。词倒排索引表作用是在不读问题集的情况下就可直接在问题库中抽取与问句中关键词一样的问句，而且与INPUT相似度为O的语句不参与计算。语句长度表的作用是在不读问题集的情况下就可在己算出从大到小依次的前K个鼬MP肠耐却们，G即在候选问题集中的基础上计算耽以甄，ZINPUT，Q。5223相似问句的查找设输入语句INPUT共有M个不同的关键词，各关键词的倒排索引如图2所示。设M个索引链表中共有R个不同的偏移量，设偏移量墨F1，】在们耐K后【1，M的索引链表中出现口1次，W0耐T在INPUT中出现口2次。SF对于，啪耐。的计数则有勋胍E肠以却彬，9SF堋FSF，肋咄对以上M个索引链表进行一次扫描就可算出所有勋聊P肪以却讲，G墨，计算的时问复杂度是D，印。其中，M表示语句的平均长度，P表示各索引链表的48天津师范大学硕士学位论文平均长度。为了提高算法效率，可以将对语句相似影响小的高频词放入忽略表中，不对它们建立索引，这样P的值将会大大缩小。这里我们没有考虑忽略表。索引表图52基于关键词的倒排索引表选出与降序排列的勋埘P肋以却们，GS，相对应的前毛个语句，这些语句就会包含相似度最大的语句，这样候选问题集的建立工作也就完成了。再根据最可从LENGTHTABLE中读出语句G置的长度，计算出肋以甄MINPUT，QS；，这个过程实现的算法时间复杂度为D毛。语句相似度中词形相似度起决定作用，所以与INPUT语句相似最大的语句肋删MINPUT，Q也一定较大，因此根据计算出的所有的以S泐INPUT，QSI值，选出也也毛个语句就会包含相似度最大的语句，然后再计算出语句长度相似度和词序相似度，最后计算出，Z纪挖CE研却“F，GS，取出最相似的语句一般取最大的前3个按降序排列输出。算法描述如下算法2相似语句查找算法。输入INPUT，INVERTINDEX，LENGTHTABLE，Q。输出相似语句前五个按降序排列。1FOREACH不同的关键词WORDININPUT2从工NVERTINDEX读出WORD的倒排索引3计算所有非零的勋MP肋耐觇，斫，G49咽咽咽咽HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文4根据LENGTHTABLE计算勋朋P暇翮却“F，留较大的前七1个的语句的5计算胁以胁INPUT，Q较大的前后2个语句的彪玎胁却斫，G6根据Q计算彪以川却以，G较大的前霓3个语句的D砘艘研F印以，9，7计算，L胞，ZCE肪，ZF哆眇F，垡8输出以胞疗C西泐F即“F，G较大的前3个语句。50天津师范大学硕士学位论文第六章面向台球领域的自动问答系统的实现与测评前面几章分别就自动问答系统中用到的相关技术、理论基础以及系统的设计思想等做了比较详细的介绍，在这一章中，介绍完问答系统的框架以后，将利用前面阐述的相关技术来实现一个中文问答系统，同时给出系统的试验结果，并进行测评。面向台球领域的自动问答系统的具体实现所使用的平台是VISUALSTUDIO2005NET和MICROSOFTSQLSERVER2005NET，所使用的开发语言为C。61系统设计思想问答系统是建立在文本检索的基础之上的、以计算机为工具，利用知识以及知识推理等技术求解问题的知识系统。问答系统的发展大大取决于自然语言处理领域以及相关领域的发展水平，由于汉语自身的复杂性，中文问答系统技术还不够不成熟，目前还处于起步阶段。本系统借鉴了国内外问答系统中的思想和技术，并结合自己的一些设想，设计了这个面向台球领域的自动问答系统，虽然系统还有许多需要完善的地方，但其应用前景还是很可观的。根据问答系统自身的特点和汉语文本处理技术的特点，本系统的设计思想如下1、友好的人机交互界面此问答系统主要是为了便于使用者获取想要得到的台球知识，它允许用户以自然语言的方式进行提问，系统在对用户的提问进行处理之后，给出正确的答案。因此，友好的人机界面是问答系统的一个至关重要的方面，它要能够支持用户以自然语言的方式进行提问，在提问方式上不对用户做任何限制，而且最终能以自然语言的方式，根据用户的需求返回最终正确的答案，为用户在信息海洋中提供有效的服务。2、良好的问题分析能力为了正确地对用户的提问进行回答，首先要充分领会用户的提问意图。本系统主要采用基于关键词的倒排索引的问句相似度计算方法来计算问句的相似度，可以保证当一个语句的分句或短语整体发生了移动后仍与原来的语句相似。语句相似度计算应用到问题库中，使查找的准确性大大提高，而且平均时间受问题库规模的影响很小。62系统框架一51HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文面向台球领域的自动问答系统重要包括三个模块问答系统模块、词库管理模块和问题库管理模块，其系统流程图如图61所示。63系统的模块设计图61系统流程图631问答系统模块问答系统模块是本文所设计的自动问答系统的核心模块。实现了与使用者的自动交互。使用者在提问界面输入问题，点击“提问“按钮后，便把问题交予系统，下图便为此系统的提问界面。52天津师范大学硕士学位论文图62通过自动分词、关键词提取、确定候选问题集、问句相似度计算等步骤后，将返回在问题集中与用户提问的问句相似度最大的问题的答案，如果计算所得的相似度低于一个指定的阈值，则返回“不知道，此问题将会提交给管理员”。然后用户所问问题将提交到问题库中，并由管理员统一管理。关于问题库模块的设计，稍后会介绍。系统的恢复界面如下图所示。53HTTP/INFO3DOUCOM/网络推广天津师范大学硕士学位论文隧|氇置訇眭差LEJIII量1昏