姜克鑫， 趙亞慧， 崔榮一

(延邊大學(xué) 工學(xué)院，吉林 延吉 133002)

0 引言

密碼匹配問(wèn)題實(shí)質(zhì)上是字符串的匹配問(wèn)題[1].傳統(tǒng)的匹配算法主要有基于字符暴力匹配的BF算法[2-3]和通過(guò)消除主串指針回溯的KMP算法[4]，其中KMP算法的時(shí)間復(fù)雜度雖然低于BF算法，但KMP算法中因存在著相同字符的重復(fù)比較，因此其匹配效率仍相對(duì)較低.2019年，李先祥等[5]提出了BM算法.由于BM算法的速度比KMP算法快3～5倍，因此其受到學(xué)者的廣泛關(guān)注.

1956年，Moore等首次提出了有限狀態(tài)自動(dòng)機(jī)的概念[6].隨后，學(xué)者們利用有限狀態(tài)自動(dòng)機(jī)對(duì)字符串匹配的問(wèn)題進(jìn)行了研究.例如：文獻(xiàn)[7]給出了一種高效的有限狀態(tài)自動(dòng)機(jī)的存儲(chǔ)表示方法，并基于這種存儲(chǔ)表示方法建立了一種效率高于KMP算法的模式匹配算法；文獻(xiàn)[8]提出了一種基于自動(dòng)機(jī)的多模式匹配算法(AC算法)，該算法在匹配失敗時(shí)能夠高效跳轉(zhuǎn)，因此其匹配效率較好.但目前相關(guān)研究中所提出的自動(dòng)機(jī)狀態(tài)數(shù)目都是固定不變的，即僅能匹配特定的輸入字符串，因此具有很大的局限性.為此，本文提出了一種新的有限自動(dòng)機(jī)——狀態(tài)數(shù)目可變自動(dòng)機(jī)(variable number of states automata,VNS-DFA)，并通過(guò)算法分析驗(yàn)證了該自動(dòng)機(jī)的有效性.

1 有限狀態(tài)自動(dòng)機(jī)

在自動(dòng)機(jī)理論中，自動(dòng)機(jī)都是指抽象的自動(dòng)機(jī)，即是一種能變化和處理信息的離散動(dòng)態(tài)數(shù)學(xué)模型.自動(dòng)機(jī)可通過(guò)形式化語(yǔ)言、狀態(tài)轉(zhuǎn)移圖以及狀態(tài)轉(zhuǎn)移表3種方式進(jìn)行描述[9].目前，自動(dòng)機(jī)主要包括確定型有限狀態(tài)自動(dòng)機(jī)、非確定型有限狀態(tài)自動(dòng)機(jī)、有窮概率自動(dòng)機(jī)[10]、模糊有窮自動(dòng)機(jī)[11]、下推自動(dòng)機(jī)[12]、圖靈機(jī)[13]等.其中確定型有限狀態(tài)自動(dòng)機(jī)是一種控制狀態(tài)和符號(hào)集都有限的自動(dòng)機(jī)，它能夠?qū)γ總€(gè)輸入的字符做出識(shí)別，并保證所輸入的字符串都能夠到達(dá)最終的狀態(tài)和路徑[14].由于確定型有限狀態(tài)自動(dòng)機(jī)實(shí)現(xiàn)簡(jiǎn)單，且能應(yīng)用于字符串匹配中，因此本文選用確定型有限狀態(tài)自動(dòng)機(jī).

1)有限狀態(tài)自動(dòng)機(jī).有限狀態(tài)自動(dòng)機(jī)M可表示為一個(gè)五元組的形式[15]：

M=(Q,Σ,δ,q0,F).

(1)

其中：Q為狀態(tài)的非空有窮集合；q稱(chēng)為M的一個(gè)狀態(tài)；Σ為輸入字母表，輸入字符串都是Σ上的字符串；δ為狀態(tài)轉(zhuǎn)移函數(shù),δ∶Q×Σ→Q，對(duì)?(q,a)∈Q×E,δ(q,a)=p，表示M在狀態(tài)q時(shí)讀入字母表的字符a，將狀態(tài)q變成p，并處理下一個(gè)字符；q0為M的開(kāi)始狀態(tài)，q0∈Q;F為M的終止?fàn)顟B(tài)，F(xiàn)?Q.

