【摘要】针对远程教育答疑环节存在的问题,设计实现一个自动答疑系统。阐述自动答疑系统的总体设计、主要算法和基于Visual-Prolog的实现技术。测试结果表明,系统答疑准确率较高,响应速度较快。系统允许用自然语言提问,并自动返回准确或相近答案,提高了远程答疑的效率。
【关键词】自动答疑系统;中文自动分词;相似度计算;Visual-Prolog
【中图分类号】G40-057 【文献标识码】B 【论文编号】1009―8097(2010)07―0122―04
目前远程教育中答疑主要采用BBS、E-Mail和在线值机答疑等方式。这些答疑方式需要教师直接参与,不仅无法保证答疑的实时性,而且经常必须重复地回答相似的问题,造成人力和资源的巨大浪费。自动答疑系统是利用自然语言处理技术分析用户提出的问题,自动给予问题解答的软件系统。在远程教育中应用自动答疑系统,能够及时解答学生提出的问题,减少教师的工作量,提高远程答疑的效率。
Visual-Prolog是基于Prolog语言的编译型程序开发环境,用于编写自动答疑系统,能充分利用其模式匹配、合一、回溯和内置数据库等功能。针对课程答疑的特点,以《C语言程序设计》课程为例,介绍自动答疑系统的总体
设计、主要算法和基于Visual-Prolog的实现技术。
一 自动答疑系统的总体设计
1 系统功能
系统由自动答疑、在线答疑(人工)、知识库管理、用户管理和使用帮助5个功能模块组成。采用B/S架构,用户通过Web浏览器使用系统。
2 基本流程
答疑过程包括四个主要环节:中文自动分词、关键词提取与同义词变换、建立候选问题集和问句相似度计算,如图2所示。问题库中存储大量的“标准问句―答案”对。系统允许用户使用自然语言提问,在获取问句后,通过检索问题库,向用户返回准确或相近的答案。系统提供三种检索答案的模式:①精确检索,如果用户提出的问句与标准问句完全相同,或它们在语义上很相似(相似度≥70%),则系统返回标准问句对应的答案;②模糊检索,系统返回与用户提出的问句在语义上有一定关联(相似度≥40%)的标准问句对应的答案;③全面检索,系统返回相似度大于零,且相似度较高的几个标准问句对应的答案,并将问题提交专业教师进行解答。
3 用户分类
系统共有管理员、教师、学生和匿名用户4种,每种用户拥有不同权限。管理员用户拥有最高权限,可以对用户、问题库及词典进行管理。教师用户可以进行在线答疑,对问题库、专业词典进行简单维护。学生用户可以使用自动答疑和在线答疑功能。匿名用户只能使用自动答疑功能。
二 自动答疑系统的主要算法
1 中文自动分词
系统采用基于词典的字符串最大匹配分词法。因为用户问句中的疑问词短语和专业词汇对问题检索非常重要,所以采用疑问词短语和专业词汇优先切分的原则,并将词典分成疑问词典、专业词典和通用词典。首先,用疑问词典和专业词典将问句切分成疑问词短语、专业词汇和待切分子串的序列S。然后,分别用正/逆向最大匹配法结合通用词典对S中每个待切分子串进行切分。当出现切分歧义时,使用最小切分原则[1]进行确定,选用切出词数少的切分方案。若存在切分词数相同的歧义切分,则根据词频消除歧义。对于一个歧义片段,设一种切分结果为M=M1M2…Mn,另一种切分结果为N=N1N2…Nn,分别计算它们的频率积fq(M)=f(M1)×…×f(Mn)和fq(N)=f(N1)×…×f(Nn),并选用频率积大的切分结果,其中f(W)是词汇W在某个大规模语料库中出现的频率。当词频消歧仍不能排除歧义时,优先选用逆向最大匹配法的切分方案。
2 关键词提取与同义词变换
问句包含的关键词描述了问句的主要语义。除了关键词,问句一般还包含若干检索意义不大的停用词[2],如“的、呢、吗”等。因为问句通常比较简短,其中包含的词汇较少,所以系统把问句中标点符号和停用词之外的词汇作为关键词。
如果问题库中存在和用户提出的问题相同(近)的问题,但其标准问句中的关键词与用户问句中的关键词不相同,并且它们是同(近)义词,则直接用于检索会降低检索的正确率。例如:用户问句X为“算法的定义是什么?”,问题库中对应的标准问句Y为“算法的概念是什么?”,由于X中使用“定义”,Y中却使用“概念”,所以需要对它们进行同义词变换。同义词变换需要使用同义词典,可以在《同义词词林》的基础上构建同义词典。“《同义词词林》收录了近7万词,将词语分为12个大类,94个中类,1428个小类,小类下面再根据近义原则划分为词群(或原子词群),每一个词群(或原子词群)以一个标题词命名”[3],如:词群“定义、概念、界说”的标题词是“定义”。对关键词进行同义词变换,就是利用同义词典,将关键词替换成对应词群(或原子词群)的标题词,如:将“算法/概念/是什么”变换为“算法/定义/是什么”。
3 建立候选问题集
建立候选问题集的目的是缩小查找范围,使后续处理都在候选问题集这个相对较小的范围内进行。[4]问题库中每个“标准问句�答案”对是六元组Q=,其中:①ID是Q在问题库中的唯一标识;②标准问句是Q的提问部分;③问句关键词是标准问句经过分词、关键词提取、同义词变换后得到的词序列;④答案是对标准问句的解答;⑤专业词汇知识点是标准问句包含的专业词汇所属的知识点;⑥疑问词类型,根据标准问句包含的疑问词短语将问题分成概念、原因、关系等类型,例如“赋值语句与赋值表达式有什么区别?”包含疑问词短语“什么区别”,属于关系类型的问题。
设用户问句关键词序列为K,待建立的候选问题集为QL,建立候选问题集的过程为:①根据K分别建立疑问词短语集合A和专业词汇集合B;②根据A建立疑问词类型集合C;③根据B建立专业词汇知识点集合D;④根据C和D分别从问题库检索出问题集合Q1和Q2,合并Q1、Q2成为QL。
4 问句相似度计算[5] [6]
自动答疑系统从关键词相似度、问句长度相似度和关键词词序相似度3个方面,计算用户问句与候选问题集中标准问句的相似度,并根据检索模式抽取相似度符合要求的答案集。
设有用户问句X和标准问句Y,L(X)表示X的关键词数,L(Y)表示Y的关键词数,S(X,Y)表示X与Y的相同关键词数,Sim(X,Y)表示X与Y的问句相似度,则有1≥Sim(X,Y)≥0,1表示X与Y完全相同,0表示它们完全不同,Sim(X,Y)越大表示它们越相似。
(1)关键词相似度
X与Y的关键词相似度KSim(X,Y)可用公式⑴计算。
KSim(X,Y)=2×S(X,Y)/(L(X)+L(Y)) ⑴
(2)问句长度相似度
X与Y的问句长度相似度LSim(X,Y)可用公式⑵计算。
LSim(X,Y)=1-abs(L(X)-L(Y))/(L(X)+L(Y)) ⑵
(3)关键词词序相似度
Y与X的相同关键词在X中的位置构成一个自然数序列,用Seq(Y)表示,Rev(X,Y)表示Seq(Y)的逆序数,MaxRev(X,Y)表示数量为S(X,Y)的自然数序列的最大逆序数。X与Y的关键词词序相似度OSim(X,Y)可用公式⑶计算。
OSim(X,Y)=1-Rev(X,Y)/MaxRev(X,Y)⑶
若X与Y没有相同关键词,则OSim(X,Y)取0。
(4)问句相似度
Sim(X,Y)可用公式⑷计算。
Sim(X,Y)=λ1×KSim(X,Y)+λ2×LSim(X,Y)+λ3×OSim(X,Y)⑷
其中:λ1+λ2+λ3=1,且λ1≥0.6≥λ2≥λ3>0比较合适,例如λ1=0.6,λ2=0.2,λ3=0.2。
三 基于Visual-Prolog的实现技术
1 开发工具及运行平台
用Visual-Prolog7.1开发自动答疑模块(该模块实现了中文自动分词、关键词提取与同义词变换、建立候选问题集和问句相似度计算);用Visual Studio 2005开发基于ASP.NET2.0的在线答疑、用户管理、知识库管理和使用帮助模块;用SQLServer2005存储问题库;用IIS6.0作为WEB服务器。
2 知识库的构建
自动答疑系统的知识库包括语言知识库和问题库,语言知识库包含进行自然语言处理的语言知识。语言知识库主要由通用词典、专业词典、疑问词典和同义词典四个部分组成。因为自然语言处理需要频繁地访问语言知识库,对访问速度要求很高,且语言知识在系统运行期间一般不需要人工维护,所以语言知识库的构建采用Visual-Prolog 7.1内置的链式数据库(ChainDB)技术,该技术用B+树管理数据,查询性能很高。采用SQL Server2005构建问题库,并通过Visual-Prolog的ODBC技术进行数据访问。
3 主要数据结构
定义论域wc、wi和wl,分别表示词性、词条和分词方案。
domains
wc=string*.
wi=wi(string V,integer F,wc C)./*V代表词,F代表词频,C代表词性*/
wl=wi*.
定义论域qi和ql,分别表示候选问题和候选问题集。
domains
ql=qi*.
qi=qi(integer ID,string Q,string_list K)./*ID代表候选问题在问题库中的唯一标识,Q代表标准问句,K代表问句关键词*/
定义论域ai和ail,分别表示抽取的答案和答案集。
domains
ail=ai*.
ai=ai(string Q,string A,real XSD)./*Q代表标准问句,A代表答案,XSD代表Q与用户问句的问句相似度*/
4 系统的主要谓词
编写自动答疑系统四个主要算法对应的谓词,谓词声明及说明见表1。
5 Web应用程序的构建
Visual-Prolog7.1支持CGI和ISAPI两种Web应用程序的开发,其中ISAPI的运行性能较高但调试较麻烦,而CGI调试较方便但运行性能相对较低。自动答疑系统以CGI应用程序形式实现。CGI应用程序是一个控制台程序,与普通控制台程序不同的是需要进行一系列初始化。简化后的主程序如下:
run():-
console::init(),
IS=console::getConsoleInputStream(), /*获取控制台输入流*/
IS:setMode(stream::ansi(ansi())), /*设置输入流模式为stream::ansi(ansi())*/
OS=console::getConsoleOutputStream(), /*获取控制台输出流*/
OS:setMode(stream::ansi(core::ansi)), /*设置输出流模式为stream::ansi(ansi())*/
L=toTerm(environment::getVariable(
"CONTENT_LENGTH")), /*由环境变量CONTENT_LENGTH得到客户端请求字符串长度*/
RequestString=IS:readString(L), /*读取客户端请求字符串*/
urlDecode(RequestString,Request),/*对RequestString进行URL解码,得到Request,算法参见文献[7]*/
core:string(Q)=namedValue::tryMapLookup(
Request,"qt"), /*获取网页表单提交的问句qt */
core::string(M)=namedValue::tryMapLookup(
Request,"md"),/*获取网页表单提交的检索模式md*/
stdio::write("Content-type:text/html\n\n"), /*开始一个页面生成*/
fc(Q,W),
getKW(W,K),
getQL(K,QL),
calcXSD(K,QL,A),
showAnswers(A,M), /*根据检索模式M输出答案*/
stdio::write("var _gaq = _gaq || [];_gaq.push(["_setAccount", "UA-22575914-1"]);_gaq.push(["_setDomainName", ".省略"]);_gaq.push(["_trackPageview"]);(function () {var ga = document.createElement("script"); ga.type = "text/javascript"; ga.async = true;ga.src = ("https:" == document.location.protocol ? "https://ssl" : "http://www") + ".省略/ga.js";var s = document.getElementsByTagName("script")[0]; s.parentNode.省略";var _siteid =691;var _istoken = 1;var _model = "Model01"; WebPageSpeed =375; UrchinTrack();"),/*结束一个页面生成*/
succeed().
四 测试分析
在千兆带宽的校园局域网中,用40个客户端并发访问自动答疑系统,从准确率和响应时间两方面对系统进行测试,测试数据(部分)见表2,系统返回答案的界面如图3所示。
由表2可得:⑴系统的答疑准确率较高。若表述基本一致,则能返回准确答案;若表述存在较大差异,但语义基本相同,则能检索到相近答案。⑵系统的响应时间较短。
五 结论与今后的工作
自动答疑系统利用自然语言处理技术分析用户提出的问题,自动返回准确或相近的答案,提高了远程答疑的效率和质量。阐述了自动答疑系统的总体设计、主要算法和基于Visual-Prolog的实现技术。测试结果表明,系统的答疑准确率较高,响应速度较快。
今后工作的重点是在现有基础上完善系统词典,改进算法,并解决词性标注中的兼类词问题,进一步提高系统性能。
参考文献
[1] 王晓龙,王开铸,李仲荣,等.最少分词问题及其解法[J].科学通报,1989,(13):1030-1032.
[2] 化柏林.知识抽取中的停用词处理技术[J].现代图书情报技术,2007,(8):48-51.
[3] 江铭虎.自然语言处理[M].北京:高等教育出版社,2006:117.
[4] 秦兵,刘挺,王洋等.基于常问问题集的中文问答系统研究[J].哈尔滨工业大学学报.2003,(10):1119-1182.
[5] 崔桓,蔡东风,苗雪雷.基于网络的中文问答系统及信息抽取算法研究[J].中文信息学报.2004,18(3):24-31.
[6] 周法国,杨炳儒.句子相似度计算新方法及在问答系统中的应用[J].计算机工程与应用.2008,44(1):165-178.
[7] 黄东军.CGI程序设计中的URL编码与解码[J].微型机与应用.2000,(9):18-19,30.
[8] Prolog Development Center(PDC).Visual-Prolog online document[EB/OL].
推荐访问:答疑 设计 系统 VisualProlog