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

無效

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

技術領域

本發明涉及一種多字符串匹配方法，屬于字符串匹配技術領域。

背景技術

在計算機領域，字符串匹配一直是計算機領域研究的焦點之一。字符串匹配問題可以描述為：已知需要匹配的t(t為正整數)個子串(通常稱之為模式串，或規則)，用P₁，P₂，…，P₁表示，需要檢索的字符串(通常稱之為文本)，用T[1…n](n為正整數)表示，查找在文本T[1…n]中所有出現的模式串，并報告其出現的位置。所謂多模式匹配，就是在文本串T[1…n]中一次匹配多個模式串P₁，P₂，…，P₁，t＝1時，多模式匹配蛻化為單模式匹配。

字符串匹配在拼寫檢查、語言翻譯搜索引擎等應用中起著關鍵的作用；同時，字符串匹配也是眾多信息內容安全系統中的關鍵技術之一。其中，多字符串匹配的方法目前已經廣泛用于網絡信息過濾，入侵檢測系統和生物信息計算的基因序列比較等實際應用中。

這些應用的共同特點有以下兩個方面：一是需要處理大量的數據(人類基因組共有30多億個堿基對；2009年6月，中國網絡國際出口帶寬達到747541Mbps)；二是需要匹配的關鍵詞條目多(以基因序列為例，關鍵詞條目達到O(104)的數量級)。隨著網絡以及生物學的發展，對多字符串匹配方法的處理能力提出了更高的要求。

在傳統的多字符串匹配方法中，Wu.Sun和Udi.Manber在文獻《A?Fast?Algorithm?for?Multi-Pattern?Searching》中提出的Wu-Manber方法，采用了跳躍不可能匹配的字符策略和HASH散列的方法，加速匹配的進行，在許多相關領域中得到了應用。

Wu-Manber方法包括一個預處理階段和一個掃描階段。

在預處理階段，首先計算模式串集合P中最短的模式串長度，記為m。然后，對所有模式串(僅考慮前m個字符組成的模式串)構建哈希表(記為HASH)、跳轉表(記為SHIFT)和前綴表(記為PREFIX)。HASH表的每個表項指向最后B(B為正整數，其值根據實驗情況擇優選擇)個字符被哈希到該表項的模式串，如果有多個模式串被哈希到同一表項，則采用鏈式存儲結構存儲；SHIFT表用于在掃描文本串的時候，根據讀入字符串決定可以跳過的字符數，其最大值為(m-B+1)，其最大值也成為跳越窗口的寬度；PREFIX表存儲的是每個模式串前B′(B′為正整數，其值根據實驗情況擇優選擇)個字符的哈希值。此處，建立HASH表和PREFIX表所用到的哈希函數根據不同情況進行選擇。

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

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

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

第3步：查SHIFT表，找到SHIFT[h]：如果大于0，則將指針q向后移動SHIFT[h]個長度，轉到第2步；否則轉到第4步；

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

第5步：查HASH表，找到HASH[h]的指針，遍歷鏈表。對鏈表中的每個模式串，如果它在PREFIX表的值與前綴哈希值h′相等，則將文本串和模式串逐一字符進行比較，判斷是否完全匹配。如完全匹配，則報告完全匹配位置q；否則，不報告；

第6步：判斷指針q是否指向文本串的結束符，如指向結束符，則結束過程；否則，將指針q向后移動一個字符，轉到第2步。

經過分析與實際運用，發現WU-MANBER方法存在以下不足：