一種改進的應用于多模式串匹配的KR算法

董志鑫, 李馨梅

(1 哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001; 2 對外經濟貿易大學 保險學院， 北京 100029)

引言

KR算法[1]是一種直觀的基于某個散列函數的模式匹配算法，KR算法首先對模式串和文本中相同長度的子串按哈希函數[2]求值，如果哈希值相同，則逐一比較模式串和子串。一個良好的哈希函數，不同子串的哈希值相同的概率很小，且匹配速度快。KR算法理論上最壞情況下的時間復雜度是O(m×n)，但實際應用中平均時間復雜度是O(m+n)[3]。KR算法屬于暴力算法[4]的改進型。KR算法設計的最初思想是考慮到每一次模式串在與目標串進行匹配時需要比較每一個字符，效率很低。而KR算法在每次比較時，使用哈希函數，分別計算出模式串以及目標文本段的hash映射，通過比較映射哈希值是否相等來確定字符串。但是因為存在hash沖突的可能性，所以在哈希值相同時還需進一步比較字符串是否相同。在每次比較時需計算哈希值，所以選擇合適的哈希算法將尤為重要。

1 常見的哈希函數分析

哈希函數具有很多的用途，其中心思想是把一個大對象映射到另一個比較小的對象，可節省空間，以便于數據保存；或者進行轉換，來加密原來的對象；或者在對字符串等數據研究處理后，便于查找、比較等功能實現。本文主要利用哈希函數應用于字符串，來進行字符串的比較[5]。

1.1 哈希函數分類

研究可知，哈希函數可以分為4類，現給出闡釋解析如下。

(1)加法哈希函數[6]。就是把字符串中所有元素均加起來，這種方法不用考慮字符串中每個字符的順序，比較適合本文算法的要求。一般加法哈希函數的構造如下：

intadditiveHash(stringkey, intprime)

