一種改進(jìn)的應(yīng)用于多模式串匹配的KR算法

董志鑫, 李馨梅

(1 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 哈爾濱 150001; 2 對(duì)外經(jīng)濟(jì)貿(mào)易大學(xué) 保險(xiǎn)學(xué)院， 北京 100029)

引言

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

1 常見的哈希函數(shù)分析

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

1.1 哈希函數(shù)分類

研究可知，哈希函數(shù)可以分為4類，現(xiàn)給出闡釋解析如下。

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

intadditiveHash(stringkey, intprime)

{

inthash,i;

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

hash+=key.charAt(i);

return (hash%prime);

}

其中，prime為一個(gè)比較大的素?cái)?shù)，保證每個(gè)字符串的哈希值不會(huì)很大。

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

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)乘除法哈希函數(shù)[7]。就是對(duì)字符串中的字符進(jìn)行乘除運(yùn)算，由此得到字符串的哈希值。一般乘法哈希函數(shù)的構(gòu)造如下：

static introtatingHash(stringkey, intprime)

{

inthash,i;

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

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

return (hash%prime);

}

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

1.2 KR算法解析

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

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

對(duì)于模式串其哈希值是不變的，而目標(biāo)串每移動(dòng)一個(gè)字符需重新計(jì)算，即：

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]

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

1.3 本文設(shè)計(jì)的哈希函數(shù)算法

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

選取等比數(shù)列中的值作為模式串中每個(gè)字符的哈希值，是因?yàn)樵谙嗤?xiàng)數(shù)的情況下，等比數(shù)列的各項(xiàng)相加和不可能相等。本文借助計(jì)算機(jī)用暴力枚舉的方法進(jìn)行逐一列舉，并未發(fā)現(xiàn)哈希值相同的情況。

2 DKR算法

本文提出一種基于上述哈希算法的DKR算法，并運(yùn)用到多模式串匹配上。研究中，該算法能夠準(zhǔn)確地匹配到模式串，對(duì)比實(shí)驗(yàn)顯示了該算法的有效性。

2.1 模式串的預(yù)處理

2.1.1 預(yù)處理中的值設(shè)定

首先對(duì)于模式串中出現(xiàn)的字符，選取包含整個(gè)模式串集所有字符的最大集合M，必須能涵蓋所有模式串中出現(xiàn)的所有字符，通常可選取ASCII碼集，記為集合H。對(duì)于互聯(lián)網(wǎng)上網(wǎng)址型數(shù)據(jù)，URL只能使用英文字母、阿拉伯?dāng)?shù)字和某些標(biāo)點(diǎn)符號(hào)，不能使用其他文字和符號(hào)。這是因?yàn)榫W(wǎng)絡(luò)標(biāo)準(zhǔn)RFC 1738[9]做出了硬性規(guī)定：只有字母和數(shù)字[0-9a-zA-Z]、一些特殊符號(hào)“$ - _ . + ! * ’ ( ) ,”[不包括雙引號(hào)]、以及某些保留字，才可以不經(jīng)過編碼直接用于URL。

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

對(duì)于x的取值，不僅關(guān)系到每個(gè)字符對(duì)應(yīng)哈希值大小，而且還涉及到運(yùn)算是否簡(jiǎn)便。x取2時(shí)進(jìn)行冪運(yùn)算的花費(fèi)時(shí)間較少，但是會(huì)造成部分字符對(duì)應(yīng)的哈希值太大。此時(shí)應(yīng)該調(diào)取mod(k)函數(shù)，k為一個(gè)較大的素?cái)?shù)，保證在字符集M中的每個(gè)字符都可得到一個(gè)合理且不相同的哈希值，并盡量保證不同字符的哈希值相加結(jié)果不同。

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

2.1.2 求得基準(zhǔn)長(zhǎng)度PLBase

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

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

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

不失規(guī)范性，將上述2種方法中的PLmin和PLbase統(tǒng)稱為PLbase。方法不變，則將利于后續(xù)文章的書寫。同時(shí)為了方便上述的處理，對(duì)模式串進(jìn)行存儲(chǔ)時(shí)，增加存儲(chǔ)模式串的長(zhǎng)度，并在新增、修改模式串時(shí)，一并新增或更改模式串長(zhǎng)度的數(shù)值，這樣在預(yù)處理時(shí)就可對(duì)模式串的長(zhǎng)度做出整合統(tǒng)計(jì)，選取出現(xiàn)次數(shù)最多的模式串長(zhǎng)度，以及最長(zhǎng)、最短的長(zhǎng)度，不僅實(shí)效便捷，而且不會(huì)增加太多存儲(chǔ)空間。

