林 輝苗永梅

（1.渭南師范學(xué)院信息與教育技術(shù)中心 陜西 渭南 714000；2.寶雞職業(yè)技術(shù)學(xué)院 陜西 寶雞 721013）

1 串匹配問(wèn)題提出

Kmp算法雖然能找到匹配位置，但是時(shí)間復(fù)雜度高，在某些領(lǐng)域還不能用，能否找到一種時(shí)間復(fù)雜度為對(duì)數(shù)數(shù)量級(jí)的匹配函數(shù)。

2 問(wèn)題分析

我們?cè)谶@里采用數(shù)據(jù)結(jié)構(gòu)中散列函數(shù)的方法，它可提供較低的時(shí)間復(fù)雜度，把一個(gè)長(zhǎng)的串映射到較小的范圍，保證不同的串映射到相同的位置概率很小。所得到的指紋函數(shù)可在O（1）時(shí)間復(fù)雜度內(nèi)進(jìn)行比較。

3 問(wèn)題解決

指紋函數(shù)：我們求串的匹配的基本策略是將串映射到某些小的整數(shù)上。令T是長(zhǎng)度為n的正文串，P是長(zhǎng)度為m的模式串，匹配的結(jié)果是識(shí)別P在T中出現(xiàn)的所有位置?？紤]長(zhǎng)度為m的T所有子串的集合B。這樣的起始在位i的子串共n-m+1個(gè)。于是我們的問(wèn)題可重新闡述為去識(shí)別與P相同的B中元素的位置。令A(yù)={fp}p∈s是函數(shù)集，使得fp將長(zhǎng)度為的串映射到域D.A要滿足下屬三個(gè)性質(zhì)：

性質(zhì)（1） 對(duì)于任意串x∈B和每個(gè)p∈S，fp（x）由O（log m）位組成。

性質(zhì)（2） 隨機(jī)選擇fp∈A，它將兩個(gè)不等的串X和Y映射到到同一位置的機(jī)率非常小。

性質(zhì)（3） 對(duì)于每個(gè)p∈S和B中的所有串，應(yīng)能很容易計(jì)算fp（x）。

上述三個(gè)性質(zhì)對(duì)于模式匹配問(wèn)題的內(nèi)涵應(yīng)是清楚的：性質(zhì)1隱含著fp（x）可在時(shí)間O（1）內(nèi)比較，性質(zhì)2是說(shuō)如果兩個(gè)串X和Y指紋相等，則X=Y的概率很高；性質(zhì)3的解釋與利用集合A的并行算法實(shí)現(xiàn)有關(guān)。

因?yàn)榇_定的串匹配的時(shí)間復(fù)雜度為O（logn）時(shí)間和O（n）次操作，所以希望計(jì)算中諸串的指紋函數(shù)亦具有相同的時(shí)間復(fù)雜度。

3.1 一類(lèi)指紋函數(shù)

試考慮下列函數(shù)：它將取值{0，1}上的串集合映射到取值整數(shù)環(huán)z上的2×2矩陣。此函數(shù)滿足性質(zhì)2，但不滿足性質(zhì)1，3。稍后修改它，使其滿足所有性質(zhì)。對(duì)于任意兩個(gè)串行x和y定義為環(huán)z上矩陣集合的乘積。

引理（1） 函數(shù)f是一到一的，使得對(duì)于任意串x，f（X）的行列式為1。如果X的長(zhǎng)度為m，則f（x）的每一項(xiàng)都是一個(gè)不大于Fm+1的整數(shù)，其中Fm+1是m+1個(gè)Fibonnacci數(shù)，F(xiàn)1=F1= 1,Fm+1=Fm+1+Fm+1。

3.2 失配概率

令X和Y是兩個(gè)長(zhǎng)度各為m的串，且令fp∈A。當(dāng)X≠Y但fp（X）=fp（Y）時(shí)就出現(xiàn)失配。注意此性質(zhì)與特定的指紋函數(shù)fp有關(guān)。

定理 令fp是從集合A={fp}中隨機(jī)選定的函數(shù)，其中p是區(qū)間[1,2…,M]中的某一素?cái)?shù)，那么任意兩個(gè)長(zhǎng)度為m的不同串失配概率≦∏（2.776）/∏（m），如果m≧11。

引理（2） 如果素?cái)?shù)的區(qū)間為（1,2…,mk）對(duì)于與給定的常數(shù)k＞1，則兩個(gè)長(zhǎng)度為m的串的失配概率≦3.48k/mk-1。

區(qū)間 [1,2…,M]中的一個(gè)素?cái)?shù)p，對(duì)于固定的k要求O（logm+logt）位。對(duì)于t這樣的串，指向它們特定位置的指針亦要求同數(shù)量級(jí)的位數(shù)，因此，能夠假定兩個(gè)的串的指紋可在O（1）時(shí)間內(nèi)比較之。顯然，此值與比較兩串需要O（m）次操作是大不一樣的。

這樣，函數(shù)同時(shí)滿足前述性質(zhì)。在此基礎(chǔ)上給出了分布式存儲(chǔ)處體系結(jié)構(gòu)上隨機(jī)串匹配的并行算法。

隨機(jī)串匹配算法

算法1.1

隨機(jī)串匹配算法

輸入:數(shù)組T（1,n）P（1,m）和整數(shù)M

輸出:數(shù)組match,其分量指明P在T中出現(xiàn)的匹配位置

顯然，在該算法中步驟（1）（4）的時(shí)間復(fù)雜度為O（n-m），步驟（2）（3）中求模式串和文本串各個(gè)子串指紋的時(shí)間復(fù)雜度分別為O（m），O（n-m）。