汉字有穷自动机的优化及相关算法研究

汉字有穷自动机的优化及相关算法研究

第38卷第2期

2006年6月东北师大学报(自然科学版)JournalofNortheastNormalUniversity(NaturalScienceEdition)Vol.38No.2June2006

[文章编号]1000 1832(2006)02 0022 05

汉字有穷自动机的优化及相关算法研究

张友红1,谷文祥2,殷明浩2

(1 佛山科学技术学院理学院,广东佛山528000;

2 东北师范大学计算机学院,吉林长春130024)

[摘 要] 在研究了汉字有穷自动机可以表示的语言基础上,引进了最小状态汉字有穷自动

机和可区分状态的概念,并利用汉字有穷自动机间的等价性和可区分状态的性质,给出了一种

最小化算法,实验证明,此算法优于最小化汉字有穷自动机算法.

[关键词] 最小汉字有穷自动机;可区分状态;等价性

[中图分类号] TP301 1 [学科代码] 520 1010 [文献标识码] A

0 引言

建立汉字信息处理的数学模型,深入研究它的构造和性质,不仅是彻底解决汉字输入瓶颈的关键问题,而且汉字有穷自动机理论作为一种建模方法,在汉字的智能输入,篇章处理、自然语言理解、机器翻译上也具有广泛的研究与应用.钱培德教授在文献[1]中提出了一种汉字信息处理的数学模型,文献[2]在此基础上利用自动机技术提出了一种新的汉字处理模型,对四种汉字输入系统给出了相关的数学模型.文献

[3]分别对运用确定有穷状态自动机理论和非确定有穷状态自动机理论的汉字系统处理模型做了研究.文献[4]则在给出了汉字有穷自动机的一般数学模型的基础上,引入了能够描述汉字有穷自动机能接受语言集合的正规表达式和能够得到最少状态的汉字有穷自动机的最小化算法.但文献[4]缺乏优化此自动机的理论根据.本文在文献[4]的基础上,对此数学模型做了进一步的探讨,给出了最小状态有穷汉字自动机,不可区分状态等相关概念.而在文献[4]中提到的最小化算法虽然能够对自动机模型给予优化,但是时间代价为O(n4),本文给出了一个更优的算法,实验证明,此算法的时间代价为O(nlg(n)).

1 相关定义

为方便,我们先给出相关定义:

定义1 1 汉字集H={h:h为汉字}.在本文中所指的汉字是 信息交换用汉字编码字符集!!!基本集 ,即GB2312-80中列出的所有汉字集合.所以|H|=6763.

定义1 2 代码字符集C={c:c=键盘字符}.c可以是26个英文字母,可以是0~9中的数字,也可以是各个键盘上的其他符号.

定义1 3 代码集E={e:e=c1c2#cm,ci C,i=1,2,#,m},其中e为代码,每个代码都是若干代码字符的有限序列.

定义1 4 汉字内码集G={g:gi=bi1bi2,i=1,2,#,6763,BoH%bi1%FEH,A1H%bi2%FEH},在本文中采用的内码集是变形国标码集.

[收稿日期] 2006 01 09

[基金项目] 国家自然科学基金资助项目(69973012);东北师范大学青年基金资助项目(20051001)

[作者简介] 张友红(1978-),女,硕士,助教,主要从事形式语言与自动机理论、人工智能规划研究;谷文祥(1947-),男,教授,主要从事形式语言与自动机理论、人工智能规划、规划图与智能用户接口等研究.

第1页下一页