2.1.3 哈希值的研究設(shè)定

經(jīng)過上述處理后，按照集合M中字符對(duì)應(yīng)的哈希數(shù)值，對(duì)每個(gè)模式串中包含的字符對(duì)應(yīng)數(shù)值不計(jì)順序相加，得到每個(gè)模式串對(duì)應(yīng)的哈希值，盡可能地實(shí)現(xiàn)每個(gè)模式串對(duì)應(yīng)的哈希值唯一。若不唯一，可采取3種方法進(jìn)行處理使哈希值唯一，執(zhí)行方法具體如下：

(1)對(duì)字符集合M重復(fù)賦值，在上述賦值的基礎(chǔ)上每個(gè)值再乘以(或除以)一個(gè)相同的素?cái)?shù)，或者對(duì)每一個(gè)值都乘以一個(gè)不同的素?cái)?shù)。

(2)調(diào)整變換字符集M所對(duì)應(yīng)的等比數(shù)列集合S，進(jìn)行更改，更改等比數(shù)列的公比q，在(1,2)之間進(jìn)行取值。

(3)對(duì)具有相同哈希值的模式串，若這些模式串的長(zhǎng)度大于基準(zhǔn)長(zhǎng)度PLbase，按照上述選取方法，繼續(xù)后移一位選取PLbase長(zhǎng)度的標(biāo)志字符段，直到各個(gè)模式串的哈希值不同。

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

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

接下來，將繼續(xù)求出包含該模式串前半段或者后半段的具有PLbase長(zhǎng)度的最小哈希值MinH，即選取包含前半段的最小值和包含后半段的最小值中的最小的那個(gè)記為MinH。設(shè)該半段的長(zhǎng)度為L(zhǎng)_half，對(duì)于PLbase-L_half部分用字符集H中具有最小哈希值的字符來補(bǔ)充，這樣補(bǔ)全的長(zhǎng)度為PLbase的字符串的哈希值即為MinH，該哈希值一定是包含該半段模式串的任何字符串中具有的最小哈希值，因?yàn)槿绻麆e的字符串包含該半段，則其余部分肯定具有大于最小哈希值的字符，那最終的哈希值肯定不是最小哈希值MinH。這樣保證在匹配時(shí)，只要該目標(biāo)段的哈希值比最小哈希值MinH小，則該目標(biāo)段就必然不能與該模式串匹配，將該模式串記為無效，在對(duì)該目標(biāo)段進(jìn)行的后續(xù)匹配中，無需比較無效的模式串。而后將hash_half_before，hash_half_after，MinH三個(gè)值均保存在表PH中。如果用結(jié)構(gòu)體表示模式串的每個(gè)屬性，則該結(jié)構(gòu)體如下：

struct _pattern_data

{

unsigned chardata[MAX_PATTERN_LEN];

//模式串

unsigned chardata[MAX_PATTERN_LEN];

//模式串代表段

intlen; //模式串長(zhǎng)度

doublehash; //模式串哈希值

doublehash_half_min;

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

doublehash_half_befor;

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

doublehash_half_after;

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

intflag_is_useful;

//模式串在當(dāng)前匹配時(shí)，是否有效

} pattern_data ;

首先利用上述算法計(jì)算出每個(gè)模式串的哈希值，再利用上述數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)每個(gè)模式串的信息，對(duì)模式串施以統(tǒng)一的預(yù)處理后，將相關(guān)信息進(jìn)行存儲(chǔ)，以備后續(xù)使用。

2.2 目標(biāo)串的處理與匹配

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

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

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

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

所以，該理論為真。

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

(1)若與某個(gè)值A(chǔ)相等，則將該劃分的概率p設(shè)為100%，并將該劃分與哈希值為A的模式串進(jìn)行比較，若2個(gè)字符串相等，則進(jìn)一步驗(yàn)視該模式串是否為模式串的代表段。若是代表段，則還要續(xù)接與原模式串的設(shè)計(jì)匹配，因?yàn)樵Ｊ酱L(zhǎng)度肯定比劃分的長(zhǎng)度(PLbase)大，此時(shí)應(yīng)在該劃分后面繼續(xù)比較，一直比較到某個(gè)字符與原模式串不同，或者匹配到原模式串長(zhǎng)度后，則表示匹配成功，繼續(xù)下一劃分的匹配。

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

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

假設(shè)目標(biāo)串T為12345abcdefghij67890，劃分段Tk為abcdefghij，詳細(xì)過程可闡釋為：

