張 麗

（ 貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽 550025 ）

多模式匹配自動(dòng)機(jī)的構(gòu)造與極小化

張 麗

（ 貴州大學(xué) 計(jì)算機(jī)科學(xué)與信息學(xué)院，貴州 貴陽 550025 ）

通過給定的單模式構(gòu)造出相應(yīng)的模式匹配自動(dòng)機(jī)，集成單模式匹配自動(dòng)機(jī)而得到多模式非確定型有窮自動(dòng)機(jī)（NFA）。將非確定型自動(dòng)機(jī)轉(zhuǎn)化為確定型自動(dòng)機(jī)，在狀態(tài)集上引入等價(jià)關(guān)系，對(duì)該確定型有窮自動(dòng)機(jī)進(jìn)行極小化，得到與原自動(dòng)機(jī)功能等價(jià)的極小化自動(dòng)機(jī)，從而使之能確定其中任意一個(gè)模式的所有匹配位置。

有窮自動(dòng)機(jī)； 多模式匹配； 等價(jià)關(guān)系； 極小化

1.引言

在文本編輯程序中，經(jīng)常要在一段文本字符串中查找出某個(gè)模式的全部出現(xiàn)位置，所查找的模式是用戶提供的一個(gè)特定單詞，這個(gè)過程稱之為模式匹配。每個(gè)模式都存在一個(gè)相應(yīng)的字符串匹配自動(dòng)機(jī)，在預(yù)處理階段，根據(jù)模式構(gòu)造出相應(yīng)的自動(dòng)機(jī)后，才能利用它搜尋文本字符串。[1]本文是根據(jù)已知的模式構(gòu)造出相應(yīng)的匹配自動(dòng)機(jī)，然后集成為一個(gè)非確定型有窮自動(dòng)機(jī)，使之能確定其中任意一個(gè)模式的所有出現(xiàn)位置，在此基礎(chǔ)上對(duì)自動(dòng)機(jī)進(jìn)行基于等價(jià)類的化簡(jiǎn),盡量使自動(dòng)機(jī)的狀態(tài)數(shù)最少。

有窮自動(dòng)機(jī)的化簡(jiǎn)（極小化）對(duì)有窮自動(dòng)機(jī)的應(yīng)用及實(shí)現(xiàn)有著重要的理論意義，而狀態(tài)的極小化是將自動(dòng)機(jī)的狀態(tài)集劃分成一些不相交的子集，其中任何兩個(gè)不同的子集中的狀態(tài)都是可區(qū)分的，而同一子集中的任何兩個(gè)狀態(tài)都是不可區(qū)分的即是等價(jià)的，等價(jià)的狀態(tài)對(duì)可進(jìn)行合并，這樣自動(dòng)機(jī)的狀態(tài)數(shù)就會(huì)得到減少。

2.基本概念

很多模式匹配算法采用建立一個(gè)有窮自動(dòng)機(jī)、通過該有窮自動(dòng)機(jī)對(duì)文本字符串進(jìn)行掃描的方法，找出模式的所有出現(xiàn)位置。有窮自動(dòng)機(jī)是計(jì)算機(jī)軟、硬件研究的重要基礎(chǔ)理論模型，這種模型有著廣泛的用途，它的應(yīng)用遍及計(jì)算機(jī)科學(xué)和其他學(xué)科的幾乎所有領(lǐng)域，其中模式匹配就是其重要應(yīng)用之一。[1][2]

定義 1一臺(tái)有窮自動(dòng)機(jī)是一個(gè)五元組，記為M=（Q,Σ,δ,q0,F），其中：

（1）Q是一個(gè)有窮集，稱為狀態(tài)集合；

（2）Σ是一個(gè)有窮的輸入符號(hào)集，稱為字母表；

（3）δ是轉(zhuǎn)移函數(shù)；

（4）q0∈Q是一個(gè)初始狀態(tài)；

（5）F?Q是一個(gè)終結(jié)狀態(tài)集。

若轉(zhuǎn)移函數(shù)定義為δ：Q×Σ→Q，則稱M為確定型有窮自動(dòng)機(jī)（DFA）；

