不確定序列子串匹配的概率矩陣算法

段楓凱，吳愛華（上海海事大學信息工程學院，上海　201306）

?

不確定序列子串匹配的概率矩陣算法

段楓凱，吳愛華
（上海海事大學信息工程學院，上海201306）

摘要：

關鍵詞：

0　引言

字符串匹配問題是計算機科學中最古老、研究最廣泛的問題之一。一個字符串是指定義在有限字母表∑上的一個字符序列，而子串就是一個字符串，它是一個長序列的子序列并且任意兩個相鄰的字符之間沒有間隔。例如：在序列w=ACDAB中，AC就是其子串之一，AD則不是，因為AD之間被C隔開。

字符串匹配問題在眾多應用中都有著十分重要的作用。例如，生物信息學、信息檢索、拼寫檢查、語言翻譯、數據壓縮、網絡入侵檢測、數據挖掘和模式匹配等應用。在現有的研究中，大部分都是對確定序列子串匹配的研究，關于不確定序列的子串匹配的研究較少，而后者的應用需求逐漸增大，比如射頻識別測量、軌跡測量和蛋白質在DNA序列中的結合等應用。因此，對不確定序列的子串匹配的研究是十分有意義的。不確定序列是相對于確定序列而言的，例如，上面提到的w= ACDAB就是一個長度為5的確定序列，其字符來源于字符集∑=｛A，B，C，D｝。當w的每一位都不確定，即每一位可能是字符集∑中的任何一個字符時，w便成為了一個不確定序列。如表格1所示，S就是一個長度為8，字符來源于字符集∑=｛A，C，G，T｝的不確定序列。

本文將首先介紹解決不確定序列子串匹配問題的兩個算法：可能域算法和簡單的概率算法，并對兩個算法進行分析，找出簡單概率算法的計算結果會出現偏差的原因。接著根據該原因提出一個新算法——概率矩陣算法，并對其進行算法的介紹和分析，最后通過實驗驗證其正確性和時間復雜度。

1　相關工作

定義1不確定序列：已知一個字符集∑=｛δ[1]，δ [2]，…，δ[c]｝和一個序列S=｛s[1]，s[2]，…，s[n]｝，若滿足：

條件（1）s[i]=δ[j]（1≤i≤n，1≤j≤c）；

例1如表格1所示，S是長度為8的序列，∑=｛A，C，G，T｝為字符集。S每個位置可能出現的字符可以是∑中的任何一個字符，滿足條件（1），且每個位置可能出現字符的概率之和為1，滿足條件（2），因此S是一個長度為8的不確定序列。

表1　長度為8的不確定序列

定義2不確定序列的子串：已知字符集∑=｛δ[1]，δ[2]，…，δ[c]｝和兩個序列s、q。s=｛s[1]，s[2]，…，s[n]｝是包含n個字符的不確定序列，q=｛q[1]，q[2]，…，q[m]｝是包含m（＜=n）個字符的確定序列，且兩個序列的字符都源于字符集∑。若滿足條件q[i]=s[i+k]（0≤k≤n-m，1≤i≤m），則稱q是不確定序列s的子串，記為q∈s，記q是不確定序列s子串概率為P（q∈s）。

例2接例1，q= AC時，不確定序列S可能出現的序列有48種情況，當S為ACAGTAGG、GCACTAAA等包含AC且AC之間沒有其他字符間隔的情況時，q則為AC的子串。

1.1可能域的方法

可能域方法是解決不確定序列子串匹配問題最直接，同時也是最耗時的算法。可能域方法介紹如下。

例3已知一個不確定序列s如表2所示，根據可能域的定義可以得到其所有的可能域以及可能域的概率如表3所示。

表2　長度為4的不確定序列

很顯然，當用可能域的方法計算不確定序列子串匹配的概率時，只需要把所有包含子串的可能域的概率相加即可。

例4接例3，求不確定序列s中，子串q=AC的概率，則：

表3　序列s的所有可能域以及其概率

P（q?s）=P（W2）+P（W3）+P（W4）+P（W5）+P（W6）+P （W7）+P（W8）+P（W9）+P（W10）+P（W11）+P（W12）=0.19

可能域方法計算不確定序列子串匹配的概率時，步驟簡單，易于理解，計算結果正確，但是其可能域的數量為cn，算法時間復雜度為O（tn），隨著n的增大，將算法編程進行運行時消耗時間太長。

1.2簡單的概率方法

簡單的概率方法解決不確定序列子串匹配的問題時，時間復雜度比可能域算法小的多，可以求得近似值，詳細描述如下。

