[9])。算法按照初始化策略对议程表进行初始化处理,如果议程表为空,那么分析失败,否则每次按照议程表组织策略,从议程表中取出一个成分。如果取出的成分覆盖整个句子,那么返回成功,否则将取出的成分加入到线图中,执行规则调用策略和活动弧递进、归约策略将产生的新成分又加入到议程表中。在这个算法流程中,各项策略均可调整,通过调整这些策略可以得到改进的线图分析算法。
   燕方法是基于线图分析方法的一种改进算法,本论文所做的相关工作是在燕方法的基础上进行的。燕方法所涉及的文法包含五种不同类型的规则,分别是苛刻型(up-tying,即传统规则)、跳跃型(by-passing)、长程型(long-spanning)、无序型(up-messing)以及交叉型(over-crossing)。其中跳跃型规则允许在规则右部各符号之间插入少量的其他符号,处理口语中的停顿和无意义词现象;无序型规则在跳跃型规则的基础上还允许规则右部符号组合的出现顺序任意,解决汉语口语语序随意的问题。燕方法有以下特点:
   1) 部分分析的特点: 对句子不作接受或拒绝的简单判断,而是保留分析过程中得到的所有部分结果,提供最大信息以便后续处理。
   2) 跨成分归约的特点: 不拘泥于传统算法中成分间位置关系的紧密相连性与严格偏序性,而是根据不同的规则类型采取更为灵活的活动弧递进、归约策略,容许更为自由的口语通过分析器。
   2 算法原理
   虽然线图分析方法通过调整规则调用策略和活动弧递进、归约策略能使句子的语法分析具有一定鲁棒性,但如果不能分析出完整的句子语法树的原因是分词过程无法识别某些语句串,就不能较好地处理。例如下面的实例:
   输入句子: 有房子在上地出租吗？
   分词结果: 有、出租—VP;上地、房子—NP;在—Prep;吗—Aux
   规则库: S→VP NP;NP→R Prep NP|VP Aux|R;VP→NP VP
   进行语法分析后,得到的语法树如图1。
   
图1 正确的语法分析树
当输入语句中“上地”由于输入时发生同音拼写错误,整句变为: 有房子在上帝出租吗。因为领域词表中不存在“上帝”这个词汇,在基于领域词表进行分词时无法识别出这个词汇。在运用线图分析方法时,因为输入语句句法成分地缺失,无法分析该语句,分析过程中断。
   尽管燕方法能较好地解决口语分析中常见的问题,但它仍然不能解决由于输入错误改变了输入语句的情况。在上例中如果用燕方法进行分析,“上帝”会被当作垃圾串进行处理,得到两个分析不完整的语法树,如图2所示。
   
图2 缺少分析成分的语法树
在上面的例子中线图分析方法和燕方法均不能解决输入错误问题,即使输入语句只是犯了一个很小的同音拼写错误(这在网络应用背景下是常见的错误)。本论文的研究工作基于针对错误类型采用高效的算法进行纠错的思想,利用文法规则和当前活动弧中的终结符信息对分词过程中的未识别语句串进行错误推测,从而将未识别语句串修正为可能的正确输入,并相应修改分词结果和分析器的状态,以使分析能够正常进行。算法的基本原理如图3所示。
   
