[發(fā)明專(zhuān)利]一種字符串匹配算法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310287683.9
• 申請(qǐng)日: 2013-07-09
• 公開(kāi)（公告）號(hào): CN103425739A
• 公開(kāi)（公告）日: 2013-12-04
• 發(fā)明（設(shè)計(jì)）人: 韓飛;楊松;莫展鵬;季統(tǒng)凱
• 申請(qǐng)（專(zhuān)利權(quán)）人: 國(guó)云科技股份有限公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 北京科億知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11350
• 代理人: 湯東鳳

技術(shù)領(lǐng)域

本發(fā)明涉及信息處理技術(shù)領(lǐng)域，尤其是一種一種快速字符串匹配算法。

背景技術(shù)

在文本編輯器、搜索引擎、數(shù)據(jù)處理、通信系統(tǒng)等應(yīng)用中，經(jīng)常需要在一大段源字符串之中對(duì)一個(gè)目標(biāo)字符串進(jìn)行快速的搜索定位和統(tǒng)計(jì)。假設(shè)源字符串長(zhǎng)度為m，目標(biāo)字符串長(zhǎng)度為n。對(duì)于樸素字符串匹配算法而言，比如C標(biāo)準(zhǔn)庫(kù)函數(shù)strstr()所使用的算法；這種算法依次序從頭到尾對(duì)字符串進(jìn)行匹配，存在大量的對(duì)目標(biāo)字符串字符的重復(fù)匹配，效率低下，最壞情況下的時(shí)間復(fù)雜度是O(m*n)。對(duì)于KMP等改進(jìn)的匹配算法，其降低了對(duì)目標(biāo)字符串字符的重復(fù)匹配，相對(duì)樸素算法而言提高了效率，但是仍然存在對(duì)整個(gè)m長(zhǎng)度源字符串的匹配，效率有待進(jìn)一步提升。

發(fā)明內(nèi)容

本發(fā)明解決的技術(shù)問(wèn)題在于提供一種快速的字符串匹配算法；可以有效提升對(duì)目標(biāo)字符串匹配、搜索的效率。

本發(fā)明解決上述技術(shù)問(wèn)題的技術(shù)方案是：

包括如下步驟，

步驟1：對(duì)目標(biāo)字符串進(jìn)行預(yù)先處理，得到其各個(gè)字符的一個(gè)簡(jiǎn)單哈希表，使確定任意一個(gè)字符是否從屬于目標(biāo)字符串的時(shí)間復(fù)雜度為1；

步驟2：開(kāi)始匹配，查找匹配的首個(gè)字符，如果搜索到源字符串末尾，結(jié)束搜索；

步驟3：如匹配到目標(biāo)字符串的第一個(gè)字符，跳轉(zhuǎn)到步驟5；

步驟4：如果不匹配，把源字符的字符指針移向下一個(gè)字符，繼續(xù)步驟2；

步驟5：檢查源字符串中以匹配的首個(gè)字符為開(kāi)頭的最后一個(gè)字符是否屬于目的字符串中的一個(gè)，如果是，則到步驟6，否則到步驟8；

步驟6：檢查目標(biāo)字符串是否全部或部分位于由匹配字符開(kāi)始到目標(biāo)字符串長(zhǎng)度后范圍內(nèi)的字符串之內(nèi)并且整個(gè)字符串得到匹配，如果匹配，到步驟7，否到步驟8；

步驟7：字符指針從新匹配的首個(gè)字符位置處再向后偏移目標(biāo)字符串長(zhǎng)度的偏移量，回到步驟2；

步驟8：字符指針從原來(lái)匹配的首個(gè)字符位置處再向后偏移目標(biāo)字符串長(zhǎng)度的偏移量，回到步驟2。

2、根據(jù)權(quán)利要求1所述的字符串匹配方法，其特征在于：對(duì)目標(biāo)字符串進(jìn)行預(yù)處理；當(dāng)匹配到首個(gè)字符后即進(jìn)行匹配目標(biāo)字符串的最后一個(gè)字符。

本發(fā)明的工作原理基于實(shí)際應(yīng)用中的一種高概率的事件，源字符指代要被檢索的字符串，目標(biāo)字符指代要被匹配的字符串：

1、字符串中的字符不是隨機(jī)字符。

2、因?yàn)椴皇请S機(jī)字符，也就是字符之間尤其是相鄰字符之間是有某種相關(guān)關(guān)系的。例如，非元音字母旁邊出現(xiàn)元音字母的概率就要比非元音字母高，‘我’字旁邊出現(xiàn)‘的’字的概率就要遠(yuǎn)高于‘地’字。相互靠得更近的兩個(gè)或多個(gè)字符，如果匹配了其中一部分，那么其旁邊的字符匹配的概率相對(duì)更遠(yuǎn)距離的字符也越高。這個(gè)事實(shí)等價(jià)于距離已匹配部分的字符越遠(yuǎn)的字符不匹配的概率相對(duì)更高。

3、即便是對(duì)于完全隨機(jī)的字符串來(lái)說(shuō)，任意一個(gè)字符是欲搜索字符串的一部分的概率也要遠(yuǎn)低于不是其一部分的概率。如果把這個(gè)位于最后的字符屬于目標(biāo)字符串中的一個(gè)視為匹配，則如果匹配了目標(biāo)字符串首個(gè)字符但是最后一個(gè)字符不匹配（由上面論述可知不匹配的概率要高于匹配），則馬上可以肯定從首個(gè)到最后一個(gè)字符之間的這段字符不用比較就可以確定是不匹配的，從而可以直接忽略這部分字符，直接跳到最后一個(gè)字符之后的一個(gè)字符，繼續(xù)剩下的匹配運(yùn)算。

4、在源字符串中，不匹配的字符串遠(yuǎn)多于匹配的字符串，因此提高查找不匹配字符串的效率相對(duì)提高查找匹配字符串效率有更積極的意義。

5、本算法基于以上這些實(shí)際應(yīng)用中的情況，通過(guò)比對(duì)最后一個(gè)字符，提高匹配“不匹配”字符串的效率從而得到更高的匹配“匹配”字符串的效率。與以上所述條件愈匹配，則效能越高。

6、即便在隨機(jī)字符的模式匹配中，本算法相對(duì)樸素算法也具有效率上的優(yōu)勢(shì)。

經(jīng)測(cè)試，本發(fā)明所述算法相對(duì)樸素字符串匹配算法平均有不低于20％的時(shí)間效率優(yōu)勢(shì)，可以有效提高字符串匹配的效率。

附圖說(shuō)明

下面結(jié)合附圖對(duì)本發(fā)明進(jìn)一步說(shuō)明：

圖1是本發(fā)明的算法流程圖；

圖2是本發(fā)明匹配示例框圖。

具體實(shí)施方式

如圖1所示，本發(fā)明以target指代目標(biāo)字符串，text指代源字符串，pos為源字符串的位置指針，found為匹配到的數(shù)目；假設(shè)字符為ASCII編碼；示例代碼以C語(yǔ)言代碼給出。

首先，對(duì)目標(biāo)字符串進(jìn)行預(yù)處理，生成一個(gè)用于快速檢索的簡(jiǎn)單哈希表，使確定任意一個(gè)字符是否從屬于目標(biāo)字符串的時(shí)間復(fù)雜度為1。