(1)首先計(jì)算Tk的哈希值Hash(Tk)，與每個(gè)模式串的哈希值比較，若與模式串Px相同，則分析Px是否為原模式串。若為原模式串，則判斷Tk與Px是否相同，得出匹配結(jié)果；若Px不是原模式串，則將原模式串與目標(biāo)串劃分段及其后續(xù)字符(67890部分)進(jìn)行比較，比較時(shí)保證2個(gè)字符串長(zhǎng)度相同。

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

(3)選取Tk的前PLbase/2個(gè)字符abcde，計(jì)算這5個(gè)字符的哈希值H_temp，將H_temp與每個(gè)模式串前后半段的哈希值(hash_half_befor和hash_half_after)進(jìn)行比較，若與某個(gè)模式串Pz的前半段相等，則將字符a的前面的PLbase/2個(gè)字符12345，與字符abcde相連，構(gòu)成字符串12345abcde，與模式串Pz進(jìn)行比較，若相同，匹配成功，繼續(xù)下一劃分匹配；若與某個(gè)模式串Pz的后半段相等，則將最后一個(gè)字符e后續(xù)的PLbase/2個(gè)字符fghij，與字符abcde相連，構(gòu)成字符串a(chǎn)bcdefghij，與模式串Pz進(jìn)行比較，若相同，匹配成功，繼續(xù)下一劃分匹配。否則，繼續(xù)從第二個(gè)字符b開始，選取PLbase/2個(gè)字符bcdef這5個(gè)字符，計(jì)算相應(yīng)的哈希值，進(jìn)行同樣的比較，一直到目標(biāo)串結(jié)束。

因?yàn)楦鶕?jù)引理1，若目標(biāo)串存在模式串，必然有一個(gè)劃分包含大于等于50%的模式串，因此只需考慮每次單元?jiǎng)澐值?0%，在這個(gè)劃分的50%里沒有查到，就不可能存在該劃分中，因而將繼續(xù)在下一個(gè)劃分中查找，則無需查找該劃分中全部的字符。

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

2.3 算法分析

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

在時(shí)間復(fù)雜度方面，本算法也具有突出優(yōu)勢(shì)，主要探討解析如下。

2.3.1 預(yù)處理上的時(shí)間復(fù)雜度分析

本文研究中主要是對(duì)模式串進(jìn)行預(yù)處理，設(shè)模式串個(gè)數(shù)為m，模式串的平均長(zhǎng)度為基準(zhǔn)長(zhǎng)度，即PLbase。過程中涉及指定的操作主要有統(tǒng)計(jì)模式串中所有出現(xiàn)的字符，構(gòu)成字符集M，時(shí)間復(fù)雜度為O(m*PLbase)；統(tǒng)計(jì)每個(gè)模式串的長(zhǎng)度，時(shí)間復(fù)雜度為O(m)；選取出現(xiàn)最多的長(zhǎng)度PLbase，時(shí)間復(fù)雜度為O(m)；計(jì)算每個(gè)模式串的哈希值、模式串前后半段的哈希值、模式串對(duì)應(yīng)的最小哈希值，這3項(xiàng)操作的時(shí)間復(fù)雜度均為O(m*PLbase)，所以預(yù)處理最終的時(shí)間復(fù)雜度為O(m*PLbase)。

2.3.2 匹配過程的時(shí)間復(fù)雜度分析

對(duì)于每一個(gè)文本段，本算法在實(shí)際的運(yùn)用中都會(huì)有多個(gè)模式串無需送入驗(yàn)證比較。因?yàn)樵趯?duì)每一段目標(biāo)串進(jìn)行處理時(shí)，首先計(jì)算該目標(biāo)串段的哈希值，如果該目標(biāo)串段的哈希值比某個(gè)模式串所對(duì)應(yīng)的最小哈希值還小，則該模式串對(duì)于本目標(biāo)段不會(huì)匹配成功，屬于無效模式串，在處理本目標(biāo)串段時(shí)可以忽略該模式串。

假設(shè)每次無需比較的模式串為h個(gè)，目標(biāo)串長(zhǎng)度為n，模式串的基準(zhǔn)長(zhǎng)度為p，則完成一次匹配，可優(yōu)化減少的匹配次數(shù)為hn/p次。相對(duì)于每個(gè)字符均需比較的情況，本算法可以減少的比較次數(shù)占總比較次數(shù)比值為h/p。在實(shí)際的測(cè)試中該比值并不小，在本次研究測(cè)試中，該比值平均為24.49%。