若轉(zhuǎn)移函數(shù)定義為δ：Q×Σ→2Q，則稱M為非確定型有窮自動(dòng)機(jī)（NFA）；

由 DFA M 的轉(zhuǎn)移函數(shù)δ誘導(dǎo)出一個(gè)新的函數(shù)δ*，δ*：Q×Σ*→Q，其中Σ*是字母表Σ上有窮符號(hào)串構(gòu)成的集合，滿足：

3.模式匹配自動(dòng)機(jī)的設(shè)計(jì)

在實(shí)際應(yīng)用中，一般采用狀態(tài)轉(zhuǎn)換圖來表示一個(gè)模式匹配自動(dòng)機(jī)。

一個(gè)有窮自動(dòng)機(jī)等價(jià)于一個(gè)狀態(tài)轉(zhuǎn)換圖，由于狀態(tài)轉(zhuǎn)換圖與程序有一定的對(duì)應(yīng)關(guān)系，如果自動(dòng)機(jī)狀態(tài)轉(zhuǎn)換圖是約簡(jiǎn)的，可以使得程序設(shè)計(jì)比較規(guī)范、達(dá)到優(yōu)化，從而高效地完成軟件設(shè)計(jì)工作。

為了說明與給定模式P[1..m]（模式P存放在長(zhǎng)度為m的一維數(shù)組中）相應(yīng)的匹配自動(dòng)機(jī)，涉及一個(gè)輔助函數(shù)σ[1]：是一個(gè)從*Σ到{0,1,…,m}上定義的映射，σ（x）=max（k：Pk?x），其中Pk是P中長(zhǎng)度為k的（前綴）字符串，記號(hào)Pk?x表示是Pk字符串x的后綴。從而，σ（x）是x的后綴與P的前綴相匹配的最大長(zhǎng)度。

下面是模式匹配自動(dòng)機(jī)的構(gòu)造算法：

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

（2）根據(jù)模式P[1..m]的下標(biāo)的上界，得出有窮自動(dòng)機(jī)的狀態(tài)集Q={0,1,2,…,m}，其中0為初始狀態(tài)q0，m為唯一的終結(jié)狀態(tài)qm；

（3）狀態(tài)q=0；

（4）對(duì)任意輸入的字符a，其中a∈Σ，根據(jù)δ（q,a）=σ（Pq a）計(jì)算轉(zhuǎn)移函數(shù)，從而得出新的狀態(tài)值；

（5）q=q+1重復(fù)步驟（4），直到q＞m結(jié)束。

通過上述算法構(gòu)造的有窮自動(dòng)機(jī)是極小化的自動(dòng)機(jī)，因?yàn)樵撚懈F自動(dòng)機(jī)在輸入任意字符時(shí)是線性向后逐步狀態(tài)轉(zhuǎn)移的或向前狀態(tài)轉(zhuǎn)移形成回路，假設(shè)任意狀態(tài)q=k，則狀態(tài)q接受字符串ω到達(dá)終結(jié)狀態(tài)，而狀態(tài)q的前面狀態(tài)0、1、2、……、k?1要接受aω才到達(dá)終結(jié)狀態(tài)，故狀態(tài)q與自己前面的狀態(tài)0、1、2、……、k?1就會(huì)是可區(qū)分的，根據(jù)前面的定義，狀態(tài)q與狀態(tài)0、1、2、……、k?1不是等價(jià)狀態(tài)對(duì)，不可合并。即證。

例1對(duì)模式P=aab構(gòu)造出相應(yīng)的匹配自動(dòng)機(jī)如圖1所示

根據(jù)前面的算法，自動(dòng)機(jī)的狀態(tài)Q={0,1,2,3}，0是初始態(tài)，3是終結(jié)狀態(tài)。具體構(gòu)造如下：計(jì)算轉(zhuǎn)移函數(shù)δ（0,a）=σ（P0a）=1，即狀態(tài)0在輸入字符a時(shí)轉(zhuǎn)移到狀態(tài) 1，δ（1,a）=σ（P1a）=2，即狀態(tài) 1在輸入字符a時(shí)轉(zhuǎn)移到狀態(tài)2，各狀態(tài)的轉(zhuǎn)移情況同理。

