自动应答系统中文处理策略和算法

2010-10-16佟欣

赤峰学院学报·自然科学版 2010年2期

关键词：分词词典文本

佟欣

（赤峰学院计算机科学与技术系，内蒙古赤峰 024000）

自动应答系统中文处理策略和算法

佟欣

（赤峰学院计算机科学与技术系，内蒙古赤峰 024000）

自动应答系统是一种对用户用自然语言提出的问题能够做出尽可能简洁、准确回答的计算机程序.在设计自动应答系统时先要解决中文分词及字符串匹配等问题，以便快速准确地搜索到需要的答案.本文主要讨论了自动应答系统中的中文处理策略和算法.

自动应答；分词；匹配算法

自动应答系统是一种对用户用自然语言提出的问题能够做出尽可能简洁、准确回答的计算机程序.这样的程序需要具备对自然语言进行分析和处理的能力，它是自然语言处理技术的一个重要的应用.

自动应答系统首先需要解决的问题就是汉语的词条切分，并从自然语言文本中抽取出能够代表问题的关键词.而关键词全文搜索的目的是查找与问题相关的答案.为了使系统能最大效率地工作，必须选择切实可行并且匹配精度较高的算法.

1 分词策略

本文采用了三种分词算法保证分词的匹配度.分词词典与关键词词典为同一文本文件，这样在分词的同时就能提取出关键词，自动筛掉停止词标点符号.这就简化了步骤提高了效率，也降低了错误率.词典中包括一些专业词汇和限制条件的词汇.当用户以自然语言进行提出问题，此语句中会包含关键词、无用词、停止词和语义限定词.为减少打开文档的次数，词典中包含了限定词汇，在分词中能自动检索出来.

例如：问题1：土地用途包括哪些种类？

分词程序处理后：土地/种类（土地是关键词，种类是语义词）

问题2：土地来源及性质？

分词程序处理后：土地/来源（土地是关键词，来源及性质是语义词）

问题3：土地

分词程序处理后：土地（只含有关键词）

问题1与问题2关键词是相同的，但是语义词是不同的，这样匹配后返回的答案结果是不相同的.如果开始的时候只提出问题3，那么系统会认为知识库中无此问题的答案.因此，建议用户提问题的时候应该加入语义限定词，这样才会返回准确的答案，否则，会显示用户并不想要的结果.

2 分词算法

2.1 正向最大匹配分词

正向减字最大匹配法切分的过程是从自然语言的中文语句中提取出设定长度字串，与词典比较，如果在词典中，就算一个有意义的词串，并用分隔符分隔输出，否则缩短字串，在词典中重新查找（词典是预先定义好的）.

算法思想：从待切分的文本D中提取，对于每个句子S1从左向右以MAXLEN为界选出候选字串W，如果W在字典中，处理下一个长为MAXLEN的侯选字段；否则，将W最右边一个字去掉，继续与字典比较；S1切分完之后，构成词的字符串或者此时W已经为单个字，用分隔符隔开输出给S2.从S1中减去W，继续处理后续的字串.S1处理结束，取D中的下一个句子赋给S1，重复前述的步骤，直到整篇文本D都切分完毕.

具体算法：输入：中文词典，待切分的文本D，D中有若干被标点符号分割的句子S1，设定最大长度MAXLEN（是一个经验值，通常设为8个字节，过小，长词会被切断，过长，又会导致切分效率低）流程图如图1所示：

伪代码：

算法分析：设文本还有句子的数目为M，句子的平均长度为K，词典的条目为N，实际中M和K远远小于N，这个算法复杂度中起决定作用的步骤在于N相关的语句，因此整个算法的时间复杂度为 O（MKLOGN）.

实验表明：正向最大匹配算法的错误率为1/169.

2.2 基于邻词的分词算法

算法思想：从D中提取，依次扫描输入串，按照从左到右的顺序截取1到MAXLEN长度的子串作为全部的候选词 w1、w2、…、wi，记录方式为该子串在输入串中的起点位置i，以及子串长度l（偏移量），在输入字串中查出每个候选词右邻词和左邻词；如果当前词wi在关键词词典中，则wi是分词结果输出，wi+1作为新的后选词循环此过程.

假定对字串从左到右进行扫描，可以得到w1，w2，…，wi-1，wi，…等若干候选词，如果 wi的尾字跟wi-1的首字邻接，就称wi为wi-1的右邻词.

算法：

输入：中文词典，待切分的文本D，D中有若干被标点符号分割的句子S1

伪代码描述：