[發明專利]基于多線程的模式匹配方法、裝置及電子設備

在審

• 申請號: 201811404448.4
• 申請日: 2018-11-22
• 公開（公告）號: CN109543751A
• 公開（公告）日: 2019-03-29
• 發明（設計）人: 袁春峰;曲志峰;紀翀;樓方平
• 申請（專利權）人: 南京中孚信息技術有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京超凡志成知識產權代理事務所(普通合伙) 11371
• 代理人: 蘇勝

1.一種基于多線程的模式匹配方法，其特征在于，包括：

獲取待掃描文本及所述待掃描文本的標識信息；其中，所述標識信息包括所述待掃描文本的字節數和所述待掃描文本的起始地址；

根據所述待掃描文本的字節數啟動多個線程，并分別為每個所述線程分配編號；其中，多個所述線程的編號呈等差數列遞增；所述等差數列的首項為0；

根據所述待掃描文本的起始地址和每個所述線程的編號，確定每個所述線程對應的起始掃描偏移；

將所述待掃描文本加載至多個所述線程，并同時在各個所述線程中，根據所述線程對應的起始掃描偏移通過預先構建的狀態機對所述待掃描文本進行掃描，得到所述待掃描文本中與所述狀態機相匹配的目標模式串；其中，所述狀態機中包含有多個模式串。

2.根據權利要求1所述的方法，其特征在于，所述線程的數量等于所述待掃描文本的字節數；所述等差數列的公差為1個字節。

3.根據權利要求1所述的方法，其特征在于，在獲取待掃描文本之前，所述方法還包括：

接收用戶輸入的關鍵詞組，并通過字典樹構建與所述關鍵詞組對應的狀態機；其中，所述關鍵詞組中的關鍵詞與所述狀態機中的模式串一一對應。

4.根據權利要求3所述的方法，其特征在于，所述狀態機中每個模式串的初始狀態值均等于所述關鍵詞組中的關鍵詞的個數加一；所述狀態機中每個模式串的終止狀態值小于或者等于所述關鍵詞組中關鍵詞的個數，且，不同的所述模式串的終止狀態值不同。

5.根據權利要求4所述的方法，其特征在于，所述狀態機包括成功轉移表，所述成功轉移表中存儲有每個所述模式串對應的狀態轉移信息；其中，所述狀態轉移信息包括輸入狀態值、觸發字節以及與所述輸入狀態值和所述觸發字節所對應的輸出狀態值。

6.根據權利要求5所述的方法，其特征在于，所述根據所述線程對應的起始掃描偏移，通過預先構建的狀態機對所述待掃描文本進行掃描，得到所述待掃描文本中與所述狀態機相匹配的目標模式串的步驟，包括：

根據所述線程對應的起始掃描偏移，確定所述待掃描文本的第一個待掃描字節；

將所述初始狀態值確定為所述輸入狀態值，并將所述第一個待掃描字節確定為當前觸發字節；

判斷所述成功轉移表中是否存在與所述輸入狀態值和所述當前觸發字節對應的輸出狀態值；

如果不存在，結束所述線程；

如果存在，判斷所述輸出狀態值是否小于所述狀態機的初始狀態值；

如果否，將所述輸入狀態值更新為所述輸出狀態值，并將當前觸發字節更新為所述待掃描文本的下一個待掃描字節后，重新執行上述步驟：判斷所述成功轉移表中是否存在與所述輸入狀態值和所述當前觸發字節所對應的輸出狀態值；

如果是，在所述狀態機中查找與所述輸出狀態值相匹配的所述終止狀態值；

將查找到的所述終止狀態值對應的模式串確定為所述待掃描文本中與所述狀態機相匹配的目標模式串。

7.根據權利要求1所述的方法，其特征在于，所述線程為GPU線程。

8.一種基于多線程的模式匹配裝置，其特征在于，包括：

待掃描文本獲取模塊，用于獲取待掃描文本及所述待掃描文本的標識信息；其中，所述標識信息包括所述待掃描文本的字節數和所述待掃描文本的起始地址；

線程啟動模塊，用于根據所述待掃描文本的字節數啟動多個線程，并分別為每個所述線程分配編號；其中，多個所述線程的編號呈等差數列遞增；所述編號的最小值為0；

起始掃描偏移確定模塊，用于根據所述待掃描文本的起始地址和每個所述線程的編號，確定每個所述線程對應的起始掃描偏移；

模式匹配模塊，用于將所述待掃描文本加載至多個所述線程，并同時在各個所述線程中，根據所述線程對應的起始掃描偏移，通過預先構建的狀態機對所述待掃描文本進行掃描，得到所述待掃描文本中與所述狀態機相匹配的目標模式串；其中，所述狀態機中包含有多個模式串。