图3 算法基本原理流程图
2.1 相关术语定义
   为了在下面的核心算法流程中描述方便,对相关术语做以下定义:
   定义1 待分析语句: 一个输入语句串经分词之后可看作由词类(未被识别的语句串属于特殊的词类)组成的一个串,写成句子sent=(K₀,K₁,…,K_n-1),其中n表示句子中的词的个数,K_i(0≤i<n)是第i个词(包括未被识别的语句串)的词类。
   定义2 未识别语句串: 在句子中会出现单个或者多个连续的无法被分词过程识别的输入文字。在分词的过程中暂时把连续的未识别文字(即未识别语句串)当成一个词,并且将这个词归为一个暂时词类R。
   定义3 分析状态: 分析状态指当前分析过程中议程表中的成分和线图中当前活动弧所对应的分析位置以及所包含的具体内容,可以写为T_i=(A_i,C_i)其中T_i表示分析器在第i个时间点的状态,A_i表示分析器的议程表在第i个时间点的状态,C_i表示分析器的线图在第i个时间点的状态。当前的分析状态决定了下一个分析状态的走向,若干个T_i就组成了整个句子的分析流程。
   定义4 规则库推测终结符集: 依据线图分析方法的原理,分析器从当前状态T_i过渡到下一个状态T_i+1需要从规则库中寻找合适的产生新的活动弧的规则。当分析器面临一个暂时词类R时,规则库中右项第一个为终结符的规则所包含的第一个终结符对这个未识别语句串有推测作用。把规则库中所有这样的终结符集合在一起即为规则库推测终结符集合,表示为Rule_T。
   定义5 当前活动弧推测终结符集: 当分析器处于某一个分析状态T_i时,所对应的线图中包含一定数量的活动弧,其中一些活动弧在当前活动位置之后待归约的成分为终结符,这个终结符对R所代表的当前未识别语句串有推测作用。把当前活动弧中所有这样的终结符集合在一起即为当前活动弧推测终结符集合,表示为Activate_T。
   2.2 核心处理流程
   从图3中可以看出,我们所提出的基于线图分析方法改进的鲁棒性文本分析算法的核心处理流程主要包含两个部分: 收集推测未识别语句串终结符集和重新调整分析器的当前分析状态。推测未识别语句串终结符集主要用来对待分析语句中未识别语句串进行错误推测,以便根据未识别语句串寻找到可能的正确语句串。当通过这样的推测寻找到对下一步的语法分析有利的分析成分时,重新调整分析器的当前分析状态,主要调整的数据结构包括当前分析状态T_i下的议程表(例如添加、删除新的成分,或者重新计算当前成分和后续成分的分析位置)和线图(主要是向线图中添加新的对应当前分析状态T_i的活动弧)的内容。具体算法如下所示。

输入: 包含未识别语句串的待分析语句。 输出: 所有的部分分析结果。 执行下列过程直到输入为空: 步骤一:    a) 如果议程表为空,查找下一个输入词语的词类,并将它们都加入到议程表中。    b) 从议程表中选择一个成分(假定该成分为C,其跨度从位置P1到P2)。如果该成分为代表未识别语句串的R,则执行步骤二,否则执行步骤三。 步骤二:    a) 在当前分析状态Ti下从规则库中收集规则库推测终结符集Rule_T与当前活动弧推测终结符集Activate_T。    b) 根据集合Rule_T与Activate_T,对未识别语句串进行错误推测,确定未识别语句串对应的可能的正确语句串以及相应的词类Ri。    c) 对于每一个Ri,创建新的在当前分析状态Ti下的成分C_Ri,其跨度与Ri在输入句子中所对应的跨度一致。    d) 对于文法规则中每条形式为X→C_RiX1...Xn的规则,增加一条活动边X→。C_RiX1...Xn,其跨度与Ri在输入句子中所对应的跨度一致。    e) 对于Chart中每条形式为X→X1..。C_Ri..Xn的活动弧(假设其跨度从位置P0到P1),增加一条活动边X→X1..C_Ri。..Xn,其跨度从位置P0到P2。    f) 对于Chart中每条形式为X→X1....Xn。C_Ri的活动弧(假设其跨度从位置P0到P1),增加一条新的成分X到Agenda中,其跨度从位置P0到P2。返回步骤一。 步骤三:    a) 对于文法规则中每条形式为X→CX1...Xn的规则,增加一条活动边X→。CX1...Xn,其跨度从位置P1到位置P2。    b) 对于Chart中每条形式为X→X1..。C..Xn的活动弧(假设其跨度从位置P0到P1),增加一条活动边X→X1..C。..Xn,其跨度从位置P0到P2。    c) 对于Chart中每条形式为X→X1....Xn。C的活动弧(假设其跨度从位置P0到P1),增加一条新的成分X到Agenda中,其跨度从位置P0到P2。返回步骤一。

在图4所示的算法步骤二b)中,可以根据实际应用中输入语句包含的不同错误类型选择合适的算法推测未识别语句串。在对汉语网络文本的分析中,因为拼音输入方法应用的普遍性,文本错误往往是因为拼音输入的选词错误所导致。针对这类错误,我们可以基于集合Rule_T与Activate_T所包含的终结符所对应的拼音与未识别语句串的拼音做汉字文本的错误推测,可以采用基于拼音或者基于拼音字符串最小编辑距离的方法寻找可能的正确文本。
   3 实验
   为了测试所提出算法的有效性和算法效率,我们在燕方法的基础上实现了本文所提出的算法,其中错误推测与纠正部分采用拼音的同音匹配方法,即试图将错误文字纠正为拼音相同的正确文字,然后在特定领域下与燕方法进行实际文本的分析对比。
   3.1 评测指标
   参考文献[6-8]中所使用的评测方法,我们从分析器的“平均分析循环次数”和“分析度”两个角度展开评测:
   1) 平均分析循环次数^[6-7]: 分析循环(a parse cycle)是专用于衡量线图分析器的一个指标。一次分析循环指的是一个成分从议程表中取出到线图中用来增加新活动弧或者递进、归约出新的成分的过程。输入语句的平均分析循环次数,体现了分析器的效率。在实验中因为基于同音词汇拼音纠错情况地存在,平均分析循环次数会有所增加。
   2) 分析度^[8]: 分析度的计算公式如下:
