劉帆， 趙亞慧,， 崔榮一

( 1.延邊大學(xué) 融合學(xué)院, 吉林 延吉 133002； 2.延邊大學(xué) 工學(xué)院, 吉林 延吉 133002 )

0 引言

用戶名合法性檢測問題的本質(zhì)是字符串匹配問題.與傳統(tǒng)的字符串匹配不同，合法性檢測問題只需保證字符類別匹配成功即可.合法的用戶名字符串需同時含有數(shù)字、特殊字符、大寫字母且其長度需大于8位.傳統(tǒng)的字符匹配算法主要有暴力匹配(BF)算法[1]、Rabin - Karp(RK)算法[2]、字符串查找(KMP)算法[3]以及正則表達(dá)式[4].其中： BF算法雖然簡單，但耗時較大； RK算法是基于哈希函數(shù)的一種對BF算法改進(jìn)的算法，在正常情況下該算法的效率雖然優(yōu)于BF算法，但當(dāng)哈希產(chǎn)生沖突時該算法的效率仍然較低； KMP算法是一種采用消除主串指針回溯的方法對BF算法進(jìn)行優(yōu)化的算法，該算法雖然能夠彌補(bǔ)BF算法在主針回溯后需重新開始進(jìn)行比較的缺點，但在重復(fù)率很高的文本中其效率低于BF算法；正則表達(dá)式與上述方法相比，雖然時間效率有所提高，但存在空間復(fù)雜度高和易出錯等缺點[5].近年來，一些研究者基于上述方法又提出了BM算法[6]和Sunday算法[7]，這兩種方法雖大幅提高了字符串匹配的效率，但二者過于依賴于輔助數(shù)據(jù)結(jié)構(gòu)，且預(yù)處理時間過長.

1956年， Moore等首次提出了有限狀態(tài)自動機(jī)的概念[8]，并在后續(xù)的研究中針對字符串匹配問題提出了有限狀態(tài)自動機(jī)算法—Aho - Corasick(AC)算法[9].該算法與上述傳統(tǒng)算法相比，只需掃描一遍字符串即可，且其時間復(fù)雜度與模式串的規(guī)模無關(guān)，因此該算法受到學(xué)者們的關(guān)注.目前利用該方法雖然可以檢測用戶名字符串中包含的類別，但無法檢測用戶名長度，因此其應(yīng)用性受到一定限制.為此，本文提出了一種新有限狀態(tài)自動機(jī)，并通過分析驗證了該自動機(jī)的有效性.

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

傳統(tǒng)的有限狀態(tài)自動機(jī)由一個五元組組成[10]：

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

(1)

其中：Q是包含自動機(jī)中所有狀態(tài)的非空集合；Σ是字母表，自動機(jī)接收的任意字符均為該集合元素；δ是狀態(tài)轉(zhuǎn)移函數(shù)，其中δ：Q×Σ→Q, 對?(q,a)∈Q×Σ, ?p∈Q有δ(q,a)=p，它表示自動機(jī)M在狀態(tài)q時讀入字符a之后，狀態(tài)q隨即轉(zhuǎn)向狀態(tài)p；q0為M的初始狀態(tài)，q0∈Q；F為終止?fàn)顟B(tài)集合，F(xiàn)?Q，?q∈F，q稱為M的一個終態(tài).

對于?x∈Σ*, 若有δ(q0,x)∈F， 則稱x被M所接受；對于?x∈Σ*， 若有δ(q0,x)?F, 則稱x不被M所接受[11].所有可以被M接受的x的集合稱為M可接受的語言,表示為：

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

(2)

假設(shè)Q={q0,q1,q2},Σ={0,1},F={q2}，δ(q0,0)=q1,δ(q0,1)=q0,δ(q1,0)=q2,δ(q1,1)=q0,δ(q2,0)=q2，δ(q2,1)=q0, 則此時的自動機(jī)M如圖1所示，其狀態(tài)轉(zhuǎn)移函數(shù)如表1所示.在圖1中，單圓圈代表自動機(jī)中的中間狀態(tài)，雙圓圈代表終止?fàn)顟B(tài)，標(biāo)有字符的有向箭頭代表轉(zhuǎn)移函數(shù)，箭頭S所指向的單圓圈代表初始狀態(tài).

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

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

2 自動機(jī)模型的構(gòu)建

為了便于檢測用戶名的合法性，本文設(shè)計了一種可計數(shù)的有限狀態(tài)自動機(jī)，其檢測流程如下：①用戶提交需檢測的用戶名.②系統(tǒng)利用同態(tài)映射對用戶名進(jìn)行字符分類(屬于同一類的字符被映射為同一個字符，同時用戶名字符串映射為對應(yīng)類別字符串)；若某類別字符串可以被該自動機(jī)正確識別，則對應(yīng)的用戶名字符串為合法，否則為不合法.由于自動機(jī)每次只能輸出一個字符，不能直接輸出用戶名是否合法，因此本文設(shè)計了一個解碼函數(shù).該解碼函數(shù)可根據(jù)自動機(jī)最后的狀態(tài)輸出用戶名不合法的原因.用戶名映射、自動機(jī)識別以及狀態(tài)解碼的過程如圖2所示.

圖2 用戶名映射、自動機(jī)識別和狀態(tài)解碼的過程

2.1 映射函數(shù)和解碼函數(shù)

用戶名字符分類是一個同態(tài)映射過程.設(shè)D是初始用戶名字符串，E是分類字符串，f:D→E為映射，對于?d1,d2∈D有f(d1d2)=f(d1)f(d2), 則稱f是D到E的同態(tài)映射.本文將用戶名字符分類的映射函數(shù)定義為：

