單模式匹配加密算法
admin 在很多應(yīng)用領(lǐng)域中，比如在DNA序列中尋找特殊的模式，都要用到模式匹配，所以模式匹配是一門重要的學(xué)科。由于模式匹配問題的求解效率的重要性，對模式匹配加密算法的研究很早就受到重視，模式匹配分為單模式匹配和多模式匹配，那么我們今天就先來介紹幾款常用單模式匹配加密算法。
常用單模式匹配加密算法
1、BF加密算法
BF加密算法是最簡單的算法，是從左到右進行匹配的。
（1）BF加密算法的思想
首先將T1與P1，進行比較，若不同，就將T2與P1進行比較，……，直到T的某一個字符Ti和P1相同，再將它們之后的字符進行比較，若也相同，則如此繼續(xù)往下比較，當(dāng)T的某一個字符Ti與P的字符Pj不同時，則T返回到本趟開始字符的下一個字符，即Ti-j+2，P返回到P1，繼續(xù)開始下一趟的比較，重復(fù)上述過程。若P中的字符全部比較完，則說明本趟匹配成功，本趟的起始位置是i-j=1或i-t[0]，否則，匹配失敗。
BF加密算法是較簡單、直觀的加密算法，但它可能產(chǎn)生不必要的回溯，所以減慢了模式匹配的速度，效率很低，時間復(fù)雜度為T（n）=O（m*n)。
2、KMP加密算法
由于BF加密算法的缺點。KMP加密算法產(chǎn)生了。KMP加密算法是由BF改進后不產(chǎn)生回溯的一種算法。
（1）KMP加密算法的思想
每當(dāng)匹配過程中出現(xiàn)字符串比較不等時，不需回溯i指針，而是利用已經(jīng)得到的”部分匹配”結(jié)果將模式向右”滑動”盡可能遠的一段距離后，繼續(xù)進行比較。
KMP加密算法將模式串向右滑動可以提高匹配算法的效率，但相對比較復(fù)雜，時間復(fù)雜度為T（n）=O（m+n)，空間復(fù)雜度為S（n）＝O（m）。
3、BM加密算法
受KMP加密算法的啟發(fā)，提出了一種新的字符串快速匹配算法一BM加密算法。BM加密算法在實際的模式匹配中，跳過了很多無用的字符，這種跳躍式的比較方式，使BM加密算法獲得了極高的效率，特別是在大字符集上進行字符串的模式匹配時。在實際的應(yīng)用中，BM加密算法比KMP加密算法更有效率。
BM加密算法從另外一個角度出發(fā)，提出一種比較新穎的方法來求解模式匹配問題。
（1）BM加密算法的思想
從右向左的把模式同文本做比較。開始時仍是P的最左邊與T的最左邊對齊，當(dāng)某趟比較中出現(xiàn)不匹配時，BM加密算法采用兩條啟發(fā)性規(guī)則計算模式串右移的距離，即壞字符啟發(fā)規(guī)則和好后綴啟發(fā)規(guī)則；當(dāng)與最右的模式符號做比較的文本符號在模式中根本就沒有出現(xiàn)，則模式可以在這個文本符號之后移位m個位置。
作如下定義：
串中出現(xiàn)的字符，
字符集：C＝｛C|C在正文中出現(xiàn)}
正文串T：T1T2…一Ti…Tim-j…Tn
模式串P：T1…Tj…T
壞字符規(guī)則：
在BM加密算法從右向左掃描的過程中，若發(fā)現(xiàn)某個字符x不匹配，則按如下兩種情況討論：
1） 如果字符x在模式P中沒有出現(xiàn)，那么從字符x開始的m個文本顯然不可能與P匹配成功，直接全部跳過該區(qū)域即可。
2）如果x在模式P中出現(xiàn)，則以該字符進行對齊。
用數(shù)學(xué)公式表示，設(shè)Skip(x)為P右移的距離，m為模式串P的長度，max(x)為字符x在P中最右位置。
好后綴規(guī)則：
若發(fā)現(xiàn)某個字符不匹配的同時，已有部分字符匹配成功，則按如下兩種情況討論：
1）如果在P中位置t處已匹配部分P'在P中的某位置t'也出現(xiàn)，且位置t'的前一個字符與位置t的前一個字符不相同，則將P右移使t'對應(yīng)t方才的所在的位置。
2）如果在P中任何位置已匹配部分P'都沒有再出現(xiàn)，則找到與P'的后綴P''相同的P的最長前綴x，向右移動P，使x對應(yīng)方才P''后綴所在的位置。
用數(shù)學(xué)公式表示，設(shè)Shift(j)為P右移的距離，m為模式串P的長度，j 為當(dāng)前所匹配的字符位置，s為t'與t的距離（以上情況1）或者x與P''的距離（以上情況2）。
（2）BM加密算法流程圖
在匹配過程中，取dist1和dist2中的最大者，其流程圖如圖所示。
其預(yù)處理階段時間復(fù)雜度為O（m+s），空間復(fù)雜度為O（s）。搜索階段時間復(fù)雜度為O（m*n），最壞情況下要比_較進行3n次比較，最好情況下時間復(fù)雜度為O（n/m）。
隨著網(wǎng)絡(luò)的發(fā)展，模式匹配加密算法的應(yīng)用越來越廣，因而提高模式匹配加密算法的效率也是當(dāng)前研究的熱點。
小知識之模式匹配
