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

在審

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

1.字符串匹配方法，其特征在于，包括：

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

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

2.根據權利要求1所述的方法，其特征在于，所述獲取前綴狀態自動機包括：

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

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

3.根據權利要求1所述的方法，其特征在于，所述獲取待匹配字符串，所述根據所述前綴狀態自動機對所述待匹配字符串進行字符串匹配包括：

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

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

4.字符串匹配方法，其特征在于，包括：

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

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

5.根據權利要求4所述的方法，其特征在于，在獲取所述狀態自動機之前，所述方法還包括：

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

將所述前綴按照多模式字符串匹配算法生成前綴狀態自動機并存儲于存儲器中，將所述后綴按照多模式字符串匹配算法生成后綴狀態自動機，并去除所述后綴狀態自動機中的狀態回溯。

6.根據權利要求5所述方法，其特征在于，所述前綴狀態自動機與所述后綴狀態自動機按照稀疏矩陣的方式存儲在所述存儲器中，所述稀疏矩陣中的行表示所述后綴狀態自動機的各個狀態，所述稀疏矩陣每一列對應一個輸入，所述稀疏矩陣中的列表示所述后綴狀態自動機接收到每一列對應的輸入時狀態跳轉的下一跳狀態，其中-1表示在該行所示的狀態下有字符串被成功匹配；

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

7.根據權利要求4所述的方法，其特征在于，所述獲取待匹配字符串，根據所述狀態自動機對所述待匹配字符串進行字符串匹配包括：

獲取所述待匹配字符串，從所述待匹配字符串的第一位置開始，由至少一個線程將所述待匹配字符串中的所述第一位置以后的每個字符輸入到所述后綴狀態自動機中，所述第一位置為所述前綴在所述待匹配字符串中被成功匹配到的位置，當所使用的線程數量大于1時，每兩個線程輸入的所述待匹配字符串中相同位置的字符數量等于所有所述后綴中長度的最大值。