在公式（1）中，s是長度為n不確定序列，q是長度為m（≤n）的子串，其原理為在s中，可能出現n-m+1種情況有連續的m位是子串q而不管其他位是什么，然后再將這n-m+1中情況的概率相加。

例5同例4，計算不確定序列s中，子串q=AC的概率。

運用公式（1），P（q?s）≈P（s[1]=q[1]）*P（s[2]=q[2]）+P（s[2]=q[1]）*P（s[3]=q[2]）+P（s[3]=q[1]）*P（s[4]=q[2]）= 0.2。

表4　簡單概率方法可能出現的情況

計算完成之后結果為0.2，比用可能域方法計算的結果0.19偏大，原因是如圖表4所示，用該方法計算時，共可能出現3種情況，其中？表示可以是字符集中的任何一個字符，那么，情況1和情況3都會有包括ACAC的情況出現，即ACAC的情況被多加了一次，如果減去這種情況的概率一次（由表3可看到出現ACAC的概率為0.01），得到0.19，則與可能域方法計算的結果一致。

簡單的概率算法在計算不確定序列子串匹配的結果時，時間復雜度為O（n），但是只能算近似值，隨著n的增大，其精確度會原來越差。根據簡單的概率算法造成偏差的原因，本文提出了一個概率矩陣的算法，其原理為在不確定序列s中，可能出現n-m+1種情況有連續的m位是子串q而不管其他位是什么，從第一種情況逐漸往第n-m+1種情況計算，并且在計算每種情況的同時，減去前面所有可能與它發生沖突的可能的子情況的概率。

2　概率矩陣算法

2.1概率矩陣算法詳細描述

概率矩陣算法分為四個步驟，分別為求重復子串的長度、求子串的行標數組、求概率矩陣和根據概率矩陣求和。

（1）求重復子串的長度

定義4重復子串：已知兩個確定字符串q=｛q[1]，q [2]，…，q[m]｝和r=｛r[1]，r[2]，…，r[t]｝（t≤m&&m％t==0），如果滿足r[j]=q[j]=q[j+t]…=q[j+（m/t-1）t]（1≤j≤t），則稱r是q的重復子串，其長度為|r|=t，且重復次數為m/ t。

例6已知兩個序列q=ACACAC，r=AC，則根據以上定義可知，r就是q的重復子串，其長度為2，重復次數為3。

求重復子串長度的偽代碼：

Input：m //子串q的長度

Output：t //重復子串的長度

1：t←m //t初始化為m

2：for i←m；i＞1；i←i-1 do //i為重復子串可能的重復次數

3：If m％i == 0 then //滿足這個條件可能找到重復子串

4：t←m/i

5：flag←true //用來判斷是否找到正確的重復子串

6：for j←t+1；j＜=m-t+1；j←j+1 do //j為和第一個重復子串匹配的子串的第一個下標

7：If！isMatch（1，j，t）then //和第一個重復子串匹配失敗

8：t=m

9：flag=false

10：break

11：if flag==true then//所有重復子串和第一個重復子串匹配成功，找到重復子串

12：break

13：return t

求重復子串長度的偽代碼如上。其詳細過程為，給定一個確定的字符串q，長度為m，其重復子串的重復次數i就可能為1，2，…，m；然后從m開始判斷那個值是正確的重復次數，直到找到正確的重復次數或者判斷完畢退出循環。在判斷的過程，取q的第一個重復子串分別和后面的重復子串匹配，如果匹配成功，則找到正確的重復次數和重復子串，重復子串長度t=m/i，否則，繼續判斷下一個重復次數。最后，若判斷完畢沒找到正確重復子串退出循環，則說明q本身就是一個重復子串，重復了一次，其長度t=m。

（2）求子串的行標數組

對于一個長度為n的不確定序列s和一個長度為m的子串q，q中的每個字符都對應s的一個行標，相應的，q中所有的字符就會對應一個行標數組，先將行標數組求出，為下一步求概率矩陣做準備。

求子串的行標數組偽代碼：

Input：q，∑//q是長度為m的子串；∑為字符集數組，順序按照不確定序列s的行標排列

Output：rows//行標數組

1：rows[1...m]←0 //初始化行標數組

2：for i←1；i＜=m；i←i+1 do

3：for j←0，j＜∑.length；j←j+1 do

4：if q[i]=∑[j]then

5：rows[i]=j

6：break

7：return rows

