基于線索完全哈希re結(jié)構(gòu)的多模式匹配算法

基于線索完全哈希re結(jié)構(gòu)的多模式匹配算法

網(wǎng)絡(luò)已成為世界信息傳播的最重要渠道之一。此外，網(wǎng)絡(luò)信息驗(yàn)證、網(wǎng)絡(luò)信息審計(jì)和其他信息技術(shù)的應(yīng)用也越來越普遍。多模式匹配算法是這些技術(shù)的核心。與傳統(tǒng)的多模式匹配相比，網(wǎng)絡(luò)信息文字的多模式匹配存在很大差異。由于不同地區(qū)的語言使用不同，網(wǎng)絡(luò)包絡(luò)結(jié)構(gòu)中的協(xié)議部分通常是英文文本，內(nèi)容部分通常是其他單詞。因此，所處理的文本通常是由不同編碼規(guī)則中的不同單詞組成的。對(duì)于漢語來說，漢字分為簡(jiǎn)體和繁體。這種情況更加突出。文本包含兩條以上的字節(jié)。已有的多模式匹配算法大都是面向單一字符環(huán)境,應(yīng)用于上述中英文混合環(huán)境時(shí),存在漏匹配、誤匹配等問題,研究高效、實(shí)用的適合于中英文字符混合環(huán)境下的多模式匹配算法有較大的理論與應(yīng)用價(jià)值.針對(duì)上述問題,本文提出了一種基于線索完全哈希Trie匹配機(jī)的多模式匹配算法THT(threadedHashTrie).理論分析與實(shí)驗(yàn)結(jié)果表明,THT算法完全適合于中英文混合環(huán)境的多模式匹配應(yīng)用,而且具有較低的時(shí)間復(fù)雜度和可接受的空間復(fù)雜度.1字符錯(cuò)位及誤匹配英文字符采用ASCII編碼,一個(gè)字符占用一個(gè)字節(jié);中文字符則采用雙字節(jié)編碼,簡(jiǎn)體字采用GB編碼,每個(gè)字節(jié)的最高位為1;繁體字使用BIG5編碼,高字節(jié)最高位必須為1,低字節(jié)的最高位沒有要求.這樣,在混合文本串中,一個(gè)字節(jié)的屬性可能有以下幾種情況:最高位為0的字節(jié)可能是英文字符或繁體漢字的低字節(jié);最高位為1的字節(jié)可能是簡(jiǎn)體或繁體漢字的高、低字節(jié).這種編碼長(zhǎng)度及規(guī)則的不同,導(dǎo)致在混合環(huán)境下進(jìn)行多模式匹配變得極為復(fù)雜.在單一字符環(huán)境下,字符的編碼長(zhǎng)度是一致的,匹配算法只需根據(jù)固定長(zhǎng)度進(jìn)行匹配即可,并可以根據(jù)規(guī)律進(jìn)行跳躍等來加速匹配.但在混合環(huán)境下,由于網(wǎng)絡(luò)信息的隨機(jī)性,文本串中不同編碼字符出現(xiàn)的概率是隨機(jī)的,若在匹配過程中錯(cuò)誤地確定字節(jié)的屬性,則會(huì)產(chǎn)生錯(cuò)位匹配的問題,導(dǎo)致將文本串漢字的低字節(jié)與模式串中漢字的高字節(jié)進(jìn)行對(duì)比,從而產(chǎn)生一連串的匹配錯(cuò)誤;或者將繁體漢字的低字節(jié)誤匹配為英文字符等.例如,對(duì)于字符串“?b?搜索產(chǎn)品?/b?”(3C|62|3E|CBD1|CBF7|B2FA|C6B7|3C|2F|62|3E),假設(shè)“產(chǎn)品(B2FA|C6B7)”為關(guān)鍵詞,如果在處理字符邊界時(shí)出現(xiàn)錯(cuò)誤,導(dǎo)致匹配從“搜”的低字節(jié)D1開始,而使字節(jié)組合變?yōu)椤?C|62|3E|CB|D1CB|F7B2|FAC6|B73C|2F|62|3E”,顯然會(huì)產(chǎn)生一連串的錯(cuò)位,導(dǎo)致漏匹配;如果錯(cuò)位的編碼正好組成某個(gè)關(guān)鍵詞,則會(huì)導(dǎo)致誤匹配,如圖1所示.發(fā)生字節(jié)錯(cuò)位后,如果該中文字符后面緊跟著出現(xiàn)一個(gè)中文模式串,則會(huì)產(chǎn)生漏匹配,直至出現(xiàn)一個(gè)非中文字符時(shí)才能糾正此種錯(cuò)位;如果某個(gè)中文字符的低字節(jié)和相鄰中文字符的高字節(jié)恰好組成某個(gè)模式串,則會(huì)造成誤匹配.為了防止錯(cuò)位匹配,目前常用的方法是先過濾掉文本串中的非中文字符,將其轉(zhuǎn)換成一個(gè)純中文文本串,再進(jìn)行相應(yīng)處理.顯然,這需要兩次掃描文本串,會(huì)浪費(fèi)較多的系統(tǒng)時(shí)間,匹配效率較低.這對(duì)網(wǎng)絡(luò)信息內(nèi)容審計(jì)、內(nèi)容搜索等實(shí)時(shí)性較高的處理有極大的影響.針對(duì)上述問題,有少數(shù)中國(guó)學(xué)者對(duì)中文及中英文混合環(huán)境下的模式匹配進(jìn)行了一定的研究,這些研究對(duì)中英文混合環(huán)境下的模式匹配作了非常有益的探索,但均存在一定的缺陷.對(duì)于主要使用單字節(jié)編碼的國(guó)家,如美國(guó)、英國(guó)等,因?yàn)椴淮嬖谏鲜鲇懻摰膯栴},相關(guān)文獻(xiàn)也較少.文獻(xiàn)提出的經(jīng)典DFSA算法應(yīng)用于英文字符環(huán)境時(shí)有很高的效率,但直接應(yīng)用于中文字符匹配時(shí),存在著存儲(chǔ)空間膨脹的問題.DFSA通常采用存取效率高的完全哈希表存儲(chǔ)狀態(tài)轉(zhuǎn)換函數(shù)以獲得高匹配速度,該表所占空間為sumof(state)×256,其中,sumof(state)為自動(dòng)機(jī)狀態(tài)總數(shù),256為單內(nèi)碼字符集的最大字符數(shù);如果采用同樣方法處理中文字符,則空間為sumof(state)×256×256,是英文字符的256倍.隨著狀態(tài)數(shù)的增加,完全哈希表所需的存儲(chǔ)空間會(huì)快速膨脹,導(dǎo)致算法在實(shí)際中無法直接應(yīng)用.文獻(xiàn)針對(duì)經(jīng)典多模式匹配算法DFSA應(yīng)用于中文字符匹配時(shí)存在的存儲(chǔ)空間膨脹問題,提出了通過分解中文字符內(nèi)碼構(gòu)造組合狀態(tài)自動(dòng)機(jī),并利用QS算法的思想進(jìn)行加速.該算法解決了中文字符構(gòu)建完全哈希表時(shí)的空間膨脹問題,但它只適用于純中文字符環(huán)境,在中英文混合環(huán)境下會(huì)導(dǎo)致字節(jié)錯(cuò)位問題.文獻(xiàn)采用加“標(biāo)記”方法來防止匹配中的錯(cuò)位問題,即模式串和待匹配文本中的每一位的屬性都被標(biāo)記.每一位的類型可分為以下3類:(類型0)英文的ASCII、(類型1)中文字符的高字節(jié)、(類型2)中文字符的低字節(jié).當(dāng)兩個(gè)字節(jié)被比較時(shí),不僅它們的數(shù)值相同,而且還要有相同的標(biāo)記,才認(rèn)為是匹配成功.這種方法可以解決中英文混合環(huán)境下字節(jié)錯(cuò)位的問題,但因需要對(duì)待匹配文本串進(jìn)行預(yù)掃描,以對(duì)每個(gè)字節(jié)加注標(biāo)記,所以匹配效率較低,而且沒有考慮ACSII,GB,BIG5這3種編碼混合的情況.文獻(xiàn)通過對(duì)中文字符內(nèi)碼的高字節(jié)Hbyte及低字節(jié)Lbyte進(jìn)行哈希運(yùn)算,如256×Hbyte+Lbyte,將所有中文字符映射到大小為65536的集合中,并在此基礎(chǔ)上提出一種基于兩級(jí)哈希表的DFSA算法.該算法以中文字符內(nèi)碼的兩個(gè)字節(jié)作為一個(gè)最小匹配單位,能夠避免中英文混合環(huán)境下的字節(jié)錯(cuò)位問題,而且也適用于3種編碼混合的情形,但在匹配中要對(duì)待匹配文本串中的每一個(gè)中文字符進(jìn)行哈希映射運(yùn)算,無疑會(huì)影響算法的匹配速度,在實(shí)際應(yīng)用中也驗(yàn)證了這個(gè)問題的存在,而且對(duì)算法效率的影響較大.另外,還有一些文獻(xiàn)也對(duì)多模式匹配算法進(jìn)行了研究,但都沒有考慮中英文混合環(huán)境對(duì)匹配算法的準(zhǔn)確性及匹配效率的影響,如文獻(xiàn).可以看出,研究一種高效、實(shí)用的適合于多種編碼字符混合環(huán)境的多模式匹配算法對(duì)網(wǎng)絡(luò)信息處理相關(guān)技術(shù)的發(fā)展極為重要,具有較大的理論與應(yīng)用價(jià)值.2文本串匹配算法通過前面的分析可以看出,與單一字符環(huán)境相比,混合環(huán)境下的多模式匹配有自己的特點(diǎn).由于英文字符與中文字符的內(nèi)碼所占字節(jié)數(shù)不同,因此,要匹配兩個(gè)英文字符還需對(duì)兩個(gè)字節(jié)的數(shù)據(jù)進(jìn)行比較,而要匹配兩個(gè)中文字符則需要對(duì)4個(gè)字節(jié)的數(shù)據(jù)進(jìn)行比較.為了方便后面的論述,這里給出匹配次數(shù)和比較次數(shù)的定義.定義1(匹配次數(shù)與比較次數(shù)).無論待匹配字符的內(nèi)碼為單字節(jié)還是雙字節(jié),每完成一個(gè)字符的比較,定義為一次匹配,即匹配次數(shù)為1.要完成一個(gè)字符的一次匹配,所需比較的字節(jié)數(shù)目,即該字符的內(nèi)碼字節(jié)數(shù)稱為該次匹配的比較次數(shù).定義2(字節(jié)長(zhǎng)度與字符長(zhǎng)度).假設(shè)T為任一包含中英文字符的隨機(jī)文本串,其中,中文字符的個(gè)數(shù)為m,英文字符的個(gè)數(shù)為n,則定義T的字符長(zhǎng)度為T中包含的中文字符與英文字符的個(gè)數(shù)之和,即m+n;字節(jié)長(zhǎng)度為T在內(nèi)存中所占的字節(jié)數(shù),即2m+n.對(duì)于英文字符環(huán)境下的模式匹配而言,匹配次數(shù)與比較次數(shù)是相等的,對(duì)于英文文本串,其字符長(zhǎng)度與字節(jié)長(zhǎng)度也是相等的.但對(duì)于多字節(jié)內(nèi)碼的字符而言,它們之間則存在著內(nèi)碼編碼長(zhǎng)度的倍數(shù)關(guān)系.定理1.如果模式串集合中含有中文字符模式串,則對(duì)任意一個(gè)隨機(jī)的含有中英文字符的待匹配文本串,在任何情況下都能正確完成匹配所需要的匹配次數(shù)不小于該文本串的字符長(zhǎng)度.證明:令T[1,2,…,M]為待匹配的含有中英文字符的隨機(jī)文本串,其中,M為其字節(jié)長(zhǎng)度,N為其字符長(zhǎng)度,T[i](1≤i≤M)為文本串中的一個(gè)字節(jié),Σ為模式串集合.根據(jù)是否對(duì)待匹配文本T進(jìn)行預(yù)處理,匹配算法可分為兩類:一類對(duì)T進(jìn)行預(yù)處理;一類不進(jìn)行處理,直接進(jìn)行匹配.與此相對(duì)應(yīng),定理證明也分為兩部分.(1)對(duì)T進(jìn)行預(yù)處理.無論是對(duì)T中字節(jié)加標(biāo)記,還是去除T中的英文或中文字符,將其轉(zhuǎn)化成單一字符的文本串,即使只對(duì)中文字符的高字節(jié)進(jìn)行判別(確定最高位是否為1),預(yù)掃描也至少要進(jìn)行N次比較才能確定T中每個(gè)字節(jié)T[i](1≤i≤M)的正確屬性.由于預(yù)處理后還要進(jìn)行匹配,所以,此類算法能完成的正確匹配次數(shù)顯然大于T的字符長(zhǎng)度N.因此,對(duì)于此類算法,定理成立.(2)對(duì)T不進(jìn)行預(yù)處理.假設(shè)存在一種不進(jìn)行預(yù)處理的匹配算法A,對(duì)于(Σ,T)在任何情況下正確完成匹配所需要的字符匹配次數(shù)Cmp都小于T的字符長(zhǎng)度N,即Cmp<N.由于Cmp<N,顯然在匹配過程中,算法A對(duì)T內(nèi)的部分字符沒有進(jìn)行匹配,即算法A在匹配過程中至少進(jìn)行了1次跳躍.不妨令算法A跳過的字符為T[i,j](1≤i≤j≤M),并且假設(shè)在跳躍之前沒有發(fā)生錯(cuò)位.根據(jù)假設(shè)可知,j-i≥1,T[i],T[i+1],…,T[j]均為隨機(jī)字符,跳躍后從T[j+1]開始下一次匹配,則有如下兩種情況:(a)j-i為偶數(shù).由于T[i],T[i+1],…,T[j-1]為隨機(jī)字符,那么,其中出現(xiàn)的英文字符個(gè)數(shù)enum也是隨機(jī)的,既可能為奇數(shù)也可能為偶數(shù).當(dāng)enum為奇數(shù)時(shí),則T[j]必為英文字符或某個(gè)中文字符的高字節(jié).然而當(dāng)T[j]為某個(gè)中文字符的高字節(jié)時(shí),T[j+1]為該中文字符的低字節(jié),從T[j+1]處開始匹配顯然會(huì)帶來一連串的匹配錯(cuò)位,所以在此情況下,算法不能保證不出現(xiàn)字節(jié)錯(cuò)位,即不能保證在任何情況下都進(jìn)行正確的匹配.(b)j-i為奇數(shù).在此情況下,要保證在T[j+1]開始進(jìn)行匹配不產(chǎn)生錯(cuò)位,則在T[i],T[i+1],…,T[j-1]之中必須存在奇數(shù)個(gè)英文字符,這樣,T[j+1]才有可能是英文字符或中文字符的高字節(jié),從T[j+1]開始匹配才不會(huì)造成字節(jié)錯(cuò)位的問題,這同樣與T為隨機(jī)文本串的前提相矛盾.因此,在此種情況下,同樣不能保證進(jìn)行正確的匹配.綜合上述兩種情況,假設(shè)不成立,即不存在這樣的一種匹配算法,使得對(duì)于(Σ,T),在任何情況下正確完成匹配所需要的字符匹配次數(shù)小于T的字符長(zhǎng)度.因此,對(duì)于直接匹配類算法,定理成立.綜合上述分析,定理成立.□定理2.在中英文混合環(huán)境下,在不對(duì)待匹配文本串進(jìn)行預(yù)掃描的情況下,基于跳躍匹配的多模式匹配算法存在漏匹配或誤匹配的情況.證明:在中英文混合環(huán)境下,待匹配文本串均可能為同時(shí)含有中英文字符的隨機(jī)文本串.基于跳躍匹配的算法在匹配過程中會(huì)跳過文本串中的一些字符,屬于亞線性匹配算法,匹配過程中的匹配次數(shù)會(huì)小于文本中的字符長(zhǎng)度.根據(jù)定理1,在中英文混合環(huán)境下,匹配次數(shù)小于待匹配文本串的字符長(zhǎng)度時(shí)會(huì)出現(xiàn)匹配字節(jié)錯(cuò)位問題,造成漏匹配或誤匹配.□3字符tri模塊本節(jié)給出THT算法的具體實(shí)現(xiàn).Trie結(jié)構(gòu)是一種深度可變的多層樹型索引結(jié)構(gòu),它采用寬度優(yōu)先搜索法,在同一層葉子結(jié)點(diǎn)上從左到右逐個(gè)查找,查到相匹配項(xiàng)后,再轉(zhuǎn)入下一層繼續(xù)查找.在匹配過程中,查找路徑為從根到葉子的一次查找,具有與DFSA相似的查找效率,但常規(guī)Trie匹配結(jié)構(gòu)在葉子結(jié)點(diǎn)處要進(jìn)行遍歷查找,會(huì)降低匹配速度.本文對(duì)常規(guī)Trie結(jié)構(gòu)進(jìn)行擴(kuò)展,將所有Trie葉子結(jié)點(diǎn)均設(shè)成大小為256的完全哈希表,以模式串字符的內(nèi)碼為鍵值構(gòu)造完全哈希Trie匹配機(jī).在完全哈希Trie匹配機(jī)中,中文字符用兩級(jí)相鄰的葉子結(jié)點(diǎn)表示,英文字符用一級(jí)葉子結(jié)點(diǎn)表示,用特殊字符表示模式串的結(jié)束.如漢字“華”的內(nèi)碼為0xBBAA,所對(duì)應(yīng)的完全哈希Trie匹配機(jī)結(jié)點(diǎn)如圖2所示.由于單字節(jié)的最大值為255,在查找過程中可以實(shí)現(xiàn)完全哈希查找,不需要對(duì)漢字的高低字節(jié)進(jìn)行任何附加運(yùn)算,因而具有極高的查找效率;由于分別對(duì)中文字符的高低字節(jié)進(jìn)行構(gòu)造,因而不存在空間膨脹問題.完全哈希Trie匹配機(jī)的構(gòu)造以字節(jié)為最小單位,能夠?qū)⒅形哪Ｊ酱c英文模式串構(gòu)造在同一Trie匹配機(jī)中,具有良好的中英文兼容性.例如,根據(jù)模式串集合{Chinese,中華,中國(guó)人}構(gòu)造的完全哈希Trie匹配機(jī)如圖3所示,其中,“中”、“華”、“國(guó)”與“人”的內(nèi)碼分別為0xD6D0,0xAABB,0xB9FA與0xC8CB.與英文字符不同,中文字母表內(nèi)字符的個(gè)數(shù)較多,在匹配過程中,首字符匹配失敗的概率較大,可以使用首字符完全哈希表進(jìn)行匹配加速,即只有首字符匹配成功以后,再進(jìn)入后面的完全哈希Trie匹配機(jī)進(jìn)行匹配.首字符完全哈希表使用一個(gè)256×256的兩維數(shù)組head_index[Hbyte][Lbyte]來實(shí)現(xiàn),在匹配過程中,以中文字符內(nèi)碼的高低字節(jié)直接作索引,獲得了較快的匹配速度.構(gòu)造完全哈希Trie匹配機(jī)所需要的數(shù)據(jù)結(jié)構(gòu)及構(gòu)造算法偽碼見算法1.由定理2可知,在中英文混合環(huán)境下,帶有跳躍匹配的算法都可能產(chǎn)生誤匹配或漏匹配,因此,首先給出基于完全哈希Trie匹配機(jī)的蠻力(bruteforce)多模式匹配算法HT(HashTrie).算法在匹配前事先判斷字符的種類,匹配失敗或成功后,匹配指針僅比上一次匹配的初始位置前進(jìn)1個(gè)字符.由于匹配指針在匹配中要進(jìn)行回溯,因此,蠻力匹配算法效率不高,但可以避免誤匹配或漏匹配的情況.HT算法偽碼見算法2.算法1.完全哈希Trie匹配機(jī)構(gòu)造算法.算法2.TH匹配算法偽碼.4個(gè)字符“日”處的匹配上一節(jié)給出的蠻力匹配算法在匹配成功或失敗后,匹配指針要進(jìn)行回溯.也就是說,待匹配文本串中的一些字符需要進(jìn)行兩次或兩次以上的匹配,這無疑會(huì)降低匹配速度.從匹配過程可以看出,這些回溯是可以避免的,因?yàn)闊o論匹配成功還是失敗,都可以利用已經(jīng)得到的部分匹配結(jié)果來判斷下一次的匹配情況,從而使匹配指針可以從當(dāng)前位置繼續(xù)向后匹配,而不需要回溯.此種處理類似于KMP算法,但由于KMP為單模式匹配算法,因此又與其有所區(qū)別.由于模式串集合是已知固定的,可以通過預(yù)處理對(duì)完全哈希Trie匹配機(jī)進(jìn)行線索化來記錄本趟匹配結(jié)束后下一趟匹配的情況,從而使得匹配指針不需要回溯,提高了匹配速度.以模式串集合{服務(wù)社會(huì),人民日?qǐng)?bào),為人民服務(wù)}為例,其線索化如圖4所示,圖中彎曲的細(xì)線為線索.當(dāng)模式串“為人民服務(wù)”在第4個(gè)字符即“服”處匹配失敗后,應(yīng)該轉(zhuǎn)移至模式串“人民日?qǐng)?bào)”的第3個(gè)字符“日”處繼續(xù)進(jìn)行匹配;當(dāng)模式串“為人民服務(wù)”匹配成功后,應(yīng)轉(zhuǎn)移到模式串“服務(wù)社會(huì)”的第3個(gè)字符“社”處繼續(xù)進(jìn)行匹配.可以看出,對(duì)完全哈希Trie匹配機(jī)的線索化可以避免匹配指針的回溯.線索化主要有兩個(gè)方面:一方面是匹配失敗的情況,另一方面是匹配成功的時(shí)候.下面給出完全哈希Trie匹配機(jī)的線索化過程.中英文模式串的Trie匹配機(jī)構(gòu)造及線索化過程是相同的,在此僅以中文模式串為例進(jìn)行論述.假設(shè)中文模式串集合Σ={p1,p2,…,psum},其中,模式串的長(zhǎng)度分別為len1,len2,…,lensum,kpj表示模式串pk內(nèi)的第j個(gè)字符.假設(shè)當(dāng)前匹配字符為kpj,令findex[k][j]與sindex[k][j]分別表示在kpj處匹配失敗與匹配成功后,需要轉(zhuǎn)向繼續(xù)進(jìn)行匹配的位置.線索化過程實(shí)質(zhì)上就是findex[k][j]與sindex[k][j]的求值過程.首先是匹配失敗線索findex[k][j]的計(jì)算.在kpj處匹配失敗后,有如下的情況:(1)當(dāng)j=1時(shí),此處的匹配失敗實(shí)際就是首字符匹配失敗,findex[i][j]的值為(0,0).此處值為(0,0)表示不需要進(jìn)行轉(zhuǎn)移,直接從當(dāng)前匹配位置的下一個(gè)相鄰字符重新開始匹配.(2)當(dāng)1<j≤lenk時(shí),需要判斷已經(jīng)匹配成功的[pk1,pk2,...,pkj-1]的后綴子串集合內(nèi)是否存在模式串pm(1≤m≠k≤sum)的前綴子串.如果不存在,則findex[k][j]=(0,0);如果存在[pkn,pkn+1,...,pkj-1](1≤n≤j-1)為pm的最長(zhǎng)前綴子串,則findex[k][j]=(m,j-n),其中,(m,n)表示從模式串pm的第n個(gè)字符開始匹配.綜合上述分析,findex[k][j]的值可以用公式(1)進(jìn)行計(jì)算.計(jì)算findex[k][j]的偽碼見算法3.算法3.匹配失敗線索計(jì)算算法.其次是匹配成功的情況,當(dāng)模式串pk匹配成功后,后續(xù)的匹配存在如下兩種情況:(1)pk的任一后綴都不是Σ中其余任一模式串的前綴,應(yīng)直接從當(dāng)前匹配位置的下一個(gè)字符重新開始匹配;(2)pk的長(zhǎng)度為n的最長(zhǎng)后綴為模式串pm的前綴,則轉(zhuǎn)向pm的第n+1個(gè)字符處進(jìn)行匹配.sindex[k]的值可以用以下公式進(jìn)行計(jì)算:計(jì)算sindex[k]的算法與計(jì)算findex[k][j]的算法3相似,在此不再給出算法偽碼.THT的匹配過程偽碼見算法4.值得說明的是,由于算法4中的findex[kw.num].n是以字節(jié)為度量最小單位,而在式(1)、式(2)中的n是以字符為最小單位,因此,在具體程序中對(duì)findex進(jìn)行初始化時(shí)應(yīng)進(jìn)行轉(zhuǎn)換,并要區(qū)分中英文模式串.算法4.THT匹配算法偽碼.5pem、pc1,pc1,pc1,pc1,pce,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,pc1,meg假設(shè)待匹配中英文混合的隨機(jī)文本串T的字符長(zhǎng)度為Twlen,字符長(zhǎng)度為Tblen;模式串集合Σ={pe1,pe2,…,peM,pc1,pc2,…,pcN},其中,pem(1≤m≤M)為英文模式串,其字符長(zhǎng)度為lenem;pcn(1≤n≤N)為中文模式串,其字符長(zhǎng)度為lencn;Ψ為所有模式串中字符的集合.對(duì)THT算法而言,Trie匹配機(jī)構(gòu)造算法的空間復(fù)雜度與匹配算法的時(shí)間復(fù)雜度至關(guān)重要,兩者決定了算法的可行性與可用性,性能分析主要集中在這兩個(gè)方面.5.1空間膨脹問題從算法1可以看出,構(gòu)造Σ的完全哈希Tire匹配機(jī)算法的時(shí)間復(fù)雜度為O(Σlenem+Σlencn).構(gòu)造算法運(yùn)行于整個(gè)算法的初始化階段,其空間復(fù)雜度是主要的,它決定了算法在實(shí)踐中是否可行.為分析構(gòu)造算法的空間復(fù)雜度,進(jìn)行以下定義.最大模式串長(zhǎng)度MAXLEN,兩個(gè)輔助參數(shù)femi,fcni,構(gòu)造算法采用首字符雙字節(jié)完全哈希表,占用64K空間,完全哈希Trie匹配機(jī)從模式串的第2個(gè)字符開始構(gòu)造,因此,算法1所需要的空間?為由式(5)可以看出,在最壞情況下,即所有模式串的字符長(zhǎng)度均為MAXLEN,且任兩個(gè)模式串之間不存在相同前綴子串,算法1使用的空間為定理3.在中文環(huán)境下,對(duì)于相同的模式串集合,完全哈希Trie構(gòu)造算法在最壞情況下的使用空間遠(yuǎn)小于DFSA算法中狀態(tài)轉(zhuǎn)換完全哈希表所需空間.證明:由于空間膨脹問題主要針對(duì)中文字符而言,因此不妨假設(shè)模式串集合內(nèi)只有中文模式串,則最壞情況下完全哈希Trie構(gòu)造算法使用空間?max為DFSA算法中狀態(tài)轉(zhuǎn)換函數(shù)完全哈希表使用空間?DFSA為256×256×sumof(state),則有當(dāng)模式串?dāng)?shù)量N較大時(shí),顯然有N<<sumof(state),又因?yàn)镸AXLEN<<256,所以在模式串?dāng)?shù)量較多時(shí)有?max/?DFSA<<1,即?max<<?DFSA.□不妨假設(shè)有2500個(gè)中文模式串,500個(gè)英文模式串,最長(zhǎng)模式串為10個(gè)中文字符,即最長(zhǎng)為20字節(jié),則最壞情況下使用空間為13.37M.根據(jù)文獻(xiàn),已知中文詞出現(xiàn)頻率依次為單字詞占12.11%,雙字詞占73.16%,三字詞占7.16%,四字詞占6.14%,多字詞占0.12%,在實(shí)際應(yīng)用中又以中文模式串為主,實(shí)際使用關(guān)鍵字的長(zhǎng)度遠(yuǎn)小于MAXLEN.可以看出,本文算法不存在空間膨脹問題,在實(shí)際應(yīng)用中完全可行.完全哈希Trie匹配機(jī)線索化算法的時(shí)間復(fù)雜度為O(sum×len2),通常,模式串的長(zhǎng)度len比較小,而且線索化運(yùn)行于算法的初始化階段,對(duì)整個(gè)匹配算法的性能基本上沒有影響.5.2thd算法的匹配效率通過算法4可以看出,THT算法在匹配過程中匹配指針不需要回溯,最壞情況下,完成對(duì)T的匹配需要進(jìn)行的匹配次數(shù)為Twlen+MAXLEN,比較次數(shù)為Tblen+MAXLEN,因此,算法的時(shí)間復(fù)雜度為O(Tblen+MAXLEN).根據(jù)定理1,在中英文混合環(huán)境下,THT算法的匹配次數(shù)已經(jīng)逼近正確匹配所需最少匹配次數(shù)的理論下限,因此,算法具有較好的匹配效率.而且,由于中文字符為大字符集,經(jīng)過首字符高字節(jié)的匹配后,匹配失敗的概率很大,因此,在實(shí)際的使用中,THT算法的比較次數(shù)一般會(huì)遠(yuǎn)遠(yuǎn)小于待匹配文本的字節(jié)長(zhǎng)度.另外,THT算法的匹配速度與以下因素有關(guān):(1)模式串之間相同字符的數(shù)量,即集合Ψ中字符在模式串中出現(xiàn)的次數(shù).相同字符數(shù)量越少,所構(gòu)造Trie匹配機(jī)內(nèi)的線索密度越小,在匹配中需要轉(zhuǎn)移的次數(shù)也越少,匹配效率也就越高.(2)集合Ψ中字符在文本串T中出現(xiàn)的概率.顯然,出現(xiàn)的概率越低,經(jīng)過首字哈希匹配后匹配失敗的概率就越大,匹配指針直接后移,匹配所花費(fèi)的時(shí)間也就越少;(3)中英文模式串在Σ中各占的比例以及T內(nèi)中英文各占的比例.中英文語言存在比較明顯的差異,如中文語言是大字符集語言,字母表數(shù)量龐大,詞語長(zhǎng)度較短;英文語言的字母表小,詞比較長(zhǎng)等.這些差異使得在大多數(shù)情況下,T內(nèi)中文字符都不屬于Ψ,而且即使屬于Ψ,匹配成功或失敗后需要匹配轉(zhuǎn)移的概率也小;對(duì)于英文則恰恰相反.所以,當(dāng)模式串集合內(nèi)英文模式串較少、待匹配文本串內(nèi)英文字符較少時(shí),算法匹配速度較快.6實(shí)驗(yàn)與分析6.1算法性能分析本節(jié)給出了實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)所使用的服務(wù)器為IBM的eServer,處理器為Intel(R)Xeon(TM)CPU2.00GHz,內(nèi)存為512M,硬盤為40G,操作系統(tǒng)為RedHat7.2,內(nèi)核版本為2.4.20.從文本1中切分出5組中文關(guān)鍵詞,關(guān)鍵詞的數(shù)量分別為500,1000,1500,2000和2500,每組詞平均長(zhǎng)度均為3.7個(gè)漢字;切分出5組英文關(guān)鍵詞,數(shù)量分別為10,20,30,40,50.由于單字漢字的語義大多不明確,在實(shí)際應(yīng)用中設(shè)置單字關(guān)鍵詞的情況較少,因此,在實(shí)驗(yàn)過程中沒有設(shè)置單字關(guān)鍵詞.3種算法所使用的空間見表1,其中,Shen,Gao分別代表文獻(xiàn)、文獻(xiàn)中的算法.由于文獻(xiàn)中加標(biāo)記的算法需要對(duì)待匹配文本進(jìn)行預(yù)掃描處理,然后才進(jìn)行匹配,匹配時(shí)間明顯大于其他算法,因此,本文沒有與文獻(xiàn)算法進(jìn)行對(duì)比實(shí)驗(yàn).為了對(duì)本算法的理論值與實(shí)際使用的空間進(jìn)行對(duì)比,假定最長(zhǎng)關(guān)鍵詞長(zhǎng)度為10個(gè)漢字,英文字符為20個(gè)字符,在表1中同時(shí)給出了THT算法的理論使用空間.首先使用文本2、文本4做對(duì)比實(shí)驗(yàn).由于算法Shen只適用于純中文環(huán)境,使用文本2、文本4可以保證每種算法都能進(jìn)行正確匹配,在此種情況下進(jìn)行效率對(duì)比才有意義.文本2、文本4為純中文文本,在匹配中不需要區(qū)分字符的種類,在算法Gao,HT及THT中將不進(jìn)行字符種類的判斷.這樣,4種算法所進(jìn)行的字符處理是一致的,匹配使用的時(shí)間反映了算法匹配效率的高低.在實(shí)驗(yàn)過程中,4種算法均能正確完成查找,文本2的5組實(shí)驗(yàn)匹配次數(shù)為11067,18525,22987,30210,50181;文本4的5組實(shí)驗(yàn)匹配次數(shù)為379016,451942,609310,941736,1636960;各種算法所使用的時(shí)間見表2.使用文本1、文本3評(píng)測(cè)Gao,Shen,HT及THT這4種算法在中英文混合環(huán)境下的性能,性能對(duì)比見表3.Gao,HT及THT算法均能正確完成查找,文本1的5組實(shí)驗(yàn)匹配次數(shù)為11132,18714,23078,30507,50639;文本4的5組實(shí)驗(yàn)匹配次數(shù)為379361,452426,609903,942643,1638205.在中英文混合環(huán)境下,算法Shen不能進(jìn)行正確匹配,文本1的5組實(shí)驗(yàn)匹配次數(shù)為5683,9394,11805,15426,31092;文本3的5組實(shí)驗(yàn)匹配次數(shù)為189328,224678,314580,489099,1053692.表4為算法HT與THT算法在實(shí)際運(yùn)行中的比較次數(shù).6.2算法性能對(duì)比(1)空間使用方面從表1可以看出,本文算法使用空間小于算法Gao及算法Shen;隨著模式串?dāng)?shù)量的增加,算法Gao使用空間增加,成超線性關(guān)系;本文算法與算法Shen的空間增加基本上與模式串?dāng)?shù)量增加,成亞線性關(guān)系.這主要是因?yàn)樗惴℅ao使用狀態(tài)完全哈希表,隨著模式串?dāng)?shù)量的增加,狀態(tài)機(jī)的狀態(tài)數(shù)量增加較快.本文算法與算法Shen優(yōu)于算法Gao,不存在存儲(chǔ)空間增長(zhǎng)過快的問題;對(duì)THT算法而言,實(shí)際運(yùn)行使用空間遠(yuǎn)遠(yuǎn)小于理論計(jì)算值,與性能分析的結(jié)論相吻合.(2)匹配時(shí)間方面從表2可以看出,在純中文環(huán)境下,THT使用時(shí)間少于算法Gao,Shen,5組實(shí)驗(yàn)使用的時(shí)間分別為算法Gao的46.53%,47.09%,45.41%,44.49%,46.72%以及算法Shen的83.7