在比較的過程中，每次以模式串基準(zhǔn)長(zhǎng)度PLbase為標(biāo)準(zhǔn)長(zhǎng)度，即目標(biāo)文本段的長(zhǎng)度，對(duì)各段每次需要比較PLbase次，獲得目標(biāo)文本段加上前后目標(biāo)文本段的后半段和后個(gè)目標(biāo)文本段的前半段之后的總文本段，對(duì)其計(jì)算哈希值，也就是計(jì)算PLbase個(gè)長(zhǎng)度為PLbase的目標(biāo)文本段的哈希值，經(jīng)過與上述第一步后仍然有效的模式串哈希值進(jìn)行比較，比較結(jié)束后每次跳躍PLbase個(gè)長(zhǎng)度。相較于AC自動(dòng)機(jī)算法，本算法每次跳躍的距離很大，因?yàn)樵谔幚砟繕?biāo)串時(shí)的方法原理不同，不能只是簡(jiǎn)單地比較跳躍距離，還應(yīng)計(jì)算一個(gè)長(zhǎng)度為n的目標(biāo)串，2個(gè)算法將調(diào)用展開的比較次數(shù)。設(shè)模式串個(gè)數(shù)為m個(gè)，模式串平均長(zhǎng)度為L(zhǎng)，目標(biāo)串長(zhǎng)度為n，研究可得分析過程如下。

2.3.2.1 最壞情況下比較

AC自動(dòng)機(jī)算法的最壞情況下比較次數(shù)C為：

C=m*n*L

(1)

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

C=m*n/L

(2)

如果再加上求取哈希值所使用的加法運(yùn)算，把加法運(yùn)算與比較運(yùn)算都算作一次運(yùn)算的情況下(因?yàn)樵趨R編語言指令下都是一個(gè)操作，而且實(shí)質(zhì)上比較大小是做減法)，DKR算法的最壞情況下比較次數(shù)C為：

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

(3)

基于前文探討結(jié)果，對(duì)其給出說明如下。在加法運(yùn)算與比較運(yùn)算都算作一次運(yùn)算的前提下，此時(shí)將PLbase基準(zhǔn)模式串長(zhǎng)度看作模式串平均長(zhǎng)度L，則目標(biāo)串總共可分為n/L段，對(duì)于每一目標(biāo)段只需計(jì)算該段的前半段哈希值。因?yàn)楦鶕?jù)引理1的結(jié)論，模式串若存在目標(biāo)段中，對(duì)于任意目標(biāo)段肯定有一段是包含不少于一半模式串，研究只考慮半段即可。對(duì)于每一段目標(biāo)串，都要計(jì)算L/2個(gè)字符相加得到哈希值，對(duì)于該半段中以每個(gè)字符開頭的PLbase/2長(zhǎng)度的段，都要計(jì)算哈希值，統(tǒng)共要計(jì)算L/2次。所以，加法運(yùn)算的運(yùn)算次數(shù)為L(zhǎng)*L/ 4。計(jì)算出哈希值后，需要與模式串的前后半段的哈希值設(shè)定比較，對(duì)于m個(gè)模式串每段就需要比較2*m次。

從上述3個(gè)公式可以發(fā)現(xiàn)，在不考慮加法運(yùn)算的情況下，只要L>1，公式(1)中比較次數(shù)C就大于公式(2)中的比較次數(shù)。考慮加法運(yùn)算后，只需要在L*L> 8*m/ (8*m-1)時(shí)，公式(3)中的比較次數(shù)C就小于公式(1)的比較次數(shù)，即DKR算法的比較次數(shù)小于AC自動(dòng)機(jī)算法的比較次數(shù)。因?yàn)樵谶\(yùn)行實(shí)踐中，無論m多大，L*L都會(huì)遠(yuǎn)大于8*m/ (8*m-1)。所以，在最壞情況下，DKR算法的比較次數(shù)明顯小于AC自動(dòng)機(jī)算法，即DKR算法的時(shí)間復(fù)雜度明顯優(yōu)勝于AC自動(dòng)機(jī)算法。

2.3.2.2 一般情況下比較

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

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

存在直接找到的情況也并不少見，即目標(biāo)串劃分的哈希值與模式串哈希值相同，但卻非一定是匹配成功，需要再次驗(yàn)證一次即可，而且可能存在順序不同，因?yàn)楸竟：瘮?shù)不考慮順序問題。最高出現(xiàn)次數(shù)的模式串長(zhǎng)度PLbase，所以不論什么樣的文本都有很高的幾率，即使只有1%的機(jī)會(huì)直接命中，對(duì)于分類型數(shù)據(jù)的效率提升也相當(dāng)高。