假設(shè)公式(1)中的Q={q0,q1}，Σ={0,1}，q0為開(kāi)始狀態(tài)，F(xiàn)={q1}為終止?fàn)顟B(tài)，且δ(q0,0)=q0，δ(q0,1)=q1，δ(q1,0)=q0，δ(q1,1)=q1，此時(shí)自動(dòng)機(jī)M的狀態(tài)轉(zhuǎn)移圖如圖1所示，其狀態(tài)轉(zhuǎn)移表如表1所示.在圖1中，一個(gè)圓圈代表一個(gè)狀態(tài)，帶標(biāo)簽的箭弧表示轉(zhuǎn)移函數(shù)，無(wú)標(biāo)簽的箭弧指向的圓圈表示初始狀態(tài)，雙圓圈表示終態(tài).在表1中，表的各行對(duì)應(yīng)M的狀態(tài)，表的各列對(duì)應(yīng)輸入事件，其中有箭頭標(biāo)注的狀態(tài)是初始狀態(tài)，有*標(biāo)注的狀態(tài)是終態(tài).

圖1 M的狀態(tài)轉(zhuǎn)移圖

表1 M的狀態(tài)轉(zhuǎn)移表

由式(1)可知，上述定義的有限狀態(tài)自動(dòng)機(jī)M只能判別輸入的字符串是否被自動(dòng)機(jī)接受，但無(wú)法給出必要的中間結(jié)果和確定自動(dòng)機(jī)M所接受的字符串是什么內(nèi)容.對(duì)此，本文在公式(1)中增加了一個(gè)輸出字母表Δ以及輸出函數(shù)g∶Q→Δ，且當(dāng)q∈Q時(shí),g(q)=a表示M在q狀態(tài)下輸出a.

2)有限狀態(tài)自動(dòng)機(jī)接受的語(yǔ)言.自動(dòng)機(jī)接受的所有字符串的集合稱(chēng)為自動(dòng)機(jī)所接受的語(yǔ)言.設(shè)M=(Q,Σ,δ,q0,F)是一個(gè)自動(dòng)機(jī)，對(duì)于?x∈Σ*，如果δ(q0,x)∈F，則稱(chēng)x被M接受；如果δ(q0,x)?F，則稱(chēng)x不被M接受.有限狀態(tài)自動(dòng)機(jī)所接受的語(yǔ)言可表示為：

L(M)={x|x∈Σ*且δ(q0,x)∈F}.

(2)

2 狀態(tài)數(shù)目可變自動(dòng)機(jī)(VNS-DFA)的構(gòu)造

為提高用戶密碼的安全性，本文設(shè)計(jì)了如下用戶注冊(cè)和用戶登錄的流程：用戶注冊(cè)時(shí)首先設(shè)置密碼，然后系統(tǒng)對(duì)密碼進(jìn)行同態(tài)映射加密;用戶登錄系統(tǒng)時(shí)，為防止密碼被偷窺，將密碼隱藏在所輸入的字符串中.為了接受這些隱藏在字符串中的密碼，本文構(gòu)造了一種VNS-DFA自動(dòng)機(jī)，只要用戶輸入的密碼被該自動(dòng)機(jī)正確識(shí)別即可成功登錄.密碼設(shè)置和VNS-DFA自動(dòng)機(jī)識(shí)別的過(guò)程如圖2所示.

圖2 密碼設(shè)置和識(shí)別的過(guò)程

2.1 密碼加密的過(guò)程

f-1(w)={x|f(x)=w且x∈Σ*}.

(3)

由式(3)可知，若w是經(jīng)過(guò)加密之后的密碼，則w的原始密碼應(yīng)包含在它的同態(tài)原像中.

