复句关系词自动识别中规则解析的包含匹配算法研究.pdf

《复句关系词自动识别中规则解析的包含匹配算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第48卷第5期华中师范大学学报(自然科学版)Vo1．48NO．52O14年1O月JOURNAL0FHUAZH0NGN0RMALUNIVERSITY(Nat．Sci．)0ct．2O14文章编号：1000—1190(2014)05—0643—07复句关系词自动识别中规则解析的包含匹配算法研究胡金柱，胡泉。，舒江波。(1．华中师范大学计算机学院，武汉430079；2．华中师范大学物理科学与技术学院，武汉430079；3．华中师范大学国家数字化学习工程技术研究中心，武汉430079)摘要：规则解析器作为现代汉语复句关系词自动识别系统中的一个重要的功能模块，其主要功能是先

2、利用复句准关系词去匹配规则库中的规则，然后对匹配成功的规则进行解析，最后调用该规则并提取规则的结论对复句关系词进行识别．因此规则的成功匹配是能够进行规则解析的首要条件．但是，在对规则库中的句式规则表和连用句式规则表进行匹配解析时，由于复句准关系词的多样性和重复性，造成了匹配的复杂性，使得无法利用传统的匹配算法去匹配规则．因此，该文研究了一种“包含匹配算法”，该算法是先用一个二维数组将复句准关系词序列在复句中的下标依次存储，然后在该二维数组中寻找可能匹配的子串序列．该算法的最大优点是既不需要实现完全匹配和回溯，还可以包含模式串的所有子串，能够得到所有的目标子串，实

3、验结果表明，该算法在排除规则的不完备性和分词的错误之后，正确率可以达到100．关键词：复句关系词；自动识别；规则解析器；包含匹配算法中图分类号：TP391文献标识码：A复句关系词(又称关联词或关系标记)是复句在一条复句中是否为真正的关系词．在该系统中，在语表形式上的标记，是复句中标示关系的一个重一个重要的功能模块是“规则解析器”，其基本功能要构件，是汉语语法、语义研究中的重要内容，人们是对规则库中的规则进行解析调用．在规则解析器对于复句的理解，往往通过“抓住标记”来实现_1]，对规则进行解析之前，需要先根据复句中的准关系所以复句关系词的计算机自动识别成为研究复句

4、词找到目标规则，比较有效的方法是用复句中的准自动识别的关键l_2]．关系词与规则的关键字进行匹配查找，这就是所谓但是，由于复句中的准关系词因其所处的位置的“字符串匹配”问题]．目前国内外比较流行的或所起的作用不同，有时充当关系词，有时又不充字符串匹配算法主要有单模式匹配算法和多模式当关系词，所以复句关系词的计算机自动识别是一匹配算法．具有代表性的有KMP算法，BM算法、大难题．例如：AC算法、有限自动机算法等_3]．例1不管是刮风下雨，还是下雪结冰，他都不单模式字符串匹配算法主要有1977年改自定的时间表，提前半小时赶到工地．Knuth、Morris和Pratt

5、三位学者提出的KMP算例2不管李登辉如何改变身份，谁都知道他法[4(又叫克努特一莫里斯一普拉特算法)，以及Bo—是政界人物．yer等学者提出的BM算法]．这两种算法的基本例1中的“是”是关系词，它引导的分句与“还思想是当匹配失败时，正文不需要回溯，而是利用是”引导的分句构成并列句式；而例2中的“是”不已得到的“部分匹配”结果将匹配模式尽可能地右是关系词，它仅仅作为句子成分．移，以减少比较的次数，从而提高其匹配效率．为了正确识别复句内的关系词，本文研究了一Aho和Corasick于1975年提出的AC算种“基于规则的复句关系词自动识别系统”，其基本法_6]，是最早

6、的基于自动机的多模式字符串匹配算思想是先建立规则，然后利用规则来判定准关系词法，该算法首先对字符串进行预处理，构建有限状收稿日期：2014—02—26．基金项目：国家社会科学基金项目(11BYY052)；国家社会科学青年基金项目(13CYY037)．作者简介：胡金柱(1947一)，男，湖北宜昌人，教授，博士生导师，主要从事软件工程、中文信息处理研究*E—mail：jzhu@mail．ccnu．edu．cn．644华中师范大学学报(自然科学版)第48卷态自动机(FSA)，然后根据FSA对字符串扫描一“还”、“不仅／而且还”、“既／同时又”、“不仅因为／而次就可以找

7、到所有匹配的字符串．但是存储自动机且因为”等．需要大量空间，其后Heo等采用稀疏压缩矩阵的由于复句中的任意一个准关系词，因其所处的算法对其进行改进_7]，国内也有许多学者提出了双位置或所起的作用不同，不仅有时充当关系词，有重压缩AC算法以减少存储空间E8-9]．这些算法的时又不充当关系词，而且与其他词之间的关系也非共同特点是实现字符串完全匹配．常复杂，所以根据定义1和定义2，按照准关系词目前，有限自动机在字符串匹配方面的算法已的不同特点，将规则库设计为普通规则表、连用规经发展的相当成熟，例如有学者针对中文信息则表、句式规则表和连用句式规则表等四种不同的的特点提出

8、了反向有限自动机的匹配算