本算法自動(dòng)包含壞字符規(guī)則，對(duì)于并未在字符集中出現(xiàn)的字符，則沒有相關(guān)的哈希值與該字符對(duì)應(yīng)，可直接跳過，將匹配串直接移動(dòng)到該字符下一字符進(jìn)行匹配。

在實(shí)際應(yīng)用中，比如一些網(wǎng)絡(luò)監(jiān)測(cè)系統(tǒng)，模式串是有一定的規(guī)則和格式的，那么子串重復(fù)的可能性就會(huì)減少。因此，使用哈希函數(shù)h(X) 計(jì)算字符串的值，通過比較函數(shù)值來代替逐一的字符串比較可以減去至少(l-lm) 的無用子串比較。

本算法在預(yù)處理上，主要存儲(chǔ)模式串的4個(gè)哈希值表，其空間復(fù)雜度為O(m)。而AC算法，因?yàn)榇嬖赥rie樹的存儲(chǔ)和失敗指針的存儲(chǔ)導(dǎo)致可觀空間消耗，不管采用怎樣的存儲(chǔ)優(yōu)化，其空間消耗也都是指數(shù)級(jí)的，由此帶來的空間復(fù)雜度均為指數(shù)級(jí)。因此算法在空間復(fù)雜度上的優(yōu)勢(shì)相當(dāng)明顯，在模式串?dāng)?shù)量較多的情況下，本算法將呈現(xiàn)巨大優(yōu)勢(shì)。

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

為了對(duì)上述算法提供合理全面的性能驗(yàn)證，本節(jié)將DKR算法和AC算法在同樣的實(shí)驗(yàn)環(huán)境下，對(duì)同樣的模式串和目標(biāo)串進(jìn)行驗(yàn)證，驗(yàn)證的主要標(biāo)準(zhǔn)是比較各自的時(shí)間效率和空間占用情況，然后通過對(duì)結(jié)果的分析得出最終結(jié)論。

3.1 實(shí)驗(yàn)環(huán)境

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

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

處理器核心數(shù)：4核；

編譯器：gcc version 5.4.0；

編程語言：c語言。

3.2 實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)選用的數(shù)據(jù)中，測(cè)試目標(biāo)文本大小為100 M；模式串集個(gè)數(shù)分別為1 000，5 000，10 000，模式串長(zhǎng)度則為5～1 000內(nèi)，任意長(zhǎng)度。

算法運(yùn)行預(yù)處理時(shí)間可見表1。

表1 不同模式串個(gè)數(shù)對(duì)應(yīng)算法預(yù)處理時(shí)間Tab. 1 Preprocessing time of string matching in different patterns

算法運(yùn)行匹配時(shí)間可見表2。

表2 不同模式串個(gè)數(shù)對(duì)應(yīng)算法匹配時(shí)間Tab. 2 Matching time of string matching in different patterns

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

算法運(yùn)行內(nèi)存最大占用量可見表3。

表3不同模式串個(gè)數(shù)對(duì)應(yīng)算法內(nèi)存最大占用量

Tab.3Maximummemoryusageofstringmatchingindifferentpatterns

模式個(gè)數(shù)/個(gè)DKR算法/KBAC算法/KB1000102376138892500011059229078810000120876478124

3.3 實(shí)驗(yàn)分析

通過對(duì)以上結(jié)果的分析，本文所提出的DKR算法在多模式串匹配的預(yù)處理和內(nèi)存占用上具有顯著鮮明優(yōu)勢(shì)。而且隨著模式串個(gè)數(shù)的增多，本算法實(shí)際展現(xiàn)出來的優(yōu)勢(shì)就越發(fā)明顯。但是本算法在匹配時(shí)間上效率并不如AC算法，這在此后的實(shí)驗(yàn)中，將進(jìn)一步展開研究?jī)?yōu)化，以達(dá)到更好的效果。

4 結(jié)束語

本文首先論述了KR算法，分析了常見的哈希函數(shù)，根據(jù)DKR算法的思想提出了相應(yīng)的哈希函數(shù)算法，同時(shí)詳細(xì)研究了該算法對(duì)模式串的預(yù)處理過程以及算法的匹配過程，并將該算法與AC算法在時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面進(jìn)行了闡釋分析。實(shí)驗(yàn)結(jié)果顯示，該算法在多模式串匹配的預(yù)處理和內(nèi)存占用上具有相當(dāng)大的優(yōu)勢(shì)，證明了算法的有效性。

[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] “科普中國(guó)”百科科學(xué)詞條編寫與應(yīng)用工作項(xiàng)目. 哈希函數(shù)[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] 葉軍偉. 哈希函數(shù)構(gòu)造方法及其適用情況[J]. 科技致富向?qū)?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.