[發明專利]字符串匹配方法和裝置

在審

• 申請號: 201410240320.4
• 申請日: 2014-05-30
• 公開（公告）號: CN105468588A
• 公開（公告）日: 2016-04-06
• 發明（設計）人: 廖勇;文劉飛;朱葛
• 申請（專利權）人: 華為技術有限公司;電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

技術領域

本發明涉及計算機技術領域，尤其涉及字符串匹配方法和裝置。

背景技術

為了應對網絡入侵，需要對端口接收到的字符串進行監控，即需要對接收到的字符串按照特定的模式字符串進行分段匹配，為了使得字符串匹配更加高效，現有技術往往在異構計算環境中使用沒有回溯跳轉的多模式字符串匹配算法進行字符串匹配，即首先由CPU建立狀態自動機，該自動機不包括字符匹配失敗后的跳轉，并將該自動機發送到圖形處理器的全局內存中，以便圖形處理器上的線程利用該自動機對接收到的待匹配字符串進行匹配，由于采用了異構計算環境，則圖形處理器上的多個線程同時對同一字符串的不同分段進行匹配，為了防止漏匹配，每個分段之間都有重疊區域，該重疊區域的長度為模式字符串長度的最大值。

上述沒有回溯跳轉的多模式字符串匹配算法是將接收到的長度為n的待匹配字符串分為n段，對于任意一個分段i(1≤i≤n)，該分段從待匹配字符串的第i個字符開始，到第n個字符結束，當在字符串匹配的過程中遇到匹配失敗的情況時，該匹配過程結束，即在利用上述狀態自動機進行字符串匹配的時候不進行狀態回溯，當較少的模式字符串之間的相似度較低的情況下，可能每個線程檢測到一個或幾個字符時即可以判斷匹配失敗，避免了圖形處理器對重疊區域進行檢測時浪費的系統資源。

在利用現有力學模型試驗裝置進行試驗的過程中，發明人發現現有技術至少存在如下問題：

當模式字符串的數量較多的時候，每個模式字符串中相似段出現的概率更高，每個線程需要檢測更多的字符才可能判斷為匹配失敗，導致每個線程的執行時間會大幅增加，從而導致在較多模式字符串的情況下，字符串匹配的效率低。

發明內容

本發明的實施例提供一種字符串匹配方法和裝置，通過將模式字符串進行分段匹配，能夠使得字符串匹配更加高效。

本發明實施例的第一方面是提供字符串匹配方法，該方法包括：

獲取前綴狀態自動機，所述前綴狀態自動機是由模式字符串的前綴按照多模式字符串匹配算法構成的狀態自動機，所述模式字符串為字符串匹配時所用的特征字符串，所述前綴由從所述模式字符串第一個字符開始逐個提取預設值個數的字符組合而成；

獲取待匹配字符串，根據所述前綴狀態自動機對所述待匹配字符串進行字符串匹配，以便所述字符串匹配成功后中央處理器利用所述模式字符串的后綴對所述待匹配字符串進行第二次字符串匹配。

結合第一方面，在第一種可能的實現方式中，所述獲取狀態自動機包括：

從存儲器中獲取所述前綴狀態自動機，所述前綴狀態自動機按照稀疏矩陣的方式存儲在所述存儲器內存中，所述稀疏矩陣中的行表示所述前綴狀態自動機的各個狀態，所述稀疏矩陣每一列對應一個輸入，所述稀疏矩陣中的列表示所述前綴狀態自動機接收到每一列對應的輸入時狀態跳轉的下一跳狀態，其中-1表示在該行所示的狀態下有字符串被成功匹配；

在所述存儲器中存儲有匹配列表，所述匹配列表包括所述前綴狀態自動機的每一個狀態以及與每一個狀態對應的地址，若其中第一狀態對應的地址不為空，則表示在該第一狀態下有所述模式字符串的前綴被成功匹配，該第一狀態對應的地址為被成功匹配到的所述模式字符串的前綴的存儲地址。

結合第一方面，在第二種可能的實現方式中，所述根據所述前綴狀態自動機對所述待匹配字符串進行字符串匹配包括：

獲取所述待匹配字符串，從所述待匹配字符串的首個字符開始，由至少一個線程將所述待匹配字符串中的每個字符輸入到所述前綴狀態自動機中，當所使用的線程數量大于1時，每兩個線程輸入的所述待匹配字符串中相同位置的字符數量等于所述預設值；

當所述待匹配字符串中的每一個字符都在所述前綴狀態自動機中完成匹配過程，則生成匹配結果，并將所述匹配結果存儲在存儲器中。

第二方面，提供一種字符串匹配方法，該方法包括：

獲取后綴狀態自動機，所述后綴狀態自動機是由模式字符串的后綴按照多模式字符串匹配算法構成的狀態自動機，且所述后綴狀態自動機不包括狀態回溯，所述模式字符串為字符串匹配時所用的特征字符串，所述后綴的長度為所述模式字符串的長度與預設值的差值；

在圖形處理器對所述待匹配字符串進行字符串匹配成功后，獲取待匹配字符串，根據所述后綴狀態自動機對所述待匹配字符串進行字符串匹配。

結合第二方面，在第一種可能的實現方式中，所述方法還包括：

將所述模式字符串拆分為前綴和后綴，所述前綴由從所述模式字符串第一個字符開始逐個提取所述預設值個數的字符組合而成，所述后綴為所述模式字符串減去所述前綴后剩下的部分；