求子串行標數組的偽代碼如上，其詳細流程為從1至m循環查找m個字符的行標。在每次尋找行標的過程中，將本次的字符依次與字符集數組中元素匹配，若匹配成功，則找到，否則，繼續匹配下一個元素，最后將得到的行標數組rows返回。

例7已知一個不確定序列s如表5所示，和一個子串q=ACAC，根據行標數組的算法，顯然可知字符集數組∑=｛A，C，G，T｝。首先將q的第一個字符A和∑中的字符一一比較，得到A為∑的第一個元素，因此第一個字符A在s中的行標為0（行標從0開始）。以此類推，求q其他字符的行標，可計算得q的行標數組rows [1...4]=｛0，1，0，1｝。

表5　規模為6的不確定序列s

（3）求概率矩陣

概率矩陣的求解是四個步驟中最核心的一步，它是一個n-m+1行，m/t+1列的矩陣，n-m+1行表示在不確定序列s中，可能出現n-m+1種可能有連續的m位是子串q而不管其他位是什么，每一行i（0≤i≤n-m）都是為了計算第i行除去會與0到i-1行發生重復情況概率的概率。在每行i的m/t+1列的后面m/t列中，依次存放在第i行下的m/t個重復子串的概率。而在每行的第一列則存放1-0到i-1行會與第i行發生重復子情況的概率。

求概率矩陣偽代碼：

Input：s，q，t，rows //s：長度為n的不確定序列，q：長度為m的子串，t：重復子串的長度，rows：行標數組

Output：matrix //（n-m+1）*（m/t+1）的概率矩陣，用二維數組表示

1：matrix[0][0]...matrix[n-m+1][m/t+1]←0；//初始化概率矩陣

2：for i←0；i＜n-m+1；i←i+1 do //計算所有除第一列以外的概率

3：for j=1；j＜m/t+1；j←j+1 do

4：p=1；//p必須是浮點型

5：for k=1；k＜t；k←k+1 do //計算第i行第j個元素的值

6：p←p*s[rows[（j-1）*s+t+1]][（j-1）*s+t+ 1+i]

7：matrix[i][j]=p；

8：for i←0；i＜n-m+1；i←i+1 do//計算第一列的概率

9：matrix[i][0]=1；

10：if i＞=t then

11：k←t

12：for l←i-t；l＞=0；l←l-k do

13：p=1；//必須為浮點數

14：count←

15：for j←0；j＜count&&j＜m/t+1；j←j+1 do

16：p←p*matrix[l][j]

17：matrix[i][0]←matrix[i][0]-p；

18：if l=（i-m）then

19：k←1

20：return matrix

求概率矩陣的偽代碼如上所示，該代碼分為兩部分，第一部分是2-7行：計算矩陣中除第一列以外的數據，第二部分是8-19行：進行計算矩陣中第一列的數據。第一部分，在上文中已經提到每行i（0≤i＜n-m+1）的后m/t列中，存放的是該行對應情況下的m/t個重復子串的概率，每個重復子串的概率為t個字符在s對應位置的概率之和。第二部分，計算矩陣中第一列的數據是最關鍵的一步，當行號i＜重復子串的長度t時，第一列的概率為1，否則，第一列概率則為1-上面行會與當前行發生重復情況的概率。

例8接例7，求子串q在不確定序列s上的概率矩陣。

根據求概率矩陣的偽代碼，首先定義一個（n-m+ 1）*（m/t+1）=5*3的矩陣matrix，其中5代表會有如表6所示的5種情況發生，？代表可以是字符集中的任何一個字符。然后執行偽代碼的第一部分，首先計算矩陣的后兩列，matrix[i][1]（0≤i＜5）是在表6的第i種情況下，子串q的第一個重復子串AC處于位置s[i+1，i+2]的概率；matrix[i][2]是在表6的第i種情況下，子串q的第二個重復子串AC處于位置s[i+3，i+4]的概率。將計算完畢的后兩列的概率存入matrix的后兩列。最后執行偽代碼的第二部分，計算矩陣的第一列，0和1都小于重復子串的長度2，所以0和1兩行第一列值都為1。計算第2行，0行和2行都有可能出現ACACAC？？的情況，所以2行的前兩位不能是AC，即2行0列的概率matrix[2][0]=1-matrix[0][1]*matrix[0][1]=0.99。同理，第3行的2、3位不可以是AC，matrix[3][0]=1-matrix[1][1]=0.9。第4行的第3、4位不能是AC，1、2、3和4位不能是ACAC，因此，matrix[4][0]=1-matrix[2][0]*matrix[2][1]-matrix[0][0]*matrix[0][1]*matrix[0][2]=0.98。致此，計算完畢，計算結果如表7所示。