2.2 自動(dòng)機(jī)的構(gòu)造及識(shí)別

本文設(shè)計(jì)的狀態(tài)數(shù)目可變自動(dòng)機(jī)(VNS-DFA)可用如下的七元組表示：

M=(Q,Σ,Δ,δ,q0,F,g).

(4)

其中：Q,δ,q0,F的含義與DFA中的含義相同；g為輸出函數(shù)，?q∈Q，a∈Σ,g(q)=a, 即在滿足條件的狀態(tài)q下輸出原始字符a；Σ為輸出字母表；Δ為Σ經(jīng)過(guò)同態(tài)映射之后的輸入字母表.

根據(jù)自動(dòng)機(jī)的結(jié)構(gòu)及原理，本文構(gòu)造的VNS-DFA算法(算法1)的具體步驟如下所示：

輸入：原始串s，驗(yàn)證串t.

輸出：加密串在驗(yàn)證串中出現(xiàn)的次數(shù).

Step 1 將串s進(jìn)行加密，得到串s1.

Step 2 初始化自動(dòng)機(jī)狀態(tài)轉(zhuǎn)移矩陣A，并對(duì)其元素全部賦值為0.

Step 3 修改矩陣A，其中m為s1的長(zhǎng)度, 0為初態(tài)，n為終態(tài).具體修改規(guī)則如下:

A[0][s1[0]]=1;

A[n][s1[0]]=n+1;

A[n+1][s1[1]]=2;

ifs1[0]= =s1[m-1];

A[n][s1[1]]=2;

A[i][s1[0]]=n+1,A[i][s1[i]]=i+1,i=1，…，m-1.

Step 4 初始狀態(tài)k=0，匹配成功次數(shù)count=0，待匹配字符位置i=0.

Step 5 如果i= =n回到Step 6；否則,跳轉(zhuǎn)至新的狀態(tài)j=A[k][s1[i]]，并將j賦值給k;

ifj= =特定狀態(tài)，輸出相應(yīng)數(shù)字,回到Step 5;

ifj= =n-1匹配成功，count+1，回到Step 5;

i=i+1.

Step 6 結(jié)束.

算法1中：輸入是原始密碼s和用戶驗(yàn)證登錄密碼t，輸出是t在s中是否出現(xiàn)及其出現(xiàn)的次數(shù)，矩陣A為自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)移矩陣，m為原始密碼經(jīng)過(guò)同態(tài)映射后的密碼長(zhǎng)度，0為初始狀態(tài)，n為終止?fàn)顟B(tài).

Step 3為算法1的核心.在由Step 3建立好的自動(dòng)機(jī)中輸入某個(gè)字符時(shí)，若自動(dòng)機(jī)成功匹配，則跳轉(zhuǎn)至下一狀態(tài)，否則跳轉(zhuǎn)至初始狀態(tài).Step 5為算法1的匹配過(guò)程，當(dāng)且僅當(dāng)狀態(tài)跳轉(zhuǎn)為終態(tài)時(shí)，輸入的字符串才能被自動(dòng)機(jī)所接受，同時(shí)輸出其同態(tài)原像.

3 算法分析

3.1 算法的有效性證明

對(duì)于任意一個(gè)輸入串a(chǎn)1a2…an，根據(jù)文獻(xiàn)[16]中的定理1(對(duì)于任意的q∈Q,w∈Σ*,a∈Σ，都有δ(q,wa)=δ(δ(q,w),a))可以得到如下式子：

δ(0,a1a2…an)=δ(δ(0,a1a2…an-1),an)=δ(δ…(δ(0,a1)…),an).

(5)

根據(jù)算法1的轉(zhuǎn)移規(guī)則(δ(0,a1)=1,…,δ(n-1,an)=n)，可將式(5)轉(zhuǎn)變?yōu)椋?/p>

δ(δ…(δ(0,a1)…),an)=δ(δ…(δ(1,a2)…),an)=δ(n-1,an)=n.

(6)

由式(6)可得

