APP下载

多模式匹配自动机的构造与极小化

2011-01-09张丽

铜仁学院学报 2011年3期
关键词:文本

张 丽

( 贵州大学 计算机科学与信息学院,贵州 贵阳 550025 )

多模式匹配自动机的构造与极小化

张 丽

( 贵州大学 计算机科学与信息学院,贵州 贵阳 550025 )

通过给定的单模式构造出相应的模式匹配自动机,集成单模式匹配自动机而得到多模式非确定型有穷自动机(NFA)。将非确定型自动机转化为确定型自动机,在状态集上引入等价关系,对该确定型有穷自动机进行极小化,得到与原自动机功能等价的极小化自动机,从而使之能确定其中任意一个模式的所有匹配位置。

有穷自动机; 多模式匹配; 等价关系; 极小化

1.引言

在文本编辑程序中,经常要在一段文本字符串中查找出某个模式的全部出现位置,所查找的模式是用户提供的一个特定单词,这个过程称之为模式匹配。每个模式都存在一个相应的字符串匹配自动机,在预处理阶段,根据模式构造出相应的自动机后,才能利用它搜寻文本字符串。[1]本文是根据已知的模式构造出相应的匹配自动机,然后集成为一个非确定型有穷自动机,使之能确定其中任意一个模式的所有出现位置,在此基础上对自动机进行基于等价类的化简,尽量使自动机的状态数最少。

有穷自动机的化简(极小化)对有穷自动机的应用及实现有着重要的理论意义,而状态的极小化是将自动机的状态集划分成一些不相交的子集,其中任何两个不同的子集中的状态都是可区分的,而同一子集中的任何两个状态都是不可区分的即是等价的,等价的状态对可进行合并,这样自动机的状态数就会得到减少。……

登录APP查看全文

猜你喜欢

文本
重点:论述类文本阅读
重点:实用类文本阅读
初中群文阅读的文本选择及组织
作为“文本链”的元电影
在808DA上文本显示的改善
“文化传承与理解”离不开对具体文本的解读与把握
基于doc2vec和TF-IDF的相似文本识别
文本之中·文本之外·文本之上——童话故事《坐井观天》的教学隐喻
从背景出发还是从文本出发
如何快速走进文本