改進字符串匹配的方法和系統的製作方法

2023-07-10 12:17:41

改進字符串匹配的方法和系統的製作方法
【專利摘要】提供了一種進字符串匹配的方法和系統。所述方法包括：將文本串和模式串的頭部對齊，以從右向左開始比較；根據BM算法的壞字符規則計算預移動距離；根據預移動距離來獲取預備壞字符；確定是否擴增移動距離；當確定對移動距離進行擴增時，根據BM算法的壞字符規則計算經擴增的移動距離；根據預移動距離或經擴增的移動距離來移動模式串；以及確定是否繼續從右向左比較。
【專利說明】改進字符串匹配的方法和系統

【技術領域】
[0001] 本發明涉及信息檢索、模式識別、文本挖掘、入侵檢測等領域，更具體地涉及一種 改進字符串匹配的方法和系統。

【背景技術】
[0002] 在當今的信息化時代，網絡資源飛速膨脹，在海量數據中找到需要的信息是亟待 決絕的問題。字符串匹配是信息檢索的核心，匹配的速度直接影響系統檢索的性能。因此 提高字符串匹配的速度尤為重要。
[0003] 現有的匹配算法主要有以下三種算法：
[0004] 順序匹配算法BF(Brute-Force)。BF算法也稱蠻力匹配算法，其採用一個二重循 環，順序匹配模式串。該算法需要將模式串逐一與文本串進行比較，導致產生大量冗餘操 作，包含過多不必要的比較，效率極低。
[0005] 前綴匹配算法KMP (Knuth-Morris-Pratt)。KMP算法採用從左至右的匹配方式，通 過一個輔助函數跳過失配串，以實現優化。在字符失配時，取消機械的從頭比對的方式，而 是依據之前的檢測信息進行計算，直接跳過不必要的檢測，從而減少冗餘。
[0006] BM(Boyer-Moore)算法。BM算法在進行模式串比對時，採用從右至左的方式，當發 現不匹配時，將模式串向右移動。BM不需要對文本串中的字符進行逐一比較，而會跳過其中 的某些部分，對於每一次匹配失敗，BM算法都能使用失敗信息來排除儘可能多的無法匹配 的位置。
[0007] BM算法的匹配性能優於其餘兩種算法，因此在實際中最常使用。BM算法採用壞字 符和好後綴規則來處理模式串的移動。
[0008] 壞字符的定義為：如果待搜索的模式串的最後一個字符與字符串中的相對應字符 不匹配，則該相對應字符被稱為壞字符。
[0009] 好後綴的定義為：假設兩個字符串分別為L、R，R左對齊L能完全匹配，同時R右 對齊L也能完全匹配，此時稱R是L的一個好後綴。如模式串"EXAMPLE"，其中"E"就是模 式串的好後綴。
[0010] 在BM算法的壞字符規則中，如下來計算後移位數Shiftbatkha:
[0011] shiftbadcha = m-l-f-S(T[k+m-l-f])
[0012] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；S(T[k+m-l-f])表示壞字符上一次在模式串P中出現的位置，並且 如果壞字符不存在於模式串中，則S(T[k+m-l-f])值為-1。
[0013] 在BM算法的好後綴規則中，如下來計算後移的位數Shiftgwdsuf :
[0014] Shiftgoodsuf = P[k+m-l-f]-G(T[k+m-l-f])
[0015] 其中G是預處理數據，G(T[k+m-l_f])表示好後綴最後出現在模式串中的位置，以 及P[k+m-l-f]表示好後綴第一次出現在模式串中的位置。
[0016] 下面通過一個案例來說明BM算法的過程，假定長度為η = 24的字符串T為"HERE IS A SMPLE EXAMPLE"，待搜索的模式串P為''EXAMPLE"，其長度為m = 7。
[0017] 如圖1(a)所示，首先將文本串T和模式串P的頭部對齊，從右向左開始比較。 [0018] 從右向左比較的最大優勢是，當最右端的字符不匹配時，剩下的字符可以不用再 比較。
[0019] 從圖1(a)可以看出，帶下劃線的"S"與"E"不匹配，這時"S"就被稱為壞字符。壞 字符"S"不存在於模式串P中，根據壞字符規則Shift baddia = m-l-f-S(T[k+m-l-f])可確定 要後移的位數Shiftbaddia = 7-1-0-(-1) = 7,意味著可將模式串直接移動到"S"的後一位。
[0020] 因此，將變成圖I (b)所示的情況。
[0021] 依然從最末位開始比較，發現帶下劃線的"P"與"E"不匹配。但與之前不同，"P" 包含在模式串P中。此時根據壞字符規則Shiftbaddia = m-l-f-S(T[k+m-l-f])可確定要後 移的位數Shiftbadeha = 7-1-0-(4) = 2,因此將模式串後移兩位，使得壞字符"P"與模式串 中的"P"對齊。
[0022] 因此，將變成圖1(c)所示的情況，繼續比較。"MPLE"四個字符匹配，"I"與"A"不 匹配，根據壞字符規則，此時根據壞字符規則Shift baddia = m-l-f-S(T[k+m-l-f])可確定要 後移的位數Shiftbaddia = 7-1-4-(-1) = 3,因此向右移動3位，將變成圖I (d)所示的情況。
[0023] 然而，由於字符"E"是模式串P的好後綴，因此根據好後綴規則Shiftgwdsuf = P[k+m-l-f]-G(T[k+m-l-f])，可以確定要移動的位數shiftg(K)dsuf = 6-0 = 6。在壞字符規 則與好後綴規則兩者之間取移動的位數相對大的一個，因此模式串應移動6位，將變成圖 1(e)所示的情況。
[0024] 繼續從尾部比較，發現"P"和"E"不匹配，根據壞字符規則壞字符規則Shiftbadcha =m-l-f-S(T[k+m-l-f])可確定要後移的位數 shiftbadeha = 7-1-0-(4) = 2,將變成圖 I (f) 所示的情況。
[0025] 繼續比較，最後找到匹配的字符串。
[0026] BM算法與BF算法、KMP算法相比，匹配效率明顯提高，但其仍有缺陷。BM算法需 要做壞字符和好後綴的預處理。其中好後綴的預處理開銷較大，尤其當模式串很長時，會影 響匹配的性能。在進行匹配時，模式串的移動距離影響匹配的速度，所以加快模式串的移動 速度是提1?匹配效率的關鍵。
[0027] 因此，期望提供一種改進字符串匹配的方法和系統。