表6　可能出現的n-m+1=5種情況

表7　概率矩陣matrix

（4）根據概率矩陣求和

概率矩陣的每行都代表可能會出現的一種情況，因此，當概率矩陣計算結束時，只需要分別將n-m+1行的m/t+1個概率相乘再相加即可。

根據概率矩陣求和的偽代碼

Input：matrix //概率矩陣（n-m+1）*（m/s+1）

Output：probability

1：probability←0//初始化概率矩陣

2：for i←0；i＜n-m+1；i←i+1 do

3：p←1//必須為浮點數

4：for j←0；j＜m/s+1；j←j+1 do

5：p←p*matrix[i][j]

6：probability←probability+p；

7：return probability

最后根據概率矩陣求和的偽代碼如上所示，其過程為對概率矩陣每行的概率相乘再相加，計算的結果則為最終的不確定序列s匹配子串q的概率。

例9接例8，根據概率矩陣求不確定序列s匹配子串q的概率。

根據偽代碼，計算每行的乘積再相加得P（q∈s）= 0.035096。

2.2概率矩陣算法復雜度分析

首先分析概率矩陣算法的空間復雜度。計算重復子串的長度時，占用固定空間的對象是長度為m子串q和重復子串的長度t；占用的可變空間忽略不計。以Java的基本類型字節標準進行計算得子串行標數組的空間復雜度為2*m+4=O（m）。

計算子串行標數組時，占用固定空間的對象是長度為m的子串q，字符集數組∑（假設其個數為c）和行標數組rows（長度為m），占用的可變空間忽略不記，以Java的基本類型字節標準進行計算得子串行標數組的空間復雜度為2*m+2*c+4*m=O（3m+2c）。

求概率矩陣時，占用固定空間的對象有長度為n的不確定序列s（行數假設為c），長度為m的子串q，重復子串的長度t和行標數組rows（個數為m），占用的可變空間忽略不記，以java的基本類型字節標準進行計算得求概率矩陣的空間復雜度為8*cn+2*m+4+4*m=O （4cn+3m）。

根據矩陣概率求和，占用固定空間的對象是上一步得到的（n-m+1）*（m/t+1）的概率矩陣matrix和最后求得的結果probability，占用的可變空間忽略不計，以Java的基本類型字節標準進行計算求得空間復雜度為（n-m+1）*（m/t+1）*8+probability*8=O（m/t（n-m））。

綜上所述，概率矩陣算法的空間復雜度為四個步驟之和：O（m）+O（3m+2c）+O（4cn+3m）+O（m/t（n-m）），由于在實際的應用中m、c和t的值非常小。所以，最后的空間復雜度為O（n）。

分析概率矩陣算法的時間復雜度。計算重復子串的長度時，有兩層循環，外層循環和內層循環最壞情況執行次數均為m，每次循環基本操作的數量也很小。因此，計算重復子串長度的時間復雜度為O（m2）。

計算子串行標數組時，有兩層循環，基本操作執行的次數最多為m*c=O（m）。

求概率矩陣時，第一部分有兩層循環，基本操作執行次數為（n-m+1）*（m/t+1）=O（m/t（n-m））；第二部分有三層循環，第一層為n-m+1次，第二層最多執行n-m次，第三層最多執行m/t+1次，因此，基本操作最多執行次數為：（n-m+1）*（n-m）*（m/t+1）=O（m/t（n-m）2）。兩部分相加為求概率矩陣時間復雜度的結果：O（m/t （n-m））+O（m/t（n-m）2）=O（m/t（n-m）2）。

根據概率矩陣求和，有兩層循環，基本操作執行次數為（n-m+1）*（m/t+1）=O（m/t（n-m）），即求和的時間復雜度為O（m/t（n-m））。

綜上所述，概率矩陣算法的時間復雜度為以上四個步驟時間復雜度之和：O（m2）+O（m）+O（m/t（n-m）2）+ O（m/t（n-m））。由于在實際的應用中m、c和t的值非常小，最終的時間復雜度為O（n2）。

3　實驗

3.1算法的正確性

首先將可能域算法和概率矩陣的算法用Java語言編程，配置環境為Win7 64位操作系統，Intel Core i3處理器和Eclipse 4.4。然后將不同規模的數據輸入進行計算，通過大量的實驗，并將概率矩陣算法的結果與可能域方法的結果作對比，證實了概率矩陣算法的正確性。

