[發明專利]一種基于過濾型的字符串快速匹配方法

有效

• 申請號: 201210211829.7
• 申請日: 2012-06-25
• 公開（公告）號: CN102750379A
• 公開（公告）日: 2012-10-24
• 發明（設計）人: 李擁軍;鄒少聰;林浩;黃格仕;謝豪
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 寧尚國

1.一種基于過濾型的字符串快速匹配方法，其特征在于包括如下步驟：

（1）對模式串進行預處理：記模式串長度為(k+s)h的前綴為P₀，將P₀切分成k+s個長度為h的模式串子塊，將每一個模式串子塊的長度延長k+q-1，則兩個連續模式串子塊之間存在長度為k+q-1的重疊部分；這k+s個延長之后的模式串子塊分別記為Q₁、Q₂、…、Q_k+s；其中m為模式串字符的個數；k為把模式串轉變成文本串某個子串所需要的最少操作次數，簡稱編輯距離，0≦k﹤m；s為在匹配過程中文本串索引與模式串子塊的因子精確匹配的最少個數，1≦s﹤m；q是文本串索引的長度，q≦h；

（2）創建文本串索引：從文本串起始位置開始，每隔h長度依次讀取文本串的q個字符作為文本串索引，文本串索引分別標記為d₁、d₂,…d_n/h；q≦h；

（3）創建匹配數組B[d，j]：如果某一個文本串索引d_i屬于Q_j,則匹配數組B[d_i，j]＝1;否則匹配數組B[d_i，j]=0；為每個文本串創建長度為m’的數組M，用于記錄文本串索引的匹配個數，記d_i對應的數組為M_di[1...m’],M_di[1...m’]初始化為0；其中m’=k+s；

（4）計算k+s個連續的文本串索引與模式串子塊的匹配個數：將文本串索引與模式串子塊進行匹配；在記錄匹配情況的過程中，若出現M_di[j]≤j-k的情況，則停止構建該數組，轉而繼續構建下一個索引的數組M_di+1；若元素M_di[m’]≥s，則需要進一步檢測近似匹配，繼續下一步；

（5）檢測近似匹配：若存在近似匹配，則待檢測的區域位于文本串的j-(k+s)h-2k-q+2至j+m-(k+s-1)h+k-q部分，并用動態規劃算法檢測該區域，如果檢測出近似匹配，則給出近似匹配的所有出現位置，否則報告該區域不存在近似匹配。

2.根據權利要求1所述的基于過濾型的字符串快速匹配方法，其特征在于：所述文本串為字符串，模式串為字符串；所述字符串是定義在有限字母表上的字符序列。

3.根據權利要求1所述的基于過濾型的字符串快速匹配方法，其特征在于：給定字符串x，y和z，稱x是xy的一個前綴，x是yx的一個后綴，x是yxz的一個因子。