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

张 丽

（ 贵州大学 计算机科学与信息学院，贵州 贵阳 550025 ）

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

张 丽

（ 贵州大学 计算机科学与信息学院，贵州 贵阳 550025 ）

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

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

1.引言

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

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

2.基本概念

很多模式匹配算法采用建立一个有穷自动机、通过该有穷自动机对文本字符串进行扫描的方法，找出模式的所有出现位置。有穷自动机是计算机软、硬件研究的重要基础理论模型，这种模型有着广泛的用途，它的应用遍及计算机科学和其他学科的几乎所有领域，其中模式匹配就是其重要应用之一。[1][2]

定义 1一台有穷自动机是一个五元组，记为M=（Q,Σ,δ,q0,F），其中：

（1）Q是一个有穷集，称为状态集合；

（2）Σ是一个有穷的输入符号集，称为字母表；

（3）δ是转移函数；

（4）q0∈Q是一个初始状态；

（5）F⊆Q是一个终结状态集。

若转移函数定义为δ：Q×Σ→Q，则称M为确定型有穷自动机（DFA）；

若转移函数定义为δ：Q×Σ→2Q，则称M为非确定型有穷自动机（NFA）；

由 DFA M 的转移函数δ诱导出一个新的函数δ*，δ*：Q×Σ*→Q，其中Σ*是字母表Σ上有穷符号串构成的集合，满足：

3.模式匹配自动机的设计

在实际应用中，一般采用状态转换图来表示一个模式匹配自动机。

一个有穷自动机等价于一个状态转换图，由于状态转换图与程序有一定的对应关系，如果自动机状态转换图是约简的，可以使得程序设计比较规范、达到优化，从而高效地完成软件设计工作。

为了说明与给定模式P[1..m]（模式P存放在长度为m的一维数组中）相应的匹配自动机，涉及一个辅助函数σ[1]：是一个从*Σ到{0,1,…,m}上定义的映射，σ（x）=max（k：Pk⊃x），其中Pk是P中长度为k的（前缀）字符串，记号Pk⊃x表示是Pk字符串x的后缀。从而，σ（x）是x的后缀与P的前缀相匹配的最大长度。

下面是模式匹配自动机的构造算法：

（1）在有穷字母表Σ上给定模式P[1..m]；

（2）根据模式P[1..m]的下标的上界，得出有穷自动机的状态集Q={0,1,2,…,m}，其中0为初始状态q0，m为唯一的终结状态qm；

（3）状态q=0；

（4）对任意输入的字符a，其中a∈Σ，根据δ（q,a）=σ（Pq a）计算转移函数，从而得出新的状态值；

（5）q=q+1重复步骤（4），直到q＞m结束。

通过上述算法构造的有穷自动机是极小化的自动机，因为该有穷自动机在输入任意字符时是线性向后逐步状态转移的或向前状态转移形成回路，假设任意状态q=k，则状态q接受字符串ω到达终结状态，而状态q的前面状态0、1、2、……、k−1要接受aω才到达终结状态，故状态q与自己前面的状态0、1、2、……、k−1就会是可区分的，根据前面的定义，状态q与状态0、1、2、……、k−1不是等价状态对，不可合并。即证。

例1对模式P=aab构造出相应的匹配自动机如图1所示

根据前面的算法，自动机的状态Q={0,1,2,3}，0是初始态，3是终结状态。具体构造如下：计算转移函数δ（0,a）=σ（P0a）=1，即状态0在输入字符a时转移到状态 1，δ（1,a）=σ（P1a）=2，即状态 1在输入字符a时转移到状态2，各状态的转移情况同理。

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

根据上述算法，先构造出单个模式匹配自动机，然后集成单个模式匹配自动机可以得到多模式匹配自动机，是一个非确定型的有穷自动机（NFA）。[2]用进入接受状态来表示看到一个这种单词，把文本一次一个字母输入到NFA，该NFA就能识别出文本中模式的出现。[1]

由此，按如下的方法可以构造出多模式匹配自动机并极小化：

（1）对每一个给定的模式，设计相应的模式匹配自动机；

（2）集成单个的模式匹配自动机，得到带ε的NFA；

（3）将NFA确定化去掉ε，转化为与之等价的DFA；

（4）对该DFA，引入等价关系，如果DFA中两个状态是不可区分的，即对任何输入串ω，当且仅当*δ（p,ω）∈F，*δ（q,ω）∈F，则称这两个状态p和q是等价的。如果两个状态等价，我们可以将其写成等价类的形式。状态等价性也是可以传递的，如果状态p和q是等价的，并且状态q和r是等价的，则状态p和r是等价的。根据等价性这一原理，可以将等价状态对合并，实现自动机的极小化。

5.结束语

确定型有穷自动机极小化是在状态集上引入一个等价关系，通过该等价关系求出状态集上所有的等价类进行状态合并来实现自动机极小化的。本文利用单个模式构造的匹配自动机，集成为多个模式的非确定型有穷自动机，将非确定型自动机转化为确定型自动机，利用等价关系，对该自动机进行极小化，并能确定其中任意一个模式的所有出现位置。

[1] Thomas H.Cormen，Charles Leiserson，Ronald L.Rivest，Clifford Stein.算法导论[M].机械工业出版社，2009.

[2] （美）John E.Hopcroft Rajeev Motwani Jeffrey D.Ullman著.自动机理论、语言和计算导论[M].机械工业出版社，2006.

[3] S Yu , G Rozenberg ,A Salomaa. Handbook of Formal Languages [J].Springer Berlin，1997（1）：41 – 110.

[4] 王杰.一种快速高效的模式匹配算法的应用研究[J].计算机工程与应用，2008，44（32）：93-94.

[5] L.Ilie,S,Yu.Reducing NFAs by invariant equivalences[J].Theoretical Computer Science，306（2003）：373-390.

[6] 秦永彬，许道云.有穷自动机中的等价性与等价归并算法[ J ].济南大学学报（自然科学版），2006，20（4）：354- 358.

Construction and Minimization of Multi-Pattern Matching Automata

ZHANG Li
（ College of Computer Science and Information, Guizhou University, Guiyang, Guizhou 550025, China ）

To a given single pattern, a corresponding pattern matching automata can be constructed. By integrating single pattern matching automates, a multi-pattern non-deterministic finite automata （NFA） can be acquired. We change the non-deterministic automata into deterministic automata, and minimize it by introducing equivalence relation on state suites. Since the acquired minimal automaton is equivalent to the original automata in function, it can determine all location where any one of pattern appears.

finite automaton;multi-pattern matching;equivalence relation;minimization

（责任编辑 王婷婷）

TP301 < class="emphasis_bold">文献标识码：A

A

1673-9639 （2011） 03-0129-03

2010-05-03

贵州省自然科学基金（黔科合J字[2007]2203号），贵大人才引进基金项目（贵大人基合字[2009]007号）。

张丽（1971-），女，贵州贵阳人，硕士，讲师，研究方向为可计算性与计算复杂性。