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

?

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

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

摘要：

關(guān)鍵詞：

0　引言

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

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

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

1　相關(guān)工作

定義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每個位置可能出現(xiàn)的字符可以是∑中的任何一個字符，滿足條件（1），且每個位置可能出現(xiàn)字符的概率之和為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可能出現(xiàn)的序列有48種情況，當(dāng)S為ACAGTAGG、GCACTAAA等包含AC且AC之間沒有其他字符間隔的情況時，q則為AC的子串。

1.1可能域的方法

可能域方法是解決不確定序列子串匹配問題最直接，同時也是最耗時的算法?？赡苡蚍椒ń榻B如下。

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

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

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

例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

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

1.2簡單的概率方法

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

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

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

運(yùn)用公式（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　簡單概率方法可能出現(xiàn)的情況

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

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

2　概率矩陣算法

2.1概率矩陣算法詳細(xì)描述

概率矩陣算法分為四個步驟，分別為求重復(fù)子串的長度、求子串的行標(biāo)數(shù)組、求概率矩陣和根據(jù)概率矩陣求和。

（1）求重復(fù)子串的長度

定義4重復(fù)子串：已知兩個確定字符串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的重復(fù)子串，其長度為|r|=t，且重復(fù)次數(shù)為m/ t。

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

求重復(fù)子串長度的偽代碼：

Input：m //子串q的長度

Output：t //重復(fù)子串的長度

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

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

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

4：t←m/i

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

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

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

8：t=m

9：flag=false

10：break

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

12：break

13：return t

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

（2）求子串的行標(biāo)數(shù)組

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

求子串的行標(biāo)數(shù)組偽代碼：

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

Output：rows//行標(biāo)數(shù)組

1：rows[1...m]←0 //初始化行標(biāo)數(shù)組

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

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

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

表5　規(guī)模為6的不確定序列s

（3）求概率矩陣

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

求概率矩陣偽代碼：

Input：s，q，t，rows //s：長度為n的不確定序列，q：長度為m的子串，t：重復(fù)子串的長度，rows：行標(biāo)數(shù)組

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

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

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

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

4：p=1；//p必須是浮點(diǎn)型

5：for k=1；k＜t；k←k+1 do //計(jì)算第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//計(jì)算第一列的概率

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；//必須為浮點(diǎn)數(shù)

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行：計(jì)算矩陣中除第一列以外的數(shù)據(jù)，第二部分是8-19行：進(jìn)行計(jì)算矩陣中第一列的數(shù)據(jù)。第一部分，在上文中已經(jīng)提到每行i（0≤i＜n-m+1）的后m/t列中，存放的是該行對應(yīng)情況下的m/t個重復(fù)子串的概率，每個重復(fù)子串的概率為t個字符在s對應(yīng)位置的概率之和。第二部分，計(jì)算矩陣中第一列的數(shù)據(jù)是最關(guān)鍵的一步，當(dāng)行號i＜重復(fù)子串的長度t時，第一列的概率為1，否則，第一列概率則為1-上面行會與當(dāng)前行發(fā)生重復(fù)情況的概率。

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

根據(jù)求概率矩陣的偽代碼，首先定義一個（n-m+ 1）*（m/t+1）=5*3的矩陣matrix，其中5代表會有如表6所示的5種情況發(fā)生，？代表可以是字符集中的任何一個字符。然后執(zhí)行偽代碼的第一部分，首先計(jì)算矩陣的后兩列，matrix[i][1]（0≤i＜5）是在表6的第i種情況下，子串q的第一個重復(fù)子串AC處于位置s[i+1，i+2]的概率；matrix[i][2]是在表6的第i種情況下，子串q的第二個重復(fù)子串AC處于位置s[i+3，i+4]的概率。將計(jì)算完畢的后兩列的概率存入matrix的后兩列。最后執(zhí)行偽代碼的第二部分，計(jì)算矩陣的第一列，0和1都小于重復(fù)子串的長度2，所以0和1兩行第一列值都為1。計(jì)算第2行，0行和2行都有可能出現(xiàn)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。致此，計(jì)算完畢，計(jì)算結(jié)果如表7所示。

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

表7　概率矩陣matrix

（4）根據(jù)概率矩陣求和

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

根據(jù)概率矩陣求和的偽代碼

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//必須為浮點(diǎn)數(shù)

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

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

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

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

2.2概率矩陣算法復(fù)雜度分析

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

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

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

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

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

分析概率矩陣算法的時間復(fù)雜度。計(jì)算重復(fù)子串的長度時，有兩層循環(huán)，外層循環(huán)和內(nèi)層循環(huán)最壞情況執(zhí)行次數(shù)均為m，每次循環(huán)基本操作的數(shù)量也很小。因此，計(jì)算重復(fù)子串長度的時間復(fù)雜度為O（m2）。

計(jì)算子串行標(biāo)數(shù)組時，有兩層循環(huán)，基本操作執(zhí)行的次數(shù)最多為m*c=O（m）。

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

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

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

3　實(shí)驗(yàn)

3.1算法的正確性

首先將可能域算法和概率矩陣的算法用Java語言編程，配置環(huán)境為Win7 64位操作系統(tǒng)，Intel Core i3處理器和Eclipse 4.4。然后將不同規(guī)模的數(shù)據(jù)輸入進(jìn)行計(jì)算，通過大量的實(shí)驗(yàn)，并將概率矩陣算法的結(jié)果與可能域方法的結(jié)果作對比，證實(shí)了概率矩陣算法的正確性。

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

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

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

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

3.2算法的時間復(fù)雜度證明

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

圖1　概率矩陣算法不同長度子串在不同規(guī)模下運(yùn)行的耗時

4　結(jié)語

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

參考文獻(xiàn)：

[1]黃建.入侵檢測系統(tǒng)中字符串匹配算法與實(shí)現(xiàn)[D].華中科技大學(xué)，2008.

[2]張寶軍.網(wǎng)絡(luò)入侵檢測若干技術(shù)研究[D].浙江大學(xué)，2010.

[3]劉微.基于生物行為的射頻識別系統(tǒng)優(yōu)化模型與算法研究[D].吉林大學(xué)，2011.

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

[5]聶波.基于流特征的P2P流量檢測方法研究[D].北京郵電大學(xué)，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(xiàn).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：

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

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

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

DOI：10.3969/j.issn.1007-1423.2016.14.007

作者簡介：

段楓凱，女，山西人，碩士研究生，研究方向?yàn)閿?shù)據(jù)庫應(yīng)用

吳愛華，女，江西人，博士，副教授，研究方向?yàn)閿?shù)據(jù)庫應(yīng)用

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

Possible Domain Algorithm；Simple Probability Algorithm；Probability Matrix Algorithm