4.多模式匹配自動(dòng)機(jī)的構(gòu)造與極小化

根據(jù)上述算法，先構(gòu)造出單個(gè)模式匹配自動(dòng)機(jī)，然后集成單個(gè)模式匹配自動(dòng)機(jī)可以得到多模式匹配自動(dòng)機(jī)，是一個(gè)非確定型的有窮自動(dòng)機(jī)（NFA）。[2]用進(jìn)入接受狀態(tài)來表示看到一個(gè)這種單詞，把文本一次一個(gè)字母輸入到NFA，該NFA就能識(shí)別出文本中模式的出現(xiàn)。[1]

由此，按如下的方法可以構(gòu)造出多模式匹配自動(dòng)機(jī)并極小化：

（1）對(duì)每一個(gè)給定的模式，設(shè)計(jì)相應(yīng)的模式匹配自動(dòng)機(jī)；

（2）集成單個(gè)的模式匹配自動(dòng)機(jī)，得到帶ε的NFA；

（3）將NFA確定化去掉ε，轉(zhuǎn)化為與之等價(jià)的DFA；

（4）對(duì)該DFA，引入等價(jià)關(guān)系，如果DFA中兩個(gè)狀態(tài)是不可區(qū)分的，即對(duì)任何輸入串ω，當(dāng)且僅當(dāng)*δ（p,ω）∈F，*δ（q,ω）∈F，則稱這兩個(gè)狀態(tài)p和q是等價(jià)的。如果兩個(gè)狀態(tài)等價(jià)，我們可以將其寫成等價(jià)類的形式。狀態(tài)等價(jià)性也是可以傳遞的，如果狀態(tài)p和q是等價(jià)的，并且狀態(tài)q和r是等價(jià)的，則狀態(tài)p和r是等價(jià)的。根據(jù)等價(jià)性這一原理，可以將等價(jià)狀態(tài)對(duì)合并，實(shí)現(xiàn)自動(dòng)機(jī)的極小化。

5.結(jié)束語

確定型有窮自動(dòng)機(jī)極小化是在狀態(tài)集上引入一個(gè)等價(jià)關(guān)系，通過該等價(jià)關(guān)系求出狀態(tài)集上所有的等價(jià)類進(jìn)行狀態(tài)合并來實(shí)現(xiàn)自動(dòng)機(jī)極小化的。本文利用單個(gè)模式構(gòu)造的匹配自動(dòng)機(jī)，集成為多個(gè)模式的非確定型有窮自動(dòng)機(jī)，將非確定型自動(dòng)機(jī)轉(zhuǎn)化為確定型自動(dòng)機(jī)，利用等價(jià)關(guān)系，對(duì)該自動(dòng)機(jī)進(jìn)行極小化，并能確定其中任意一個(gè)模式的所有出現(xiàn)位置。

[1] Thomas H.Cormen，Charles Leiserson，Ronald L.Rivest，Clifford Stein.算法導(dǎo)論[M].機(jī)械工業(yè)出版社，2009.

[2] （美）John E.Hopcroft Rajeev Motwani Jeffrey D.Ullman著.自動(dòng)機(jī)理論、語言和計(jì)算導(dǎo)論[M].機(jī)械工業(yè)出版社，2006.

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

[4] 王杰.一種快速高效的模式匹配算法的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（32）：93-94.

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

[6] 秦永彬，許道云.有窮自動(dòng)機(jī)中的等價(jià)性與等價(jià)歸并算法[ J ].濟(jì)南大學(xué)學(xué)報(bào)（自然科學(xué)版），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

（責(zé)任編輯 王婷婷）

TP301 < class="emphasis_bold">文獻(xiàn)標(biāo)識(shí)碼：A

A

1673-9639 （2011） 03-0129-03

2010-05-03

貴州省自然科學(xué)基金（黔科合J字[2007]2203號(hào)），貴大人才引進(jìn)基金項(xiàng)目（貴大人基合字[2009]007號(hào)）。

張麗（1971-），女，貴州貴陽人，碩士，講師，研究方向?yàn)榭捎?jì)算性與計(jì)算復(fù)雜性。