(3)

其中x是原始用戶名字符串中的字符.

輸出不合法原因的解碼函數(shù)是一個映射過程，即當(dāng)?a∈A,?b∈B, 且有h(a)=b, 稱h是A到B的映射.本文將解碼函數(shù)定義為：

(4)

其中，x是指自動機(jī)在接收一個字符串后跳轉(zhuǎn)到的最終狀態(tài).

2.2 自動機(jī)模型的構(gòu)建

本文建立的自動機(jī)模型G由一個六元組組成：

G=(Q,Σ,δ,q0,F,n).

(5)

其中：Q、Σ、δ、q0、F與有限狀態(tài)自動機(jī)的定義一致；n為計數(shù)器(自動機(jī)每接受1個字符時，n減1).G的狀態(tài)轉(zhuǎn)移函數(shù)如表2所示.本文算法的具體步驟如下：

輸入：字符串s

輸出：用戶名是否合法

Step 1 對字符串s進(jìn)行映射，得到映射串s′;

Step 2 根據(jù)狀態(tài)轉(zhuǎn)移函數(shù)表初始化狀態(tài)轉(zhuǎn)移字典trans， 同時將n初始化為8;

Step 3 設(shè)初始狀態(tài)為q0， 即設(shè)待匹配字符串的首位為i=0;

表2 G的狀態(tài)轉(zhuǎn)移函數(shù)

Step 4 讀完字符串時，若n≤0時則算法結(jié)束，否則跳轉(zhuǎn)到Step 5;

Step 5 依據(jù)最終狀態(tài)進(jìn)行解碼并輸出字符中不合法的原因，算法結(jié)束.

該算法中，輸入是需驗證合法性的原始用戶名s； 輸出是該用戶名s是否合法.若合法，不輸出錯誤；若不合法，輸出不合法并給出原因.映射串s′是輸入字符串s經(jīng)函數(shù)f(x)同態(tài)映射得到的分類字符串，字典trans是依據(jù)表2進(jìn)行初始化的狀態(tài)轉(zhuǎn)移函數(shù)，n賦值為8表示合法用戶名至少是9位字符；end表示自動機(jī)為終態(tài)，end∈F.

3 算法分析

3.1 算法有效性證明

對于任意的一個輸入字符串a(chǎn)1a2…an， 根據(jù)文獻(xiàn)[10]中的定理1可知：對于?q∈Q,ω∈Σ*,a∈Σ, 有δ(q,wa)=δ(δ(q,w),a).由此可得：

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

(6)

再根據(jù)表2可得：

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

(7)

依據(jù)計數(shù)器的定義，此時接收到的字符串a(chǎn)1a2…an的值為：

n=8-|a1a2…an|.

(8)

公式(8)中的|a1a2…an|表示字符串a(chǎn)1a2…an的長度.當(dāng)式(8)中求得的n大于0時，自動機(jī)在end(終態(tài))處跳轉(zhuǎn)至下一狀態(tài)，即表示用戶名不合法.因此，只有當(dāng)自動機(jī)最后到達(dá)的狀態(tài)是終態(tài)時，該用戶名才是合法的，否則為不合法.根據(jù)本文算法構(gòu)造的用于檢驗用戶名合法性的可計數(shù)自動機(jī)如圖3所示.

圖3 可計數(shù)自動機(jī)的狀態(tài)轉(zhuǎn)移圖

本文以輸入字符串s和t為例驗證本文構(gòu)造的自動機(jī)的有效性，其中假設(shè)s為‘a(chǎn)bA*’和t為‘2B&’， 映射串s1(‘a(chǎn)aAT’)和t1(‘1AT’)由s和t經(jīng)映射函數(shù)f(x)得到.圖4和圖5分別是s1和t1的狀態(tài)轉(zhuǎn)移圖，圖中的虛線為字符串在自動機(jī)中的轉(zhuǎn)移路線.由圖可知，s1和t1經(jīng)自動機(jī)轉(zhuǎn)移到的最終狀態(tài)分別是q4和q8.由于q4和q8均不是終態(tài)，因此這兩個字符串是不合法的.此時解碼函數(shù)h(x)輸出的是：“該用戶名缺少數(shù)字，不合法”和“該用戶名長度不夠，不合法”.上述實例證明本文提出的算法可以有效驗證用戶名的合法性，且具有簡單、穩(wěn)定的優(yōu)點.

圖4 s1的狀態(tài)轉(zhuǎn)移圖

圖5 t1的狀態(tài)轉(zhuǎn)移圖

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

表3為傳統(tǒng)有限自動機(jī)模型(DFA)與本文所提模型(N - DFA)的復(fù)雜度，其中n為需要滿足的條件個數(shù)，m為用戶名長度.由表3可知，本文所提模型在時間復(fù)雜度和空間復(fù)雜度方面均優(yōu)于傳統(tǒng)模型.

表3 不同模型的復(fù)雜度

4 結(jié)論

研究表明，本文設(shè)計的模型可實現(xiàn)有限狀態(tài)自動機(jī)的計數(shù)和設(shè)置輸入字符串的長度，且具有檢測效率高、性能穩(wěn)定等優(yōu)點，因此本文方法可用于用戶名的合法性檢驗.本文算法未能實現(xiàn)計數(shù)器和終態(tài)的完全分離，擬在今后的研究中通過調(diào)整計數(shù)器和終態(tài)的關(guān)系使二者相互獨立，以使本文算法達(dá)到更好的檢測效果.