如表格8-表格10所示，分別為當子串q= ACAC、q= ACGTCAG和q= ACGTACGTA時，在不確定序列s的規模n為10、30、50、100、300、600和1200下兩個算法的實驗結果的比較，通過觀察可以發現隨著n的變化，兩個算法的結果是相同的，而且不受子串q的長度的影響，其中有一些末位不相同，這是由于Double類型的精度導致的。

表8　m=4時，兩種算法求得的結果比較表

表9　m=7時，兩種算法求得的結果比較表

表10　m=9時，兩種算法求得的結果比較表

3.2算法的時間復雜度證明

通過對概率矩陣算法進行大量實驗，獲得了不同規模下的運行時間。圖1為選取一些數據繪制而成的圖，橫坐標為不確定序列s的規模n，縱坐標為不同規模數據運行時所消耗的時間，圖1描繪了當子串q= ACAC、q= ACGTCAG和q= ACGTACGTA即子串長度m=4、m=7和m=9時，隨著n的增大用概率矩陣算法計算耗費的時間圖，仔細觀察可以發現其曲線趨勢和時間復雜度O（n2）相吻合。此外，當q的長度m不同，s的規模不變時，消耗時間相差極小，說明其消耗時間不受子串的長度m的影響。

圖1　概率矩陣算法不同長度子串在不同規模下運行的耗時

4　結語

首先介紹了計算不確定序列子串匹配問題的可能域方法和簡單的概率方法，然后根據兩個算法的比較和分析得出簡單的概率算法計算結果會出現偏差的原因，基于這個原因，提出了一個全新的算法——矩陣概率的方法。最后，通過對概率矩陣算法進行分析與大量的實驗，證明了矩陣概率算法是正確的，并且其時間復雜度為O（n2），不受子串的長度m大小的影響。

參考文獻：

[1]黃建.入侵檢測系統中字符串匹配算法與實現[D].華中科技大學，2008.

[2]張寶軍.網絡入侵檢測若干技術研究[D].浙江大學，2010.

[3]劉微.基于生物行為的射頻識別系統優化模型與算法研究[D].吉林大學，2011.

[4]韓曉莉.字符串匹配算法在P2P流量檢測中的研究與實現[D].北京郵電大學，2007.

[5]聶波.基于流特征的P2P流量檢測方法研究[D].北京郵電大學，2009.

[6]C.A GGARWAL，Y.L I，J.WANG，J.WANG.Frequent Pattern Mining with Uncertain Data.in SIGKDD，ACM，2009.

[7]C.C.A GGARWAL，P.S.Y U，A survey of uncertain data algorithms and applications，TKDE，2009.

[8]Y.TONG，L.C HEN，Y.C HENG，P.Y U.Mining Frequent Itemsets Over Uncertain Databases，PVLDB，2012.

[9]L.WAN，C.L ING，C.Z HANG.Mining Frequent Serial Episodes Over Uncertain Sequence Data，in EDBT，2013.

[10]Q.ZHANG，F.L I，K.Y I.Finding Frequent Items in Probabilistic Data.in SIGMOD，ACM，2008：819-832.

[11]Y.X.LI，B.JAMES，K.LARS，J.PEI，Efficient Matching of Substrings in Uncertain Sequences，in SIAM.

Probability Matrix Algorithm of Substrings Matching in Uncertain Sequence

DUAN Feng-kai，WU Ai-hua
（College of Information Engineering，Shanghai Maritime University，Shanghai 201306）

Abstract：

The researches about substrings matching in uncertain sequence are less now.To study possible domain algorithm and a simple probabilistic algorithm，finds the reason of the error of simple probability algorithm，on this basis，puts forward probability matrix algorithm.Describes the probability matrix algorithm in details and complexity analysis，and proves the correctness of the results through programming and comparing with the possible domain algorithm.

Keywords：

目前關于不確定序列子串匹配算法的研究比較少。經過對可能域算法和簡單概率算法的分析，發現簡單概率算法出現誤差的原因，在此基礎上，提出概率矩陣算法。對概率矩陣算法進行詳細描述和復雜度分析，并通過編程與可能域算法的結果進行比較證明其正確性。

可能域算法；簡單概率算法；概率矩陣算法

文章編號：1007-1423（2016）14-0032-07

DOI：10.3969/j.issn.1007-1423.2016.14.007

作者簡介：

段楓凱，女，山西人，碩士研究生，研究方向為數據庫應用

吳愛華，女，江西人，博士，副教授，研究方向為數據庫應用

收稿日期：2016-03-22修稿日期：2016-05-10

Possible Domain Algorithm；Simple Probability Algorithm；Probability Matrix Algorithm