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

無效

• 申請號: 201010232463.2
• 申請日: 2010-07-21
• 公開（公告）號: CN101901257A
• 公開（公告）日: 2010-12-01
• 發明（設計）人: 嵩天;黎達
• 申請（專利權）人: 北京理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種多字符串匹配方法，其特征在于：包括一個預處理階段和一個掃描階段；

預處理階段包括構建哈希表HASH、跳轉表SHIFT、前綴表PREFIX和短模式串過濾表HOT，其具體工作步驟如下：

第1步：設置HOT表的大小SUM以及HOT表選取的字符塊的長度s；其中，SUM≥256并且SUM為正整數；s＝2或3；

第2步：將模式串集合P中的全部模式串分為長模式串和短模式串兩類，長模式串集合記為P₁，短模式串集合記為P₂，短模式串的數量記為SumP₂；具體為：

第a步：確定跳越窗口的寬度與最短模式串長度的比值r，r為正整數，其取值范圍滿足公式1；

2≤r≤lmaxlmin---(1)]]>

其中，lmax為模式串集合P中最長的模式串的長度；lmin為模式串集合P中最短的模式串長度；

第b步：根據公式2、公式3確定分類標準M值：

M＝r×lmin-(r-1)×s(2)

第c步：當模式串的長度大于M時，則判斷其為長模式串；否則，判斷其為短模式串；

第d步：判斷當前的短模式串的數量SumP₂是否滿足SumP₂≤1.5×SUM，如果滿足，執行第3步；否則，減小r值，并確保r滿足然后返回到第b步；

第3步：對于全部長模式串的前M個字符組成的字符串StringL以及全部短模式串的前lmin個字符組成的字符串StringS進行操作，構建哈希表HASH、跳轉表SHIFT、前綴表PREFIX和短模式串過濾表HOT；具體為：

①HASH表：HASH表的每個表項指向所述字符串StringL或StringS最后B個字符被哈希到該表項的模式串，如果有多個模式串被哈希到同一表項，則采用鏈式存儲結構存儲；其中，B為正整數，其值根據實際情況確定；

②PREFIX表：存儲所述字符串StringL或StringS前B′個字符的哈希值；其中，B′為正整數，其值根據實際情況確定；

③HOT表：依次對短字符串集合P2中的所有模式串作如下操作：

第a步：將指針指向其起始位置，向后取長度為s的字符塊，計算其哈希值為h_hot，將HOT[h_hot]設置為1；

第b步：將指針后移一位；判斷指針與該字符串的結束標識符之間的距離是否為(s-1)，如果不是，執行第a步；否則，結束操作；

經過上述步驟的操作，即可完成HOT表的構建；

④SHIFT表：

首先，將SHIFT表中的所有項賦值為M-B+1；

然后，對長模式串集合P₁中的模式串依次做如下處理：

第a步：將指針指向該模式串的第M個字符，并用qi表示當前指針指向字符串中的位置，qi為正整數，qi的初始值為M；

第b步：向前取長度為B的字符塊，計算其哈希值為h_shift_l，將SHIFT[h_shift_l]的值設置為M-qi；

第c步：將指針向前移動一個字符，并為qi賦值為qi-1；判斷距離該模式串的起始字符的距離是否小于B-1，如果不是，回到第b步；否則，結束操作；

再對短模式串集合P₂中的模式串依次做如下處理：

第a步：將指針指向該模式串的第lmin個字符，并用qj表示當前指針指向字符串中的位置，qj為正整數，qj的初始值為lmin；

第b步：向前取長度為B的字符塊，計算其哈希值為h_shift_s，將SHIFT[h_shift_s]的值設置為lmin-qj；

第c步：將指針向前移動一個字符，并為qj賦值為qj-1；判斷距離該模式串的起始字符的距離是否小于B-1，如果不是，回到第b步；否則，結束操作；

經過上述步驟的操作，即可完成SHIFT表的構建；

所述HASH表、PREFIX、SHIFT表和HOT表在建立時所用到的哈希函數根據不同情況進行選擇；

在掃描階段，按如下步驟進行：

第1步：設一指針q_text，指向文本T的第M個字符；

第2步：從當前指針往前的B-1個字符開始，向后掃描B個字符，使用預處理階段建立HASH表所用到的哈希函數，計算該B個字符的哈希值h；

第3步：查SHIFT表，找到SHIFT[h]；如果SHIFT[h]等于0，執行第4步；否則，跳轉到第7步；

第4步：從當前指針往前的M-1個字符開始，向后掃描B′個字符，使用預處理階段建立PREFIX表所用到的哈希函數，計算這B′個字符的前綴哈希值h_long；從當前指針往前的lmin-1個字符開始，向后掃描B′個字符，使用預處理階段建立PREFIX表所用到的哈希函數，計算這B′個字符的前綴哈希值h_short；

第5步：查HASH表，找到HASH[h]的指針，遍歷鏈表；對鏈表中的每個模式串，如果它在PREFIX表的值與相應的前綴哈希值相等，則將文本T和模式串逐一字符進行比較；判斷是否完全匹配；如完全匹配，則報告完全匹配位置；否則，不報告；對于長模式串，匹配的起始位置為當前指針位置往前M-1個字符處；對于短模式串，匹配的起始位置為當前指針位置往前lmin-1個字符處；

第6步：將指針q_text向后移動一個字符，轉到第8步；

第7步：若SHIFT[h]不大于(lmin-B+1)，則將指針向后移動SHIFT[h]個距離；否則，進行如下操作：

第a步：設置r′＝1，

第b步：從當前指針所在位置往后((r′+1)×(lmin-s)-(B-1))個字符的位置處向前取長度為s的字符串；計算其哈希值hash_h，判斷“HOT[hash_h]＝0”是否成立；若成立，執行第c步；否則，跳轉到第d步；

第c步：判斷“(r′+1)×lmin-(r′)×s-(B-1)＜SHIFT[h]”是否成立，若成立，將r′取值為(r′+1)，返回到第b步；否則，將指針向后移動SHIFT[h]個字符的距離；

第d步：令dis＝((r′+1)×lmin-r*s-(B-1))，并將指針向后移動dis個字符的距離；

第8步：判斷指針q_text是否指向文本T的結束符，如指向結束符，則結束；否則，轉到第2步；

經過上述步驟的操作，即可完成多個模式串的匹配。