[發明專利]一種字符串匹配算法

有效

• 申請號: 201310287683.9
• 申請日: 2013-07-09
• 公開（公告）號: CN103425739A
• 公開（公告）日: 2013-12-04
• 發明（設計）人: 韓飛;楊松;莫展鵬;季統凱
• 申請（專利權）人: 國云科技股份有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京科億知識產權代理事務所(普通合伙) 11350
• 代理人: 湯東鳳

技術領域

本發明涉及信息處理技術領域，尤其是一種一種快速字符串匹配算法。

背景技術

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

發明內容

本發明解決的技術問題在于提供一種快速的字符串匹配算法；可以有效提升對目標字符串匹配、搜索的效率。

本發明解決上述技術問題的技術方案是：

包括如下步驟，

步驟1：對目標字符串進行預先處理，得到其各個字符的一個簡單哈希表，使確定任意一個字符是否從屬于目標字符串的時間復雜度為1；

步驟2：開始匹配，查找匹配的首個字符，如果搜索到源字符串末尾，結束搜索；

步驟3：如匹配到目標字符串的第一個字符，跳轉到步驟5；

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

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

步驟6：檢查目標字符串是否全部或部分位于由匹配字符開始到目標字符串長度后范圍內的字符串之內并且整個字符串得到匹配，如果匹配，到步驟7，否到步驟8；

步驟7：字符指針從新匹配的首個字符位置處再向后偏移目標字符串長度的偏移量，回到步驟2；

步驟8：字符指針從原來匹配的首個字符位置處再向后偏移目標字符串長度的偏移量，回到步驟2。

2、根據權利要求1所述的字符串匹配方法，其特征在于：對目標字符串進行預處理；當匹配到首個字符后即進行匹配目標字符串的最后一個字符。

本發明的工作原理基于實際應用中的一種高概率的事件，源字符指代要被檢索的字符串，目標字符指代要被匹配的字符串：

1、字符串中的字符不是隨機字符。

2、因為不是隨機字符，也就是字符之間尤其是相鄰字符之間是有某種相關關系的。例如，非元音字母旁邊出現元音字母的概率就要比非元音字母高，‘我’字旁邊出現‘的’字的概率就要遠高于‘地’字。相互靠得更近的兩個或多個字符，如果匹配了其中一部分，那么其旁邊的字符匹配的概率相對更遠距離的字符也越高。這個事實等價于距離已匹配部分的字符越遠的字符不匹配的概率相對更高。

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

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

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

6、即便在隨機字符的模式匹配中，本算法相對樸素算法也具有效率上的優勢。

經測試，本發明所述算法相對樸素字符串匹配算法平均有不低于20％的時間效率優勢，可以有效提高字符串匹配的效率。

附圖說明

下面結合附圖對本發明進一步說明：

圖1是本發明的算法流程圖；

圖2是本發明匹配示例框圖。

具體實施方式

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

首先，對目標字符串進行預處理，生成一個用于快速檢索的簡單哈希表，使確定任意一個字符是否從屬于目標字符串的時間復雜度為1。