多模式匹配自动机的构造与极小化
2011-01-09张丽
铜仁学院学报 2011年3期
关键词:文本
张 丽
( 贵州大学 计算机科学与信息学院,贵州 贵阳 550025 )
多模式匹配自动机的构造与极小化
张 丽
( 贵州大学 计算机科学与信息学院,贵州 贵阳 550025 )
通过给定的单模式构造出相应的模式匹配自动机,集成单模式匹配自动机而得到多模式非确定型有穷自动机(NFA)。将非确定型自动机转化为确定型自动机,在状态集上引入等价关系,对该确定型有穷自动机进行极小化,得到与原自动机功能等价的极小化自动机,从而使之能确定其中任意一个模式的所有匹配位置。
有穷自动机; 多模式匹配; 等价关系; 极小化
1.引言
在文本编辑程序中,经常要在一段文本字符串中查找出某个模式的全部出现位置,所查找的模式是用户提供的一个特定单词,这个过程称之为模式匹配。每个模式都存在一个相应的字符串匹配自动机,在预处理阶段,根据模式构造出相应的自动机后,才能利用它搜寻文本字符串。[1]本文是根据已知的模式构造出相应的匹配自动机,然后集成为一个非确定型有穷自动机,使之能确定其中任意一个模式的所有出现位置,在此基础上对自动机进行基于等价类的化简,尽量使自动机的状态数最少。
有穷自动机的化简(极小化)对有穷自动机的应用及实现有着重要的理论意义,而状态的极小化是将自动机的状态集划分成一些不相交的子集,其中任何两个不同的子集中的状态都是可区分的,而同一子集中的任何两个状态都是不可区分的即是等价的,等价的状态对可进行合并,这样自动机的状态数就会得到减少。……
登录APP查看全文