{

inthash,i;

for (hash=key.length(),i= 0;i

hash+=key.charAt(i);

return (hash%prime);

}

其中，prime為一個比較大的素數，保證每個字符串的哈希值不會很大。

(2)位運算哈希函數[6]。就是利用移位或者異或等各種位運算來處理輸入的字符串，此種方法在計算整個字符串的哈希值時，都要對前期運算得到的哈希值進行位運算，這是基于字符串中字符的順序來定制設計了，字符相同但位置順序不同的字符串經過位運算后得到的哈希值不同，不適用于本文中的算法。一般位運算哈希函數的構造如下：

static introtatingHash(stringkey, intprime)

{

inthash,i;

for (hash=key.length(),i= 0;i

hash= (hash<<4)^(hash>>28)^key.charAt(i);

return (hash%prime);

}

(3)乘除法哈希函數[7]。就是對字符串中的字符進行乘除運算，由此得到字符串的哈希值。一般乘法哈希函數的構造如下：

static introtatingHash(stringkey, intprime)

{

inthash,i;

for (hash=key.length(),i= 0;i

hash=hash*33 +key.charAt(i);

return (hash%prime);

}

(4)混合哈希函數[8]。就是綜合利用上述方式進行哈希運算，得到字符串的哈希值。

1.2 KR算法解析

KR算法一般所使用的哈希函數算法為加法和乘法混合使用的算法，可以表示為：

Hash(x[0,1,2,…,m-1])=(x[0]*2^(m-1)+x[1]*2^(m-2)+…+x[m-1]*2^0)

對于模式串其哈希值是不變的，而目標串每移動一個字符需重新計算，即：

Hash(x[i+1,i+2,…，i+m])=(Hash(x[i,i+1,…，i+m-1]) -x[i] * 2^(m-1)) *2+x[i+m]

很明顯，該算法考慮了字符串中每個字符的順序，字符相同、順序不同的哈希值則不同，這與本文對KR算法改進的思想不同，本文需要尋找一個不考慮字符順序的哈希函數設計方法。

1.3 本文設計的哈希函數算法

綜合分析了上述多種哈希算法，針對本文需求設計提出了如下的哈希函數算法。本算法的根本思想是利用加法哈希函數，首先設計一個等比數列，公比和首項的選取根據模式串的規模和其中包含的不同字符數目來決定，模式串集合中每個字符對應等比數列中的一項，在計算整個模式串的哈希值時，直接將對應字符的哈希值相加得出的結果作為整個模式串的哈希值。設等比數列為arr[n]，則：

選取等比數列中的值作為模式串中每個字符的哈希值，是因為在相同項數的情況下，等比數列的各項相加和不可能相等。本文借助計算機用暴力枚舉的方法進行逐一列舉，并未發現哈希值相同的情況。

2 DKR算法

本文提出一種基于上述哈希算法的DKR算法，并運用到多模式串匹配上。研究中，該算法能夠準確地匹配到模式串，對比實驗顯示了該算法的有效性。

2.1 模式串的預處理

2.1.1 預處理中的值設定

首先對于模式串中出現的字符，選取包含整個模式串集所有字符的最大集合M，必須能涵蓋所有模式串中出現的所有字符，通常可選取ASCII碼集，記為集合H。對于互聯網上網址型數據，URL只能使用英文字母、阿拉伯數字和某些標點符號，不能使用其他文字和符號。這是因為網絡標準RFC 1738[9]做出了硬性規定：只有字母和數字[0-9a-zA-Z]、一些特殊符號“$ - _ . + ! * ’ ( ) ,”[不包括雙引號]、以及某些保留字，才可以不經過編碼直接用于URL。

對集合H中的每個字符賦值，該值直接關系到哈希函數的好壞，本文選取字符對應的ASCII碼值減去某固定值b，得到的值取另一個定值x(x>1)的次冪。減去固定值b是因為ASCII碼表所對應的某些字符一般不出現在模式串集合中，使得模式串字符集M中字符對應的哈希值都比較小，避免出現較大數的情況。針對不同的模式串集合，值b可以變化。本文在處理數據時，采用了ASCII碼集作為模式串的字符集合，因為ASCII碼表中，用十進制數表示字符，則0～31及127(共33個)是控制字符或通信專用字符，這些不出現在模式串中，而且32代表的空格，也不會出現在模式串中，所以在ASCII碼表中，模式串中代表數字最小的字符為嘆號(!)，其所代表的數字為33，因此在本文的實驗測試中，固定值b取33。

對于x的取值，不僅關系到每個字符對應哈希值大小，而且還涉及到運算是否簡便。x取2時進行冪運算的花費時間較少，但是會造成部分字符對應的哈希值太大。此時應該調取mod(k)函數，k為一個較大的素數，保證在字符集M中的每個字符都可得到一個合理且不相同的哈希值，并盡量保證不同字符的哈希值相加結果不同。

這里，基于上一節中設計的哈希函數，研究將選取等比數列，計算出字符集M中的字符個數m，確定等比數列公比q，生成首項為1，公比為q的等比數列，并選取前m項，由此構成的集合S作為模式串字符集M對應的哈希值集合。根據上述分析可知，集合S中任意相同數量的項相加和均不相同，所以對于每個字符所對應等比數列中具體哪一項，不用考慮順序。而且，還可依據目標文本發生動態改變。對于目標文本中出現次數較多的字符可以選用等比數列中位置排前的項，對應的哈希值較小，有利于計算機的求值，可進一步減少運算時間；對于出現較少的字符選用等比數列中相對偏后的項，字符對應的哈希值較大。

2.1.2 求得基準長度PLBase

研究中，求出模式串集合P中最短和最長模式串的長度，分別記為PLmin和PLmax；若PLmax-PLmin<10(該值表示最短模式串長度和最長模式串長度相差不大)，對模式串集合P中的模式串長度大于PLmin的取前PLmin個字符，若前PLmin個字符與之前某個模式串的前PLmin個字符相同或者字符對應的哈希值不計順序相加結果值相同，則從該模式串的第二個字符開始選取PLmin個字符；若仍與之前某個模式串的前PLmin個字符相同或者字符哈希值之和相同，則從該模式串的第三個字符開始選取PLmin個字符，依此類推，直到選取出模式串PLmin長度的代表段所對應的哈希值均不相同。

對于最短模式串長度和最長模式串長度相差比較大的情況，研究采取另一種方法，對其展開論述如下。

對每個模式串的長度進行統計，選取出現頻率最高的模式串長度記為PLbase。把小于PLbase長度的模式串與大于等于PLbase長度的模式串分類，各自存儲起來，而且并行地開啟模式串匹配識別流程。對于小于PLbase長度的字符串，按照上述方法，選取這些模式串中的最短長度，記為PLmin，繼續按照上述方法進行處理，得到每個模式串的哈希值。對于不小于PLbase長度的模式串，以PLbase為基準，選取前PLbase個字符，若前PLbase個字符與之前某個模式串的前PLbase個字符相同或者字符所對應的哈希值不計順序相加結果值相同，則從該模式串的第二個字符開始選取PLbase個字符；若仍與之前某個模式串的前PLbase個字符相同或者字符哈希值之和相同，則從該模式串的第三個字符開始選取PLbase個字符，依此類推，直到選取出模式串PLbase長度的代表段所對應的哈希值均不相同，此時選出的PLbase個字符串段代表原模式串段。在匹配時，首先匹配代表段，若代表段相同，再匹配代表段所對應的原模式串，兩次匹配成功才能完成匹配。

不失規范性，將上述2種方法中的PLmin和PLbase統稱為PLbase。方法不變，則將利于后續文章的書寫。同時為了方便上述的處理，對模式串進行存儲時，增加存儲模式串的長度，并在新增、修改模式串時，一并新增或更改模式串長度的數值，這樣在預處理時就可對模式串的長度做出整合統計，選取出現次數最多的模式串長度，以及最長、最短的長度，不僅實效便捷，而且不會增加太多存儲空間。

2.1.3 哈希值的研究設定

經過上述處理后，按照集合M中字符對應的哈希數值，對每個模式串中包含的字符對應數值不計順序相加，得到每個模式串對應的哈希值，盡可能地實現每個模式串對應的哈希值唯一。若不唯一，可采取3種方法進行處理使哈希值唯一，執行方法具體如下：

(1)對字符集合M重復賦值，在上述賦值的基礎上每個值再乘以(或除以)一個相同的素數，或者對每一個值都乘以一個不同的素數。

(2)調整變換字符集M所對應的等比數列集合S，進行更改，更改等比數列的公比q，在(1,2)之間進行取值。

(3)對具有相同哈希值的模式串，若這些模式串的長度大于基準長度PLbase，按照上述選取方法，繼續后移一位選取PLbase長度的標志字符段，直到各個模式串的哈希值不同。

若經過前述3種方法仍然無法避免每個模式串的哈希值不同，那就先按相同來檢控處理，當與目標文本匹配成功時，再多比較一步，看具體與哪個模式串相同，但此種情況的概率較低，在本文實驗中還并未出現。

最終，模式串集合P有一個對應的哈希值表PH。然后求出每個模式串前半段和后半段對應的哈希值hash_half_before和hash_half_after，仍然保存在表PH中。當模式串長度為奇數時，即PLbase是奇數時，在選擇半段(前后半段的統稱)長度時，取PLbase/2整數部分加1；當PLbase為偶數時，直接取PLbase/2。這種做法就使得與目標串段匹配時，只考慮包含大于等于模式串50%的部分，保證算法的有效性。

接下來，將繼續求出包含該模式串前半段或者后半段的具有PLbase長度的最小哈希值MinH，即選取包含前半段的最小值和包含后半段的最小值中的最小的那個記為MinH。設該半段的長度為L_half，對于PLbase-L_half部分用字符集H中具有最小哈希值的字符來補充，這樣補全的長度為PLbase的字符串的哈希值即為MinH，該哈希值一定是包含該半段模式串的任何字符串中具有的最小哈希值，因為如果別的字符串包含該半段，則其余部分肯定具有大于最小哈希值的字符，那最終的哈希值肯定不是最小哈希值MinH。這樣保證在匹配時，只要該目標段的哈希值比最小哈希值MinH小，則該目標段就必然不能與該模式串匹配，將該模式串記為無效，在對該目標段進行的后續匹配中，無需比較無效的模式串。而后將hash_half_before，hash_half_after，MinH三個值均保存在表PH中。如果用結構體表示模式串的每個屬性，則該結構體如下：

struct _pattern_data

{

unsigned chardata[MAX_PATTERN_LEN];

//模式串

unsigned chardata[MAX_PATTERN_LEN];

//模式串代表段

intlen; //模式串長度

doublehash; //模式串哈希值

doublehash_half_min;

//包含模式串半段的最小哈希值

doublehash_half_befor;

//模式串前半段的哈希值

doublehash_half_after;

//模式串的后半段的哈希值

intflag_is_useful;

//模式串在當前匹配時，是否有效

} pattern_data ;

首先利用上述算法計算出每個模式串的哈希值，再利用上述數據結構來存儲每個模式串的信息，對模式串施以統一的預處理后，將相關信息進行存儲，以備后續使用。

2.2 目標串的處理與匹配

引理1對于長度為m的字符串Str，將其分成2個字符串Str1和Str2，則Str1或者Str2至少有一個其中包含不少于50%的Str中的字符個數。該引理可用反證法證明。

證明假設Str1和Str2沒有一個包含不少于50%的Str的字符個數。

設Str1包含a%的字符個數，Str2包含b%的字符個數(a% < 50%，b% < 50%)。

則a%+b% < 100%，這與字符串Str分成兩個字符串Str1和Str2矛盾。

所以，該理論為真。

根據引理1可知，任何一個模式串只要被包含在目標串中，目標串的PLbase劃分中一定有一個分段包含該模式串至少50%的字符，運用該引理，對目標串T進行PLbase劃分，對于每個劃分設立一個變量p，表示該劃分包含模式串的概率。然后根據2.1節中字符集M中字符對應的哈希數值表，對每個劃分求取哈希值B。將哈希值B與模式串的哈希值A進行比較，分析處理過程如下：

(1)若與某個值A相等，則將該劃分的概率p設為100%，并將該劃分與哈希值為A的模式串進行比較，若2個字符串相等，則進一步驗視該模式串是否為模式串的代表段。若是代表段，則還要續接與原模式串的設計匹配，因為原模式串長度肯定比劃分的長度(PLbase)大，此時應在該劃分后面繼續比較，一直比較到某個字符與原模式串不同，或者匹配到原模式串長度后，則表示匹配成功，繼續下一劃分的匹配。

(2)否則，與表PH中的最小哈希值hash_half_min進行比較，若小于該表中的某個模式串的最小哈希值，則將該劃分在當前匹配中的有效性flag_is_useful置為無效，表示該劃分不包含該模式串不小于50%部分，后續無需對該劃分處理時考慮該模式串。

(3)對該劃分從第一個字符開始計算前PLbase/2個字符的哈希值，將此哈希值與模式串前后半段的哈希值(hash_half_befor和hash_half_after)進行比較，若與某個模式串前半段的哈希值相等，則將該劃分的PLbase/2個字符與這些字符后的PLbase/2個字符進行相連，然后與該模式串進行比較，若相等則匹配成功，否則匹配失敗，從下一字符開始繼續計算PLbase/2個字符的哈希值，繼續按照上述方法進行比較，直至該劃分的第PLbase/2個字符時比較終止，停止該劃分比較，繼續下一劃分的匹配。舉例說明如下。

假設目標串T為12345abcdefghij67890，劃分段Tk為abcdefghij，詳細過程可闡釋為：

(1)首先計算Tk的哈希值Hash(Tk)，與每個模式串的哈希值比較，若與模式串Px相同，則分析Px是否為原模式串。若為原模式串，則判斷Tk與Px是否相同，得出匹配結果；若Px不是原模式串，則將原模式串與目標串劃分段及其后續字符(67890部分)進行比較，比較時保證2個字符串長度相同。

(2)若Tk的哈希值Hash(Tk)小于模式串Py的最小哈希值，則將該模式串的有效位置為無效。

(3)選取Tk的前PLbase/2個字符abcde，計算這5個字符的哈希值H_temp，將H_temp與每個模式串前后半段的哈希值(hash_half_befor和hash_half_after)進行比較，若與某個模式串Pz的前半段相等，則將字符a的前面的PLbase/2個字符12345，與字符abcde相連，構成字符串12345abcde，與模式串Pz進行比較，若相同，匹配成功，繼續下一劃分匹配；若與某個模式串Pz的后半段相等，則將最后一個字符e后續的PLbase/2個字符fghij，與字符abcde相連，構成字符串abcdefghij，與模式串Pz進行比較，若相同，匹配成功，繼續下一劃分匹配。否則，繼續從第二個字符b開始，選取PLbase/2個字符bcdef這5個字符，計算相應的哈希值，進行同樣的比較，一直到目標串結束。

因為根據引理1，若目標串存在模式串，必然有一個劃分包含大于等于50%的模式串，因此只需考慮每次單元劃分的50%，在這個劃分的50%里沒有查到，就不可能存在該劃分中，因而將繼續在下一個劃分中查找，則無需查找該劃分中全部的字符。

按照上述方法從目標串第一劃分開始處理，一直到最后一個劃分，若最后一個劃分小于PLbase長度，則直接可以不用比較。原因在于此時模式串的長度都大于該劃分，故而不再存在匹配的情況。

2.3 算法分析

本文提出的針對多模式串的匹配算法，與AC自動機算法[10]相比，首先在空間復雜度上就具有顯著優勢。本算法的空間復雜度為O(n)，而AC自動機算法的空間復雜度則為指數級的。并且無論將如何優化，AC自動機算法都很難達到本算法的空間復雜度。

在時間復雜度方面，本算法也具有突出優勢，主要探討解析如下。

2.3.1 預處理上的時間復雜度分析

本文研究中主要是對模式串進行預處理，設模式串個數為m，模式串的平均長度為基準長度，即PLbase。過程中涉及指定的操作主要有統計模式串中所有出現的字符，構成字符集M，時間復雜度為O(m*PLbase)；統計每個模式串的長度，時間復雜度為O(m)；選取出現最多的長度PLbase，時間復雜度為O(m)；計算每個模式串的哈希值、模式串前后半段的哈希值、模式串對應的最小哈希值，這3項操作的時間復雜度均為O(m*PLbase)，所以預處理最終的時間復雜度為O(m*PLbase)。

2.3.2 匹配過程的時間復雜度分析

對于每一個文本段，本算法在實際的運用中都會有多個模式串無需送入驗證比較。因為在對每一段目標串進行處理時，首先計算該目標串段的哈希值，如果該目標串段的哈希值比某個模式串所對應的最小哈希值還小，則該模式串對于本目標段不會匹配成功，屬于無效模式串，在處理本目標串段時可以忽略該模式串。

假設每次無需比較的模式串為h個，目標串長度為n，模式串的基準長度為p，則完成一次匹配，可優化減少的匹配次數為hn/p次。相對于每個字符均需比較的情況，本算法可以減少的比較次數占總比較次數比值為h/p。在實際的測試中該比值并不小，在本次研究測試中，該比值平均為24.49%。

在比較的過程中，每次以模式串基準長度PLbase為標準長度，即目標文本段的長度，對各段每次需要比較PLbase次，獲得目標文本段加上前后目標文本段的后半段和后個目標文本段的前半段之后的總文本段，對其計算哈希值，也就是計算PLbase個長度為PLbase的目標文本段的哈希值，經過與上述第一步后仍然有效的模式串哈希值進行比較，比較結束后每次跳躍PLbase個長度。相較于AC自動機算法，本算法每次跳躍的距離很大，因為在處理目標串時的方法原理不同，不能只是簡單地比較跳躍距離，還應計算一個長度為n的目標串，2個算法將調用展開的比較次數。設模式串個數為m個，模式串平均長度為L，目標串長度為n，研究可得分析過程如下。

2.3.2.1 最壞情況下比較

AC自動機算法的最壞情況下比較次數C為：

C=m*n*L

(1)

DKR算法的最壞情況下比較次數C為：

C=m*n/L

(2)

如果再加上求取哈希值所使用的加法運算，把加法運算與比較運算都算作一次運算的情況下(因為在匯編語言指令下都是一個操作，而且實質上比較大小是做減法)，DKR算法的最壞情況下比較次數C為：

C= (L*L/4+2m) *n/ 2L

(3)

基于前文探討結果，對其給出說明如下。在加法運算與比較運算都算作一次運算的前提下，此時將PLbase基準模式串長度看作模式串平均長度L，則目標串總共可分為n/L段，對于每一目標段只需計算該段的前半段哈希值。因為根據引理1的結論，模式串若存在目標段中，對于任意目標段肯定有一段是包含不少于一半模式串，研究只考慮半段即可。對于每一段目標串，都要計算L/2個字符相加得到哈希值，對于該半段中以每個字符開頭的PLbase/2長度的段，都要計算哈希值，統共要計算L/2次。所以，加法運算的運算次數為L*L/ 4。計算出哈希值后，需要與模式串的前后半段的哈希值設定比較，對于m個模式串每段就需要比較2*m次。

從上述3個公式可以發現，在不考慮加法運算的情況下，只要L>1，公式(1)中比較次數C就大于公式(2)中的比較次數。考慮加法運算后，只需要在L*L> 8*m/ (8*m-1)時，公式(3)中的比較次數C就小于公式(1)的比較次數，即DKR算法的比較次數小于AC自動機算法的比較次數。因為在運行實踐中，無論m多大，L*L都會遠大于8*m/ (8*m-1)。所以，在最壞情況下，DKR算法的比較次數明顯小于AC自動機算法，即DKR算法的時間復雜度明顯優勝于AC自動機算法。

2.3.2.2 一般情況下比較

AC自動機算法在匹配過程中存在可跳躍的情形，從而達到減少比較次數的目的。跳躍的情況，則根據不同的模式串有不同的情況。在最優的情況下，時間復雜度可以達到O((m+n)L)。

DKR算法在匹配過程中對每段不同的目標文本段，都包含不用比較的模式串個數，而當目標串與文本串差別較大時，算法效率則將提升。理想情況，每次只剩下一個模式串，即命中模式串，無需與別的模式串比較。至于匹配成功的目標串的前半段比較就相等，即2*m= 1，此時算法效率極高，時間復雜度為O((L/8+1 /8*L)*n)，約為O(n*L/8)。

存在直接找到的情況也并不少見，即目標串劃分的哈希值與模式串哈希值相同，但卻非一定是匹配成功，需要再次驗證一次即可，而且可能存在順序不同，因為本哈希函數不考慮順序問題。最高出現次數的模式串長度PLbase，所以不論什么樣的文本都有很高的幾率，即使只有1%的機會直接命中，對于分類型數據的效率提升也相當高。

本算法自動包含壞字符規則，對于并未在字符集中出現的字符，則沒有相關的哈希值與該字符對應，可直接跳過，將匹配串直接移動到該字符下一字符進行匹配。

在實際應用中，比如一些網絡監測系統，模式串是有一定的規則和格式的，那么子串重復的可能性就會減少。因此，使用哈希函數h(X) 計算字符串的值，通過比較函數值來代替逐一的字符串比較可以減去至少(l-lm) 的無用子串比較。

本算法在預處理上，主要存儲模式串的4個哈希值表，其空間復雜度為O(m)。而AC算法，因為存在Trie樹的存儲和失敗指針的存儲導致可觀空間消耗，不管采用怎樣的存儲優化，其空間消耗也都是指數級的，由此帶來的空間復雜度均為指數級。因此算法在空間復雜度上的優勢相當明顯，在模式串數量較多的情況下，本算法將呈現巨大優勢。

3 實 驗

為了對上述算法提供合理全面的性能驗證，本節將DKR算法和AC算法在同樣的實驗環境下，對同樣的模式串和目標串進行驗證，驗證的主要標準是比較各自的時間效率和空間占用情況，然后通過對結果的分析得出最終結論。

3.1 實驗環境

操作系統：Ubuntu 16.04(64位)；

處理器：Intel(R)Core(TM) i7-2670QM CPU @ 2.20 GHz ；

處理器核心數：4核；

編譯器：gcc version 5.4.0；

編程語言：c語言。

3.2 實驗結果

因本文主要研究算法的高效性，而且是在線匹配的高效，所以只對2種算法的匹配時間效率進行分析，暫不考慮算法的空間效率(占用內存大小)和算法的預處理時間。

實驗選用的數據中，測試目標文本大小為100 M；模式串集個數分別為1 000，5 000，10 000，模式串長度則為5～1 000內，任意長度。

算法運行預處理時間可見表1。

表1 不同模式串個數對應算法預處理時間Tab. 1 Preprocessing time of string matching in different patterns

算法運行匹配時間可見表2。

表2 不同模式串個數對應算法匹配時間Tab. 2 Matching time of string matching in different patterns

算法采用的是Linux中/usr/bin/time命令，內存的占用選取的是最大駐留集的大小來表示程序運行中內存占用的最大量。

算法運行內存最大占用量可見表3。

表3不同模式串個數對應算法內存最大占用量

Tab.3Maximummemoryusageofstringmatchingindifferentpatterns

模式個數/個DKR算法/KBAC算法/KB1000102376138892500011059229078810000120876478124

3.3 實驗分析

通過對以上結果的分析，本文所提出的DKR算法在多模式串匹配的預處理和內存占用上具有顯著鮮明優勢。而且隨著模式串個數的增多，本算法實際展現出來的優勢就越發明顯。但是本算法在匹配時間上效率并不如AC算法，這在此后的實驗中，將進一步展開研究優化，以達到更好的效果。

4 結束語

本文首先論述了KR算法，分析了常見的哈希函數，根據DKR算法的思想提出了相應的哈希函數算法，同時詳細研究了該算法對模式串的預處理過程以及算法的匹配過程，并將該算法與AC算法在時間復雜度和空間復雜度兩個方面進行了闡釋分析。實驗結果顯示，該算法在多模式串匹配的預處理和內存占用上具有相當大的優勢，證明了算法的有效性。

[1] KARP R M, RABIN M O. Efficient randomized pattern-matching algorithms[J]. IBM Journal of Research and Development—Mathematics and computing,1987,31(2):249-260.

[2] “科普中國”百科科學詞條編寫與應用工作項目. 哈希函數[EB/OL].[2017-06].http://baike.baidu.com/link?url=_mdPrKjxu9EOMuUgQ18D55OO9Mti5FJ1pE7Ov_3gO9Ccs7fGarPGN_VVWCOboUm33y1AX6lksC6iLsl8VezzbDXxLgPIN17luuKQ-IPc B1tkHjvqFVyIkLu_vQGBIv0T.

[3] KNUTH D E，MORRIS J H，PRATT V R.Fast pattern matching in strings[J]. SIAM J Computing，1977，6(2)：323-350.

[4] 毛先森. 字符串匹配—暴力匹配算法[EB/OL]. [2016-08-12]. http://www.cnblogs.com/Kevin-mao/p/5764726.html.

[5] 葉軍偉. 哈希函數構造方法及其適用情況[J]. 科技致富向導,2014(8) :278.

[6] HORSPOOL R N. Practical fast searching in strings [J]. Software Practice and Experience,1980,10(6):501-506.

[7] WU Sun, MANBER U. A fast algorithm for multi-pattern searching[R]. Tucson:University of Arizona, 1994.

[8] Chinaunix.幾種常用hash算法及原理[EB/OL].[2016-08-09]. http://blog.chinaunix.net/uid-30592332-id-5749402.html.

[9] Network Working Group. RFC 1738 - Uniform Resource Locators[EB/OL].[1994-11]. https://tools.ietf.org/html/rfc1738.html.

[10]AHO A V, CORASICK M J. Efficient string matching: An aid to bibliographic search[J]. Communications of the ACM, 1975, 18(6):333-340.