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

在審

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

本發明提供了一種基于多線程的模式匹配方法、裝置及電子設備，涉及模式匹配技術領域，該方法包括：獲取待掃描文本及待掃描文本的標識信息；其中，標識信息包括待掃描文本的字節數和待掃描文本的起始地址；根據待掃描文本的字節數啟動多個線程，并分別為每個線程分配編號；其中，多個線程的編號呈等差數列遞增；等差數列的首項為0；根據待掃描文本的起始地址和每個線程的編號，確定每個線程對應的起始掃描偏移；將待掃描文本加載至多個線程，并同時在各個線程中，根據線程對應的起始掃描偏移通過預先構建的狀態機對待掃描文本進行掃描，得到待掃描文本中與狀態機相匹配的目標模式串。本發明能夠有效提升模式匹配的效率。

技術領域

本發明涉及模式匹配技術領域，尤其是涉及一種基于多線程的模式匹配方法、裝置及電子設備。

背景技術

目前常用AC(Aho-Corasick)算法對待掃描文本進行模式匹配，然而AC算法的時間復雜度由待掃描文本的字節數所決定。對于字節較多的待掃描文本，應用AC算法掃描需要耗費較長的時間，算法的性能不優。通過這樣的方式進行模式匹配，效率較低。

發明內容

有鑒于此，本發明的目的在于提供一種基于多線程的模式匹配方法、裝置及電子設備，以有效提升模式匹配的效率。

第一方面，本發明實施例提供了一種基于多線程的模式匹配方法，包括：獲取待掃描文本及待掃描文本的標識信息；其中，標識信息包括待掃描文本的字節數和待掃描文本的起始地址；根據待掃描文本的字節數啟動多個線程，并分別為每個線程分配編號；其中，多個線程的編號呈等差數列遞增；等差數列的首項為0；根據待掃描文本的起始地址和每個線程的編號，確定每個線程對應的起始掃描偏移；將待掃描文本加載至多個線程，并同時在各個線程中，根據線程對應的起始掃描偏移通過預先構建的狀態機對待掃描文本進行掃描，得到待掃描文本中與狀態機相匹配的目標模式串；其中，狀態機中包含有多個模式串。

結合第一方面，本發明實施例提供了第一方面的第一種可能的實施方式，其中，線程的數量等于待掃描文本的字節數；等差數列的公差為1個字節。

結合第一方面，本發明實施例提供了第一方面的第二種可能的實施方式，其中，在獲取待掃描文本之前，上述方法還包括：接收用戶輸入的關鍵詞組，并通過字典樹構建與關鍵詞組對應的狀態機；其中，關鍵詞組中的關鍵詞與狀態機中的模式串一一對應。

結合第一方面的第二種可能的實施方式，本發明實施例提供了第一方面的第三種可能的實施方式，其中，上述狀態機中每個模式串的初始狀態值均等于關鍵詞組中的關鍵詞的個數加一；狀態機中每個模式串的終止狀態值小于或者等于關鍵詞組中關鍵詞的個數，且，不同的模式串的終止狀態值不同。

結合第一方面的第三種可能的實施方式，本發明實施例提供了第一方面的第四種可能的實施方式，其中，上述狀態機包括成功轉移表，成功轉移表中存儲有每個模式串對應的狀態轉移信息；其中，狀態轉移信息包括輸入狀態值、觸發字節以及與輸入狀態值和觸發字節所對應的輸出狀態值。

結合第一方面的第四種可能的實施方式，本發明實施例提供了第一方面的第五種可能的實施方式，其中，根據線程對應的起始掃描偏移，通過預先構建的狀態機對待掃描文本進行掃描，得到待掃描文本中與狀態機相匹配的目標模式串的步驟，包括：根據線程對應的起始掃描偏移，確定待掃描文本的第一個待掃描字節；將初始狀態值確定為輸入狀態值，并將第一個待掃描字節確定為當前觸發字節；判斷成功轉移表中是否存在與輸入狀態值和當前觸發字節對應的輸出狀態值；如果不存在，結束線程；如果存在，判斷輸出狀態值是否小于狀態機的初始狀態值；如果否，將輸入狀態值更新為輸出狀態值，并將當前觸發字節更新為待掃描文本的下一個待掃描字節后，重新執行上述步驟：判斷成功轉移表中是否存在與輸入狀態值和當前觸發字節所對應的輸出狀態值；如果是，在狀態機中查找與輸出狀態值相匹配的終止狀態值；將查找到的終止狀態值對應的模式串確定為待掃描文本中與狀態機相匹配的目標模式串。