分析度=被分析器接受语句的数量分析语句总数量
   当输入的待分析句子都是应接受的领域内文本时,分析度越高说明分析器的鲁棒性越好。
   3.2 评测集组织与评测结果
   实验使用了北京得意音通技术有限公司提供的1 000条租房领域句子作为评测数据,其中正确语句和错误语句各一半,错误语句中同音拼写错误所占比例约为80%。我们分别用燕方法和本文方法进行分析,并计算上述两个评测指标。
   从评测集中随机抽取360条正确语句和240条错误语句进行分析,作为一次实验,重复三次,计算总的分析循环次数和被分析器接受的语句,计算平均分析循环次数和分析度,评测结果如表1所示。
表1 平均分析循环次数和分析度

分析循 环次数 接受 语句数 输入语 句总数 平均分析 循环次数 分析度

燕方法 10 515 1 366 1 800 5.842 75.89%

本文方法 11 500 1 568 1 800 6.389 87.11%

相对提高 9.363% 14.78%

4 结论与讨论
   从表1的实验结果可知,与燕方法比较,本文所设计的鲁棒性文本分析算法以增加一定比例的平均分析循环次数为代价,换取了分析度的更多提升,实际上将不被分析器接受的领域内句子数相对减少了46.54%。
   本文算法只对输入句子由于错误导致分词过程无法识别部分文字的情况进行处理,如果错误结果能够被分词过程识别为其他词类(例如采用领域无关的分词算法,可识别所有汉字单字),则算法无法启动错误推测和纠正的处理过程。在面向领域的应用中,如果基于领域词表进行分词和句法分析,则输入错误导致正确的词变为另一个合法领域词的可能性较小,算法能比较有效的推测输入错误并纠正为正确的领域词。
   另外,2.2节所示算法流程主要针对处理汉语的情况进行描述。对于类似英语这样的字母语言,输入包含一个字母的错误,经常会导致原单词变为一个错误的单词,应用上述算法的效果是基于当前分析状态T_i下的推测终结符集合,试图将错误的单词纠正为具有某些词性的单词,这样要比盲目的基于编辑距离纠正可能会好一些。
   本文算法是在基于线图的分析算法基础上附加错误推测与纠正的处理,以提高实际应用时句子分析的鲁棒性,对于分析过程所应用的文法规则和活动弧的递进归约策略并没有限制。
   未来的工作是在本文的算法框架基础上,研究更好的错误推测方法,包括尝试利用拼音音节的最小编辑距离来推测正确的输入语句;探索鲁棒性分析算法中可能的剪枝策略,以提高算法的分析效率。
   5 参考文献
[1] 冯志伟.自然语言处理中的概率语法[J].当代语言学,2005,7(2): 166-178.
[2] 刘智博,Michael Brasser,郑方,徐明星.一个基于文本输入的口语对话系统的新的实现策略[J].计算机科学,2006,22(11) : 205-209.
[3] Pengju Yan,Fang Zheng,Hui Sun,and Mingxing Xu.Spontaneous speech parsing in travel information inquiring and booking system[J].Journal of Computer Science and Technology,2002,17(6): 924-932.
[4] 燕鹏举.对话系统中自然语言理解研究[D].北京: 清华大学,2002.
[5] Ye-Yi Wang.A Robust Parser For Spoken Language Understanding[C]//Eurospeech,1999,5: 2055-2058.
[6] Jennifer Foster and Carl Vogel.Parsing Ill-Formed Text Using an Error Grammar[J].Artificial Intelligence Review ,2004,21: 269-291.
[7] Mellish.Some Chart-based Techniques for Parsing Ill-formed Input[C]// Proceedings of the 27th ACL,1989.
[8] Gertjan van Noord.Error Mining for Wide-Coverage Grammar Engineering[C]// Proceedings of the 42th ACL,2004.
[9] Kay,M.Algorithm schemata and data structures in syntactic processing[R].Technical Report CSL.Xerox PARC,1980.