δ(0,a1a2…an)=δ(δ…(δ(1,a2)…),an)=δ(n-1,an)=n.

(7)

由式(7)可知，自動(dòng)機(jī)在初態(tài)時(shí)可接受字符串a(chǎn)1a2…an，并且最后可到達(dá)終態(tài).根據(jù)本文提出的算法所構(gòu)造的識(shí)別串a(chǎn)1a2…an的有限狀態(tài)自動(dòng)機(jī)如圖3所示.

圖3 識(shí)別a1a2…an的有限狀態(tài)自動(dòng)機(jī)

本文以輸入密碼s為例驗(yàn)證本文構(gòu)造的自動(dòng)機(jī)能夠接受該密碼.假設(shè)s= ′12′，且s對(duì)應(yīng)的同態(tài)映射為f(1)= ′one′,f(2)= ′two′.在該假設(shè)下匹配該密碼的自動(dòng)機(jī)如圖4所示.由圖4可知：當(dāng)輸入的字符串中只要包含′onetwo′，該自動(dòng)機(jī)就可接受該字符串；當(dāng)自動(dòng)機(jī)匹配到′one′時(shí)，自動(dòng)機(jī)輸出′one′對(duì)應(yīng)的同態(tài)原像′1′；當(dāng)自動(dòng)機(jī)匹配到′two′時(shí)，自動(dòng)機(jī)輸出′onetwo′對(duì)應(yīng)的同態(tài)原像′12′.由以上可知，本文提出的自動(dòng)機(jī)能夠匹配包含加密密碼的字符串，并能夠輸出用戶輸入的原始密碼，因此本文構(gòu)造的自動(dòng)機(jī)是有效的.

圖4 識(shí)別原始串′12′的有限狀態(tài)自動(dòng)機(jī)

3.2 算法的復(fù)雜度分析

自動(dòng)機(jī)算法的復(fù)雜度通常包括建立算法的時(shí)間復(fù)雜度和匹配字符的時(shí)間復(fù)雜度.為了驗(yàn)證VNS-DFA算法的有效性，本文將VNS-DFA算法的時(shí)間復(fù)雜度、空間復(fù)雜度與傳統(tǒng)的DFA和改進(jìn)后的DFA的時(shí)間復(fù)雜度、空間復(fù)雜度進(jìn)行了對(duì)比，結(jié)果如表1所示.實(shí)驗(yàn)中，將待匹配串的長(zhǎng)度設(shè)置為m, 輸入串的長(zhǎng)度設(shè)置為n, 字母長(zhǎng)設(shè)置為|Δ|.

由表2可知：在時(shí)間復(fù)雜度上，在輸入規(guī)模相同的情況下3種算法在字符匹配的過(guò)程中的時(shí)間復(fù)雜度均為Θ(n)，但VNS-DFA算法的建立時(shí)間最短(復(fù)雜度為O(m))；在空間復(fù)雜度上，在輸入規(guī)模相同的情況下其差別不大.這是因?yàn)?種算法都可用二維數(shù)組表示狀態(tài)轉(zhuǎn)移矩陣，因此其大小取決于自動(dòng)機(jī)的狀態(tài)個(gè)數(shù)以及輸入字母表的長(zhǎng)度.

表2 3種不同算法的復(fù)雜度

4 結(jié)論

研究表明，本文構(gòu)造的VNS-DFA能夠匹配任意輸入的字符串，且其匹配速率優(yōu)于傳統(tǒng)的DFA及改進(jìn)的DFA，因此本文方法可以用于密碼的識(shí)別.在本文的算法中，當(dāng)待匹配的字符串長(zhǎng)度較大時(shí)，會(huì)因自動(dòng)機(jī)的狀態(tài)數(shù)目增多而導(dǎo)致耗費(fèi)更多的內(nèi)存空間.因此在今后的研究中，我們將對(duì)自動(dòng)機(jī)的狀態(tài)數(shù)目進(jìn)行改進(jìn)，以節(jié)約內(nèi)存空間.