【發明內容】

[0028] 為了解決現有技術中的上述缺點和問題中的至少一個而提出本發明。基於現有技 術存在的缺點，本發明提供了 一種改進字符串匹配的方法和系統。在本發明的方法和系統 中，根據BM算法的不足提出了改進，取消了好後綴的預處理過程，僅採用壞字符來作為模 式串移動的依據。提出了預備壞字符，預移動處理過程和移動距離擴增的概念。為了增加 模式串的移動距離，引進了預移動處理過程，將模式串的匹配過程分為兩個階段：預移動處 理過程和移動距離擴增。根據本發明的方法和系統不僅節省了好後綴預處理的開銷，而且 能大幅度的提升匹配效率。
[0029] 根據一個方面，本發明提出了一種進字符串匹配的方法，包括：將文本串和模式串 的頭部對齊，以從右向左開始比較；根據BM算法的壞字符規則計算預移動距離；根據預移 動距離來獲取預備壞字符；確定是否擴增移動距離；當確定對移動距離進行擴增時，根據 BM算法的壞字符規則計算經擴增的移動距離；根據預移動距離或經擴增的移動距離來移 動模式串；以及確定是否繼續從右向左比較。
[0030] 可選地，可以通過以下公式來計算預移動距離shifty :
[0031] shiftpre = m-l-f-S (T [k+m-1-f])
[0032] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；S(T[k+m-l_f])表示壞字符上一次在模式串P中出現的位置，並且 如果壞字符不存在於模式串中，則S(T[k+m-l_f])值為-1。
[0033] 可選地，可以通過以下公式來獲取預備壞字符PREbaddm :
[0034] PREbadchar = T [ (k+m-1-f) +m-1-S (T [k+m-1-f])]
[0035] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；T(n)表示待匹配的文本串，長度為n ;S(T[k+m-l-f])表示壞字符 上一次在模式串P中出現的位置，並且如果壞字符不存在於模式串中，則S (T [k+m-1-f])值 為-1。
[0036] 可選地，確定是否擴增移動距離可以包括：將預備壞字符PREbaddm與字符P [m-1] 進行比較；當二者匹配時，確定不擴增移動距離；以及當二者不匹配時，確定對移動距離進 行擴增。
[0037] 可選地，可以通過以下公式來計算經擴增的移動距離shift :
[0038] shift = shiftpre+(m-l)-S (PREbadchar),
[0039] 其中shifty表示預移動距離，S (PREbadehJ表示預備壞字符PREbadeha,上一次在模 式串中出現的位置。
[0040] 根據另一個方面，本發明提出了一種改進字符串匹配的系統，包括：初始化模塊， 用於將文本串和模式串的頭部對齊以從右向左開始比較；預移動距離計算模塊，用於根據 BM算法的壞字符規則計算預移動距離；預備壞字符獲取模塊，用於根據預移動距離來獲取 預備壞字符；擴增判斷模塊，用於確定是否擴增移動距離；擴增移動距離計算模塊，用於在 擴增判斷模塊確定對移動距離進行擴增時根據BM算法的壞字符規則來計算經擴增的移動 距離；移動模塊，用於根據預移動距離或經擴增的移動距離來移動模式串；以及終止判斷 模塊，用於確定是否繼續從右向左比較。
[0041] 可選地，可以通過以下公式來計算預移動距離shifty :
[0042] shiftpre = m-l-f-S (T [k+m-1-f])
[0043] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；S(T[k+m-l-f])表示壞字符上一次在模式串P中出現的位置，並且 如果壞字符不存在於模式串中，則S(T[k+m-l-f])值為-1。
[0044] 可選地，可以通過以下公式來獲取預備壞字符PREbaddm :
[0045] PREbadchar = T [ (k+m-l-f) +m-I-S (T [k+m-1-f])]
[0046] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；T(n)表示待匹配的文本串，長度為n ;S(T[k+m-l-f])表示壞字符 上一次在模式串P中出現的位置，並且如果壞字符不存在於模式串中，則S (T [k+m-1-f])值 為-1。
[0047] 可選地，擴增判斷模塊可以通過以下來確定是否擴增移動距離：
[0048] 將預備壞字符PREbaddm與字符P [m-1]進行比較；
[0049] 當二者匹配時，確定不擴增移動距離；以及
[0050] 當二者不匹配時，確定對移動距離進行擴增。
[0051] 可選地，可以通過以下公式來計算經擴增的移動距離shift :
[0052] shift = shiftpre+(m-l)-S (PREbadchar),
[0053] 其中shifty表示預移動距離，S (PREbadehJ表示預備壞字符PREbadeha,上一次在模 式串中出現的位置。

【專利附圖】

【附圖說明】
[0054] 通過下面結合附圖進行的描述，本發明一些示範性實施例的上述和其他方面、特 徵和優點對於本領域技術人員來說將變得顯而易見，其中：
[0055] 圖I (a) - I (f)是運用BM算法的一個示例的過程圖；
[0056] 圖2是根據本發明的一個實施例的改進字符串匹配的方法的流程圖；
[0057] 圖3(a)_3(c)是運用根據本發明的字符串匹配方法的一個示例的過程圖；以及
[0058] 圖4是根據本發明的一個實施例的改進字符串匹配的系統的框圖。

【具體實施方式】
[0059] 提供參考附圖的下面描述以幫助全面理解本發明的示範性實施例。其包括各種細 節以助於理解，而應當將它們認為僅僅是示範性的。因此，本領域普通技術人員應當認識 至IJ，可以對這裡描述的實施例做出各種改變和修改，而不會背離本發明的範圍和精神。同 樣，為了清楚和簡明，省略了對公知功能和結構的描述。
[0060] 圖2是根據本發明的一個實施例的改進字符串匹配的方法的流程圖。
[0061] 如圖2中所示，在步驟210中，將文本串和模式串的頭部對齊，以從右向左開始比 較。
[0062] 在步驟220中，根據BM算法的壞字符規則計算預移動距離。用shifty表示預移 動距離，可以通過以下公式來計算預移動距離：
[0063] shiftpre = m-l-f-S (T [k+m-1-f])
[0064] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；S(T[k+m-l-f])表示壞字符上一次在模式串P中出現的位置，並且 如果壞字符不存在於模式串中，則S(T[k+m-l-f])值為-1。
[0065] 在步驟230中，根據預移動距離來獲取預備壞字符。在本發明中將預備壞字符定 義為模式串移動shif tpM的距離後，模式串最末位P [m]對應的文本串中的字符。用PREbaddm 表示預備壞字符，可以通過以下公式來獲取預備壞字符：
[0066] PREbadchar = T [ (k+m-l-f) +m-I-S (T [k+m-1-f])]
[0067] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭 部與文本串的相對位置；T(n)表示待匹配的文本串，長度為n ;S(T[k+m-l-f])表示壞字符 上一次在模式串P中出現的位置，並且如果壞字符不存在於模式串中，則S (T [k+m-1-f])值 為-1。
[0068] 在步驟240中，確定是否擴增移動距離。在根據本發明的方法中，將字符PREbaddm 與P[m-1]進行比較，當二者匹配時，確定不擴增移動距離；當二者不匹配時，確定對移動距 離進行擴增。
[0069] 在步驟250中，當在步驟130中確定對移動距離進行擴增時，根據BM算法的壞字 符規則對PREbaddm計算移動距離。用shift表示經擴增的移動距離，可以通過以下公式將 移動距離擴增為：
[0070] shift = shiftpre+(m-D-S(PREbadchar)
[0071] 在步驟260中，根據預移動距離或經擴增的移動距離來移動模式串。
[0072] 在步驟270中，確定是否繼續從右向左比較。例如，在沒有找到模式串的匹配字符 串且沒有移動到文本串的最末位時，繼續從右向左比較；否則結束。
[0073] 下面參考圖3(a)_3(c)來說明根據本發明的改進字符串匹配的方法的一個示例 的過程圖。
[0074] 在該示例中繼續使用上面針對BM算法使用的示例，即假定長度為η = 24的字符 串T為"HERE IS A SMPLE EXAMPLE"，待搜索的模式串P為''EXAMPLE"，其長度為m = 7。
[0075] 首先，如圖3(a)中所示，將文本串和模式串的頭部對齊，從右至左進行比較。壞字 符"S"與"E"不匹配，此時根據壞字符規則計算預移動距離：
[0076] shiftpre = m-1-f-S (T [k+m-l-f] )= 7-1-0-(_1) = 7 [0077] 根據預移動距離，獲取預備壞字符：
[0078] PREbadchar = T[(k+m-l-f)+m-卜S(T[k+m-l-f])] = T[ (0+7-1-0)+7-1-(-1)]= T[13]
[0079] 由此可知預備壞字符T [13]為"Ρ"，其與P [6](即"L"）不匹配，於是根據壞字符 規則來根據下列公式擴增移動距離：
[0080] shift = shiftpre+(m-1)-S (PREbadchar) = 7+(7-1)-4 = 9
[0081] 意味著可將模式串移動9位。因此，將變成圖3(b)所示的情況。
[0082] 繼續從右端開始比較，文本串中的空格與"E"不匹配，且空格不在模式串中，根據 公式shift pra = m-l-f-S(T[k+m-l-f])計算得到預移動距離為7。
[0083] 然後，根據公式 PREbaddm = T[(k+m-l-f)+m-l-S(T[k+m-l-f])]獲得預備壞字符 T [23] ="E"，其與P [6]匹配，移動距離不可擴增。
[0084] 因此，將模式串向右移動7位，將變成圖3 (c)所示的情況。從圖3 (c)中可以看出， 已找到匹配字符串，從而結束。
[0085] 在下面的表中示出了 BM算法和根據本發明的改進字符串匹配的方法的移動次數 和比較次數的對比。
[0086]

【權利要求】
1. 一種改進字符串匹配的方法，包括： 將文本串和模式串的頭部對齊，W從右向左開始比較； 根據BM算法的壞字符規則計算預移動距離； 根據預移動距離來獲取預備壞字符； 確定是否擴增移動距離； 當確定對移動距離進行擴增時，根據BM算法的壞字符規則計算經擴增的移動距離； 根據預移動距離或經擴增的移動距離來移動模式串；W及 確定是否繼續從右向左比較。
2. 根據權利要求1所述的方法，其中通過W下公式來計算預移動距離shift。,。； shiftpre 二 m-1-f-S 們k+m-1-f]) 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭部與 文本串的相對位置；S(T比+m-l-f])表示壞字符上一次在模式串P中出現的位置，並且如果 壞字符不存在於模式串中，則S(T比+m-l-f])值為-1。
3. 根據權利要求1所述的方法，其中通過W下公式來獲取預備壞字符PREbaddwt: PREbadeh。!?二 T [化+m-l-S (T 比])] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭部 與文本串的相對位置；T(n)表示待匹配的文本串，長度為n ;S(T比+m-l-f])表示壞字符上 一次在模式串P中出現的位置，並且如果壞字符不存在於模式串中，則S(T比值 為-1。
4. 根據權利要求1所述的方法，其中確定是否擴增移動距離包括： 將預備壞字符PREbaddut與字符P虹-1]進行比較； 當二者匹配時，確定不擴增移動距離；W及 當二者不匹配時，確定對移動距離進行擴增。
5. 根據權利要求1所述的方法，其中通過W下公式來計算經擴增的移動距離shift ; shift = shiftpre+(m-l)-S(PREbadchJ， 其中shift。,。表示預移動距離，S(PREbadehJ表示預備壞字符PREbaddut上一次在模式串 中出現的位置。
6. -種改進字符串匹配的系統，包括： 初始化模塊，用於將文本串和模式串的頭部對齊W從右向左開始比較； 預移動距離計算模塊，用於根據BM算法的壞字符規則計算預移動距離； 預備壞字符獲取模塊，用於根據預移動距離來獲取預備壞字符； 擴增判斷模塊，用於確定是否擴增移動距離； 擴增移動距離計算模塊，用於在擴增判斷模塊確定對移動距離進行擴增時根據BM算 法的壞字符規則來計算經擴增的移動距離； 移動模塊，用於根據預移動距離或經擴增的移動距離來移動模式串；W及 終止判斷模塊，用於確定是否繼續從右向左比較。
7. 根據權利要求6所述的系統，其中通過W下公式來計算預移動距離shift。,。； shiftpre 二 m-1-f-S 們k+m-1-f]) 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭部與 文本串的相對位置；S(T比+m-l-f])表示壞字符上一次在模式串P中出現的位置，並且如果 壞字符不存在於模式串中，則S(T比+m-l-f])值為-1。
8.根據權利要求6所述的系統，其中通過W下公式來獲取預備壞字符PREbaddwt: PREbadeh。!?二 T [化+m-l-S (T 比])] 其中，m表示待搜索的模式串的長度；f表示已匹配的字符的數目；k表示模式串頭部 與文本串的相對位置；T(n)表示待匹配的文本串，長度為n ;S(T比+m-l-f])表示壞字符上 一次在模式串P中出現的位置，並且如果壞字符不存在於模式串中，則S(T比值 為-1。
9. 根據權利要求6所述的系統，其中擴增判斷模塊通過W下來確定是否擴增移動距 離： 將預備壞字符PREbaddut與字符P虹-1]進行比較； 當二者匹配時，確定不擴增移動距離；W及 當二者不匹配時，確定對移動距離進行擴增。
10. 根據權利要求6所述的系統，其中通過W下公式來計算經擴增的移動距離shift ; shift = shiftpre+(m-l)-S(PREbadchar)， 其中shift。,。表示預移動距離，S(PREbadehJ表示預備壞字符PREbaddut上一次在模式串 中出現的位置。
【文檔編號】G06F17/27GK104462266SQ201410681087
【公開日】2015年3月25日 申請日期:2014年11月21日 優先權日:2014年11月21日
【發明者】蔣松林 申請人:北京京東尚科信息技術有限公司