非數值問題的并行算法的研究及軟件的實現

林 輝苗永梅

（1.渭南師范學院信息與教育技術中心 陜西 渭南 714000；2.寶雞職業技術學院 陜西 寶雞 721013）

1 串匹配問題提出

Kmp算法雖然能找到匹配位置，但是時間復雜度高，在某些領域還不能用，能否找到一種時間復雜度為對數數量級的匹配函數。

2 問題分析

我們在這里采用數據結構中散列函數的方法，它可提供較低的時間復雜度，把一個長的串映射到較小的范圍，保證不同的串映射到相同的位置概率很小。所得到的指紋函數可在O（1）時間復雜度內進行比較。

3 問題解決

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

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

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

性質（3） 對于每個p∈S和B中的所有串，應能很容易計算fp（x）。

上述三個性質對于模式匹配問題的內涵應是清楚的：性質1隱含著fp（x）可在時間O（1）內比較，性質2是說如果兩個串X和Y指紋相等，則X=Y的概率很高；性質3的解釋與利用集合A的并行算法實現有關。

因為確定的串匹配的時間復雜度為O（logn）時間和O（n）次操作，所以希望計算中諸串的指紋函數亦具有相同的時間復雜度。

3.1 一類指紋函數

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

引理（1） 函數f是一到一的，使得對于任意串x，f（X）的行列式為1。如果X的長度為m，則f（x）的每一項都是一個不大于Fm+1的整數，其中Fm+1是m+1個Fibonnacci數，F1=F1= 1,Fm+1=Fm+1+Fm+1。

3.2 失配概率

令X和Y是兩個長度各為m的串，且令fp∈A。當X≠Y但fp（X）=fp（Y）時就出現失配。注意此性質與特定的指紋函數fp有關。

定理 令fp是從集合A={fp}中隨機選定的函數，其中p是區間[1,2…,M]中的某一素數，那么任意兩個長度為m的不同串失配概率≦∏（2.776）/∏（m），如果m≧11。

引理（2） 如果素數的區間為（1,2…,mk）對于與給定的常數k＞1，則兩個長度為m的串的失配概率≦3.48k/mk-1。

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

這樣，函數同時滿足前述性質。在此基礎上給出了分布式存儲處體系結構上隨機串匹配的并行算法。

隨機串匹配算法

算法1.1

隨機串匹配算法

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

輸出:數組match,其分量指明P在T中出現的匹配位置

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